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

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

(c) А. А. Шалыто

2.Нетрадиционные языки описания алгоритмов логического управления.

2.1. Язык SDL.

Идеи теории автоматов нашли свое отражение при разработке Международной комиссией по телефонии и телеграфии графического языка спецификации и описания алгоритмов - SDL-диаграммы (Specification and Description Language) [15], которые по внешнему виду напоминают схемы алгоритмов, но отличаются от последних введением в них состояний в явном виде. Недостатки SDL состоят в том, что они весьма громоздки и соответствуют только одному классу автоматов - автоматам Мили [11].

2.2. Р-схемы.

Еще одна модель, базирующаяся на использовании автоматов Мили, была предложена И.В. Вельбицким [16] и носит название Р-схемы (R-chart). Р-схема - нагруженный по дугам ориентированный граф, изображаемый с помощью вертикальных и горизонтальных линий и состоящий из структур, каждая из которых имеет только один вход и один выход. Схемы этого класса содержат по два типа (один из которых специальный) вершин и дуг и один тип соединительных линий. Р-схемы образуются за счет трех типов соединений - последовательного, параллельного и вложенного.

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

2.3. Сети Петри и графы операций.

Для описания сложных, в том числе параллельных процессов, в 1962 г. К. Петри [17] была предложена графовая модель, названная его именем, которая состоит из вершин двух типов - позиций и переходов, связанных между собой дугами, причем две вершины одного типа не могут быть соединены непосредственно. Для отражения динамики в сеть вводятся маркеры (метки), размещаемые в позициях. Если все позиции, связанные входящими дугами с некоторым переходом, маркированы, то переход срабатывает и маркеры переходят в позиции, связанные исходящими дугами с рассматриваемым переходом. Для целей управления С.А. Юдицким [18] было предложено применять только безопасные и живые сети Петри. В безопасной сети Петри в позициях не может быть более одного маркера, а в живых сетях Петри - имеется возможность срабатывания любого перехода. Назовем указанный класс сетей - управляющими сетями Петри, а сети Петри, в которых каждый переход имеет только одну входящую и одну исходящую дугу - автоматными сетями Петри.

В качестве модели для описания алгоритмов управления С.А. Юдицкий [18] предложил использовать графы операций, являющиеся управляющими сетями Петри, в которых позиции помечены значениями выходных переменных, а переходы - значениями входных переменных. Для описания иерархически построенных алгоритмов им было предложено применять системы вложенных графов операций.

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

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

2.4. Язык "Графсет".

Этот графический язык, разработанный в Центре космических исследований в Тулузе (Франция), применяется в настоящее время наряду с другими языками [19] такими фирмами как, например, "Телемеханик" (Франция), "Сименс" (Германия), "Ален Бредли" (США), "Тошиба" (Япония), "Омрон" (Япония). Этот язык алгоритмизации при наличии транслятора с него является и языком программирования.

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

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

Язык "Графсет" несмотря на наличие ряда недостатков, указанных выше, входит в состав программного обеспечения программируемых логических контроллеров, выпускаемых ведущими в области автоматизации фирмами мира. Так, например, фирма "Сименс" обеспечивает возможность написания программ для своих программируемых логических контроллеров с помощью языка STEP-5 (языки инструкций, лестничных и функциональных схем), а также языка S7-GRAF (язык "Графсет") [20,21].

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

При этом для разных моделей контроллеров одной той же фирмы [22] предлагается использовать различные языки (для "младших" моделей лестничные схемы, а для старших - "Графсет"), в то время как единый язык спецификаций алгоритмов для всех моделей не применяется.

Изложенное является вполне естественным, так как в рассматриваемой области до настоящего времени не установилась даже терминология. Так, например, под термином "Sequential Function Chart" (SFC) понимают как графы переходов, так и схемы алгоритмов (фирма "Опто") и "Графсет" (фирма "Омрон"), а в документации фирмы "Телемеханик" отмечено, что диаграммы "Графсет" известны, так же как SFC. Фирма "Сименс", как отмечено выше, применяет для тех же целей другой термин - "GRAF".

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

2.5. Проблемно - ориентированные языки, близкие к естественным.

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

Указанное достоинство этих языков влечет за собой ряд трудностей и недостатков, основные из которых следующие:

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

Из языков рассматриваемого класса наибольшее теоретическое обоснование получили следующие языки логического управления и их модификации - Форум [24], Условие [25], Управление [26], Ярус [27].

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

При использовании языка "Управление" в первичное лингвистическое описание (текст программы) вводятся по аналогии с разметкой схем алгоритмов для построения автомата [11] двоичные метки, трактуемые как состояния, и по помеченному описанию строится граф переходов автомата Мили, на базе которого, в частности, решаются задачи минимизации числа состояний и параллельной декомпозиции [26].

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

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

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

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

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

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

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

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

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

2.6. Алгоритмические языки программирования.

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