Программирование на основе автоматов (подход Шалитоса) - Википедия - Automata-based programming (Shalytos approach)

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

Программирование на основе автоматов это технология программирования (Непейвода 2005 г. ). Его определяющая характеристика - использование конечные автоматы для описания поведения программы. Переход графики конечных автоматов используются на всех этапах программного обеспечения разработка (спецификация, реализация, отладка и документация). Технология программирования на основе автоматов была представлена Анатолий Шалыто в 1991 г. (Шалыто 1991 ). Switch-технология (Шалыто 1998 г. ) был разработан для поддержки программирования на основе автоматов. Автоматное программирование считается методологией разработки программ общего назначения, а не просто еще одной реализацией конечного автомата.

Программирование на основе автоматов

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

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

Основные особенности

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

Одновременно с развитием синхронного программирования в Европа, подход к разработке программного обеспечения для важнейших систем, называемый автоматное программирование или же государственное программирование (Шалыто 1998 г. ) создавался в Россия.

Период, термин мероприятие все больше и больше используется в программировании; в последнее время он стал одним из наиболее часто используемых терминов при разработке программного обеспечения. В отличие от него предлагаемый подход основан на термине государственный (Государственная архитектура). После введения термина действие ввода, который может обозначать входную переменную или событие, термин автомат без выходов может быть внесен. После добавления термина выходное действие, можно использовать термин «автомат». Это конечный детерминированный автомат.

Поэтому разновидность программирования, основанная на этом термине, получила название «автоматное программирование». Таким образом, процесс создания программного обеспечения можно назвать «автоматическим проектированием программного обеспечения» (Шалыто 2000 ).

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

Использование понятия «состояние» в отличие от понятий «события» и «переменные» позволяет более четко понять и определить задачу и ее части (подзадачи).

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

Для этого подхода существует формальный и изоморфный метод преобразования графа переходов в исходный код программы. Так что при использовании языки программирования высокого уровня, самый простой способ - использовать конструкцию, похожую на выключатель построение Язык программирования C. Поэтому первая реализация автоматного программирования получила название «Switch-Technology». Дополнительную информацию о программировании на основе автоматов можно найти в Статья «Свитч-технология».

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

Российское регистрационное свидетельство выдано на Ядро программирования на основе автоматов и для Подключаемый модуль для программирования на основе автоматов для Eclipse IDE.

Логический контроль

В 1996 г. Российский фонд фундаментальных исследований.[1] в рамках издательского проекта № 96-01-14066 поддержал издание книги (Шалыто 1998 г. ), в котором описана предлагаемая технология применительно к системам логического управления.

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

Государственное программирование

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

Автоматная реализация событийных систем была произведена с помощью процедурный подход разработке программного обеспечения (Шалыто 2001а ) (Шалыто 2001б )Отсюда и название «программирование на основе состояний».

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

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

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

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

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

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

Композитный подход, основанный как на парадигмах объектно-ориентированного, так и на автоматном программировании (Шалыто 2004 г. ), (Шалыто 2005 ), может оказаться весьма полезным для решения задач из очень широкого спектра. Этот подход получил название «объектно-ориентированное программирование на основе состояний».

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

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

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

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

Вычислительные алгоритмы

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

Автоматный подход очень эффективен для реализации некоторых алгоритмов дискретной математики, например, алгоритма парсинга дерева (Корнеев 2004 ).

Предложен новый государственный подход к созданию визуализаторов алгоритмов. Такое программное обеспечение для визуализации широко используется в отделе компьютерных технологий Санкт-Петербургский государственный университет информационных технологий, механики и оптики для студентов, преподающих программирование и дискретную математику (Казаков 2005 ) (Корнеев 2005 ). Такой подход позволяет представить логику визуализатора как систему взаимодействующих конечных автоматов. Эта система состоит из пар автоматов; каждая из этих пар содержит «прямой» и «обратный» автоматы, которые обеспечивают пошаговое выполнение алгоритмов вперед и назад соответственно.

Приборы

Для поддержки программирования автоматов разработаны различные программные инструменты. Один из этих инструментов - UniMod (Гуров 2004 ) (Гуров 2005 ) (UniMod ). Этот инструмент основан на следующих концепциях: UML, Switch-технология, Eclipse IDE, Язык программирования Java, открытый исходный код (http://unimod.sourceforge.net/ ). Все это позволяет говорить о UniMod с момента реализации исполняемый UML.

Некоторые примеры использования инструмента UniMod показаны в (Примеры UniMod ).

Сборник статей по автоматному программированию

Сборник статей по автоматному программированию опубликован в Университет ИТМО. Бюллетень (ifmo.ru 2008 г. ) содержит 28 статей по различным проблемам автоматного программирования.

Первая книга о программировании на основе автоматов

В 2009 году в Санкт-Петербурге, Россия, была издана первая книга по автоматному программированию (Поликарпова2009 ).

Рекомендации

  1. ^ «Архивная копия». Архивировано из оригинал на 2008-03-14. Получено 2008-03-17.CS1 maint: заархивированная копия как заголовок (связь)

Смотрите также