Так же как и в [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]. Он был, в частности, использован в НПО "Аврора" при создании:

• системы управления дизель-генератором ДГР-2А 500*500 для трех судов проекта 15640 на базе аппаратуры "Selma-2" фирмы "ABB Stromberg" (Финляндия). Программирование выполнялось на языке функциональных блоков [43];
• системы управления дизель-генератором того же типа для судна проекта 15967 на базе аппаратуры "Selma-2" фирмы "ABB Stromberg". Программирование выполнялось на языке функциональных блоков;
• системы управления дизель-генератором того же типа для судна проекта 15760 на базе аппаратуры фирмы "Norcontrol" (Норвегия). Программирование выполнялось фирмой на языке ПЛ/М [42];
• комплексной системы управления техническими средствами пяти судов проекта 17310 на ПЛК "Autolog" фирмы "FF-Automation" (Финляндия) [45]. Программирование для общесудовых систем выполнялось на языке инструкций ALPro [46], а для системы управления вспомогательными механизмами — с помощью транслятора "Ядро языка Си — язык инструкций ALPro" [47];
• комплекта "Авролог" для управления техническими средствами судна на ПЛК "Autolog" фирмы "FF-Automation". Программирование выполнялось с помощью указанного выше транслятора;
• автоматизированной системы управления технологическими процессами (АСУ ТП) центральной подготовительной станции первичной обработки нефти "Авролог-НП1" (Северо-Ореховское месторождение). Программирование выполнялось на языке инструкций ALPro;
• АСУ ТП дожимной насосной станции "Авролог-НП2" (Северо-Покурское месторождение). Программирование выполнялось на языке инструкций ALPro;
• системы управления турбокомпрессорным агрегатом "Ларина", используемой при производстве полиэтилена в ПО "Полимир" (Новополоцк). Программирование выполнялось на языке ассемблера однокристальной микроЭВМ КР 1816 ВЕ51 [44].

В настоящее время подход, основанный на применении графов переходов, названный "State Logic", начал использоваться также и фирмой "GE Fanuc Automation" (GE — General Electric) для программирования старших моделей своих ПЛК [77]. При этом был разработан язык программирования ECLiPS (English Control Language Program Software), позволяющий описывать графы переходов. При этом в материалах фирмы отмечено, что предложенный подход может применяться специалистами, которые не имеют опыта программирования. Этот подход рассматривается фирмой как практическая альтернатива лестничным схемам.

Диаграммы состояний применяются в качестве одного из языков программирования промышленных контроллеров фирмы "Matsushita Automation Соntrols" [78], а язык "список состояний" — для программирования контроллеров фирмы "Festo Cybernetic" [79].

Такой метод был разработан Г. Бучем в 1991 г. [84]. Он включает несколько визуальных формализмов (диаграмм) для отображения различных особенностей выделяемых классов и объектов. При этом в [84] было предложено (на одной странице) для описания поведения объектов использовать диаграммы переходов и был приведен пример применения этих диаграмм. Однако в рамках метода Буча в отличие от излагаемого подхода эти диаграммы являлись лишь "картинками" [12], помеченными словами, а не были математическими моделями. Кроме того, Г. Бучем (в отличие от [8, 17]) не было отмечено, что при определенном подходе к построению схем алгоритмов они могут быть изоморфны графам переходов, и поэтому их противопоставление в этом случае некорректно. Этот факт не был отмечен также и в работах [50, 86].

Д.Харел предложил свой подход для несколько более широкого класса систем управления по сравнению с системами логического управления, которые называются "реактивными" или "реагирующими" ("reactive") [90], "поведение которых лучше всего характеризуется их реакцией на события, произошедшие вне их контекста" [91]. Такие системы реагируют на поток событий изменением состояний и выполнением действий при переходах из состояния в состояние или действий и деятельностей в состояниях [92-100]. При этом Д.Харелом был предложен визуальный формализм (модификация диаграммы состояний и переходов), названный им "картой состояний" ("State-chart" в [88], или "State chart" в [92]), которая "математически эквивалентна диаграммам автоматов Мура-Мили" [90], но позволяет в ряде случаев описывать поведение этих автоматов более компактно. Карты состояний могут быть также названы как "диаграммы Харела". Отметим основные особенности этих диаграмм.

В излагаемой технологии вместо понятия "объект" применяются понятие "автомат" и динамические диаграммы одного типа (система взаимосвязанных графов переходов) даже при наличии большого числа автоматов с большим уровнем вложенности, которые весьма просто формально и изоморфно реализуются практически на любом языке программирования.

SWITCH-технология может рассматриваться в качестве методологии проектирования программного обеспечения по крайней мере для класса SoftLogic [72]. Этот подход позволяет "не говорить о том, что программное обеспечение работает, а объяснить, почему оно работает" [20]. Подход, в частности, позволяет ответить на три вопроса: откуда появляются внутренние (управляющие) переменные, сколько их должно быть и для какой цели каждая из них используется?

Автоматный подход применяется для спецификации протоколов сетей ЭВМ [38, 102-105], а также в SDL-методологии [106-108], разработанной Международной комиссией по телефонии и телеграфии для создания программного обеспечения телекоммуникационных систем. Однако SDL-диаграммы, являющиеся некоторой разновидностью схем алгоритмов, в которые в явном виде могут вводиться состояния, весьма громоздки и соответствуют только одному классу автоматов — автоматам Мили. В SDL-методологии не оговаривается ряд вопросов, отмеченных выше, которые связаны, например с умолчаниями и флагами. Ряд других недостатков SDL-диаграмм (в частности, их вертикальная направленность, существенно уменьшающая обозримость спецификации и не позволяющая эффективно использовать плоскость листа бумаги или дисплея) отмечен в [109].

Это привело к тому, что при разработке [109-112] технологии программирования встроенных систем реального времени, реализующих широкий класс алгоритмов, ее авторы, отметив недостатки модели Харела, например, "отсутствие ориентации на генерацию конечного кода", при создании модели поведения объектов объединили достоинства SDL-диаграмм и диаграмм Харела, сохранив, правда, альтернативные нотации каждого из них. Та же ситуация сохранилась и при создании объектно-ориентированной методологии разработки программного обеспечения систем реального времени [113]: в поведенческой модели используются диаграммы состояний в модифицированной нотации Харела, а для детализации — SDL-диаграммы [114]. Это делает модели, предложенные в [109, 114], весьма специфичными и ограничивает их применение для задач логического управления технологическими процессами, при решении которых SDL-диаграммы (в отличие от телефонии) ведущими в этой области фирмами мира не используются.

В этом языке для описания поведения объектов используется "конечный автомат" ("State Machine"), который в зависимости от приоритета состояний или деятельностей в этом описании задается диаграммой состояний (State Diagram) или диаграммой деятельностей (Activity Diagram) соответственно, что не корректно, так как в последних возможен параллелизм по переходам в одной диаграмме. При этом диаграмма состояний не является одной из классических, а считается эквивалентной диаграмме Харела [90], но почему-то несколько отличается от нее [92].

Кроме того, в [15], в отличие от [12, 92], показано, что каждая диаграмма деятельностей (так же как и каждая диаграмма "Графсет" (п.21)) может быть заменена системой взаимосвязанных графов переходов, которые, как отмечено в п.6 для диаграмм "Графсет", могут быть реализованы с меньшим числом внутренних переменных.

Расширение нотации диаграмм Харела выполнено в [120]. Если в диаграммах Харела на переходах допустимо применение лишь отдельных условных вершин, характерных для схем алгоритмов (Flow Diagram), в которых понятие "состояние" не используется (stateless), то в [120] эти вершины могут образовывать более сложные конфигурации. Получающаяся при этом тесная связь между "state diagram" и "flow diagram" привела к появлению нового термина "stateflow". Возможность применения этих диаграмм в качестве исполняемых спецификаций на широко используемом (по крайней мере, в университетских кругах) языке "MATLAB" [121] позволяет также реализовать эти диаграммы на языках С и С++.

Однако, так как и эта нотация является весьма специфической, то для систем логического управления, принадлежащих к нижнему уровню управляющих систем (особенно при реализации их на ПЛК), более целесообразно при алгоритмизации применять системы взаимосвязанных графов переходов, содержащих минимальную номенклатуру компонент и обозначений ("не надо размножать сущности без необходимости" (Оккам)) и ориентированных на классические модели теории автоматов, по которым, как отмечено выше, программирование может выполняться формально и изоморфно даже вручную.

Изложенное весьма актуально, так как обычно эта документация в лучшем случае содержит только тексты программ [122], их описания и руководство пользователя, а в худшем — тексты программ в документацию не включаются [123].

Более того, графы переходов могут использоваться для описания поведения машин Тьюринга, применяемых при формальном определении понятия алгоритм [101, 152]. Поэтому заданная машина Тьюринга также может быть реализована на основе конструкции switch, в которой используются дополнительные действия, имитирующие сдвиг головки "чтение-запись" по рабочей ленте. Таким образом, излагаемый подход в принципе может применяться и для более широкого по сравнению с рассматриваемым класса задач, как например это делается при использовании модели "расширенного конечного автомата", который рассматривается в виде композиции двух автоматов — конечного и контекстного, состояния первого из которых называются основными и кодируются одной переменной, а состояния второго отражают переменные, называемые контекстными [38, 102]. Этот же подход может применяться при описании "объектов" в объектно-ориентированном программировании, что позволяет в явном виде поддержать одно из определений объекта как некоторого элемента, на который можно воздействовать, изменяя его состояния.

В этой связи особо следует отметить, что в [154] создатель операционной системы Unix К.Томпсон на вопрос о текущей работе ответил: "Мы создали язык генерации машин с конечным числом состояний, так как реальный селекторный телефонный разговор — это группа взаимодействующих машин с конечным числом состояний. Этот язык применяется в "Bell Labs" по прямому назначению — для создания указанных машин, а кроме того, с его помощью стали разрабатывать драйверы".

Технология, описанная в разд.2, предназначена для создания алгоритмического и программного обеспечения систем логического управления, в которых ввод входных переменных выполняется только путем опроса [155, 156] — используется "циклический исполнитель" [91]. Другая особенность этой технологии состоит в том, что при ее применении программы реализуются компилятивно: по графам переходов строятся конструкции switch или их аналоги, которые выполняются непосредственно и поэтому являются "активными".

Н. И. Туккель (НПО "Аврора") и автор применили SWITCH-технологию при разработке системы управления дизель-генератором, реализуемой на промышленном компьютере и операционной системе QNX, в которой управляющая программа выполняется как один процесс, а программа, моделирующая объект управления — как другой процесс. При этом был создан вариант SWITCH-технологии для "реактивных" систем [39, 186], ввиду того что управление на основе событий приводит к существенным отличиям при проектировании системы по сравнению со случаем применения в ней только "циклического исполнителя" [91]. Такие системы обычно реализуются на промышленных компьютерах, работающих под управлением операционных систем реального времени.

• в качестве базового используется понятие "автомат", а не "класс", "объект", "алгоритм" или "агент", как это имеет место при других подходах. При этом соответствующая область программирования может быть названа "автоматно-ориентированное программирование";
• в общем случае автоматы рассматриваются не изолированно, а как составные части взаимосвязанной системы — системы взаимосвязанных автоматов, поведение которой формализуется с помощью системы взаимосвязанных графов переходов;
• в качестве основной применяется модель смешанного автомата, для описания поведения которого используется соответствующий граф переходов только с "простыми" состояниями (гиперсостояния не используются);
• расширена (по сравнению с [8]) нотация, применяемая при построении графов переходов (например, в части перечисления вложенных автоматов);
• на этапе изучения предметной области на основе технического задания, которое при автоматизации технологических процессов обычно выдается Заказчиком в словесной форме в виде совокупности сценариев и случаев использования [91], строится структурная схема системы, позволяющая получить общее представление об организации управления, применяемой аппаратуре и интерфейсе объекта управления;
• на этапе анализа на основе технического задания выделяются сущности, каждая из которых называется автоматом (например, автомат управления насосом или автомат контроля температуры);
• состояния каждого автомата первоначально определяются по выделенным состояниям объекта управления или его части, а при большом их количестве — по алгоритму управления, построенному в другой нотации (например, в виде схемы алгоритма [51]);
• в автоматы также могут быть введены и другие состояния, связанные, например, с неправильными действиями Оператора;
• каждый автомат при необходимости может быть декомпозирован;
• итеративный процесс анализа может выполняться многократно и завершается созданием перечня автоматов и перечня состояний для каждого из них;
• на этапе проектирования в отличие от традиционного программирования вводится подэтап — кодирование состояний автомата. При этом в каждом автомате для различия состояний применяется многозначный код, в качестве комбинаций которого вводятся десятичные номера состояний;
• автоматы взаимодействуют за счет обмена номерами состояний, вложенности и вызываемости. Они также могут быть одновременно вложенными и вызываемыми;
• строится схема взаимодействия автоматов, отражающая указанные типы взаимодействий. Она формализует систему взаимодействующих автоматов. Эта схема заменяет в предлагаемой технологии диаграмму объектов и частично диаграмму взаимодействий (диаграмму кооперации), которые применяются в объектном моделировании [91];
• входные воздействия разделяются на события, действующие кратковременно, и входные переменные, вводимые путем опроса;
• входные воздействия целесообразно реализовывать в виде входных переменных, а применять события — для сокращения времени реакции системы. При этом одно и то же входное воздействие может быть одновременно представлено и событием и входной переменной;
• прерывания обрабатываются операционной системой и передаются программе в виде сообщений, а после этого обрабатываются как события с помощью соответствующих обработчиков;
• некоторые входные переменные могут формироваться в результате сравнения входных аналоговых сигналов с уставками;
• номера состояний других автоматов, с которыми автомат взаимодействует за счет обмена номерами состояний, также рассматриваются в качестве его входных воздействий;
• все выходные воздействия являются действиями, а не деятельностями;
• группы входных и выходных воздействий связываются с состояниями, выделенными для каждого автомата;
• связи каждого автомата с его "окружением" формализуются схемой связей автомата, предназначенной для полного описания интерфейса автомата. В этой схеме приводятся источники и приемники информации, полные названия всех воздействий и их обозначения, а также информация о том, в какой автомат он вложен и какие автоматы вложены в него;
• имя автомата начинается с символа 'A', имя события — с символа 'e' (от английского слова event — событие), имя входной переменной — с символа 'x', имя переменной состояния автомата — с символа 'y', а имя выходного воздействия — с символа 'z'. После каждого из указанных символов следует номер соответствующего автомата или воздействия;
• система взаимосвязанных автоматов образует системонезависимую (например, от операционной системы) часть программы, которая реализует алгоритм функционирования системы управления;
• реализация входных переменных, обработчиков событий, выходных воздействий, вспомогательных модулей и пользовательских интерфейсов образует системозависимую часть программы;
• обработчики событий содержат вызовы функций графов переходов (автоматов) с передачей им соответствующих событий. Функции входных и выходных воздействий вызываются из функций, реализующих автоматы. Функции, образующие вспомогательные модули, вызываются из функций входных и выходных воздействий. Таким образом, автоматы находятся в "центре" структуры программы, создаваемой на основе предлагаемого подхода;
• если составляющая системозависимой части программы спроектирована как автомат (например, автомат разбора файла рекомендаций Оператору), то он также может быть введен в схему взаимодействия автоматов;
• если платформа не изменяется, то вспомогательные модули могут быть использованы повторно, как образцы [91];
• запуск автоматов может производиться как из системозависимой части программы (например, из обработчиков событий), так и из системонезависимой части;
• вложенные автоматы последовательно запускаются с передачей "текущего" события в соответствии с путем в схеме взаимодействия автоматов, определяемым их состояниями в момент запуска головного автомата. При этом последовательность запуска и завершения работы автоматов напоминает алгоритм поиска в глубину [157];
• вызываемые автоматы запускаются из выходных воздействий с передачей соответствующих "внутренних" событий;
• автоматы могут запускаться однократно с передачей какого-либо события или многократно (в цикле) с передачей одного и того же события;
• при реализации системы учтено, что функции, реализующие автоматы, не реентерабельны (не допускают повторного запуска до их завершения);
• каждый автомат при запуске выполняет не более одного перехода;
• после обработки очередного события автомат сохраняет свое состояние и "засыпает" до появления следующего события;
• дуги и петли графов переходов помечаются произвольными логическими формулами, которые могут содержать входные переменные и предикаты, проверяющие номера состояний других автоматов и номера событий;
• дуги и петли кроме условий переходов могут содержать список последовательно выполняемых выходных воздействий;
• вершины в графах переходов практически всегда являются устойчивыми и содержат петли. Если на петле не выполняются выходные воздействия, то она умалчивается. В противном случае, в явном виде изображаются одна или несколько петель, каждая из которых помечена по крайней мере выходными воздействиями;
• вершина графа переходов может содержать список последовательно запускаемых вложенных автоматов и список последовательно выполняемых выходных воздействий;
• для обобщения "одинаковых" исходящих дуг в каждом графе переходов допускается объединение вершин в группы. Также допускается слияние входящих в вершину дуг в одну линию;
• каждый граф переходов проверяется на достижимость, непротиворечивость, полноту и отсутствие генерирующих контуров;
• этап завершается построением графа переходов для каждого автомата, совокупность которых образует систему взаимосвязанных автоматов;
• на этапе реализации строится программа, в которой графы переходов, входные переменные, обработчики событий и выходные воздействия выполняются в виде функций. Кроме того, программа содержит вспомогательные модули, состоящие из наборов соответствующих функций (например, модуль управления таймерами);
• выделение функций декомпозирует задачу, а выделение состояний — ее последовательностную логику;
• для хранения номера состояния автомата (различения состояний) используется одна внутренняя переменная. Для различения изменения состояния применяется вторая переменная, носящая вспомогательный характер;
• разработан универсальный алгоритм программной реализации иерархии графов переходов с произвольным их количеством и произвольным уровнем вложенности;
• каждый граф переходов формально и изоморфно реализуется отдельной функцией (подпрограммой), создаваемой по шаблону, содержащему две конструкции switch и оператор if. Первая конструкция switch вызывает вложенные автоматы и реализует переходы и действия на дугах и петлях. Оператор if проверяет изменилось ли состояние, и если оно изменилось, вторая конструкция switch активирует вложенные автоматы и реализует действия в новой вершине;
• после реализации графа переходов текст подпрограммы должен корректироваться для обеспечения бесповторности опроса входных переменных, помечающих дуги, исходящие из одного состояния. Таким образом, решается проблема "риска" [8];
• каждая входная переменная и каждое выходное воздействие также реализуется функцией, что и позволяет применять SWITCH-технологию не только для решения задач логического управления;
• имена функций и переменных, используемых при реализации автоматов, совпадают с обозначениями, применяемыми в схемах связей автоматов и графах переходов. Например, переменная, в которой хранится номер произошедшего события, имеет имя 'e';
• все функции, реализующие входные переменные, записываются в порядке возрастания их номеров в один файл, а реализующие выходные воздействия — в другой;
• функции, реализующие автоматы, входные переменные и выходные воздействия, содержат вызовы функций для обеспечения протоколирования;
• этап завершается построением структурной схемы разработанного программного обеспечения, отражающей взаимодействие его частей. Эта схема может включать схему взаимодействия автоматов, которая при этом отдельно не выпускается;
• на этапе отладки обеспечена возможность одновременной индикации значений переменных состояний всех автоматов на одном экране;
• на этапе сертификации за счет введения в функции автоматов, входных и выходных воздействий вызовов функций протоколирования обеспечено автоматическое ведение протокола. В нем указываются события, запуск автоматов, их состояния в момент запуска, переходы в новые состояния, завершение работы автоматов, значения входных переменных, выходные воздействия и время начала выполнения каждого из них. Кроме "полного" протокола также автоматически строится "короткий" протокол, в котором фиксируются только события и инициируемые ими выходные воздействия, интересующие Заказчика;
• сообщения в "полном" протоколе о запуске и завершении реализации каждого автомата играют роль скобок, логически выделяющих разные уровни вложенности автоматов;
• на этапе документирования для точного оформления результатов проектирования и разработки программы создается и сдается в архив документация (по крайней мере в электронном виде), имеющая как минимум следующую комплектность: структурная схема системы; схема разработанного программного обеспечения; распечатки экранов пользовательских интерфейсов; перечни событий, входных переменных и выходных воздействий; диаграмма взаимодействия автоматов; описание нотации, используемой в графах переходов; шаблон для реализации графов переходов смешанных автоматов произвольного уровня вложенности; для каждого автомата: словесное описание (фрагмент технического задания), рассматриваемое в качестве комментария, схема связей автомата, граф переходов и исходный текст функции, реализующей автомат; алгоритмы, например в виде графов переходов, и исходные тексты вспомогательных модулей и функций, реализующих входные переменные, обработчики событий и выходные воздействия; протоколы для сертификации программы, выполняющие роль контрольных примеров [158]; руководство программиста; руководство пользователя;
• изложенный вариант технологии может использоваться и при построении модели объекта управления, для которой должен создаваться аналогичный комплект документации;
• после этого, при появлении любых изменений, возникающих в ходе дальнейших этапов жизненного цикла программы, весь комплект документации (по завершении каждого этапа) должен корректироваться [159]. Для этого составляется перечень исполняемых модулей программы, в котором для каждого из них указывается значение циклической контрольной суммы, отражающей любое изменение в модуле. При этом Контролер по документации должен знать значение этой суммы для исходного файла, и после завершения каждого этапа при любом изменении указанного значения требовать представления извещения на выполненную модификацию, по которому документация должна быть комплектно откорректирована и сдана в архив.

• в отличие от объектного моделирования [91, 113], во-первых, построение всех основных моделей основано на применении только автоматной терминологии, а во-вторых, используется динамическая модель только одного типа — система взаимосвязанных графов переходов;
• применение такой динамической модели позволяет эффективно описывать и реализовывать задачи рассматриваемого класса даже при большой их размерности. Применение графов переходов в качестве языка спецификаций алгоритмов делает обозримым даже весьма сложное поведение программы и позволяет легко вносить изменения как в спецификацию, так и в ее реализацию;
• совместное рассмотрение схемы связей автомата и его графа переходов позволяет понимать этот граф, а совместное рассмотрение этого графа и изоморфной ему подпрограммы позволяет понимать эту подпрограмму;
• подробное документирование проекта создания программного обеспечения позволяет при необходимости вносить изменения в него через длительный срок после его выпуска и даже другими Специалистами;
• без использования объектно-ориентированного подхода программа четко разделяется на две части — системонезависимую и системозависимую;
• при проектировании системонезависимой части программы детали реализации входных и выходных воздействий скрыты. Они раскрываются только при реализации системозависимой части программы;
• этапы проектирования и реализации системонезависимой части программы полностью разделены;
• реализация входных переменных и выходных воздействий в виде функций обеспечивает: их протоколирование, простоту перехода от одних типов источников и приемников информации к другим, наличие действующего макета программы [158] в любой момент времени после начала реализации системозависимой части;
• упорядоченное хранение функций, реализующих входные переменные и выходные воздействия, упрощает внесение изменений;
• для кодирования любого числа состояний автомата используется только одна внутренняя переменная, что обеспечивает наблюдаемость поведения автомата за счет "слежения" за изменениями значений только этой переменной. Для системы из N автоматов "слежение" выполняется по N многозначным переменным, значения каждой из которых выводятся на "отладочный" экран, представленный в форме, определяемой схемой взаимодействия автоматов;
• каждый граф переходов формально и изоморфно реализуется по шаблону, что при необходимости позволяет решить обратную задачу — однозначно восстановить граф переходов по этой подпрограмме;
• системонезависимая часть программы имеет регулярную структуру и, следовательно, легко читается и корректируется;
• системонезависимая часть программы зависит только от наличия компилятора или интерпретатора выбранного языка программирования на используемой платформе. При смене аппаратуры или переносе программы под другую операционную систему необходимо изменить только системозависимую часть;
• автоматическое ведение протокола в терминах спецификации обеспечивает возможность сертификации программы. При этом демонстрируется соответствие функционирования программы "поведению" системы взаимосвязанных графов переходов для рассматриваемых событий при выбранных значениях входных переменных. Это достигается за счет сопоставления "полного" протокола со спецификацией. Совокупность "полных" протоколов обеспечивает возможность сертификации программы в целом. Для сертификации в терминах, понятных Заказчику, могут применяться "короткие" протоколы, которые можно использовать также и в качестве фрагментов методики проверки функционирования системы. При этом отметим, что из двух групп понятий "объект-алгоритм" и "алгоритм-программа" сертификация обычно связывается только со второй группой понятий;
• "короткий" протокол позволяет определить наличие ошибки в выдаче выходных воздействий, а "полный" — определить автомат, который при этом необходимо откорректировать. Поэтому "короткие" протоколы могут быть названы "проверяющими", а "полные" — "диагностирующими";
• возможность автоматического получения "полных" протоколов в терминах автоматов показывает, что система взаимосвязанных графов переходов, используемая для спецификации алгоритмов, является не "картинкой", а математической моделью;
• несмотря на достаточно высокую трудоемкость проведения "подробной" сертификации при применении предлагаемых протоколов, этот способ существенно более практичен, чем другие подходы к построению качественных программ, которые изложены, например, в [160, 161];
• порождаемый некоторыми событиями протокол или его часть является соответствующим сценарием. Таким образом, сценарий [64] строится автоматически при анализе программы, а не вручную при ее синтезе, как это предлагается делать при других подходах [91, 113]. Ручное построение всей совокупности сценариев и формальный синтез системонезависимой части программы по ним для задач со сложной логикой практически не осуществимы;
• излагаемый подход не исключает интерактивной отладки и сертификации;
• поведение системы взаимосвязанных автоматов является разновидностью коллективного поведения автоматов [162] и может использоваться при построении "многоагентных систем, состоящих из реактивных агентов" [163].

Разработка системы управления дизель-генератором, выполненная с помощью предлагаемого варианта технологии [186], подтвердила мнение Ф.Брукса [158] о том, что время, затрачиваемое на проектирование алгоритма, при котором строятся не картинки, а математические модели, значительно превышает время, затрачиваемое на написание системонезависимой части программы, изоморфной спроектированному алгоритму, а также мнение Д.Воаса [164] о CASE-средствах, которые сами по себе мало что убыстряют, а "практика их применения показала только то, что из некорректных картинок можно получить некорректный код".

6. Применение конечных автоматов при программировании схем программируемой логики

Это правило используется для реализации последовательностной логики (Sequential Logic), описываемой в терминах состояний с помощью конечных автоматов (State Machine). При этом автоматы с многозначным кодированием состояний (этот термин в [168] не применяется) задаются в виде диаграмм состояний (State Diagram). В [169] приводятся примеры реализации автоматов с синхронными выходами (State Machines with Synchronous Outputs), соответствующих автоматам Мура, и автоматов с асинхронными выходами (State Machines with Asynchronous Outputs), соответствующих автоматам Мили.

Таким образом, технология проектирования алгоритмического и программного обеспечения, изложенная в разд.2 и 5, дополняет известные подходы к настройке схем программируемой логики, что позволяет с единых позиций проводить аппаратную [171] и программную реализации алгоритмов логического управления, так же как это имеет место в технологии "Co-Design", предназначенной для совместной разработки аппаратных и программных средств с помощью формализованных методов, в которой в качестве языка описания высшего уровня абстракции применяются конечные автоматы [172].

В этом же году Э.Дейкстра [174] предложил ввести так называемые переменные состояния, с помощью которых можно описывать состояния системы в любой момент времени, и ввел для этих целей целочисленные переменные. При этом им были поставлены вопросы о том, какие состояния должны вводиться, как много значений должны иметь переменные состояния и что эти значения должны означать. Он предложил сначала определять набор подходящих состояний, а лишь затем строить программу. Он также предложил сопоставлять процессы с переменными состояния и связывать процессы через эти переменные. По мнению Э.Дейкстры, диаграммы состояний могут оказаться мощным средством для проверки программ. Все это обеспечивает поддержку его идеи, состоящей в том, что программы должны быть с самого начала составлены правильно, а не отлаживаться до тех пор, пока они не станут правильными.

Если процедурное программирование ориентировано на выбор и действия, объектное программирование — на объекты [175], событийное программирование — на события, то предлагаемое в [8] автоматное программирование — на автоматы, включающие состояния и входные и выходные воздействия.

Список литературы