Источник:http://is.ifmo.ru/works/tech_aut_prog
Автор: Докт. техн. наук, профессор Анатолий Шалыто
Излагаются основные положения новой технологии программирования, названной автором "автоматное программирование". При этом графы переходов конечных автоматов используются при спецификации, реализации, отладке и документировании программ. Автоматное программирование является разновидностью синхронного программирования, которое было создано и нашло применение в Европе для разработки систем управления ответственными объектами.
Если хочешь построить лодку, не зови людей, не бей в барабаны, а всели в них
тоску по бескрайнему синему морю.
Антуан де Сент-Экзюпери
Что такое автоматное программирование?
В последние годы большое внимание уделяется разработке технологий программирования для встроенных систем и систем реального времени, к которым предъявляются высокие требования по качеству программного обеспечения. Одним из наиболее известных подходов в этом направлении является синхронное программирование [1].
Параллельно с развитием в Европе синхронного программирования, в России создается подход к разработке программного обеспечения, названный "автоматное программирование" [2–4], который можно рассматривать в качестве разновидности синхронного программирования.
В настоящей работе описываются основные положения "автоматного программирования". Оно поддерживает такие этапы создания программного обеспечения как проектирование, реализация, отладка и документирование.
Если в программировании в последнее время все шире используется понятие "событие", то предлагаемый подход базируется на понятии "состояние". Добавляя к нему понятие "входное воздействие", которое может быть входной переменной или событием, вводится термин "автомат без выхода". Добавляя к последнему понятие "выходное воздействие", вводится термин "автомат" (конечный, детерминированный).
Поэтому область программирования, базирующаяся на этом понятии, была в работе [4] названа "автоматное программирование", а процесс создания таких программ — "автоматное проектирование программ".
Особенность рассматриваемого подхода состоит в том, что при его использовании автоматы задаются графами переходов, для различения вершин в которых вводится понятие "кодирование состояний". При выборе "многозначного кодирования" с помощью одной переменной можно различить состояния, число которых совпадает со значностью выбранной переменной. Это позволило ввести в программирование такое понятие, как "наблюдаемость программ".
В рамках предлагаемого подхода программирование выполняется "через состояния", а не "через переменные" (флаги), что позволяет лучше понять и специфицировать задачу и ее составные части.
При этом необходимо отметить, что в автоматном программировании отладка проводится путем протоколирования в терминах автоматов.
В силу того, что в рамках этого подхода от графа переходов к тексту программы предлагается переходить формально и изоморфно, то при применении языков программирования высокого уровня это наиболее рационально выполнять с помощью конструкции switch языка Си либо ее аналогов в других языках программирования. Поэтому технологию автоматного программирования в работе [4] было решено назвать "Switch-технология".
В настоящее время эта технология разрабатывается в нескольких вариантах, различающихся
как классом решаемых задач, так и типом вычислительных устройств, на которых
осуществляется программирование.
Логическое управление
В 1996 г. Российский фонд фундаментальных исследований (РФФИ) в рамках издательского
проекта № 96-01-14066 поддержал издание работы [4], в которой предлагаемая
технология была изложена применительно к системам логического управления, в
которых события отсутствуют, выходные воздействия являются двоичными переменными,
а операционная система работает в режиме сканирования. Системы этого класса
реализуются обычно на программируемых логических контроллерах, которые имеют
относительно небольшой объем памяти, а их программирование выполняется на таких
специфических языках, как, например, язык функциональных блоков [5]. В работе
[4] предложены методы формального написания программ для таких языков при задании
спецификации для разрабатываемого проекта системой взаимосвязанных графов переходов.
Показаны преимущества использования языка графов переходов по сравнению с языком "Графсет".
Программирование с явным выделением состояний
В дальнейшем автоматный подход был распространен на событийные системы, которые называются также "реактивными" [6]. В них указанные выше ограничения сняты. Как следует из названия этих систем, в них среди входных воздействий используются события, в качестве выходных воздействий применяются произвольные процедуры, а в качестве операционных систем — любые операционные системы реального времени.
Для программирования событийных систем с применением автоматов был использован процедурный подход, и поэтому такое программирование было названо "программирование с явным выделением состояний" [7].
При этом выходные воздействия "привязаны" к дугам, петлям или вершинам графов переходов (применяются смешанные автоматы — автоматы Мура-Мили). Это позволяет в компактном виде представлять последовательности действий, которые являются реакциями на соответствующие входные воздействия.
Особенность предлагаемого подхода к программированию этого класса систем состоит в том, что в них повышается централизация логики за счет устранения ее в обработчиках событий и формирования системы взаимосвязанных автоматов, которые вызываются из обработчиков [8]. Автоматы между собой могут взаимодействовать по вложенности, вызываемости и за счет обмена номерами состояний.
Последний вид взаимодействия рассматривался также в работе [9], в которой утверждается, что "указанное взаимодействие может оказаться мощным средством при проверке программ".
Система взаимосвязанных автоматов образует системонезависимую часть программы, а системозависимая часть формируется из функций входных и выходных воздействий, обработчиков событий и т.д.
Другая важнейшая особенность описываемого подхода состоит в том, что при его применении автоматы используются триедино: при спецификации; при программировании (сохраняются в программном коде); при протоколировании, выполняемом, как указано выше, в терминах автоматов. Последнее позволяет контролировать правильность функционирования системы автоматов. Протоколирование выполняется автоматически по построенной программе и может использоваться для задач большой размерности при сложной логике программы.
При этом каждый построенный протокол может рассматриваться в качестве соответствующего сценария. Отметим, что для "больших" задач невозможно применение диаграмм последовательностей и диаграмм кооперации, входящих в состав языка UML [10], так как при использовании этого языка указанные диаграммы предлагается строить вручную на этапе проектирования, в то время, как в автоматном программировании протоколы строятся автоматически при выполнении программы.
Протоколы позволяют наблюдать за ходом выполнения программы и демонстрируют тот факт, что автоматы являются не "картинками", а реально действующими сущностями.
Автоматный подход предлагается применять не только при создании системы управления, но и при моделировании объектов управления.
Этот подход был апробирован при разработке системы управления судовыми дизель-генераторами [11]. Система была специфицирована более чем тридцатью взаимодействующими автоматами. Для описания модели дизеля также использовались автоматы. При проектировании на каждый автомат выпускалось четыре документа: словесное описание ("декларация о намерениях"), схема связей (поясняющая на русском языке символы, входящие в интерфейс автомата), граф переходов (с символьными обозначениями событий, входных переменных и выходных воздействий), текст программного модуля, который формально и изоморфно реализует граф переходов (также без использования смысловых идентификаторов и комментариев). Эти документы заменяют самодокументирующиеся программы, содержащие смысловые идентификаторы и комментарии, так как эти средства при сложной логике программы не обеспечивают должного понимания программ и их пригодности для дальнейшей модификации [12]. Эту проблему при сложной логике не решают и самодокументирующиеся графы переходов [10].
Выполненный проект подтвердил целесообразность использования протоколов для проверки корректности взаимодействия столь большого количества автоматов и каждого из них в отдельности.
Реализация указанного проекта была осуществлена на вычислительной системе с архитектурой ix86. В дальнейшем этот подход был развит Н.И. Туккелем применительно к созданию систем на микроконтроллерах. При этом все проектирование можно выполнять на персональном компьютере, используя автоматное программирование, и переносить полученное программное обеспечение на микроконтроллер только на последней стадии разработки.
Продолжение статьи можно найти по этой ссылке: http://is.ifmo.ru/works/tech_aut_prog