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

Ваганов С.А. Автоматное программирование во "Флоре"

Объекты автоматного программирования

К объектам автоматного программирования относятся следующие.

Объект	Описание
AState	Абстракное состояние. Содержит свойства и методы состояния
State	Состояние
ADiagram	Абстрактная диаграмма. Содержит свойства и методы диаграммы состояний.
StateMachine	Конечный автомат
Activity	Деятельность
Factory	Фабрика
CombinationalSceme	Комбинационная схема
CombinationalElement	Комбинационный элемент

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

Автоматное программирование во Флоре

Содержание

1. Введение
2. Принципы автоматного программирования
3. Технология Флоры и автоматное программирование
   1. Вложенные автоматы
   2. Выделение логики программы
   3. Графическое представление логики программы
   4. Группы состояний
   5. Инициализация
   6. Недетерминированные автоматы
4. Объекты автоматного программирования
   1. Графическое представление автоматов
   2. Входы автомата
   3. Выходы автомата
   4. Граф переходов объекта, реализующего автомат
   5. Функционирование конечного автомата
   6. Функционирование деятельности
   7. Функционирование фабрики и комбинационной схемы
5. Заключение
6. Ссылки

Введение

Разработка и внедрение объектов автоматного программирования - это качественно новая ступень в развитии технологии Флоры. Для того чтобы это подчеркнуть, Флора, содержащая наряду с аппаратом шаблонов объекты автоматного программирования и инструменты для работы с ними, получила рабочее название Флора 2.

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

Принципы автоматного программирования

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

Автомат - это "черный ящик", содержащий внутри себя некоторую логику (рис. 1). Вне автомата его логика никому не интересна, а интерес представляют его входы и выходы. Внешняя среда воздействует на входы, а автомат, обрабатывая входы, предоставляет выходы. Входы автомата (входные воздействия) - это все то, что он получает из внешней среды. Выходы - это все то, что он возвращает внешней среде. Сокрытие логики внутри автомата - это один из принципов автоматного программирования.

Рис. 1 Автомат

Функциональность каждой отдельной подсистемы может быть описана автоматом. Функциональность всей системы - другим автоматом, находящемся на более высоком уровне абстракции (рис. 2). Для системы не интересно, как решают свои задачи подсистемы. Системе необходимо знать, как получить необходимые результаты от подсистемы. В ООП этот принцип называют инкапсуляцией - сокрытием данных и алгоритмов более низкого уровня от данных и алгоритмов более высокого уровня.

Рис. 2 Взаимодействие автоматов на различных уровнях абстракции

Часто использование именно конечных автоматов в программировании называют автоматным программированием. Что представляет собой конечный автомат? Автомат может запоминать свое состояние. Такой автомат называется автоматом с памятью. Выход автомата без памяти не зависит от предыдущих значений входов, а зависит только от текущих значений входов. Выход автомата с памятью зависит от предыдущих воздействий. Это принципиальное отличие автомата без памяти от автомата с памятью.

Основное понятие автомата с памятью - это его состояние. Если значение выходов автомата без памяти зависит только от входов, то значение выходов автомата с памятью зависит не только от входов, но и от состояния автомата. Состояний у автомата может быть множество. Автомат с памятью, имеющий конечное число состояний, называется конечным автоматом.

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

Конечный автомат хранит состояние одного объекта. Но автомат может хранить состояния нескольких объектов. Автомат с памятью, который может хранить состояния нескольких объектов, во Флоре называется фабрикой. Фабрика хранит состояния переданных фабрике объектов.

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

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

Для реализации логики программы необходимо учитывать значение всех управляющих переменных (флагов). Пусть количество этих переменных N, а значений каждая из них имеет всего два: истина или ложь. Тогда необходимо учесть 2^N различных ситуаций, что с увеличением N становится все сложнее.

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

Кроме того, в описании поведения системы с помощью состояний нет ничего противоестественного. Каждый объект реального мира можно считать автоматом: объект извне получает входные воздействия и реагирует автоматически с помощью выходных воздействий. Познание объектов обычно заключается в воздействии на него и наблюдении за его действиями. Но цель такого познания заключается в выявлении состояний объекта и переходов из состояния в состояние. Объекты, принципы функционирования которых мы понимаем, можно считать конечными автоматами, т.к. все состояния и переходы уже выявлены. Если у объекта обнаруживается неизвестное состояние, то возникает ощущение неполноты знания, а то и вовсе полного незнания об объекте.

В SWITCH-технологии, которая вдохновила разработчиков Флоры на создание объектов автоматного программирования, предлагается использовать указанные принципы в разработке систем управления, но и, что главное, сделать автомат из"черного ящика" "белым ящиком". В этой технологии рассматривается, как сделать "белым ящиком" конечный автомат. Разработчики Флоры, придерживаясь той же технологии, пошли дальше: они не только реализовали объект конечный автомат с автоматическим созданием исходного текста, но и создали другие объекты, реализующие автоматы нескольких типов.

Во Флоре реализуются автоматы с конечным числом состояний (StateMachine, Factory, Activity) и без состояний (CombinationalSceme), хранящие текущее состояние (StateMachine, Factory), хранящие текущие состояния нескольких объектов (Factory) и не хранящие текущего состояния (Activity, CombinationalSceme), с магазинной памятью (StateMachine), детерминированные или недетерминированные (StateMachine, Factory, Activity).

Технология Флоры и автоматное программирование

Вложенные автоматы

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

Рис. 3 Реализация иерархичности и вложенности во Флоре

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

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

Во Флоре могут быть использованы два типа вложенных автоматов: с историей и без истории. Вложенный автомат с историей во все время работы главного автомата "помнит" свое состояние. Вложенный автомат без истории "помнит" свое состояние, пока главный автомат находится в состоянии (содержащем этот вложенный автомат), и "забывает" свое состояние, как только главный автомат переходит в другое состояние.

Выделение логики программы

Поведение стандартных объектов Флоры определяется установкой значений свойств. Но при создании систем требуется выделить группу объектов и задать собранной системе функциональность. Выделение в отдельную группу объектов системы происходит, если поместить эти объекты в ветвь дерева. С заданием функциональности дело обстоит сложнее. Основные свойства и методы системы выносились в контакты каталога, а реализация методов оказывалась разбросана по всей ветви в функциях, задачах, рефлексах. Получается, что логика системы терялась во множестве функций. При разработке программы часто приходиться возвращаться с более высокого уровня абстракции на более низкий и наоборот. При таком разбросе логики по функциям и задачам требуется намного больше усилий от программиста при восстановлении в памяти логики необходимого уровня абстракции, чем, если бы эта логика была сконцентрирована в одном месте на каждом уровне программы. Т.е., если мы хотим создавать программы, легко поддающиеся модификации, то необходимо иметь быстрый доступ к просмотру и редактированию логики программы.

Графическое представление логики программы

Насколько быстро мы можем осознать логику работы системы по тексту программы? Текст программы имеет линейную природу. Когда мы читаем текст, мы имеем дело с операциями, блоками, функциями, следующими одна за другой. Восприятие текста последовательно во времени. Чтобы понять, как работает программа, приходится просмотреть весь текст, который содержит намного больше того, что необходимо. Чтобы избежать линейности текста, изобретаются правила расстановки скобок, пробелов и т.п. в тексте программы. Это предназначено для того, чтобы структурировать текст, придать ему обозримость, легкость для восприятия при чтении.

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

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

Группы состояний

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

Инициализация

Есть еще кое-что в теории конечных автоматов, что идеально соответствует технологии Флоры. Это задание начального состояния. По SWITCH-технологии, чтобы запустить автомат, необходимо его вызвать со специальным событием е0. Во Флоре каждому объекту присуще понятие инициализации. Поэтому необходимость задания начального состояния автомата для Флоры вовсе не является чем-то особенным, просто при старте автомата на этапе инициализации будет установлено его начальное состояние. Инициализация приводит к тому же, что и событие e0 в SWITCH-технологии - устанавливает автомат в начальное событие, которое включает не только установку переменной состояния, но и выполнение действий на входе в состояние.

Недетерминированные автоматы

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

Объекты автоматного программирования

Чтобы логика создаваемой системы могла описываться автоматом, во Флору были добавлены специальные объекты - объекты автоматного программирования. Четыре объекта Флоры являются объектами, обладающими возможностью создания логики работы, конечно, логики не своей работы, а работы произвольной системы. Графически описать логику работы любой системы позволяют следующие объекты Флоры: StateMachine (конечный автомат), Activity (деятельность), Factory (фабрика) и CombinationalSceme (комбинационная схема). Эти объекты реализуют различные типы автоматов.

При создании приложений во Флоре с использованием объектов автоматного программирования предлагается:

1. для реализации условий использовать комбинационные схемы;
2. для реализации функций использовать деятельности;
3. для реализации функциональности каждой создаваемой подсистемы использовать конечный автомат или фабрику.
4. конечный автомат использовать для систем, требующих сохранение только своего состояния;
5. фабрику использовать для систем, осуществляющих управление несколькими объектами.

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

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

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

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

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

CombinationalSceme - объект, реализующий автомат без памяти (не помнит текущее состояние, но имеет конечное число узлов-состояний).

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

Activity - объект, реализующий автомат без памяти (имеет конечное число состояний, одно из них начальное и одно или несколько конечных, но текущего состояние не имеет).

Factory - объект, реализующий фабрика (имеет конечное число состояний, одно из них начальное и несколько текущих, соответствующих каждому управляемому объекту). Указанные объекты связаны отношениями наследования. Отношениями наследования для перечисленных объектов показаны на рис. 4

Рис. 4 Схема отношений наследования объектов автоматного программирования

Схема позволяет увидеть общее для этих объектов. Например, видно, что объект CombinationalSceme заметно отличается от трех остальных. Объекты StateMachine, Activity и Factory имеют общего предка ADiagram. Объект ADiagram является абстрактным объектом (не может быть добавлен в дерево Флоры), Объекты StateMachine, Activity и Factory наследуют у него общие типы входов и выходов.

Объект Activity является наследником AProgFunc, поэтому деятельность вызывается как функция, может принимать параметры и возвращать результат.

Все четыре объекта наследуют свойства и методы каталога (Dir). В объект CombinationalSceme (как в каталог) добавляются его узлы - комбинационные элементы (CombinationalElement). В объекты StateMachine, Activity и Factory (как в каталог) добавляются состояния (State).

Все четыре объекта наследуют свойства и методы программы (Program) - для всех объектов генерируется текст программы.

Объекты StateMachine, Activity и Factory могут работать на собственном стеке (наследники MainProgram).

После анализа отношений наследования можно дать следующее описание рассматриваемых объектов.

CombinationalSceme - объект-программа, работающая на собственном стеке, и объект- каталог, содержащий узлы схемы - объекты CombinationalElement (или CombinationalSceme). StateMachine - объект-программа, работающая на своем стеке или стеке вызывающей задачи, и объект-каталог, содержащий состояния - объекты State.

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

Factory - объект, расширяющий возможности объекта StateMachine.

Графическое представление автоматов

Объекты автоматного программирования (конечный автомат, фабрика, деятельность и комбинационная схема) могут быть представлены в виде графов. А именно, в виде ориентированных мультиграфов.

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

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

Фабрика может быть представлена в виде в виде двухслойного ориентированного мультиграфа. Один граф - граф переходов объектов. Его узлы - состояния объектов, ребра - переходы-конвейеры. Переходами-конвейерами называют перемещение объекта из узла в узел фабрики или, что равносильно, изменение состояния объекта, управляемого фабрикой. Название перехода-конвейера выбрано из соображения, что работу фабрики можно представить как работу конвейера: поступающие объекты обрабатываются в заданных узлах. Другой граф фабрики - граф переходов событий. Его узлы - узлы анализа событий, ребра - переходы.

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

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

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

Указанные графы должны быть односвязными, что является необходимым условием достижимости вершин.

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

Более подробно определить объекты автоматного программирования можно по типу входов и выходов. Далее рассмотрены допустимые во Флоре типы входов и выходов автоматов.

Входы автомата

Входы автомата - входные воздействия - это все то, что автомат получает из внешней среды.

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

Рис. 5 Классификация событий по назначению

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

Рис. 6 Классификация входов-событий

Входами, опрашиваемыми во время работы автомата, могут быть входы- переменные и входы с исходным текстом (рис. 7).

Рис. 7 Классификация опрашиваемых входов

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

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

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

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

События конечного автомата

События, обрабатываемые конечным автоматом и фабрикой во Флоре, представлены на рис. 8.

Рис. 8 Классификация событий конечного автомата

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

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

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

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

Классический вызов автомата реализуется с помощью вызова специальной функции анализа А(int e), содержащейся в сгенерированном тексте автомата. При передаче события с помощью этой функции необходим указатель на автомат и идентификатор события. Для того, чтобы вместо номера события использовать его имя, необходимо перед вызовом функции А(int e) использовать директиву #include:

#include указатель_на_автомат
...
Указатель_на_автомат.A(имя_автомата::имя_события);

Конечный автомат и фабрика во Флоре позволяют использовать события с параметрами. Событие с параметрами реализовано с помощью метода-функции, исходный текст которой генерируется при трансляции графа переходов автомата в текст. Цель сгенерированной метод- функции - скопировать в контакты автомата значения переданных параметров, а затем запустить функцию анализа А(int e). Копирование произойдет, когда событие будет извлечено из очереди для обработки. Таким образом, происходит сохранение в очереди события вместе с параметрами. Передача события с параметрами происходит путем вызова этой метод-функции:

Указатель_на_автомат.Имя_события(Параметр1, Параметр2);

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

События с периодическим опросом генерируются с помощью функции анализа A(), которая наряду с функцией A(int e) содержится в сгенерированном тексте автомата. Функцию A() можно вызвать извне аналогично функции A(int e). Однако предназначение этой функции совсем другое. Функция A() осуществляет опрос списка событий автомата. После установки флага "периодический опрос событий" функция A() вызывается с указанным периодом. Если опрос какого-нибудь из этих событий вернул значение "истина", то будет вызвана функция A(int e) с номером соответствующего события.

Тело функции A(int e) создается из графа переходов и с точки зрения программиста представляет собой switch оператор по состоянию плюс ряд дополнительных действий, обеспечивающие рекурсивность автомата. Функция A(int e) - основная часть текста автомата. Кроме функций анализа A() и A(int e) текст автомата содержит исходные тексты входов и выходов. Все входы и выходы автомата для удобства реализуются в виде функций. Входы в виде функций, возвращающих целое значение, выходы в виде функций, не возвращающих значение. Приведение всех типов входов и выходов к однотипным функциям обеспечивает одинаковое обращение к ним из функции анализа A(int e).

События фабрики

События фабрики в отличие от событий конечного автомата делятся на два типа (рис. 9). События могут относиться к фабрике в целом. И события могут относиться к конкретному объекту или к конкретному состоянию.

Рис. 9 Классификация событий фабрики

События, относящиеся к фабрике в целом, представлены теми же типами, что и в конечном автомате и передаются аналогично.

События, относящиеся к конкретным объектам или конкретным состояниям, передаются с помощью методов фабрики Awake().

Событие, предназначенное объекту, находящемуся в фабрике, передается фабрике с указанием объекта, к которому относится.

Указатель_на_фабрику.Awake(номер_события, номер_состояния);

Событие, предназначенное обработке в конкретном состоянии, передается фабрике с указанием объекта, к которому относится.

Указатель_на_фабрику.Awake(номер_события, указатель_на_объект);

Событие, относящееся к конкретному объекту, обрабатывается по схеме характерной для конечного автомата. Т.е. происходит обработка события в текущем состоянии этого объекта. События, относящиеся к фабрике в целом, обрабатываются по совсем иной схеме. Оно проходит по всем узлам графа переходов событий. Граф переходов событий - это особенность фабрики во Флоре. Граф переходов событий накладывается на граф переходов для объектов. Граф переходов событий и граф переходов объектов образуют двухслойную структуру фабрики. Граф переходов событий не обязан соответствовать графу переходов объектов (рис. 10).

Рис. 10 Граф переходов конечного автомата (a) и графы переходов объектов и событий фабрики (б)

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

Во Флоре фабрика является потомком конечного автомата. У конечного автомата узлы - состояния объекта. У фабрики эти же узлы могут обозначать состояние любого из нескольких объектов. Для деятельности узлы - это не состояния. Это узлы проверки условий и выбора дальнейшего пути по графу.

Выходы автомата

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

Рис. 11 Классификация выходов

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

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

Выходы комбинационной схемы - это переменные, назовем их выходами-переменными. Типы выходов-действий для конечного автомата и фабрики делятся на специальные выходы для работы с таймером и другие выходы, действия для которых задаются в виде исходного текста (рис. 12).

Рис. 12 Классификация выходов-действий конечного автомата и фабрики

Специальные выходы для работы с таймером в своей основе просто выходы-действия, только они генерируются редактором.

Выходы для работы с таймером - это сброс и запуск таймера. Выходы с исходным текстом - это выражения и функции.

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

Так как деятельность не предназначена для использования таймера, выходы деятельности - это только выходы-функции.

Граф переходов объекта, реализующего автомат

Каждый из четырех объектов автоматного программирования может находиться в одном из четырех состояний: "Не готов", "Готов", "Работает" (рис. 13).

Рис. 13 Граф переходов объекта, реализующего автомат

Состояние "Не готов" - начальное состояние, когда статус объекта меньше "Запущен".

Объект находиться в состоянии "Готов", когда его статус "Запущен"> и он находиться в состоянии ожидания.

Объект находиться в состоянии "Работает", когда его статус "Запущен" и он выполняет анализ входов и генерацию выходов.

Для перехода из состояния "Не готов" в состояние "Готов" требуется, чтобы тело объекта было собрано и оттранслировано, и статус объекта был переустановлен до "Запущен".

Для перехода из состояния "Готов" в состояние "Работает" объект должен быть вызван.

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

Для перехода из состояния "Работает" в состояние "Готов" конечный автомат или фабрика должны завершить анализ события, деятельность должна придти в конечное состояние (состояние без переходов).

В состояние "Не готов" объект может перейти при ошибке или при понижении статуса объекта.

Функционирование конечного автомата

В состояние "Работает" конечный автомат может переходить по двум причинам: при получении события или периодически.

При получении события объект StateMachine произведет его обработку и вернется в состояние "Готов".

Асинхронный автомат вызывается периодически. С указанным периодом проверяется очередь событий, а при поднятом флаге "Периодический опрос событий" происходит опрос входов-событий. Если булева функция опрашиваемого события вернет результат "Истина", то автомат сам себе передаст номер случившегося события. После опроса входов-событий автомат перейдет в состояние "Готов".

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

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

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

Рис. 14 Работа конечного автомата по обработке события

Граф переходов, показывающий схему анализа переходов конечного автомата. Жирным шрифтом выделены комментарии к переходам. У1, У2 - условия переходов, причем У1 по порядку первое, поэтому и проверяться будет первым.

Этапы жизни события конечного автомата

Событие проходит следующие этапы: генерацию, передачу, запись в очередь, извлечение из очереди, анализ, удаление (рис. 15).

Рис. 15 Этапы жизни события конечного автомата

Генерация событий производится внешними объектами или посредством опроса событий синхронного автомата.

Передача события автомату производится внешним объектом или самим автоматом (опрос событий в асинхронном автомате).

Запись номера события в очередь (и данных для события с параметрами) производиться сразу после получения события.

Тип события влияет только на способ его генерации, передачи и записи в очередь и никак не влияет на его дальнейшую обработку.

Извлечение события из очереди производится соответственно в строгой очередности. Если событие с параметрами, то перед его анализом значения параметров из очереди извлекаются и записываются в переменные-контакты. Асинхронный автомат проверяет очередь событий с заданным периодом. Из очереди будет извлечено событие (если конечно оно там есть) при вызове функции анализа A(). Синхронный автомат по очереди извлечет и обработает события всех ждущих задач.

Пока событие не будет проанализировано автоматом (проверка условий переходов, действия на выходе из состояния, на переходе, на входе в состояние) следующее событие не будет извлечено.

Очередь событий. Синхронный и асинхронный конечные автоматы

Анализ входов-переменных автомата происходит при проверке условий переходов, поэтому не требует специальных средств для обработки в отличие от входов-событий. Необходимость в использовании специальных средств работы с событиями возникает по следующим причинам. События могут поступать от нескольких задач. На обработку события затрачивается некоторое время. Событие может придти автомату во время его работы. Как поступить с этим событием? Естественное решение - поместить его в очередь событий.

Обработку событий, поступающих в очередь, конечный автомат во Флоре может осуществлять двумя способами: синхронно или асинхронно.

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

Рис. 16 Схема обработки событий в синхронном конечном автомате

При асинхронной обработке событий конечный автомат работает под управлением собственной задачи, и вызывающие задачи, сообщив о событии, продолжают работу (рис. 17).

Рис. 17 Схема обработки событий в асинхронном автомате

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

Работа на стеке вызывающей задачи позволяет решать задачу синхронизации, а работа на собственном стеке позволяет работать самостоятельно, независимо от каких-либо других задач Флоры. Оба решения необходимы Флоре. Возможность работать самостоятельно может быть характерна создаваемой системе. Система может, получив событие, разбираться с ним по собственному усмотрению и не задерживать работу других. Но часто бывает необходимо и обратное. Автомат может синхронизировать работу других систем. Конечный автомат обеспечивает простую и надежную синхронизацию между параллельно работающими системами. Дело в том, что объекты Флоры в принципе функционируют параллельно. Конечно, параллельное программирование предлагает несколько способов синхронизации, но вряд ли предполагается такое огромное количество параллельных процессов, которыми необходимо управлять. Параллельное и независимое функционирование объектов приложения Флоры большой плюс, но для ряда задач требуется управление этими процессами. Стандартные методы синхронизации (семафоры, например) служат для выполнения элементарных действий, в отличие от них конечный автомат кроме синхронизации задач предоставляет очередь и алгоритм обработки событий.

Функционирование деятельности

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

Рис. 18 Алгоритм работы деятельности

При вызове деятельность принимает начальное состояние.

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

Если из состояния нет ни одного перехода, то состояние считается конечным, и деятельность завершает работу.

Функционирование фабрики и комбинационной схемы

В состояние "Работает" фабрика переходит, если было передано событие или был передан объект. После обработки события, и выполнения операций над объектом, фабрика возвращается в состояние "Готов".

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

Фабрика может работать с объектами заданных типов. Тип объекта - это идентификатор. Список типов обрабатываемых объектов задается фабрике программистом.

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

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

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

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

Заключение

1. Технология автоматного программирования идеально вписывается в технологию Флоры.

   • Технология Флоры позволяет добавить новые объекты, реализующие конечные автоматы. Работа с конечными автоматами может быть автоматизирована с помощью специальных редакторов.

   • Объекты Флоры взаимодействуют посредством событий и связей. Взаимодействие уже не только обеспечено, но и может быть качественно улучшено.

   • При создании новых объектов статическая сторона нового объекта задается сборкой ветви дерева из элементарных объектов. С помощью объектов автоматного программирования может быть задана динамическая часть.

   • Древовидная структура приложений реализует вложенность и иерархичность. Расположение автоматов будет реально вложенным.

2. Технология автоматного программирования решает ряд задач во Флоре.

   • Объекты, реализующие автомат в виде "белого ящика", дают быстрый доступ к логике функционирования системы.

   • Использование объектов, реализующих автомат, позволяет сконцентрироваться скорее на проектировании системы, нежели на программировании.

   • Использование синхронного конечного автомата решает задачу синхронизации.

3. Автоматы во Флоре реализуются с помощью объектов автоматного программирования: комбинационной схемы, конечного автомата, фабрики и деятельности.

   Комбинационная схема

   - это объект, реализующий автомат, входы и выходы которого являются переменными. Работа комбинационной схемы заключается в анализе значений входов и соответствующей установке значений выходов. Комбинационная схема приводится в действие посредством событий-стробов, т.е. при изменении переменных, на которые ссылаются выбранные входы.

   Деятельность

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

   Конечный автомат

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

   Фабрика

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

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

5. Конечный автомат, деятельность и фабрика во Флоре транслируются из графа переходов в исходный текст по SWITCH-технологии.

6. Объекты автоматного программирования имеют широкие возможности по созданию автоматов. При программировании во Флоре с помощью объектов автоматного программирования могут быть использованы следующие возможности.

   • Автоматы с памятью (конечный автомат и фабрика) и автоматы без памяти (деятельность и комбинационная схема)

   • Детерминированные и недетерминированные автоматы на основе деятельности, конечного автомата или фабрики с помощью опрашиваемых входов с исходным текстом.

   • Конечный автомат во Флоре - автомат с магазинной памятью. Он обладает возможностью запоминать и восстанавливать свое состояние.

   • Вложенные автоматы с историей и без истории.

   • Группы состояний.

   • Синхронные автоматы (деятельность, конечный автомат и фабрика) позволяют синхронизировать работу объектов Флоры, функционирующих как параллельные процессы

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

   • Встроенные функции для работы с таймером в конечном автомате и фабрике.

   • Асинхронные автоматы (конечный автомат и фабрика) могут генерировать события с помощью периодического опроса булевых входов с исходным текстом.

   • Конечный автомат, фабрика и комбинационная схема могут стробироваться на состояния других автоматов.

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

   • Фабрика реализует конечный автомат, который хранит несколько состояний - состояний объектов.

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

   ---

Ссылки

    1. Шалыто А.А. SWITCH-технология. Алгоритмизация и программирование
       задач логического управления. СПб.: Наука, 1998.
    2. Туккель Н.И., Шалыто А.А., Ваганов С.А. Повышение централизации
       управления при программировании "реактивных" систем
       /Труды международной научно-методической конференции
       "Телематика'2001". СПб.: СПбГИТМО (ТУ), 2001. С.176-177.
    3. http://www.softcraft.ru/design/cold/cold.shtml