Реализация автоматов при программировании событийных систем



Статья опубликована в журнале "Программист", 2002. #4. C.74-80.

(краткая аннотация)

(C) 2001 г. А.А.Шалыто, Н.И.Туккель

Федеральный научно-производственный центр ГУП "НПО "Аврора"",
Санкт-Петербургский государственный институт точной механики и оптики
(технический университет)

Отсюда можно скачать полный текст статьи в формате pdf (206 кб)

В работе [1] был предложен подход к алгоритмизации и программированию задач логического управления, использующий конечные автоматы, который был назван "автоматным программированием", "программированием с явным выделением состояний" или "SWITCH-технологией" (www.softcraft.ru).

Изложим основные особенности этого подхода. Если процедурное программирование базируется на терминах "данные" и "процедуры", объектно-ориентированное — на "атрибутах" и "методах", а событийное — на "событиях" и "обработчиках событий", то в автоматном программировании, как и в теории управления, используются три термина: "входные воздействия", "состояния" и "выходные воздействия", причем состояния рассматриваются как абстракции и выделяются на этапе проектирования явно. По аналогии с Н. Виртом, который назвал свою книгу "Алгоритмы + Структуры данных = Программы", может быть введено соотношение: "Состояния + Входные воздействия + Выходные воздействия = Автомат". При этом автомат обычно рассматривается как конечный и детерминированный и предназначается для формального описания логики программ. Универсальность применения автоматов в программировании обоснована в работе [2].

Отметим, что автоматное программирование не противопоставляется процедурному, объектно-ориентированному и событийному, а может использоваться совместно с каждым их них в части описания логики, что продемонстрировано в проектах, приведенных на сайте www.softcraft.ru.

Одна из основных особенностей автоматного программирования состоит в том, что для обеспечения связи состояний с переменными введен этап, названный в работе [1] кодированием состояний. Такое кодирование применяется в теории автоматов, однако в традиционном программировании оно выполняется неявно путем эвристического введения флагов, что затрудняет понимание программ. В предлагаемом подходе для кодирования любого числа состояний автомата применяется одна многозначная переменная, что предопределило реализацию автоматов с помощью конструкции switch языка С. Указанная реализация выполняется формально по графу переходов, визуально описывающему поведение автомата. Под поведением при этом, в отличие от объектно-ориентированного программирования, понимаются не только его внешние проявления, но и внутренняя сущность, связанная с переходами между состояниями, за которыми можно наблюдать по значениям указанной переменной. Понятие "наблюдаемость" введено в программирование в работе [1].

При описании поведения сложных систем обычно используется не один автомат, а система взаимосвязанных автоматов, что позволяет, в частности, описывать параллельные процессы.

Предлагаемый подход, в отличие от других подходов, рассмотренных в работе [1], обеспечивает применение автоматов при проектировании, программировании, документировании и протоколировании.

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

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

К этому классу систем относятся разнообразные приложения - от графических пользовательских интерфейсов [3] до компьютерных игр [4]. К ним также могут быть отнесены системы управления различными техническими объектами (бытовая техника, лифты, дизель-генераторы и т.д.)

Целесообразность применения автоматного подхода для указанного класса систем подтверждается тем, что создатель операционной системы UNIX К.Томпсон на вопрос о текущей работе ответил: "Мы создали язык генерации машин с конечным числом состояний, так как реальный селекторный телефонный разговор — это группа взаимодействующих машин с конечным числом состояний. Этот язык применяется в "Bell Labs" по прямому назначению — для создания указанных машин, а вдобавок с его помощью стали разрабатывать драйверы" [5].

Более того, в работе [6] приведено высказывание одного из участников семинара "Software 2000: a View of the Future": "Я знаю людей из "Боинга", занимающихся системами стабилизации самолетов с использованием чистой теории автоматов. Даже трудно себе представить, что им удалось сделать при помощи этой теории".

Автоматный подход может применяться и при разработке объектно-ориентированных программ с целью наглядного описания их поведения [7]. Пример применения такого подхода, названного авторами настоящей работы "объектно-ориентированным программированием с явным выделением состояний", приведен на сайте www.softcraft.ru.

Еще одним направлением использования автоматного подхода является визуализация вычислительных алгоритмов [8].

Таким образом, область применения SWITCH-технологии заключается в решении задач управления, понимаемого весьма широко.

Наибольшие трудности при использовании автоматного подхода связаны с пониманием особенностей функционирования автоматов в событийных системах. Настоящая работа призвана на примере программной реализации пояснить эти особенности. Выполнено сравнение предлагаемого подхода с аналогичным подходом, применяемым в языке объектно-ориентированного моделирования UML [7].

Литература

  1. Шалыто А.А. SWITCH-технология. Алгоритмизация и программирование задач логического управления. СПб.: Наука, 1998. 628 с.
  2. Шалыто А.А., Туккель Н.И. От тьюрингова программирования к автоматному //Мир ПК. 2002. №2. С.144-149.
  3. Шалыто А.А., Туккель Н.И. Программирование с явным выделением состояний //Мир ПК. 2001. №8. C. 116-121, №9. C. 132-138.
  4. Секреты программирования игр /А. Ла Мот, Д. Ратклифф, М. Семинаторе и др. СПб.: Питер, 1995. 278 с.
  5. Кук Д., Урбан Д., Хамилтон С. Unix и не только. Интервью с Кеном Томпсоном //Открытые системы. 1999. №4. С. 35-47.
  6. Карпов Ю.Г. Теория алгоритмов и автоматов. СПб.: Геликон Плюс, 2000.
  7. Рамбо Д., Якобсон А., Буч Г. UML. Специальный справочник. СПб.: Питер, 2002. 652 с.
  8. Шалыто А.А., Туккель Н.И. Реализация вычислительных алгоритмов на основе автоматного подхода //Телекоммуникации и информатизация образования. 2001. №6. С. 35-53.