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

Материал из свободной русской энциклопедии «Традиция»
Перейти к: навигация, поиск

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

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

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

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

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

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

Fig1.png

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

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

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

Основные принципы[править]

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

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

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

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

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

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

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

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

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

Логическое управление[править]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вычислительные алгоритмы[править]

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

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

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

Инструментальные средства[править]

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

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

Ссылки[править]

  1. Непейвода Н.Н. Стили и методы программирования. М.: Интернет-Университет Информационных технологий, 2005. http://is.ifmo.ru/foundation/moving
  2. Шалыто А.А. Программная реализация управляющих автоматов //Судостроительная промышленность. Серия «Автоматика и телемеханика». 1991. Вып.13, с.41,42. http://is.ifmo.ru/works/switch_prr/
  3. а б в Шалыто А.А. SWITCH-технология. Алгоритмизация и программирование задач логического управления. СПб.: Наука. 1998, 628 с. http://is.ifmo.ru/books/switch/1
  4. Benveniste A. et al. The Synchronous Languages 12 Years Later. Proceedings of the IEEE, vol. 91, no. 1, January 2003. pp. 64–83. http://www-verimag.imag.fr/~caspi/PAPIERS/iee03.pdf
  5. Шопырин Д.Г., Шалыто А.А. Синхронное программирование //Информационно-управляющие системы. 2004. № 3, с.35–42. http://is.ifmo.ru/works/sync_prog/
  6. Шалыто А.А. Автоматное проектирование программ. Алгоритмизация и программирование задач логического управления //Известия РАН. Теория и системы управления. 2000. № 6, c.63–81. http://is.ifmo.ru/works/app-aplu/1/
  7. Harel D. Statecharts: A Visual Formalism for Complex Systems //Science of Computer Programming. 1987. vol.8, pp. 231–274. http://web.archive.org/web/20070221190813/http://www.tik.ee.ethz.ch/tik/education/lectures/hswcd/papers/Statecharts.pdf
  8. Шалыто А.А. Алгоритмизация и программирование для систем логического управления и "реактивных" систем //Автоматика и телемеханика, 2001, № 1, с.3−39. http://is.ifmo.ru/works/arew/1/
  9. Туккель Н.И., Шалыто А.А. SWITCH-технология − автоматный подход к созданию программного обеспечения "реактивных" систем //Программирование. 2001. № 5, c.45–62. http://is.ifmo.ru/works/switch/1/
  10. Туккель Н.И., Шалыто А.А. Программирование с явным выделением состояний //Мир ПК. 2001. № 8, с.116–121; № 9, с.132–138. http://is.ifmo.ru/works/mirk/
  11. Туккель Н.И., Шалыто А.А. Система управления дизель-генератором (фрагмент). Программирование с явным выделением состояний. Проектная документация. 2002. 51 с. http://is.ifmo.ru/projects/dg/
  12. Шалыто А.А. Новая инициатива в программировании. Движение за открытую проектную документацию //PC Week/RE. 2003. № 40, с.38,39,42. http://is.ifmo.ru/works/open_doc/
  13. Сайт по автоматному программированию. http://is.ifmo.ru
  14. Шалыто А.А., Наумов Л.А. Методы объектно-ориентированной реализации реактивных агентов на основе конечных автоматов //Искусственный интеллект. 2004. № 4. с.756–762. http://is.ifmo.ru/works/_aut_oop.pdf
  15. Shalyto A.A., Naumov L.A., Korneev G.A. Methods of Object-Oriented Reactive Agents Implementation on the Basis of Finite Automata /2005 International Conference on “Integration of Knowledge Intensive Multiagent Systems. KIMAS ’05: Modeling, Exploration, and Engineering”. USA, MA: IEEE, 2005, pp. 460–465. http://is.ifmo.ru/articles_en/_kimas05-1.pdf
  16. Туккель Н.И., Шалыто А.А. Автоматы и танки //BYTE/Россия. 2003. № 2. с.69–73. http://is.ifmo.ru/works/tanks_new/
  17. Туккель Н.И., Шалыто А.А. Система управления танком для игры "Robocode". Вариант 1. Объектно-ориентированное программирование с явным выделением состояний. 2001. 52 с. http://is.ifmo.ru/projects/tanks/
  18. Кузнецов Д.В., Шалыто А.А. Система управления танком для игры "Robocode". Вариант 2. Объектно-ориентированное программирование с явным выделением состояний. 2003. 86 с. http://is.ifmo.ru/projects/robocode2/
  19. Туккель Н.И., Шалыто А.А. Преобразование итеративных алгоритмов в автоматные //Программирование. 2002. № 5, c.12–26. http://is.ifmo.ru/works/iter/
  20. Корнеев Г.А., Шамгунов Н.Н., Шалыто А.А. Обход деревьев на основе автоматного подхода //Компьютерные инструменты в образовании. 2004. № 3, с.32–37. http://is.ifmo.ru/works/traverse/
  21. Казаков М.А., Шалыто А.А. Автоматный подход к реализации анимации в визуализаторах алгоритмов //Компьютерные инструменты в образовании. 2005. № 3, с.52–76. http://is.ifmo.ru/works/heapsort/
  22. Корнеев Г.А., Шалыто А.А. Построение визуализаторов алгоритмов дискретной математики //Научно-технический вестник СПбГУ ИТМО. Выпуск 23. Высокие технологии в оптических и информационных системах. СПб.: СПбГУ ИТМО. 2005, с.118–129. http://is.ifmo.ru/works/_a_visualizerExample.pdf
  23. Гуров В.С., Мазин М.А., Нарвский А.С., Шалыто А.А. UML. SWITCH-технология. Eclipse //Информационно-управляющие системы. 2004. № 6, c.12–17. http://is.ifmo.ru/works/uml-switch-eclipse/
  24. Gurov V.S., Mazin M.A. , Narvsky A.S., Shalyto A.A. UniMod: Method and Tool for Development of Reactive Object-Oriented Programs with Explicit States Emphasis /Proceedings of St. Petersburg IEEE Chapters. Year 2005. International Conference “110 Anniversary of Radio Invention”. SPb ETU "LETI". 2005. V. 2, pp. 106–110. http://is.ifmo.ru/articles_en/_unimod.pdf
  25. UniMod. http://unimod.sourceforge.net/intro.html
  26. Executable UML. http://en.wikipedia.org/wiki/Executable_UML
  27. Примеры использования инструментального средства UniMod. http://is.ifmo.ru/unimod-projects/