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

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

Что такое автоматное программирование

В последние годы большое внимание уделяется разработке технологий программирования для встроенных систем и систем реального времени, к которым предъявляются высокие требования по качеству программного обеспечения. Одним из наиболее известных подходов в этом направлении является синхронное программирование [1]. Параллельно с развитием в Европе синхронного программирования в России создается подход к разработке программного обеспечения, названный «автоматное программирование» [2—4], который можно рассматривать в качестве разновидности синхронного программирования. В настоящей работе описываются основные положения автоматного программирования. Оно поддерживает такие этапы создания программного обеспечения, как проектирование, реализация, отладка и документирование.

Если в программировании в последнее время все шире используется понятие «событие», то предлагаемый подход базируется на понятии «состояние». С добавлением к нему понятия «входное воздействие», которое может быть входной переменной или событием, вводится термин «автомат без выхода». К последнему добавляется понятие «выходное воздействие» и вводится термин «автомат» (конечный, детерминированный). Поэтому область программирования, базирующаяся на этом понятии, была в работе [4] названа автоматным программированием, а процесс создания таких программ — автоматным проектированием программ.

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

В рамках предлагаемого подхода программирование выполняется «через состояния», а не «через переменные» (флаги), что помогает лучше понять и специфицировать задачу и ее составные части. При этом отладка проводится путем протоколирования в терминах автоматов.

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

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

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

В 1996 г. Российский фонд фундаментальных исследований (РФФИ) в рамках издательского проекта № 96-01-14066 поддержал издание работы [4], где предлагаемая технология была изложена применительно к системам логического управления, в которых события отсутствуют, выходные воздействия являются двоичными переменными, а операционная система работает в режиме сканирования. Системы этого класса реализуются обычно на программируемых логических контроллерах, имеющих относительно небольшой объем памяти: их программирование выполняется на таких специфических языках, как, например, язык функциональных блоков [5]. В работе [4] предложены методы формального написания программ для таких языков при задании спецификации для разрабатываемого проекта системой взаимосвязанных графов переходов. Показаны преимущества использования языка графов переходов по сравнению с языком «Графсет».

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

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

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

Особенность предлагаемого подхода к программированию этого класса систем состоит в том, что в них повышается централизация логики за счет устранения ее в обработчиках событий и формирования системы взаимосвязанных автоматов, вызываемых из обработчиков [8]. Автоматы в такой системе могут взаимодействовать по вложенности, вызываемости и за счет обмена номерами состояний. Последний вид взаимодействия рассматривался также в работе [9], где утверждается, что «указанное взаимодействие может оказаться мощным средством при проверке программ».

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

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

При этом каждый построенный протокол может рассматриваться в качестве соответствующего сценария. Отметим, что для «больших» задач невозможно применение диаграмм последовательностей и диаграмм кооперации, входящих в состав языка UML [10], так как при использовании этого языка указанные диаграммы предлагается строить вручную на этапе проектирования, в то время как в автоматном программировании протоколы строятся автоматически при выполнении разработанной программы. Протоколы позволяют наблюдать за ходом выполнения программы и демонстрируют тот факт, что автоматы являются не «картинками», а реально действующими сущностями.

Автоматный подход предлагается применять не только при создании системы управления, но и при моделировании объектов управления. Он был апробирован при разработке системы управления судовыми дизель-генераторами [11]. Эта система была специфицирована более чем тридцатью взаимодействующими автоматами. Для описания модели дизеля также использовались автоматы. При проектировании на каждый автомат выпускалось четыре документа: словесное описание («декларация о намерениях»), схема связей, поясняющая на русском языке символы, входящие в интерфейс автомата; граф переходов с символьными обозначениями событий, входных переменных и выходных воздействий; текст программного модуля, который реализует граф переходов (также без использования смысловых идентификаторов и комментариев). Эти документы заменяют самодокументирующиеся программы, содержащие смысловые идентификаторы и комментарии, так как эти средства при сложной логике программы не обеспечивают их понимания и пригодности для дальнейшей модификации [12]. Эту проблему при сложной логике не решают и самодокументирующиеся графы переходов [10].

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

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

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

Для решения широкого круга задач весьма эффективен подход, основанный на совместном использовании объектной и автоматной парадигм. В работе [13] он называется «объектно-ориентированное программирование с явным выделением состояний». Особенности этого подхода состоят в следующем. Так же как и в машине Тьюринга [14], явно выделены управляющие (автоматные) состояния объекта, число которых значительно меньше числа остальных состояний, например «вычислительных». В программирование введено понятие «пространство состояний»; под ним понимается множество управляющих состояний объекта. Это обеспечивает существенно более понятное поведение по сравнению со случаем, когда такое пространство или ориентация в нем отсутствует. Предложен минимальный набор документов, позволяющий наглядно и строго описывать как структурные (статические), так и поведенческие (динамические) стороны программ.

Как и при использовании любого другого подхода, применение предлагаемого связано с множеством эвристик, возвратов назад, уточнений и параллельно выполняемых работ. Однако после завершения создания программы предлагаемый подход может быть сформулирован (во всяком случае, для ее документирования) как «идеальная» технология, фиксирующая принятые решения [15].

1. На основе анализа предметной области выделяются классы и строится их диаграмма.
2. Для каждого класса разрабатывается словесное описание по крайней мере в форме перечня решаемых задач.
3. Для каждого класса создается структурная схема, отражающая его интерфейс и структуру. При этом атрибуты и методы разделены на автоматные и остальные.
4. При наличии в классе нескольких автоматов строится схема их взаимодействия.
5. Для каждого автомата разрабатываются словесное описание, схема связей, граф переходов.
6. Каждый класс реализуется соответствующим модулем программы. Его структура должна быть изоморфна структуре класса, а методы, соответствующие автоматам, реализованы по шаблону, приведенному в работе [8].
7. Для отладки системы и подтверждения правильности ее работы автоматически строятся протоколы, в которых функционирование объектов, содержащих автоматы, описывается в терминах состояний, переходов, событий, входных и выходных воздействий.
8. Выпускается проектная документация, куда в качестве составной части входит программная документация.

Из опыта использования изложенной технологии можно сделать вывод, что применение автоматов проясняет поведение программы так же, как использование объектов делает прозрачной ее структуру. Описанный подход был использован при создании ПО управления танком в системе Robocode [15]. В отличие от систем управления сотнями других танков, на этот танк выпущена подробная проектная документация, содержащая, в частности, графы переходов и схемы связей автоматов, реализующих его функциональность. Детальные протоколы поведения танка позволяют проследить все течение боя. Метод их построения, возможно, является основой для новой концепции построения «черных ящиков».

В описанной технологии автоматы применялись как методы классов. В рамках этой технологии могут быть использованы и другие подходы к объектной реализации автоматов, изложенные, например, в работах [16 — 18]. Автоматы могут выступать, в частности, как объекты-наследники определенного класса, реализующего базовую функциональность автоматов, обусловленную семантикой Switch-технологии. Возможно также использование классов, реализующих понятия «состояние» или «группа состояний». При проектировании автоматных программ может быть использован паттерн State [19] или другие паттерны.

Особенности автоматной реализации параллельных процессов на основе механизма обмена сообщениями рассмотрены в работе [20]. Еще один подход к автоматной реализации параллельных процессов описан в работе [21].

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

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

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

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

Одна из целей настоящей работы состоит в том, чтобы показать, что автоматы в программировании служат не только «для распознавания цепочек символов» [26] и управления «стиральными машинами». Кроме того, показано, что они не просто являются одной из математических моделей дискретной математики, а могут применяться при реализации любых программ, обладающих сложным поведением. Предлагаемая технология должна ответить на вопрос, поставленный одним из моих коллег: «Теорию конечных автоматов мы проходили, но при чем здесь программирование?»

Движение за открытую проектную документацию

27 ноября 2002 г. на открытии полуфинальных соревнований командного чемпионата мира по программированию ACM (Association for Computing Machinery) в Северо-Восточном регионе Европы было объявлено об организации «Движения за открытую проектную документацию» [27], в частности о создании на сайте http://is.ifmo.ru раздела «Проекты», в котором в ближайшее время будет размещено около 40 проектов разработки программного обеспечения на основе автоматного подхода. Перечислим некоторые проекты, реализованные в рамках описанного подхода:

• автоматная реализация интерактивных сценариев образовательной анимации с использованием Macromedia Flash;
• построение визуализаторов алгоритмов для обучения дискретной математике и программированию;
• обучающая и тестирующая программа с примером настройки для изучения английского языка;
• совместное использование теории построения компиляторов и Switch-технологии;
• скелетная анимация;
• управление различными технологическими процессами и объектами (упрощенная модель цеха холодной прокатки, упрощенная модель автомобиля, дизель-генератор, турникет, кодовый замок, светофор, кофеварка, телефон, банкомат, лифт, система безопасности банка и т. д.);
• игры (Terrarium, Robocode, CodeRally, "Морской бой", Lines [27], Bomber [28], Tron, "Однорукий бандит", "Завалинка");
• моделирование игры "Пятнашки" для роботов LEGO;
• XML-формат для описания внешнего вида видеопроигрывателя (www.crystalplayer.com);
• примеры клиент-серверных приложений;
• построение пользовательских интерфейсов;
• реализация сетевого протокола SMTP;
• классические "параллельные" задачи ("Синхронизация цепи стрелков", "Обедающие философы");
• управление в задачах логистики.

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

Об авторе

Анатолий Абрамович Шалыто — докт. техн. наук, профессор С.-Петербургского государственного института точной механики и оптики (Технического университета). Победитель конкурса исследовательских проектов в области автоматизации проектирования интегральных схем, проводившегося в СНГ в 2003 г. С ним можно связаться по адресу: Shalyto@mail.ifmo.ru.

Литература

1. Benveniste A., Caspi P., Edwards S. et al. The Synchronous Languages 12 Years Later // Proceedings of the IEEE. 2003. V. 91. № 1.
2. Шалыто А.А. Алгоритмизация и программирование для систем логического управления и "реактивных" систем: Обзор // Автоматика и телемеханика. 2001. № 1. http://is.ifmo.ru
3. Шалыто А.А. Логическое управление. Методы аппаратной и программной реализации алгоритмов. СПб.: Наука, 2000.
4. Шалыто А.А. Switch-технология. Алгоритмизация и программирование задач логического управления. СПб.: Наука, 1998.
5. Шалыто А.А. Реализация алгоритмов логического управления программами на языке функциональных блоков // Промышленные АСУ и контроллеры. 2000. № 4. http://is.ifmo.ru
6. Harel D., Politi M. Modeling Reactive Systems with Statecharts. NY: McGraw-Hill, 1998.
7. Шалыто А., Туккель Н. Программирование с явным выделением состояний //Мир ПК. 2001. № 8, 9. http://is.ifmo.ru
8. Шалыто А.А., Туккель Н.И. Switch-технология. Aвтоматный подход к созданию программного обеспечения "реактивных" систем // Программирование. 2001. № 5. http://is.ifmo.ru
9. Дейкстра Э. Взаимодействие последовательных процессов // Языки программирования. М.: Мир, 1972.
10. Буч Г., Рамбо Д., Джекобсон А. Язык UML: Руководство пользователя. М.: ДМК, 2000.
11. Шалыто А.А., Туккель Н.И. Проектирование программного обеспечения системы управления дизель-генераторами на основе автоматного подхода //Системы управления и обработки информации. СПб.: ФГУП "НПО "Аврора", 2003, вып. 5.
12. Безруков Н. Повторный взгляд на "собор" и "базар" //BYTE/Россия. 2000. № 8.
13. Шалыто А.А., Туккель Н.И. Объектно-ориентированное программирование с явным выделением состояний // Материалы международной научно-технической конференции "Искусственный интеллект - 2002". Т.1. Таганрог - Донецк: ТГРУ - ДИПИИ, 2002.
14. Шалыто А., Туккель Н. От тьюрингова программирования к автоматному // Мир ПК. 2002. № 2. http://is.ifmo.ru
15. Шалыто А.А., Туккель Н.И. Танки и автоматы // BYTE/Россия. 2003. № 2. http://is.ifmo.ru
16. Гуров В.С., Нарвский А.С., Шалыто А.А. Автоматизация проектирования событийных объектно-ориентированных программ с явным выделением состояний //Труды Х Всероссийской научно-методической конференции "Телематика-2003". Т. 1. СПб.: СПбГИТМО (ТУ), 2003. http://tm.ifmo.ru.
17. Шопырин Д.Г., Шалыто А.А. Применение класса "STATE" в объектно-ориентированном программировании с явным выделением состояний //Труды Х Всероссийской научно-методической конференции "Телематика-2003". Т. 1. СПб.: СПбГИТМО (ТУ), 2003. http://tm.ifmo.ru.
18. Корнеев Г.А., Шалыто А.А. Реализация конечных автоматов с использованием объектно-ориентированного программирования //Труды Х Всероссийской научно-методической конференции "Телематика-2003". Т. 2. СПб.: СПбГИТМО (ТУ), 2003. http://tm.ifmo.ru.
19. Гамма Э., Хелм Р., Джонсон Р., Влиссидес Дж. Приемы объектно-ориентированного программирования. Паттерны проектирования. СПб.: Питер, 2001.
20. Гуисов М.И., Кузнецов А.Б., Шалыто А.А. Интеграция механизма обмена сообщениями в Switch-технологию. http://is.ifmo.ru.
21. Любченко В. О бильярде с Microsoft Visual C++ 5.0 // Мир ПК. 1998. № 1
22. Шалыто А., Туккель Н., Шамгунов Н. Ханойские башни и автоматы //Программист. 2002. № 8. http://is.ifmo.ru
23. Шалыто А., Туккель Н., Шамгунов Н. Задача о ходе коня //Мир ПК. 2003. № 1. http://is.ifmo.ru
24. Шалыто А.А., Туккель Н.И. Преобразование итеративных алгоритмов в автоматные //Программирование. 2002. № 5. http://is.ifmo.ru
25. Корнеев Г.А., Казаков М.А., Шалыто А.А. Построение логики работы визуализаторов алгоритмов на основе автоматного подхода //Труды Х Всероссийской научно-методической конференции "Телематика-2003". Т. 2. СПб.: СПбГИТМО (ТУ), 2003. http://tm.ifmo.ru.
26. Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений. М.: Вильямс, 2002.
27. Шалыто А.А. Новая инициатива в программировании. Движение за открытую проектную документацию // Мир ПК. 2003. № 9.
28. Аллен Э. Типичные ошибки проектирования. СПб.: Питер, 2003.