Автоматное программирование
Материал из Википедии — свободной энциклопедии
Автоматное программирование — стиль программирования, основанный на применении конечных автоматов для описания поведения программ. В автоматном программировании графы переходов конечных автоматов используются при спецификации, проектировании, реализации, отладке, документировании и сопровождении программ.
Автоматное программирование было предложено А. А. Шалыто в 1991 г. Для поддержки автоматного программирования разработана Switch-технология. Под термином «автоматное программирование» понимается не только построение и реализация конечных автоматов, но и проектирование и реализация программ в целом, поведение которых описывается автоматами.
Содержание |
[править] Основные принципы
В последние годы большое внимание уделяется разработке технологий программирования для встроенных систем и систем реального времени, к которым предъявляются высокие требования по качеству программного обеспечения. Одним из наиболее известных подходов в этом направлении является синхронное программирование.
Параллельно с развитием в Европе синхронного программирования, в России создается подход к разработке программного обеспечения, названный «автоматное программирование».
Если в программировании в последнее время все шире используется понятие «событие», то рассматриваемый подход базируется на понятии «состояние». Добавляя к нему понятие «входное воздействие», которое может быть входной переменной или событием, вводится термин «автомат без выхода». Добавляя к последнему понятие «выходное воздействие», вводится термин «автомат» (конечный, детерминированный).
Поэтому область программирования, базирующаяся на понятии «автомат», была названа «автоматное программирование», а процесс создания таких программ — «автоматное проектирование программ».
Особенность рассматриваемого подхода состоит в том, что при его использовании автоматы, описывающие поведение программы, задаются графами переходов, для различения вершин в каждом из которых вводится понятие «кодирование состояний». При выборе «многозначного кодирования» с помощью одной переменной можно различать состояния автомата, число которых определяет значность выбранной переменной. Это позволило ввести в программирование такое понятие, как «наблюдаемость программ» (по значениям переменных, кодирующих состояния}.
В рамках рассматриваемого подхода базовым является понятие «состояние», а не «события» и «переменные», что позволяет лучше понять и специфицировать задачу и ее составные части.
При автоматном программировании отладка проводится путем протоколирования в терминах автоматов.
В силу того, что в рамках этого подхода от графа переходов к тексту программы предлагается переходить формально и изоморфно, то при применении языков программирования высокого уровня это проще всего выполнить с помощью конструкции switch языка Си либо ее аналогов в других языках программирования. Поэтому технология, основанная на автоматном программировании была названа «Switch-технология».
В настоящее время технология автоматного программирования разрабатывается в нескольких вариантах, различающихся как классом решаемых задач, так и типом вычислительных устройств, на которых осуществляется программирование.
На «Ядро автоматного программирования» получено свидетельство об официальной регистрации программы для ЭВМ № 2006 613249 от 14.09.2006 г., а на «Встраиваемый модуль автоматного программирования для среды разработки Eclipse» — свидетельство № 2006 613817 от 07.11.2006 г.
[править] Логическое управление
В 1996 г. Российский фонд фундаментальных исследований в рамках издательского проекта № 96-01-14066 поддержал издание монографии Шалыто А. А. SWITCH-технология. Алгоритмизация и программирование задач логического управления. СПб.: Наука, 1998. — 628 с., в которой предлагаемая технология была изложена применительно к системам логического управления. В таких системах события отсутствуют, входные и выходные воздействия являются двоичными переменными, а операционная система обеспечивает режим сканирования. Системы этого класса реализуются обычно на программируемых логических контроллерах, которые имеют относительно небольшой объем памяти, а их программирование выполняется на таких специфических языках, как, например, язык функциональных блоков. Разработаны методы формального написания программ для таких языков при задании спецификации для разрабатываемого проекта системой взаимосвязанных графов переходов.
[править] Программирование с явным выделением состояний
В дальнейшем автоматный подход был распространен на событийные системы, которые называются также «реактивными». В них указанные выше ограничения сняты. Как следует из названия этих систем, в них входными воздействиями могут быть события, в качестве выходных воздействий применяются произвольные процедуры, а в качестве операционных систем — любые операционные системы реального времени.
Для программирования событийных систем с применением автоматов был использован процедурный подход, и поэтому такое программирование было названо «программирование с явным выделением состояний».
При этом выходные воздействия могут быть «привязаны» к дугам, петлям или вершинам графов переходов (в общем случае применяются смешанные автоматы — автоматы Мура-Мили). Это позволяет в компактном виде представлять последовательности действий, которые являются реакциями на соответствующие входные воздействия.
Особенность предлагаемого подхода к программированию этого класса систем состоит в том, что в них повышается централизация логики за счет устранения ее в обработчиках событий и формирования системы взаимосвязанных автоматов, которые вызываются из обработчиков. Автоматы между собой могут взаимодействовать по вложенности, вызываемости и за счет обмена номерами состояний.
Другая важнейшая особенность описываемого подхода состоит в том, что при его применении автоматы используются триедино: при спецификации, при программировании (сохраняются в программном коде) и протоколировании. Последнее позволяет контролировать правильность функционирования системы автоматов. Протоколирование выполняется автоматически по построенной программе и может использоваться для отладки программ со сложным поведением.
[править] Объектно-ориентированное программирование с явным выделением состояний
Для решения широкого круга задач весьма эффективен подход, основанный на совместном использовании объектной и автоматной парадигм, который был назван «объектно-ориентированное программирование с явным выделением состояний». Особенности этого подхода состоят в следующем. Так же, как и в машине Тьюринга, явно выделяются управляющие (автоматные) состояния объекта, число которых значительно меньше числа остальных состояний, названных «вычислительными». В программирование введено понятие «пространство состояний», под которым понимается множество управляющих состояний объекта. Это обеспечивает существенно более понятное поведение по сравнению со случаем, когда такое пространство явно не выделяется. Предложен минимальный набор документов, позволяющий наглядно и строго описывать как структурные (статические), так и поведенческие (динамические) стороны программ.
Объектно-ориентированное программирование с явным выделением состояний включает следующие этапы:
- На основе анализа предметной области выделяются классы, и строится диаграмма классов.
- Для каждого класса разрабатывается словесное описание, по крайней мере, в форме перечня решаемых задач.
- Для каждого класса создается структурная схема, отражающая его интерфейс и структуру. При этом атрибуты и методы разделены на автоматные и остальные.
- При наличии в классе нескольких автоматов строится схема их взаимодействия.
- Для каждого автомата разрабатываются словесное описание, схема связей, граф переходов.
- Каждый класс реализуется соответствующим модулем программы. Его структура должна быть изоморфна структуре класса, а методы, соответствующие автоматам, реализованы по определенному шаблону.
- Для отладки системы и подтверждения правильности ее работы автоматически строятся протоколы, в которых функционирование объектов, содержащих автоматы, описывается в терминах состояний, переходов, событий, входных и выходных воздействий.
- Выпускается проектная документация, составной частью которой является программная документация.
Из опыта применения изложенной технологии можно сделать вывод, что применение автоматов проясняет поведение программы так же, как использование объектов делает прозрачной ее структуру. Наличие качественной проектной документации резко упрощает осуществление рефакторинга программы (изменение ее структуры при сохранении функциональности).
[править] Вычислительные алгоритмы
Автоматный подход используется в настоящее время и при реализации вычислительных алгоритмов. Так, в частности, показано, что произвольный итеративный алгоритм может быть реализован конструкцией, эквивалентной циклу do-while, телом которого является оператор switch (Switch-технология).
На основе автоматов на кафедре «Компьютерные технологии» СПбГУ ИТМО предложен новый подход к построению визуализаторов алгоритмов, используемых при обучении программированию и дискретной математике. Подход позволяет представить логику работы визуализаторов системой взаимосвязанных конечных автоматов. Система состоит из пар автоматов, каждая из которых содержит «прямой» и «обратный» автоматы, обеспечивающие пошаговое выполнение алгоритма вперед и назад соответственно.
[править] Инструментальные средства
Для поддержки автоматного программирования разработаны различные истументальные средства, такие как, например, UniMod. Это средство базируется на следующих понятиях: UML, Switch-технология, проектирование программы в целом, среда разработки Eclipse, язык программирования Java, открытый исходный код (http://unimod.sourceforge.net/). Позволяет говорить об одной из реализаций исполняемого UML(http://en.wikipedia.org/wiki/Executable_UML)
