Отсюда можно скачать полный текст статьи в формате pdf (280 кб)
Федеральный научно-производственный центр
ГУП "НПО "Аврора"",
Санкт-Петербургский государственный институт точной механики и оптики
(технический университет)
Статья опубликована в разделе "Обзоры" журнала "Автоматика и телемеханика", 2001, N1, C.3-39.
Существует английская версия статьи: Shalyto A.A. Logic Control and "Reactive" Systems: Algorithmization and Programming // Automation and Remote Control. 2001. N1, pp. 1-29.
УДК 519.714
На основе обзора методов алгоритмизации и программирования для систем логического управления и "реактивных" систем сформулированы основные положения технологии алгоритмизации и программирования для этих классов систем, в рамках которой алгоритмы и программы рассматриваются как конечные автоматы. Выполнен обзор работ, посвященных применению конечных автоматов при программировании других классов задач.
В настоящее время в различных областях программирования все шире применяются конечные автоматы, которые в течение многих десятилетий использовались в основном при аппаратных реализациях. В настоящей работе на основе обзора методов алгоритмизации и программирования для систем логического управления и "реактивных" систем, сформулированы основные положения технологии алгоритмизации и программирования для этих классов систем. При этом проектируемые программы рассматриваются как взаимосвязанные конечные автоматы. Показано, что конечные автоматы начинают применяться ведущими фирмами мира для программирования программируемых логических контроллеров (ПЛК), а также для описания поведения отдельных объектов в объектно-ориентированном программировании. Они используются при программировании протоколов, игр и схем программируемой логики, а также в такой традиционной для их применения области как создание компиляторов.
Обзор призван показать, что существующее в настоящее время у некоторых специалистов мнение "о смерти теории автоматов" является преждевременным и ее широкое практическое применение в программировании только начинается.
Известен международный стандарт [1], определяющий языки программирования для ПЛК и программно реализованных ПЛК (PC-контроллеров) — промышленных (управляющих) компьютеров (обычно IBM PC совместимых) с программным обеспечением класса SoftPLC и SoftLogic для создания прикладных программ.
Известны также языки программирования для микроконтроллеров и собственно промышленных (управляющих) компьютеров [2].
Однако ведущими в области автоматизации фирмами мира [1-7], как показал обзор, выполненный в [8], до сих пор не был выбран (разработан) язык алгоритмизации для задач логического (основанного на истинности и ложности) управления, который позволил бы:
Отсутствие такого языка оставляло открытым вопрос о создании сквозной технологии алгоритмизации и программирования для систем логического управления, которая позволила бы повысить качество проектирования их программного обеспечения.
В [8] выполнен обзор известных технологий алгоритмизации и программирования для систем рассматриваемого класса, на основе которого была разработана новая технология, названная "SWITCH-технология", позволяющая обеспечить выполнение указанных выше требований. Эта технология может быть названа также "STATE-технология" или, более точно, "AUTOMATON-технология". Изложим основные положения этой технологии.
1. В качестве основного в предлагаемой технологии используется понятие "внутреннее состояние" (в дальнейшем — "состояние").
Состояния рассматриваются как некоторые абстракции, вводимые в начале процесса алгоритмизации, например путем однозначного сопоставления каждого из них с одним из физических состояний управляемого объекта, так как обычно "функционирование производственных систем проявляется через изменение их состояний" [9]. При этом каждое состояние в алгоритме поддерживает объект в соответствующем состоянии, а переход в новое состояние в алгоритме приводит к переходу объекта в новое соответствующее состояние, что и обеспечивает процесс логического управления объектом.
Например, объект "клапан" может находиться в одном из четырех рабочих состояний ("закрыт", "открывается", "открыт", "закрывается"), каждое из которых может поддерживаться соответствующим состоянием в алгоритме управления. Для клапана "с памятью" алгоритм управления может иметь и три состояния, поддерживая закрытое и открытое состояния объекта одним своим состоянием (разд. 5.4.1 в [8]).
При необходимости в алгоритм управления могут быть введены также и другие состояния, связанные, например, с неисправностями объекта и неправильными действиями Оператора.
Связь состояний с внутренними (управляющими) переменными появляется в дальнейшем на этапе кодирования состояний, отсутствующем в традиционном программировании. При этом число вводимых управляющих переменных зависит от принятого вида кодирования.
Такой подход, известный из теории автоматов, принципиально отличается от подхода, обычно применяемого в программировании, при котором в ходе процесса программирования по необходимости вводятся внутренние (обычно двоичные) переменные, а затем каждый различный набор их значений объявляется состоянием программы [10]. Однако, так как понятие "состояние" в программировании прикладных задач обычно не используется, ответ на вопрос о количестве состояний в программе, содержащей, например, n двоичных внутренних переменных, остается в большинстве случаев открытым. Отметим, что в этом случае число состояний может находиться в диапазоне от n до 2n. При этом остается неясным также, откуда "берутся" эти переменные, сколько их должно быть и для какой цели каждая из них применяется. Отметим также, что при циклическом выполнении программы (ввиду наличия обратной связи от выхода к входу) она может быть последовательностной даже и при отсутствии управляющих переменных (гл.13 в [8]).
2. Добавляя к понятию "состояние" понятие "входное воздействие", естественным образом вводится понятие "автомат без выхода" (автомат без выхода = состояния + входные воздействия), а после введения понятия "выходное воздействие", под которым понимается "действие" ("action") и "деятельность" ("activity"), эта формула приобретает вид: автомат = состояния + входные воздействия + выходные воздействия.
При этом соответствующая область программирования может быть названа "автоматным программированием", а процесс создания программ в этом случае — "автоматным проектированием программ" [8, 188].
Так же как и в [11, 12], предполагается, что действие является однократным, мгновенным и непрерываемым, а деятельность может длиться достаточно долго и возможно ее прерывание некоторым входным воздействием.
Входное воздействие в общем случае может изменить состояние; инициировать выходное воздействие без изменения состояния; инициировать выходное воздействие и изменить состояние.
3. В рассматриваемой технологии в качестве основной математической модели используется "конечный детерминированный автомат" (в дальнейшем — "автомат"), понимая под ним по классификации [13] автомат с внутренними состояниями, а не автомат с функциями поведения (Приложение 13 в [8]).
4. В качестве структурных моделей (гл.3 в [8]) применяются автоматы без выходного преобразователя, автоматы Мура, автоматы Мили и смешанные автоматы (С-автоматы или автоматы Мура-Мили) [14, 15].
В качестве основной структурной модели предлагается использовать автоматы Мура, в которых коды состояний и значения выходов принципиально разделены, а значения выходных переменных в каждом состоянии не зависят от входных воздействий, что упрощает внесение изменений в описания таких автоматов. Свойства алгоритмов и программ, обеспечивающие упрощение внесения корректных изменений в них, названы в [8] "управляемостью".
Первоначально число состояний в автомате Мура может быть выбрано равным числу состояний в управляемом им объекте (включая его неисправные состояния при необходимости). В дальнейшем в автомат могут вводиться дополнительные состояния, связанные, например, с неправильными действиями Оператора (Приложение 12 в [8]), а после этого число состояний в автомате может минимизироваться за счет объединения эквивалентных состояний или перехода к другой структурной модели, что, правда, без крайней необходимости делать нецелесообразно.
В автомате Мура значения выходных переменных сохраняются в течение времени его пребывания в соответствующем состоянии за счет памяти, реализующей эти состояния. В автомате Мили значения указанных переменных формируются в том числе и на соответствующем переходе, и, следовательно, для их "длительного" хранения требуется память, отличная от реализующей состояния. Поэтому в указанном смысле эти автоматы не эквивалентны.
5. Применяются автоматы первого и второго рода [8, 16]. Приоритет отдается автоматам второго рода, у которых новое состояние и значения выходных переменных формируются без задержки на "такт" (в одном программном цикле).
6. Используются различные виды кодирования состояний автоматов (разд.3.3 в [8]): принудительное, принудительно-свободное, двоичное, двоичное логарифмическое и многозначное. Приоритет отдается многозначному кодированию состояний. Возможность применения в автоматах (ввиду наличия только одного активного состояния в каждом из них) многозначного кодирования состояний позволяет отказаться от традиционной точки зрения на автоматы как на частный случай сетей Петри, так как в последних из-за принципиальной необходимости обеспечения в общем случае одновременной активности нескольких позиций одной сети отсутствует возможность использования одной переменной для их кодирования. При этом если для автомата вне зависимости от числа состояний для их отличия достаточно только одной многозначной переменной, то, например, для частного случая сети Петри, в которой в каждой позиции не может находиться более одной метки (аналог диаграммы "Графсет" по стандарту NFC-03-190 Grafcet), число двоичных переменных, требующихся для отличия позиций, равно числу последних. В разд.12.3 в [8] показано, что диаграмма "Графсет" с параллельными "участками" может быть заменена системой взаимосвязанных графов переходов. При этом если в первом случае число указанных двоичных переменных равно числу позиций, то во втором — число многозначных переменных равно числу графов переходов вне зависимости от числа вершин в них.
7. В качестве алгоритмической модели для автоматов с памятью при их программной реализации применяется такой непроцедурный визуальный формализм, разработанный в теории автоматов, как графы переходов, которые в литературе называются также диаграммами состояний или диаграммами состояний и переходов ("State Diagram" или "State Transition Diagram" в англоязычной литературе).
При этом отметим, что в этих названиях, так же как и в предлагаемой технологии, отдается приоритет понятию "состояние", а не понятию "событие", являющемуся одним из наиболее распространенных в современном программировании. В излагаемом подходе событие вторично и наряду с входной переменной рассматривается в качестве разновидности входного воздействия, которое может изменить состояние.
В другом визуальном формализме (схемы (граф-схемы) алгоритмов и программ), предложенном в теоретическом программировании и являющемся процедурным, понятие "состояние" в явном виде не используется, что резко усложняет его понимаемость [17]. Это понятие не применяется и в языке регулярных выражений алгебры событий [18].
Отметим также, что графы переходов имеют плоскостное изображение, а не вертикальную направленность (как, например, схемы алгоритмов, SDL-диаграммы [8] и диаграммы "Графсет"), что существенно повышает их обозримость.
Они значительно более компактны по сравнению с эквивалентными
схемами из функциональных блоков (традиционных логических элементов) и более обозримы, так как взаимодействие между графами переходов выполняется по данным, а между этими схемами — по управлению.
8. Одно из достоинств графов переходов, которые должны быть "максимально" планарными, состоит в том, что на каждой его дуге указываются не все входные воздействия (например, в форме минтермов), а только те из них, которые обеспечивают переход по этой дуге. На каждой дуге входные воздействия могут объединяться в булевы формулы, в том числе и произвольной глубины, что резко повышает компактность описания алгоритма.
Введение в модель булевых формул, как и при аппаратной реализации (структурном синтезе последовательностных схем), расширяет классическую модель абстрактного конечного автомата, в которой дуги помечаются лишь отдельными буквами входного алфавита, и обеспечивает "параллельную" обработку входных воздействий. По сравнению с последовательной по входам программной реализацией такое описание алгоритмов в общем случае позволяет уменьшить число состояний в реализующих их автоматах [8].
Можно утверждать, что каждое состояние в графе переходов "выделяет" из множества всех входных воздействий только то их подмножество, которое обеспечивает переходы из этого состояния — декомпозирует указанное множество.
Изложенное позволяет применять графы переходов для решения задач логического управления при большом числе входных воздействий, значительно упрощая решение проблемы тестирования по всем путям.
9. Каждый граф переходов должен быть семантически и синтаксически корректен. Первое свойство определяет, правильная ли построена модель, а второе — правильно ли она построена [19]. При проверке синтаксической корректности граф переходов проверяется на достижимость, полноту, непротиворечивость, реализуемость и отсутствие генерирующих контуров. При проверке достижимости определяется наличие по крайней мере одного пути в графе переходов из любой его вершины в любую другую. Полнота [8] проверяется для каждой вершины графа переходов и позволяет, в частности для автоматов Мура, умалчивать пометку ее петли. При обеспечении непротиворечивости [8] каждой вершины графа переходов вместо ортогонализации могут расставляться приоритеты, что уменьшает сложность реализующей его программы. Реализуемость обеспечивается за счет различения одинаково помеченных вершин в исходном графе переходов. Генерирующие контуры [8] в графе переходов устраняются, например, за счет ортогонализации пометок дуг, образующих соответствующие контуры.
10. Дальнейшее расширение модели абстрактного конечного автомата и обеспечение "параллелизма" по выходам, как и при аппаратной реализации, достигается за счет указания в компонентах (в вершинах и/или на дугах) графа переходов не отдельных букв выходного алфавита, а значений выходных переменных (деятельностей), формируемых в этих компонентах. При этом непосредственное указание в каждой компоненте (в зависимости от выбранной структурной модели автомата) значений всех выходных переменных резко упрощает понимание алгоритма, описанного графом переходов, возможно за счет увеличения числа вершин в нем. Построенный таким образом граф переходов задает структурный конечный автомат без умолчаний значений выходных переменных. При этом отметим, что например для графа переходов автомата Мура при необходимости сокращения объектного кода в программе, его реализующей, неизменяющиеся при соседних переходах значения выходных переменных, указанные в вершине, в которую выполняются переходы, должны быть закомментированы.
Еще большее расширение модели конечного автомата достигается (при уменьшении ее понятности) за счет указания в компонентах графа переходов не только значений выходных переменных, но и булевых формул (возможно, автоматных, что соответствует вложенным автоматам) (разд.12.4 в [8]).
11. "Параллелизм" по входам и выходам позволяет даже с помощью одного автомата, являющегося по определению последовательностным по состояниям (в соответствующем ему графе переходов в каждый момент времени активной является только одна вершина), реализовать параллельные процессы.
12. Поведение автоматов с памятью в отличие от автоматов без памяти зависит от предыстории, сводящейся к тому, что каждый переход в некоторое состояние зависит от одного, непосредственно связанного с ним состояния, а значения выходов, например для автоматов Мура, зависят только от состояния, в котором находится автомат.
В рамках излагаемой технологии эти свойства автоматов с памятью должны быть сохранены, а для обеспечения независимости от глубокой предыстории по состояниям и выходам графы переходов не должны содержать флагов и умолчаний соответственно [8, 17]. При этом число вершин в графе переходов должно совпадать с числом состояний в автомате. Независимость от глубокой предыстории ("будущее зависит от настоящего и не зависит от прошлого") существенно упрощает понимание [20] поведения автомата и внесение изменений как в граф переходов, так и в реализующую его программу.
Аналогичная ситуация имеет место и в марковских процессах, для исследования которых разработан весьма простой математический аппарат, который становится существенно более трудоемким для процессов, зависящих от глубокой предыстории.
13. При формальном и изоморфном переходе к программе от графа переходов без флагов и умолчаний последний является сертификационным тестом для ее проверки. При этом появляется возможность проводить сертификацию, начиная со сверки каждого графа переходов с изоморфным ему фрагментом программы. Вопросы тестирования и верификации программ, построенных с использованием конечных автоматов ("Finite State Machine" или "State Machine" в англоязычной литературе), рассмотрены в [21-28]. Кроме этих работ в пятом номере журнала "Computer" за 2000 г. описывается подход к практической верификации встроенного программного обеспечения, основанный на расширенной модели конечных автоматов, который применяется в программном продукте "VisualState". В рамках этого подхода проверяется достижимость состояний верифицируемой системы.
14. При использовании многозначного кодирования состояний для каждого автомата с любым (конечным) их числом достаточно одной внутренней переменной, значность которой равна числу состояний.
При этом отметим, что так как (по крайней мере теоретически) любой алгоритм логического управления может быть реализован одним графом переходов, то вне зависимости от числа вершин в нем он может быть реализован программой, содержащей только одну внутреннюю (управляющую) переменную.
Отметим также, что при каждом переходе предыдущее значение многозначной переменной сбрасывается автоматически, а кроме того, ей "не с чем" состязаться.
Применять такое кодирование можно лишь в том случае, когда априори (в начале процесса алгоритмизации) известно, какое число состояний будет иметь автомат.
15. Работа с многозначными переменными поддерживается большинством языков программирования, в том числе, и таким "экзотическим" языком, как язык функциональных блоков [8, 29].
Граф переходов с многозначным кодированием вершин, соответствующий выбранной структурной модели автомата, формально и изоморфно реализуется одной или двумя конструкциями switch языка Си (гл.5 в [8]) или их аналогами в других языках программирования, что и определило название предлагаемой технологии. Кроме того, слово switch (переключатель) ассоциируется с теорией переключательных схем, являющейся основой теории логического управления.
Возможны два подхода к реализации графов переходов, которые могут быть обозначены следующим образом: "состояния-события" и "события-состояния".
В первом случае при реализации графа переходов используются одна или две конструкции switch по "состояниям", а во втором — каждому типу "событий" сопоставляется функция, описываемая конструкцией switch по "состояниям", отражающая переходы, инициируемые этим "событием" [30].
Если событиям соответствуют значения многозначной переменной (функции, формирующей эти значения), то в первом случае первичной является конструкция switch по "состояниям", в которую вложены конструкции switch по "событиям", а во втором — конструкция switch по "событиям", в которую вложены конструкции switch по "состояниям" (Приложение 11 в [8]). При этом отметим, что в первом случае принцип построения программ совпадает с принципом логического управления (переход из состояния в состояние под воздействием события), что резко упрощает понимание таких программ Пользователем. Отметим также, что в "развитых" науках (например, физике) понятие "пространство состояний" является одним из основополагающих [31], в то время как понятие "поток событий" таковым в этих науках не является. Например, для воды определяющими являются состояния (жидкое, твердое, газообразное), а условия переходов и тем более выполняемые ею действия вторичны.
16. Значение многозначной переменной полностью характеризует "положение" программы, реализующей один граф переходов, в пространстве ее состояний, что позволяет ввести в программирование понятие "наблюдаемость" (по одной внутренней переменной). При этом программа рассматривается как "белый ящик" с одним внутренним параметром.
Сертификация программы, построенной формально и изоморфно, например по графу переходов автомата Мура без флагов и умолчаний, может проводиться в два этапа:
Графы переходов автоматов других типов всегда могут быть сведены к графам переходов эквивалентных автоматов Мура. При этом, например, каждой вершине графа переходов автомата Мили без флагов и умолчаний сопоставляются вершины графа переходов эквивалентного автомата Мура, число которых равно числу дуг, входящих в рассматриваемую вершину и помеченных различными значениями выходных переменных (разд. 4.4.3 в [8]).
Анализ всех функциональных возможностей графа переходов может выполняться с помощью графа достижимых маркировок, под которым будем понимать граф достижимых состояний, каждой вершине которого в дальнейшем могут быть однозначно приписаны выполняемые в ней деятельности. Поэтому граф переходов автомата Мура (или автомата без выходного преобразователя) без флагов и умолчаний может использоваться в качестве графа достижимых маркировок, а для других типов автоматов графы переходов и графы достижимых маркировок различаются между собой. Так, например, для графа переходов автомата Мили без флагов и умолчаний в качестве графа достижимых маркировок может применяться графа переходов эквивалентного автомата Мура.
17. Из изложенного в предыдущем пункте следует, что описываемый подход позволяет снять проблему, названную в [32] расшифровкой автоматов, в [33] — распознаванием автоматов, а в [34] — идентификацией автоматов, так как считается, что автомат распознан (расшифрован, идентифицирован), если для него построен граф переходов.
В [32] показано, что автомат нераспознаваем, если он является "абсолютно черным ящиком", для которого отсутствует какая-либо информация о его внутренних состояниях. Таким образом, для автоматов с памятью тестирование типа "вход-выход", наиболее часто используемое при создании систем логического управления, проблему распознавания не решает и говорить при этом о гарантированном поведении системы управления не приходится [35].
В [33] показано, что конечный детерминированный автомат распознаваем в результате анализа последовательности "вход-выход", если известно максимальное число состояний в минимальной (по числу состояний) форме этого автомата, а его граф переходов является сильносвязанным.
В [32] автомат, для которого известна указанная оценка числа состояний, назван "относительно черным ящиком".
18. Из изложенного в предыдущем пункте следует, что если понятие "состояние" априори не вводится, то в результате тестирования алгоритмов и программ с помощью входо-выходных последовательностей в общем случае не удается распознать автоматы, которые они реализуют.
В предлагаемой технологии состояния вводятся априори, а графы переходов строятся как сильносвязанные, что снимает проблему распознавания.
В рамках SWITCH-технологии предлагается отказаться от использования "черных ящиков" и перейти к "белым ящикам". При этом, если автомат задан в любой форме, отличной от графа переходов без флагов и умолчаний, он может быть назван "относительно белым ящиком", а если он задан графом переходов без флагов и умолчаний, то — "абсолютно белым ящиком".
Распознавание "относительно белых ящиков" может проводиться с
помощью математических преобразований [8].
19. В качестве основной алгоритмической модели в рамках SWITCH-технологии предлагается применять систему взаимосвязанных графов переходов [36], что поддерживает возможность композиции и декомпозиции алгоритмов и обеспечивает практическое применение технологии при построении сложных систем логического управления.
При этом автоматы (графы переходов) могут образовывать централизованные, децентрализованные и иерархические структуры (рис.5.41, 5.51, 5.55 в [8]).
20. Если в систему входят N графов переходов с любым числом состояний каждый, то при программной реализации даже с учетом взаимодействия графов могут использоваться только N внутренних многозначных переменных, введенных при кодировании состояний автоматов.
Для этого на программную реализацию накладывается ограничение, состоящее в том, что в каждом программном цикле в каждом графе переходов выполняется не более одного перехода: сохраняется предыдущее состояние автомата или выполняется только один переход в нем, даже в том случае, когда в рассматриваемом программном цикле в этом автомате последовательно могут быть выполнены несколько переходов.
Это обеспечивает доступность каждого значения каждой внутренней переменной для "всего окружения" — остальных N-1 графов системы, что позволяет не увеличивать число внутренних переменных для осуществления взаимосвязи графов переходов и делает взаимодействие графов переходов с помощью значений многозначных внутренних переменных весьма наглядным. При этом предикаты, проверяющие значения этих переменных, используются в качестве еще одной из разновидностей входных воздействий.
Таким образом, при автоматном программировании, так же как и при объектно-ориентированном программировании, автоматы обмениваются сообщениями. Однако возможность взаимодействия автоматов, из которых состоит программа, за счет обмена номерами их внутренних состояний существенно отличает автоматное программирование от объектно-ориентированного, в котором объекты рассматриваются как "черные ящики", внутреннее содержание каждого из которых скрыто [37].
21. Графы переходов в системе могут взаимодействовать по принципам "запрос-ответ-сброс" или "запрос-ответ", обмениваясь при этом десятичными номерами состояний.
Частным случаем такого взаимодействия является взаимосвязь головного и остальных графов переходов. При этом в случае необходимости имеется возможность запускать из головного графа параллельные процессы, реализуемые указанными графами переходов, и возвращать управление головному графу после завершения их работы. Это расширяет область применения конечных автоматов, каждый из которых, как отмечалось выше, по определению является последовательностным по состояниям. В [8] показано, что при реализации алгоритма в виде системы взаимосвязанных графов переходов они имеют преимущества по сравнению с языком "Графсет", разработанным для описания параллельных процессов фирмой "Телемеханик" (Франция), входящей в настоящее время в группу "Шнайдер Электрик".
22. Кроме обмена номерами состояний между автоматами, реализуемыми последовательным расположением в программе конструкций switch, графы переходов могут взаимодействовать и по принципу вложенности, что может быть реализовано вложенными конструкциями switch произвольной глубины или обращениями к функциям, построенным из этих конструкций, которые реализуют графы переходов указанной глубины вложенности.
23.Указанные принципы взаимодействия графов переходов поддерживают возможность иерархического построения алгоритмов.
Предлагаемая технология обеспечивает также проектирование алгоритмов как "сверху-вниз", так и в обратном порядке. При этом первая стратегия упрощает построение корректных алгоритмов. Так, например, если алгоритм не обладает параллелизмом по состояниям, то в первоначально построенном графе переходов каждая вершина может быть заменена фрагментом, содержащим несколько вершин; в нее могут быть вложены другие графы переходов; из нее могут вызываться другие графы переходов. В полученной структуре каждая вершина, в свою очередь, может быть детализирована. Структура программы, реализующей построенный алгоритм, должна быть изоморфна его структуре.
24. При задании алгоритма в виде системы графов переходов, последняя, если это возможно, разбивается на не связанные между собой подсистемы, образованные взаимосвязанными графами переходов, и для каждой из них, если позволяет размерность, строится граф достижимых маркировок (состояний), описывающий все функциональные возможности подсистемы.
Таким образом, в рамках предлагаемой технологии, если позволяет размерность выделяемых подсистем графов переходов, тестирование систем графов переходов и реализующих их программ может быть заменено определением всех функциональных возможностей рассматриваемого описания, как это делается при верификации протоколов [38].
При использовании сильносвязанных систем графов переходов большой размерности проектирование на основе предлагаемой технологии обеспечивает возможность построения "контролепригодных" программ, для которых может быть выполнено автоматическое протоколирование их работы в терминах автоматов [39].
25. Вводится понятие управляющего автомата, под которым понимается совокупность автомата и функциональных элементов задержки. При этом для автомата эти элементы рассматриваются наравне с объектом управления (его исполнительными механизмами и сигнализаторами): автомат кроме значений "объектных" выходных переменных формирует также значения "временных" выходных переменных, а кроме значений "объектных" входных переменных получает также значения "временных" входных переменных. "Временные" переменные отображаются на графах переходах так же, как и "объектные" переменные. В [8] рассмотрены различные подходы к программной реализации функциональных элементов задержки, например с использованием функций (Приложение 4 в [8]).
В общем случае кроме таких функций в компонентах графах переходов могут применяться и функции других типов, например реализующие регуляторы (Приложение 10 в [8]).
26. Графы переходов могут использоваться также и при создании моделей объектов логического управления, что позволяет с единых позиций проводить описание и выполнять моделирование как разомкнутого, так и замкнутого комплекса "Управляющий алгоритм — модель объекта управления".
27. При применении излагаемой технологии спецификация на разработку управляющей программы должна состоять из замкнутой (в общем случае) схемы связей "источники информации — система взаимосвязанных автоматов — функциональные элементы задержки — исполнительные механизмы объекта управления — средства представления информации", описывающей интерфейсы автоматов, и системы взаимосвязанных графов переходов, описывающих поведение автоматов, входящих в эту схему.
При этом схема связей (некоторый аналог диаграммы потоков данных в структурном системном анализе [40]) и графы переходов должны быть изображены так, чтобы их (по возможности) можно было охватить одним взглядом, что упрощает понимание спецификации (требование "гештальтности" описания [41]). Для этого, в частности, в графах переходов должны использоваться только символы переменных, а не их аббревиатуры, а смысл каждой переменной должен быть ясен при "переводе взгляда" на схему связей, которая может содержать в том числе и комментарии.
Для задач большой размерности указанная схема может строиться (с учетом всего "окружения") для каждого автомата в отдельности.
28. В рамках SWITCH-технологии предлагается иметь один язык спецификации алгоритмов (графы переходов) при применении различных языков программирования, что не было отмечено в [1].
В [8] разработаны методы формальной и изоморфной реализации графов переходов программами, написанными на различных языках программирования, которые используются в управляющих вычислительных устройствах различных типов, в том числе и в программируемых логических контроллерах. Для ПЛК наиболее целесообразно применять аналоги конструкции switch, позволяющие строить компактные и обозримые текстовые программы. Эту конструкцию моделирует цифровой мультиплексор, обеспечивающий возможность построения для программирования ПЛК функциональных схем, формально и изоморфно реализующих графы переходов (разд.4.2.3 в [8]).
Графы переходов, построенные, как изложено выше, и используемые в качестве спецификации для разработки программы (определяя ее функциональные возможности), а в дальнейшем и в качестве теста для ее сертификации, могут быть реализованы также и с помощью языка "Графсет". При этом появляется возможность при сертификации программы визуально наблюдать переходы в графах переходов. Однако этот язык программирования имеет ряд недостатков. Перечислим некоторые из них: возможность одновременного отражения активности нескольких вершин в одной диаграмме приводит при реализации к двоичному их кодированию, при котором число двоичных внутренних переменных (используемых для кодирования вершин и имеющихся в ПЛК в ограниченном количестве) равно числу вершин в диаграмме; язык "Графсет" позволяет непосредственно реализовать только графы переходов автоматов Мура, требуя увеличения числа вершин для графов переходов, соответствующих другим типам автоматов; каждый граф переходов реализуется на нескольких экранах; графы переходов с переходами "назад" реализуются ненаглядно, так как для таких переходов линии, связывающие вершины, не изображаются или не могут быть изображены, и поэтому заменяются "соединителями".
При этом интересно отметить, что если в ПЛК, например при реализации одной совокупности графов переходов, израсходованы все двоичные внутренние переменные, выделенные для программ на языке "Графсет", то, изменив язык программирования при реализации другой совокупности графов переходов, может появиться возможность использовать другие типы внутренних переменных контроллера. Таким образом, даже при программировании одного ПЛК может возникнуть необходимость в программировании на разных языках при применении одного и того же языка спецификаций.
29. Излагаемый подход позволяет Заказчику, Проектанту (Технологу), Разработчику, Программисту, Пользователю и Контролеру однозначно понимать, что должно быть сделано, что делается и что сделано в программно реализуемом проекте. Он позволяет разделять работу, а самое главное, ответственность между Специалистами различных областей знаний, а также между организациями, что особенно важно при работе с инофирмами из-за наличия языкового барьера и неоднозначности понимания естественных языков.
Подход обеспечивает возможность уже на ранних стадиях проектирования учесть все детали технического задания и продемонстрировать Заказчику в удобной для него форме, как оно понято.
30. Описываемая технология позволяет Участникам разработки проекта общаться не традиционным путем, в терминах технологического процесса (например, не "идет" режим экстренного пуска дизель-генератора), а на полностью формализованном, но понятном Специалистам различных областей знаний языке (на своего рода техническом эсперанто), на котором объясняться можно, например, следующим образом: "В третьем графе переходов, в пятой вершине, на четвертой позиции — изменить значение 0 на 1", что не вызывает разночтений, возникающих из-за неоднозначности понимания даже для одного естественного языка, а тем более для нескольких таких языков в случае, когда Участники разработки представляют разные страны, и не требует привлечения Специалистов, знающих технологический процесс, для корректного внесения изменений в программы [42].
31. Излагаемый подход позволяет снять с Программиста необходимость знания технологического процесса, а с Разработчика — тонкостей программирования.
Он дает возможность Программисту прикладных задач ничего не додумывать за Заказчика, Технолога и Разработчика, а только однозначно реализовать формализованную спецификацию, что позволяет резко снизить требования к его квалификации, а в конечном счете и вовсе отказаться от его услуг и перейти к автопрограммированию Разработчиком.
Этот подход обеспечивает возможность оставлять понятные "следы" после завершения разработки, что упрощает сопровождение и модификацию программ даже новыми Специалистами.
Он позволяет контролировать разработку и тексты программ, а не только результаты их выполнения, как это имеет место в большинстве случаев в настоящее время, приближая приемку программ к приемке аппаратуры, которая проверяется не только на функционирование [8].
32. При реализации графов переходов значения "временных" выходных переменных заменяются, например, вызовами функций, реализующих функциональные элементы задержки, а значения "объектных" выходных переменных могут заменяться вызовами других типов функций.
Поэтому рассматриваемый подход может использоваться также и при реализации управляющей части логико-вычислительных алгоритмов, как это, например, показано в Приложении 10 в [8], в котором приведена программа, обеспечивающая синхронизацию генератора с шинами главного распределительного щита.
33. Описываемая технология применяется в НПО "Аврора" при создании систем управления техническими средствами для судов различных проектов и других технологических объектов, в которых используются вычислительные средства разных фирм с различными языками программирования. При применении одного языка спецификаций в [42] программирование выполнялось на языке ПЛ/М, в [43] — на языке функциональных блоков, в [44] — на языке ассемблера однокристальной микроЭВМ КР 1816 ВЕ51, а при создании комплексной системы управления техническими средствами для судна проекта 17310 — на языке инструкций ALPro [45, 46].
Для упрощения программирования в последнем случае Б.П.Кузнецовым (НПО "Аврора") при участии автора был создан транслятор "Ядро языка Си — язык ALPro" [47], который применяется к программам на языке Си, построенным формально и изоморфно по графам переходов.
34. Опыт проектирования, испытаний и эксплуатации ряда систем логического управления подтвердил эффективность использования SWITCH-технологии для систем рассматриваемого класса. При этом фирма "Norcontrol" (Норвегия) в [42] отметила, что применение излагаемого подхода позволило ей повысить качество системы логического управления дизель-генератором ДГР-2А 500*500 для судна проекта 15640.
Примеры использования этой технологии для других классов задач управления приведены в Приложениях 10 и 11 в [8].
35. Из изложенного выше следует, что наибольший эффект от применения предлагаемой технологии достигается в случае, когда алгоритмизация и программирование выполняются в разных организациях или странах [42].
36. Излагаемая технология может характеризоваться совокупностью, состоящей из семи терминов: "состояние" — "автомат" — "независимость от глубокой предыстории" — "многозначное кодирование состояний" — "система взаимосвязанных графов переходов" — "формальное и изоморфное программирование" — "конструкция switch".
Ее применение обеспечивает наглядность, понятность, структурность, вызываемость, вложенность, иерархичность, управляемость и наблюдаемость программ, формально и изоморфно построенных по графам переходов.
Относительно небольшое число внутренних переменных, получаемое за счет применения многозначного кодирования состояний, резко упрощает и ускоряет их пересылку между вычислителями, которая может возникнуть, например, при построении отказоустойчивых систем, в которых при традиционном использовании, например, языка функциональных блоков, приходится пересылать содержимое сотен, а то и тысяч триггеров.
37. Для задач, отличных от логического управления, следует различать состояния управляющего автомата, описываемого графом переходов, от состояний остальной памяти. Если число состояний первого типа обычно не превышает нескольких десятков, то число состояний второго типа существенно превышает эту величину [18], и поэтому они в явном виде не выделяются. Если указанное разделение состояний не выполнять, как это сделано, например, в [37], то состояния в дальнейшем и не используются, а поведение программной компоненты определяется как набор действий, выполняемых в ответ на события, без упоминания состояний первого типа, с которыми эти действия связаны. При этом следует отличать управляющие переменные от других внутренних переменных, соответствующих остальным атрибутам.
38. В рамках описываемой технологии управляющие автоматы могут строиться для:
Построенные автоматы могут взаимодействовать между собой непосредственно путем обмена номерами состояний, вложения и вызова, а также через дополнительные автоматы. При этом отметим, что с увеличением числа автоматов в системе доказательство правильности их совместного функционирования усложняется.
Из изложенного следует, что излагаемый подход может использоваться как при объектно-ориентированном проектировании (Приложение 8 в [8]), так и при процедурном проектировании (Приложение 5 в [8]).
39. Если исходно алгоритм реализуется граф-схемой с одним оператором ввода и одним оператором вывода [48], то по ней с помощью методов, изложенных, например, в [49], может быть построен граф переходов соответствующего автомата (разд.11.5 в [8] и [50]), который в общем случае реализуется конструкцией switch, являющейся телом в конструкции do while с условием выхода из цикла по номеру начальной вершины. Изложенный метод является более эффективным по сравнению с методом структурирования программ Ашкрофта и Манны [8]. При этом отметим, что в [51] в качестве примера приведен граф переходов, реализующий один из алгоритмов сортировки чисел, который традиционно описывается циклической граф-схемой.
40. При непроцедурном задании автоматов в виде таблиц переходов и выходов их строкам и столбцам (или наоборот) соответствуют состояния и события, и поэтому при непроцедурной реализации автоматов интерпретатором порядок обработки (состояние — событие или событие — состояние) не имеет значения (Приложение 3 в [8]). При процедурном задании автоматов в виде схем алгоритмов (программ) [52] выполняется процедурная реализация, которая обычно более экономична по объему памяти и для которой порядок обработки состояний и событий существенен.
Будем называть эти схемы, начинающиеся с дешифратора событий (значений входных переменных), событийными, а схемы, начинающиеся с дешифратора состояний — автоматными. При этом подходы к построению таких схем будем называть событийным и автоматным соответственно.
Автоматный подход позволяет отказаться от применения указанных схем, так как программирование в этом случае может выполняться непосредственно по наиболее "обозримой" форме задания автоматов — графам переходов (с многозначным кодированием вершин), которые изоморфны таким схемам с дешифратором состояний (автоматные схемы алгоритмов) и конструкции switch языка Си (разд.13.4 в [8], [17]).
В [8] предложены схемы алгоритмов, построенные с помощью событийного и автоматного подходов, которые реализуют R-триггер и счетный триггер соответственно. По мнению автора, автоматные схемы алгоритмов являются более "понятными".
В [53, 54] описаны программы, реализующие некоторые функции управления элементом графического пользовательского интерфейса "тулбар", построенные на основе событийного и автоматного подходов. В первом случае, так же как и в объектном программировании, в котором "делается упор на создание автономных агентов, взаимодействующих между собой для достижения желаемого результата" [37], для каждого события реализован свой обработчик. При этом так же, как и в объектном программировании для обеспечения взаимодействия методов класса, эвристически вводятся флаговые (управляющие) переменные (в данном случае одна), оставляя вопрос о понятности и корректности последовательностной логики такой программы открытым. Во втором случае обработчики событий вызывают функцию, формально и изоморфно реализующую граф переходов, передавая ей в качестве параметра номер произошедшего события. Благодаря тому, что логика, ранее рассредоточенная по обработчикам, теперь сконцентрирована внутри одной функции, резко упрощается понимание поведения программы [54, 55].
41. Описываемая технология является сквозной и прозрачной, так как она охватывает этапы алгоритмизации и программирования, для которых разработаны методы, обеспечивающие высокое качество проектирования не только в пределах одного этапа, но и между этапами.
42. Изложенный подход подробно описан в [8], а также в [17, 56-59]. Подходы, наиболее близкие к предлагаемому, содержатся в [36, 60-62].
Разработанный подход существенно дополняет международный стандарт IEC 1131-3 (IEC 61131-3) [1], который, описывая типовые языки программирования для ПЛК, не содержит (в отличие от [8]) методов проектирования программ на этих языках. Эта проблема не решена и в документации ведущих в области автоматизации фирм мира [63], в которой в лучшем случае содержатся лишь отдельные примеры (например, в [64]. Такая же ситуация имеет место и в литературе [65-74].
Рассмотренный подход был предложен и внедрен автором в 1991 г. [43, 75]. Он был, в частности, использован в НПО "Аврора" при создании: