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

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

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

Автоматное программирование было предложено А. А. Шалыто в 1991 г. .

Для поддержки автоматного программирования разработана Switch-технология .

Под термином «автоматное программирование» понимается не только построение и реализация конечных автоматов, но и проектирование и реализация программ в целом, поведение которых описывается автоматами.

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

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

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

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

Основные принципы

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

Параллельно с развитием в Европе синхронного программирования, в России создается подход к разработке программного обеспечения ответственных систем, названный «автоматное программирование» .

Если в программировании в настоящее время широко используется понятие «событие», то рассматриваемый подход базируется на понятии «состояние». Добавляя к нему понятие «входное воздействие», которое может быть входной переменной или событием, вводится термин «автомат без выхода». Добавляя к последнему понятие «выходное воздействие», вводится термин «автомат» (конечный, детерминированный).

Использование понятия «состояние» в качестве базового позволяет лучше понять и специфицировать поведение программы и ее составных частей.

Область программирования, базирующаяся на понятии «автомат», названа «автоматное программирование», а процесс создания таких программ — «автоматное проектирование программ» .

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

В автоматном программировании преобразование графов переходов в текст программы выполняется формально и изоморфно.

При применении языков программирования высокого уровня это наиболее просто выполняется с помощью конструкции switch языка Си либо ее аналогов в других языках программирования. Поэтому технология, основанная на автоматном программировании, была названа «Switch-технология».

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

Логическое управление

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

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

Программирование с явным выделением состояний

В дальнейшем автоматный подход был распространен на событийные системы, которые называются также «реактивными» .

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

Для программирования событийных систем с применением автоматов в работах был использован процедурный подход. Это направление программирования названо «программирование с явным выделением состояний».

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

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

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

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

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

Это позволило организовать "Движение за открытую проектную документацию" , в рамках которого выполняются работы по совершенствованию автоматного программирования.

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

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

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

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

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

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

Автоматный подход эффективен при реализации таких алгоритмов дискретной математики, как, например, поиск подстрок и обход дерева .

На основе автоматного программирования на кафедре «Компьютерные технологии» СПбГУ ИТМО предложен новый подход к построению визуализаторов алгоритмов, которые используются при обучении программированию и дискретной математике . Подход позволяет задавать поведение визуализаторов системой взаимодействующих конечных автоматов. Система состоит из пар автоматов, каждая из которых содержит «прямой» и «обратный» автоматы, обеспечивающие пошаговое выполнение алгоритма вперед и назад соответственно.

Инструментальные средства

Для поддержки автоматного программирования разработаны различные инструментальные средства, такие как, например, UniMod . Это средство базируется на следующих понятиях: UML, Switch-технология, среда разработки Eclipse, язык программирования Java, открытый исходный код. Разработка этого средства позволяет говорить об одной из реализаций «исполняемого UML» . При использовании инструментального средства UniMod программа в целом проектируется с помощью двух типов UML-диаграмм: диаграмм классов в виде схем связей автоматизированных объектов и диаграмм состояний. Эти диаграммы реализуются автоматически, а фрагменты программ, соответствующие входным и выходным воздействиям, пишутся вручную. Таким образом, это инструментальное средство позволяет совмещать декларативный и процедурный подходы к написанию программ.

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

Ссылки

• Автоматное программирование для начинающих