Телематика'2004

XI Всероссийская
научно-методическая
конференция


 

 

РЕАЛИЗАЦИЯ АВТОМАТОВ В ОБЪЕКТНО-ОРИЕНТИРОВАННЫХ ПРОГРАММАХ

А.А.Шалыто, Л.А.Наумов

Санкт-Петербургский государственный университет информационных технологий, механики и оптики, Санкт-Петербург

Тел.: (812) 247-95-45, e-mail: shalyto@mail.ifmo.ru

В [1] был предложен подход к созданию программ для систем логического управления на основе использования конечных автоматов. Это подход был назван «Switch-технология» или «автоматное программирование».
В [2] этот подход был развит для проектирования программного обеспечения событийных систем. Описанных подход является процедурным, поэтому он был назван «процедурное программирование с явным выделением состояний».
В [3] рассматриваемый подход был расширен на объектно-ориентированные программы и получил название «объектно-ориентированное программирование с явным выделением состояний». При этом автоматы реализовывались в качестве методов классов.
В ходе педагогического эксперимента [4] выполнено более 40 проектов с применением объектно-ориентированного программирования с явным выделением состояний. В ходе выполнения проектов был создан ряд методов реализации автоматов, отличных от предложенного в [3].
Цель настоящей работы состоит в классификации этих методов и кратком их описании. Перечислим эти методы.
Автоматы как методы классов [3]. Этот подход близок к процедурному стилю программирования и может быть назван «обертыванием автоматов в классы».
Автоматы как классы без использования базового класса, реализующего типовые функции автоматов [5].
Автоматы как классы с использованием базового класса, реализующего типовые функции автоматов. Этот подход основан на совместном применении преимуществ, как объектного, так и автоматного стилей программирования. При этом автоматы разрабатываются как наследники класса, реализующего базовую функциональность. Базовый класс и другие необходимые классы образуют в библиотеку, предоставляемую разработчику.
В [6] приводится пример простейшей библиотеки классов для разработки программного обеспечения в рамках объектно-ориентированного программирования с явным выделением состояний. В нее входят два класса: класс Automat для дальнейшего наследования от него классов разрабатываемых автоматов и вспомогательный класс AutoService. Первый класс обеспечивает, в частности, выполнение шага и пост-шага автомата, автоматическое протоколирование и т.п. Второй класс используется для реализации функций автоматического протоколирования. Похожий подход предлагался в [7].
В [8] предложена библиотека STOOL (Switch-Technology Object Oriented Library), в которой не только автомат, но и его логические составные части имеют соответствующие базовые классы. Кроме того, библиотека предоставляет возможность разработки многопоточного программного обеспечения.
В [9] предложена еще одна библиотека для объектно-ориентированной реализации автоматов, названная Auto-Lib, и приведен пример ее использования.
В [10] предложена библиотека, позволяющая «собирать» простые автоматы из наследников базовых классов «состояние автомата» и «переход между состояниями». Эта библиотека позволяет обеспечить изоморфизм между текстом программы и графом переходов даже при наличии в нем групповых переходов (переходов из гиперсостояний).
Наряду с использованием библиотек при объектно-ориентированной реализации автоматов могут применяться и разрабатываться паттерны проектирования [11].
Описанный в [12] паттерн Automat позволяет проектировать и реализовывать программное обеспечение, пользуясь классами, реализующими следующие понятия: «состояние», «условие перехода», «действие», «переход», «дуга перехода», «автомат». При этом класс, реализующий последнее понятие, является базовым для разрабатываемых автоматов и содержит в себе их основную логику.
Использование паттерна State. Данный паттерн [11] реализует абстракцию состояние. Для реализации конкретного состояния необходимо разработать наследника базового класса State и переопределить в нем функцию переходов.
Похожий подход рассмотрен в [13]. В ней для каждого автомата предложено создать базовый класс состояние, от которого наследуются конкретные классы, реализующие состояния данного автомата. Переходы между состояниями обеспечиваются базовыми классами состояний, но непосредственно осуществляются в классах наследниках.
Реализация автоматов на основе интерпретации. В [14] предложен подход, позволяющий автоматически преобразовывать графы переходов в текстовое описание в формате XML. На языке Java разработана среда исполнения полученного XML-описания. Сначала указанное описание однократно и целиком преобразуется в соответствующее внутреннее объектное представление программы. В результате образуется система, состоящая из среды исполнения и объектного представления программы. При этом каждое входное и выходное воздействие реализуется вручную, в соответствии с его функциональностью. Упомянутая система при появлении события анализирует его и входные переменные и выполняет выходные воздействия, а также запускает вложенные автоматы.
В работе [15] предложено использовать XML для автоматного описания динамики изменения внешнего вида виртуального устройства – видеопроигрывателя Crystal Player (http://www.crystalplayer.com).
Механизм обмена сообщениями и автоматы. В ходе выполнения работ [16, 17] по реализации классического параллельного алгоритма синхронизации цепи стрелков выяснилось, что автоматы, построенные по предложенному в [2] шаблону, реализующему событийно-управляемые автоматы, который состоит из двух операторов switch, не позволяет реализовать взаимодействующие параллельные процессы. Для решения этой задачи в [16] было предложено использовать механизм обмена сообщениями. Для этого была разработана библиотека SWMEM (Switch Message Exchange Mechanism). При этом в шаблон для реализации автоматов были внесены следующие изменения: шаг работы автомата разделен на три этапа (выбор перехода, совершение действий на переходе и обновление переменной состояния); введены переменная для учета приоритетов условий на дугах графа переходов и переменная для хранения выбранного действия и последующего его выполнения.
В [18] механизм обмена сообщениями между параллельно «расположенными» автоматами реализуется за счет введения такой сущности, как «общая шина». Этот подход позволяет однотипно реализовать разнотипные по своей природе алгоритмы, которые могут быть иерархическими, вложенными или параллельными. Для реализации параллельно работающих автоматов было предложено изменить шаблоны, предложенные в [2, 16], строя автомат с помощью двух функций: функции перехода-действия и функции обновления. Первая из них сначала осуществляет выходные воздействия, как в состоянии, так и на переходе, а потом определяет номер нового состояния и осуществляет выходные воздействия в нем. Вторая функция обеспечивает выполнение одинаковых действий: обновляет состояние автомата и массив поступающих ему сообщений. Для синхронизации автоматов сначала должны вызываться все функции перехода-действия, а затем – все функции обновления.
Все предложенные подходы проиллюстрированы примерами, приведенными на сайте http://is.ifmo.ru.
Литература
1. Шалыто А.А. SWITCH-технология. Алгоритмизация и программирование задач логического управления. СПб.: Наука, 1998.
2. Шалыто А.А., Туккель Н.И. SWITCH-технология – автоматный подход к созданию программного обеспечения "реактивных" систем // Программирование. 2001. №5. http://is.ifmo.ru, раздел «Статьи».
3. Шалыто А.А., Туккель Н.И. Танки и автоматы // BYTE/Россия. 2003. №2. http://is.ifmo.ru, раздел «Статьи».
4. Шалыто А.А. Новая инициатива в программировании. Движение за открытую проектную документацию // Мир ПК. 2003. № 9. http://is.ifmo.ru, раздел «Статьи».
5. Наумов А.С., Шалыто А.А. Система управления лифтом. СПб.: СПбГУ ИТМО, 2003. http://is.ifmo.ru, раздел «Проекты».
6. Наумов Л.А., Шалыто А.А. Автоматное решении задачи Д.Кнута о лифте. СПб.: СПбГУ ИТМО, 2003. http://is.ifmo.ru, раздел «Проекты».
7. Корнеев Г.А., Шалыто А.А. Реализация конечных автоматов с использованием объектно-ориентированного программирования // Труды X Всеросс. научн.-метод. конф. "Телематика’2003". 2003. Т.2.
8. Шопырин Д.Г., Шалыто А.А. Объектно-ориентированный подход к автоматному программированию. СПб.: СПбГУ ИТМО, 2003. http://is.ifmo.ru, раздел «Проекты».
9. Фельдман П.И., Шалыто А.А. Совместное использование объектного и автоматного подходов в программировании. СПб.: СПбГУ ИТМО, 2004. http://is.ifmo.ru, раздел «Проекты».
10. Заякин Е.А., Шалыто А.А. Метод устранения повторных фрагментов кода при реализации конечных автоматов. СПб.: СПбГУ ИТМО, 2003. http://is.ifmo.ru, раздел «Проекты».
11. Гамма Э., Хелм Р., Джонсон Р., Влассидес Дж. Приемы объектно-ориентированного проектирования. Паттерны проектирования. СПб.: Питер, 2001.
12. Астафуров А.А., Шалыто А.А. Разработка и применение паттерна «Automata». СПб.: СПбГУ ИТМО. 2003. http://is.ifmo.ru, раздел «Проекты».
13. Кузнецов Д.В., Шалыто А.А. Система управления танком для игры «Robocode». Вариант 2. СПб.: СПбГУ ИТМО, 2003.
14. Гуров В.С., Шалыто А.А. XML и автоматы. СПб.: СПбГУ ИТМО. 2004. http://is.ifmo.ru, раздел «Проекты».
15. Бондаренко К.А., Шалыто А.А. Разработка XML-формата для описания внешнего вида видеопроигрывателя с использованием конечных автоматов. СПб.: СПбГУ ИТМО. 2003. http://is.ifmo.ru, раздел «Проекты».
16. Гуисов М.И., Кузнецов А.Б., Шалыто А.А. Интеграция механизма обмена сообщениями в Switch-технологию. СПб.: СПбГУ ИТМО. 2003. http://is.ifmo.ru, раздел «Проекты».
17. Гуисов М.И., Кузнецов А.Б., Шалыто А.А. Задача Д. Майхилла «Синхронизация цепи стрелков». Вариант 2. СПб.: СПбГУ ИТМО. 2003. http://is.ifmo.ru, раздел «Проекты».
18. Альшевский Ю.А., Раер М.Г., Шалыто А.А. Система управления турникетом. СПб.: СПбГУ ИТМО. 2003. http://is.ifmo.ru, раздел «Проекты».


 



Санкт-Петербург, 7-10 июня 2004 г.
XI Всероссийская научно-методическая конференция "Телематика'2004"