УНИВЕРСИТЕТ ИТМО
Кафедра «Технологии программирования»

Алгоритмизация и программирование для систем логического управления и «реактивных» систем

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

В 1993 г. фирма "Модикон" (США), входящая в настоящее время в группу "Шнайдер Электрик" [4], а в 1996 г. и фирма "Сименс" (Германия) предложили использовать графы переходов в качестве одного из языков программирования для своих ПЛК, причем последняя в работе [2] утверждает, что описание на таком языке не только подходит для Программиста ПЛК, но также понятно Инженеру-механику, Инженеру по запуску оборудования и Инженеру по обслуживанию. При этом отметим, что этот язык был введен указанными фирмами в практику проектирования, несмотря на то что он не входит в состав языков, рекомендуемых международным стандартом [1].

Подходы, предложенные этими фирмами, обладают по сравнению с излагаемой технологией тем преимуществом, что они разработали трансляторы непосредственно с этого языка, получив тем самым исполняемый язык спецификаций [76], а недостатки этих подходов состоят в следующем:

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

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

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

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

4. Использование конечных автоматов в программировании

До последнего времени графы переходов применялись лишь в отдельных задачах теоретического программирования [80], а в практическом программировании они в основном использовались лишь для разработки компиляторов [81, 82], в то время как для аппаратных реализаций графов переходов давно и широко применяются [16]. В [83] было предложено использовать графы переходов в программировании, ввиду того что "мы можем рассматривать любую программу так, будто бы она полностью реализована аппаратными средствами".

Однако при создании программ для решения прикладных задач до последнего десятилетия главенствующим был процедурный подход (функциональная декомпозиция [185]), использующий не графы переходов, а такой визуальный формализм, как схемы алгоритмов.

Ограниченность (по мнению Г. Буча [84]) этого подхода при создании сложных программ привела к разработке и широкому распространению объектно-ориентированного подхода. Однако первое время новый подход поддерживали лишь языки программирования [85], а метод проектирования программ в рамках этой парадигмы отсутствовал.

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

Примерно та же картина, что и в книге Г. Буча, сохранялась в работе [87], авторы которой предложили моделировать "мир" в состояниях. При этом отметим, что этот "мир" в основном состоит из микроволновых печей, клапанов и насосов, относящихся к объектам, управляемым системами логического типа.

Существенно большее внимание диаграммам состояний и переходов, не изменив определения состояний через значения внутренних переменных, Г.Буч уделил в книге [11], разд.5.3 которой написан на основе работ Д.Харела [88, 89], предложившего, по мнению Г.Буча, "простой, но очень выразительный подход, который гораздо эффективнее традиционных автоматов с конечным числом состояний".

Однако указанное противопоставление некорректно, так как подход Д.Харела, как и подход, излагаемый в настоящей работе, базируется на таких автоматах.

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

Наряду с состояниями могут использоваться "гиперсостояния (суперсостояния [12]), объединяющие несколько состояний, имеющих идентичную реакцию на одно и то же событие" [101]. При этом вместо изображения таких переходов в некоторое состояние из всех состояний, охватываемых гиперсостоянием, изображается только один переход из гиперсостояния в указанное состояние (обобщение переходов [101]).

Гиперсостояния теоретически могут иметь произвольную глубину вложения. Переходы из гиперсостояния связаны со всеми уровнями вложения.

Гиперсостояния могут объединять ИЛИ-состояния (последовательные состояния) и И-состояния (параллельные состояния) [91]. В первом случае, перейдя в гиперсостояние, автомат может находиться только в одном из состояний (или в одном состоянии или в другом), а во втором случае в гиперсостоянии "возникает необходимость в параллельных состояниях" [91], изображаемых в "ортогональных регионах".

В вершинах диаграмм, соответствующих состояниям или гиперсостояниям, могут указываться: деятельности (помечаются словом do); действия, выполняемые однократно при входе в вершину (помечаются словом entry); действия, выполняемые однократно при выходе из вершины (помечаются словом exit).

Два последних случая могут быть названы обобщением действий, так как при этом действия, однократно выполняемые при входе в вершину, заменяют одинаковые действия, которые в автоматах Мили или смешанных автоматах указываются на всех входящих в нее дугах, соответствующих переходам, а действия, однократно выполняемые при выходе из вершины, заменяют одинаковые действия, которые в автоматах Мили или смешанных автоматах указываются на всех выходящих из нее дугах, соответствующих переходам.

На каждой дуге диаграммы может быть указано событие, вызывающее переход, и логическое условие, "охраняющее" этот переход. На дуге также могут быть указаны действия, однократно выполняемые на переходе, и формируемые на переходе события.

В диаграммах могут применяться также псевдосостояния, например условное (С), терминальное (Т) и историческое (H), которые не являются реальными состояниями.

Если гиперсостояние содержит историческое псевдосостояние, то при переходе в это гиперсостояние "управление передается тому состоянию, в котором система находилась в данном гиперсостоянии в последний раз" [101]. Использование обобщения переходов и исторического псевдосостояния позволяет, например, эффективно специфицировать прерывание, связанное с переходом системы из любого состояния, принадлежащего гиперсостоянию, в некоторое другое состояние, в котором выполняется обработка прерывания, и продолжение работы системы (после обработки прерывания) из того состояния, в котором наступило прерывание [101].

Некоторые из предложений Д.Харела, например обобщение переходов, могут применяться и в рамках SWITCH-технологии.

Несмотря на некоторую похожесть подхода Д.Харела и излагаемого, они имеют принципиальные отличия, состоящие в том, что, во-первых, у Д.Харела могут использоваться как состояния, так и гиперсостояния, в то время как в SWITCH-технологии применяются только состояния, а во-вторых, при наличии гиперсостояний, по крайней мере с ИЛИ-состояниями, считается, что такая диаграмма Харела описывает поведение одного автомата, в то время как в SWITCH-технологии в этом случае применяется система взаимосвязанных графов переходов, описывающих функционирование системы взаимосвязанных автоматов.

При этом, во-первых, не ясно, как с помощью нотации Харела изобразить диаграмму при большом числе гиперсостояний с большим уровнем вложенности, а во-вторых, видимо, по этой причине в объектном моделировании считается, что диаграмма Харела (диаграмма состояний) описывает жизненный цикл отдельного объекта, а для моделирования поведения сообщества совместно работающих объектов предлагается использовать диаграммы другого типа (диаграммы взаимодействий) [91], что резко усложняет формальный переход к реализации.

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

Кроме того, при объектном подходе остается не ясной формальная связь между статическими и динамическими диаграммами [90, 91], в то время как при замене диаграммы объектов схемой взаимодействия автоматов, использовании схемы связей, включающей систему взаимосвязанных автоматов, и системы взаимосвязанных графов переходов вся концепция в целом оказывается выраженной в терминах автоматов.

Видимо, по этим причинам, а также из-за сложности и специфичности нотации диаграммы Харела в отличие от графов переходов не применяются до настоящего времени при программировании ПЛК.

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

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

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

Еще более разнообразной является модель поведения, предложенная при разработке унифицированного языка моделирования (Unified Modeling Language (UML)) [12, 91, 92, 115, 116], являющегося, по мнению его авторов, коллекцией наилучших инженерных нотаций, применяемых при объектном моделировании сложных систем общего назначения. Построение этого языка базируется на подходах, предложенных в [11, 84, 117, 118].

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

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

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

Неопределенность с выбором нотации для описания поведения объектов в UML еще более увеличивается, в связи с тем что к диаграммам деятельностей отнесены также и конструкции, аналогичные SDL-диаграммам, что свидетельствует о недостаточном научном обосновании формирования рассмотренной части "коллекции".

Для большего однообразия фирма "I-Logix", принимавшая участие в разработке указанного языка, при создании методологии проектирования объектно-ориентированных встроенных систем реального времени выбрала из этой части "коллекции" только диаграммы Харела в их первозданной нотации [99], но, однако, не решила и даже не поставила вопрос о сертификации поведения совокупности таких диаграмм.

Отметим также, что диаграммы Харела используются в [119] и при визуальной разработке программных компонент, описываемых конечными автоматами и предназначенных для различных целевых платформ. Только эти диаграммы применяются и для описания поведения объектов в [181].

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

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

Для этого класса систем предлагаемая технология позволяет строить математические модели, по которым, в частности, при любом типе двоичного кодирования состояний для программной реализации могут быть построены системы булевых формул, в то время как при других подходах такая задача даже не ставится.

Предлагаемая технология поддерживает проектирование и реализацию программного обеспечения для рассматриваемого класса систем и определяет состав и содержание выпускаемой документации, которая должна контролироваться Заказчиком.

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

Кроме перечисленных выше работ конечные автоматы, рассматриваемые в [182] как разновидность процессов, в настоящее время применяются при управлении автоматическими выключателями корабельных электроэнергетических систем [124], при создании непроцедурных языков программирования для автоматизированных систем управления технологическими процессами [125], при поиске подстрок [126], при описании поведения "объектов" [15, 127] программно реализуемых сложных систем [87, 128-147], в том числе "многониточных" контроллеров [30], а также при решении других задач, связанных с параллельными процессами (например, задачи о пяти философах, собравшихся за круглым столом и имеющих "проблемы" с вилками [148], о функционировании мячиков внутри окна [149], о синхронизации цепи стрелков [150]).

Графы переходов являются также основной формой описания управляющих последовательностных процессов при создании программного обеспечения систем обработки информации на основе методов структурного системного анализа и проектирования [40]. Они используются и для проводимого по методологии IDEF (Integration Definition for Function Modeling) документирования трансформаций объектов, происходящих в ходе выполнения технологического процесса [74].

Роль и место состояний ("состояния бытия"), конечных автоматов, графов переходов и конструкции switch при программировании игр описаны в [151].

В [189] предложено среди шаблонов, предназначенных для обеспечения повторного использования кода при объектно-ориентированном программировании, применять шаблон "State".

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

Из изложенного следует, что в настоящее время автоматный подход еще только начинает использоваться при программной реализации алгоритмов, и утверждение, высказанное в [153], о "смерти" теории автоматов является, по мнению автора, сильно преувеличенным. Более того, рецензент книги [8] определяет в [123] "конечные автоматы как инструмент борьбы с монополизмом фирм, разрабатывающих программное обеспечение", а в [50, 86] и вовсе приведен "гимн" применению автоматов в программировании.

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