(c) А. А. Шалыто
Идеи теории автоматов нашли свое отражение при разработке Международной комиссией по телефонии и телеграфии графического языка спецификации и описания алгоритмов - SDL-диаграммы (Specification and Description Language) [15], которые по внешнему виду напоминают схемы алгоритмов, но отличаются от последних введением в них состояний в явном виде. Недостатки SDL состоят в том, что они весьма громоздки и соответствуют только одному классу автоматов - автоматам Мили [11].
Еще одна модель, базирующаяся на использовании автоматов Мили, была предложена И.В. Вельбицким [16] и носит название Р-схемы (R-chart). Р-схема - нагруженный по дугам ориентированный граф, изображаемый с помощью вертикальных и горизонтальных линий и состоящий из структур, каждая из которых имеет только один вход и один выход. Схемы этого класса содержат по два типа (один из которых специальный) вершин и дуг и один тип соединительных линий. Р-схемы образуются за счет трех типов соединений - последовательного, параллельного и вложенного.
Этот язык позволяет более компактно по сравнению с схемами алгоритмов отражать структуру алгоритмов, однако применение нестандартных обозначений и только одного типа автоматных моделей ограничивает использование P-схем.
Для описания сложных, в том числе параллельных процессов, в 1962 г. К. Петри [17] была предложена графовая модель, названная его именем, которая состоит из вершин двух типов - позиций и переходов, связанных между собой дугами, причем две вершины одного типа не могут быть соединены непосредственно. Для отражения динамики в сеть вводятся маркеры (метки), размещаемые в позициях. Если все позиции, связанные входящими дугами с некоторым переходом, маркированы, то переход срабатывает и маркеры переходят в позиции, связанные исходящими дугами с рассматриваемым переходом. Для целей управления С.А. Юдицким [18] было предложено применять только безопасные и живые сети Петри. В безопасной сети Петри в позициях не может быть более одного маркера, а в живых сетях Петри - имеется возможность срабатывания любого перехода. Назовем указанный класс сетей - управляющими сетями Петри, а сети Петри, в которых каждый переход имеет только одну входящую и одну исходящую дугу - автоматными сетями Петри.
В качестве модели для описания алгоритмов управления С.А. Юдицкий [18] предложил использовать графы операций, являющиеся управляющими сетями Петри, в которых позиции помечены значениями выходных переменных, а переходы - значениями входных переменных. Для описания иерархически построенных алгоритмов им было предложено применять системы вложенных графов операций.
Достоинство графов операций состоит в возможности описания в наглядной графической форме, в том числе и в виде одной компоненты, сложных алгоритмов управления, обладающих параллелизмом, а их ограничения и недостатки заключаются в том, что:
Этот графический язык, разработанный в Центре космических исследований в Тулузе (Франция), применяется в настоящее время наряду с другими языками [19] такими фирмами как, например, "Телемеханик" (Франция), "Сименс" (Германия), "Ален Бредли" (США), "Тошиба" (Япония), "Омрон" (Япония). Этот язык алгоритмизации при наличии транслятора с него является и языком программирования.
Язык "Графсет" отличается от языка графов операций в основном только формой изображения: квадраты вместо кружков для обозначения позиций и прямоугольники для записи значений выходных переменных, отсутствующие в графах операций. Поэтому все достоинства и недостатки этого языка сохраняются и в языке "Графсет". Созданы трансляторы с этого языка по крайней мере указанными выше фирмами для своих управляющих вычислительных устройств.
Одно из достоинств диаграмм "Графсет" состоит в стандартизации их изображения. При этом диаграммы преимущественно располагаются в направлении сверху вниз. Это одновременно является и их недостатком, так как для целостного (гештальтного) восприятия "картин" человеком более целесообразно их плоскостное изображение (как это имеет место в графах переходов), которое позволяет по этой причине отображать алгоритмы более компактно.
Язык "Графсет" несмотря на наличие ряда недостатков, указанных выше, входит в состав программного обеспечения программируемых логических контроллеров, выпускаемых ведущими в области автоматизации фирмами мира. Так, например, фирма "Сименс" обеспечивает возможность написания программ для своих программируемых логических контроллеров с помощью языка STEP-5 (языки инструкций, лестничных и функциональных схем), а также языка S7-GRAF (язык "Графсет") [20,21].
Однако опыт показывает, что при наличии для одного и того же программируемого логического контроллера нескольких языков программирования разработчики обычно используют более традиционные для систем логического управления языки, такие как лестничные и функциональные схемы. Это во многом связано с недостаточностью научно-методического обеспечения использования управляющих графов для спецификации алгоритмов. Более того, в документации многих фирм лестничные и функциональные схемы обычно предлагается строить эвристически, без предварительного описания алгоритмов с помощью управляющих графов, а эффективность применения таких графов по сравнению, например, с лестничными схемами демонстрируется в отдельных случаях (фирма "Омрон") только на примерах, без изложения метода формального перехода от управляющего графа к "схеме".
При этом для разных моделей контроллеров одной той же фирмы [22] предлагается использовать различные языки (для "младших" моделей лестничные схемы, а для старших - "Графсет"), в то время как единый язык спецификаций алгоритмов для всех моделей не применяется.
Изложенное является вполне естественным, так как в рассматриваемой области до настоящего времени не установилась даже терминология. Так, например, под термином "Sequential Function Chart" (SFC) понимают как графы переходов, так и схемы алгоритмов (фирма "Опто") и "Графсет" (фирма "Омрон"), а в документации фирмы "Телемеханик" отмечено, что диаграммы "Графсет" известны, так же как SFC. Фирма "Сименс", как отмечено выше, применяет для тех же целей другой термин - "GRAF".
Более того, термин SFC не отражает главную отличительную особенность рассматриваемого языка - возможность представления в одном графе параллельных по состояниям процессов, так как слово "sequential" переводится на русский язык как "последовательный", в то время как из теории автоматов известно, что для описания последовательных (последовательностных) процессов может использоваться граф переходов детерминированного автомата, который не позволяет отображать параллельные по состояниям процессы.
Для целей логического управления разработано несколько проблемно-ориентированных языков, предназначенных для формального лингвистического описания алгоритмов рассматриваемого класса. Эти языки называются [23] также первичными, так как, по мнению авторов указанной работы, они прежде всего ориентированы на Заказчика и обладают развитыми изобразительными средствами и конструкциями, употребляемыми при задании условий работы на естественном языке.
Указанное достоинство этих языков влечет за собой ряд трудностей и недостатков, основные из которых следующие:
Из языков рассматриваемого класса наибольшее теоретическое обоснование получили следующие языки логического управления и их модификации - Форум [24], Условие [25], Управление [26], Ярус [27].
Так, например, конструкции первичного языка "Условие" сначала транслируются в базовый язык операторных схем параллельных алгоритмов с памятью, являющийся развитием схем алгоритмов, а затем в автоматный язык - язык функций возбуждения и выходов.
При использовании языка "Управление" в первичное лингвистическое описание (текст программы) вводятся по аналогии с разметкой схем алгоритмов для построения автомата [11] двоичные метки, трактуемые как состояния, и по помеченному описанию строится граф переходов автомата Мили, на базе которого, в частности, решаются задачи минимизации числа состояний и параллельной декомпозиции [26].
Подход, наиболее близкий к предлагаемому в настоящей работе, был применен при разработке языка "Ярус". При этом О.П. Кузнецовым [28] для описания работы "пунктов" было предложено использовать автоматную модель, названную графом переключений, являющуюся графом переходов автомата Мили с умолчаниями неизменяющихся значений выходных переменных. Возможность сокращения числа вершин в этом графе по сравнению с классическими автоматными моделями привело к замене термина "состояние" на термин "ситуация", правда, с одновременным ухудшением читаемости графа в виду появления зависимости от "глубокой" предыстории.
В отличие от изложенного в предлагаемой в настоящей работе технологии первичным и формализованным является не лингвистическое, а автоматное описание последовательностных процессов с помощью графов переходов, тип, количество, способ кодирования и взаимосвязь которых в общем случае не фиксированы и определяются решаемой задачей. Понятность такого описания для Заказчика обеспечивается строгостью и простотой синтаксиса этого языка при описании статики, а самое главное, динамики процессов, а также обязательной разработкой схемы связей "управляющий автомат - объект управления", которая определяет семантику каждой внешней переменной, используемой в графах переходов. Применение графов переходов без флагов и умолчаний [29] позволяет непосредственно при описании процесса обеспечивать его корректность и использовать в дальнейшем в качестве теста для проверки формально построенной программы. За счет исключения флагов и умолчаний упрощается внесение изменений и устраняется зависимость от "глубокой" предыстории (в дальнейшем предыстории - будущее зависит от настоящего, но не зависит от прошлого).
"Понятность" алгоритмов и программ, построенных по ним, еще более повышается, если устранить также и зависимость значений выходных переменных, от значений входных переменных, что достигается при использовании графов переходов автомата Мура, в котором значения выходных переменных зависят только от номера состояния, в котором автомат находится.
Граф переходов автомата этого типа либо строится непосредственно, либо получается в результате преобразования графа переходов автомата другого типа. Так, например, по графу переходов автомата Мили может быть построен граф переходов автомата без выходного преобразователя, являющегося графом достижимых маркировок исходного графа, который, в свою очередь, весьма просто преобразуется в граф переходов автомата Мура.
При этом можно считать, что каждая вершина в графе переходов соответствует одному состоянию автомата используемого типа, для которого граф строится, и одному состоянию оперативной памяти вычислителя, программно реализующего этот граф.
Однако, так как поведение автомата наиболее наглядно описывается не графом переходов, а соответствующим ему графом достижимых маркировок [30], то "реальное" число состояний автомата совпадает с их числом в этом графе или в эквивалентном ему графе переходов "классического" (без флагов и умолчаний) автомата Мура.
Таким образом, если граф переходов в общем случае можно рассматривать как "закодированное" (число вершин в графе переходов может быть существенно меньше, чем число "реальных" состояний автомата) и поэтому компактное описание поведения автомата, то наиболее "понятным" является граф переходов "классического" автомата Мура при многозначном кодировании его вершин, который одновременно является и графом его достижимых маркировок. Именно граф переходов этого типа и предлагается применять в качестве основного языка спецификаций для задач логического управления.
В разрабатываемой технологии переход к лингвистическому описанию выполняется не при алгоритмизации, а только на этапе программирования и только при использовании алгоритмических языков. В этом случае в тексте программы должны быть по возможности сохранены все структурные особенности и свойства выбранной автоматной модели, что обеспечивается только при однозначном, а самое главное, изоморфном переходе от графа переходов, согласованного с Заказчиком, к программе. При этом программирование выполняется не по "мотивам" алгоритма, а по принципу "один в один".
При применении предлагаемой технологии удается обеспечить соответствие между текстом программы и порядком ее выполнения и реализовать процедуру пошаговой детализации, как этого требует структурное проектирование (программирование) [31], а также использовать понятия "объект" и "класс", как это принято в объектно-ориентированном проектировании (программировании) [32].
Из изложенного выше следует, что алгоритмические языки как высокого, а тем более низкого уровня, целесообразно применять в задачах логического управления только на этапе изоморфного перехода от автоматного описания к тексту программ, так как в противном случае возникают многие из проблем, перечисленных выше, применительно к использованию проблемно-ориентированных языков в качестве первичного описания.