Танки и автоматы

Анатолий Шалыто,
ученый секретарь ФНПЦ ФГУП "НПО Аврора", профессор кафедры "Компьютерные технологии"
СПбГИТМО (ТУ)

mail@avrorasystems.com

Никита Туккель,
инженер-программист ФНПЦ ФГУП "НПО Аврора"
cynical@mail.ru

При создании объектно-ориентированных (ОО) программ [1, 2] в литературе все большее внимание уделяется их проектированию [3-5]. Мы рассмотрим технологию проектирования на основе минимального набора документов, описывающих как структурные, так и поведенческие стороны ОО программ. Эта технология, которую можно назвать объектно-ориентированным программированием с явным выделением состояний, предполагает совместное применение объектно-ориентированного и автоматного [6] подходов. Для иллюстрации методики воспользуемся примером разработки системы управления виртуальным танком для игры, которую предложила компания Alphaworks (robocode.alphaworks.ibm.com) в рамках коллективного учебного проекта Robocode.

Танки

Мы выбрали игру Robocode, поскольку в качестве языка программирования в ней использованы не специализированные средства, а один из широко распространенных объектно-ориентированных языков — Java. Отметим, что другая версия этой игры была предложена в качестве "разминки" для участников командного чемпионата мира по программированию ACM 2002 г.

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

Рис. 1. Фрагмент боя.

История создания танка делится на два этапа. Сначала был разработан нестреляющий танк (counterwallrobot.Cynical_1), который осенью 2001 г. оказался лучшим на открытом турнире, проводимом организаторами сайта http://robocode.isbeautiful.org. Затем была разработана "стреляющая" версия (Cynical_2), которая стабильно занимала в мировом рейтинге 5-6-е места. Программная документация для следующей версии (Cynical_3), разработанная в соответствии с предлагаемой технологией, размещена на сайте http://is.ifmo.ru в разделе "Проекты". Сейчас работы по модернизации танка не ведутся, но он по-прежнему входит в десятку лучших танков мира.

Автоматы

При объектном проектировании для описания поведения объектов наряду с другими используется и автоматная модель [4,5]. В работе [7] была предложена основанная на процедурном подходе технология создания ПО для систем логического управления, названная SWITCH-технологией. В ней для спецификации программ использовались графы переходов автоматов. Сейчас существует вариант этой технологии, предназначенный для построения событийных систем и охватывающий все этапы создания ПО, включая сертификацию и документирование. Этот подход получил название "программирование с явным выделением состояний" [6].

Известны среды разработки, использующие автоматы при визуальном программировании (например, пакет Stateflow [8]). По сравнению с используемыми в этих средах методами предлагаемый нами подход обеспечивает большую универсальность, так как не зависит от применяемых инструментальных средств.

Хотя при использовании объектной парадигмы применяются автоматы [5], при этом не делается акцент на явном выделении состояний. Так, в работе [9] в качестве одного из признаков объектно-ориентированного языка названо "поддержание им объектов как абстракции данных с определенным интерфейсом поименованных операций и скрытым состоянием". Да и само определение объекта в этом смысле мало что проясняет: "Объект — это сущность, способная сохранять свое состояние (информацию) и обеспечивающая набор операций (поведение) для проверки и изменения этого состояния" [10]. Это определение не позволяет конструктивно использовать автоматы, так как при большом числе свойств (атрибутов) количество состояний объекта может быть огромным, что делает невозможным выделение состояний в явном виде. Более того, явное выделение состояний обычно не выполняется и при небольшом количестве атрибутов.

Предлагаемый подход

Перечисленные выше трудности устраняются при соблюдении пяти условий.

1. Атрибуты объекта следует разделить на управляющие и остальные по аналогии
   с организацией машины Тьюринга или машины фон Неймана [11].
2. Управляющие (автоматные) состояния объекта, число которых обычно значительно
   меньше числа остальных состояний (например, "вычислительных"), нужно выделить
   явно.
3. При спецификации задачи следует рассматривать автоматные состояния в качестве
   абстракций, переходя к соответствующим им переменным только на этапе реализации.
   Это позволяет программисту отказаться от неупорядоченного введения "флагов"
   при программировании. Программы с флагами, а не с явно выделенными состояниями,
   неустойчивы, как слоны с тонкими ножками на одной из картин Сальвадора Дали.
   Однако такие слоны, в отличие от программ с флагами, не встречаются повсеместно.
4. Необходимо ввести в этап реализации программ новый подэтап, называемый в
   теории автоматов "кодирование состояний", и использовать многозначное кодирование
   для каждого автомата с целью различия его состояний по значениям одной переменной,
   обеспечив тем самым "наблюдаемость" программы.
5. Необходимо обеспечить протоколирование в терминах автоматов с целью проверки
   корректности построенной программы, представляющей собой систему взаимосвязанных
   объектов.

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

1. На основе анализа предметной области выделяются классы и строится
диаграмма классов, отражающая в основном наследование и агрегирование (например,
вложенность).

2. Для каждого класса разрабатывается словесное описание, хотя бы в
форме перечня решаемых задач.

3. Для каждого класса создается его структурная схема, напоминающая
карту CRC (Class-Responsibility-Collaboration, [12]). Нотация, используемая
при построении структурных схем классов, приведена на рис. 2.

Рис. 2. Нотация, используемая при построении структурных схем классов.

Интерфейс класса образуют открытые (public) и защищенные (protected) атрибуты и методы, к которым обращаются другие объекты. Эти методы, в свою очередь, вызывают закрытые (private) методы рассматриваемого класса. Закрытые методы можно разделить на две части — автоматные и остальные. Автоматные методы в общем случае делятся на три разновидности: реализующие автоматы; реализующие входные переменные; реализующие выходные воздействия.

4. При наличии в классе нескольких автоматов строится схема их взаимодействия
[6].

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

6. Для каждого автомата разрабатывается словесное описание.

7. Для каждого автомата с помощью правил, изложенных в [6], строится
схема связей, определяющая его интерфейс. В этой схеме в качестве событий (наряду
с другими) могут быть указаны сообщения, получаемые объектом и приведенные в
структурной схеме класса.

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

8. Для каждого автомата на основе нотации, приведенной в [6], строится
граф переходов.

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

Благодаря такому подходу методы, соответствующие входным переменным и выходным воздействиям автомата, могут быть виртуальными (virtual) и переопределяться в порождаемых классах. Таким образом можно создать базовый класс для управления некоторой группой "устройств", в котором реализуются только автоматы, а используемые ими входные переменные и выходные воздействия переопределяются на уровне порождаемых классов, управляющих конкретными "устройствами".

10. Для изучения поведения программы (определяемого, в частности, взаимодействием
объектов), а в ходе разработки — и для ее отладки автоматически строятся
протоколы, описывающие работу всех автоматов в терминах состояний, переходов,
входных переменных и выходных воздействий с указанием соответствующих объектов.
Это обеспечивается путем включения функций протоколирования в соответствующие
методы. При необходимости могут протоколироваться и аналоговые параметры.

11. Выпускается созданная в ходе проекта документация.

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

Этапы процесса создания программы соответствуют предлагаемой технологии.

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

Рис. 3. Диаграмма классов.

Среда формирует определенные правилами игры события и вызывает их обработчики, объявленные в классе Robot. Эти обработчики наследует класс AdvancedRobot. Указанные классы реализуют методы, обеспечивающие непосредственное управление танком путем опроса и установки его параметров в среде исполнения.

По принятым правилам программа должна состоять из одного класса, порожденного классом Robot или AdvancedRobot. Название содержащего программу пакета counterwallrobot вместе с названием головного класса образует название танка. Головной класс "Супервизор" в рассматриваемой программе имеет имя Cynical и содержит шесть вложенных классов: "Стрелок", "Водитель", "Радар", "Список целей", "Цель" и "Вектор". Класс "Стрелок" — это система управления стрельбой, класс "Водитель" — система управления маневрированием, а класс "Радар" — система управления радаром. На диаграмме в классах, содержащих автоматы, указаны обозначения этих автоматов.

Рассмотрим проектирование классов на примере класса "Стрелок", содержащего два автомата А1 и А2. Этот класс предназначен для управления стрельбой и решает следующие задачи: выбор цели; анализ параметров цели и расчет упреждения; управление пушкой; определение скорости охлаждения пушки.

Структурная схема класса "Стрелок" приведена на рис. 4. Интерфейс его состоит из трех обработчиков событий и метода, возвращающего вызвавшему его объекту текущее положение пушки.

Рис. 4. Структурная схема класса "Стрелок".

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

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

Рис. 5. Схема взаимодействия автоматов класса "Стрелок".

В этапах 5 и 6 (составление перечней событий, входных переменных и выходных воздействий, разработка словесного описания) в данном случае нет необходимости.

Схема связей автомата A1 приведена на рис. 6. Отметим, что в этой схеме — в отличие от структурной схемы класса — на линиях указываются не названия сообщений, а названия входных и выходных воздействий. Например, выходное воздействие z30, названное "Выбрать цель" (рис. 6), осуществляет выбор цели, передавая объекту класса "Список целей" сообщение "Вернуть ближайшую цель" (см. рис. 4).

Рис. 6. Схема связей автомата управления стрельбой.

Граф переходов автомата A1, построенный на этапе 8, приведен на рис. 7.

Рис. 7. Граф переходов автомата управления стрельбой.

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

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

Документация на программу в целом, разработанная на основе предлагаемого подхода
и включающая ее полный текст, приведена на сайте http://is.ifmo.ru
в разделе "Проекты". Отметим, что использование состояний, помимо прочего, уменьшает
вероятность того, что программа не успеет выполнить необходимые расчеты в отведенный
ей интервал времени. Так, например, из рис. 7 следует, что точный расчет упреждения,
занимающий значительное время, выполняется только в состояниях 2 и 3, в которых
автомат находится гораздо меньшее время, чем в остальных состояниях, в которых
расчет упреждения выполняется грубо.

Сравнение с UML

Предложенный подход, по мнению авторов, может служить альтернативой процессу проектирования [13], принятому при использовании UML, описание которого весьма громоздко [5]. Язык UML затруднительно применять при разработке систем со сложным поведением, так как в этом случае диаграммы последовательностей и взаимодействий практически невозможно построить вручную.

Мнение о сложности использования UML разделяют многие специалисты. Говоря о книге "трех друзей" ([13]), автор [2] пишет: "Когда вы в первый раз сталкиваетесь с языком UML, кажется, что его невозможно понять — такое там множество диаграмм и мелочей. Во втором издании книги [12] ее авторы утверждают, что большая часть всего этого попросту никому не нужна, и поэтому они отбрасывают малозначительные детали и говорят только о самом главном из имеющегося в языке".

Мы в настоящей работе пошли дальше, а именно:

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

Заключение

Описанный здесь подход — это продолжение работ авторов, направленных на широкое внедрение таких понятий, как "состояние" и "автомат", в инженерное программирование (Software Engineering). Он берет начало в теории автоматов и в проектировании систем управления. В этой статье изложена первая редакция предлагаемой концепции для рассматриваемого класса задач, в дальнейшем она будет усовершенствоваться. В частности, автоматы могут реализовываться не в виде методов класса, а отдельными классами. Кроме того, каждое состояние можно рассматривать как отдельный объект [15].

Подчеркнем, что объектно-ориентированное программирование с явным выделением состояний базируется на двух парадигмах — объектной и автоматной. При этом если "объектный подход предоставляет программисту средства для решения задачи в ее пространстве" [2], то автоматный подход — средства для описания поведения объектов в терминах пространства состояний. Применение автоматов проясняет поведение программы так же, как применение объектов проясняет ее структуру.

Авторы надеются, что предложенный подход внесет определенный вклад в инженерное программирование. В необходимости такого программирования, по словам Г. Буча, "многие сомневаются", а "Б. Гейтс публично заявляет, что не верит в диаграммы и не желает, чтобы его программисты занимались проектированием" [14]. И это при наличии в выпускаемом Microsoft и другими разработчиками программном обеспечении огромного числа ошибок, которые в системах, управляющих ответственными объектами, недопустимы вовсе. Однако в последнее время формальные методы (например, на основе абстрактных машин состояний при построении спецификаций [16]) начинают использоваться и в Microsoft.

Подход, основанный на применении автоматов в программировании, был использован авторами и в других проектах. Некоторые из них описаны на сайте http://is.ifmo.ru в разделе "Проекты". Кроме того, предлагаемая технология с 1991 г. применяется при создании систем управления технологическими процессами, в том числе и на программируемых логических контроллерах [7].

Данная работа была выполнена на кафедре "Компьютерные технологии" Санкт-Петербургского
государственного института точной механики и оптики (технического университета)
при поддержке Российского фонда фундаментальных исследований по гранту № 02-07-90114
"Разработка технологии автоматного программирования".

 

Литература 1. Страуструп Б. Язык программирования Си++. М.: Бином, СПб.: Невский диалект, 1999. 2. Эккель Б. Философия Java. СПб.: Питер, 2001. 3. Буч Г. Объектно-ориентированный анализ и проектирование с примерами приложений на С++. М.: Бином, СПб.: Невский диалект, 1998. 4. Терехов А. Н., Романовский К. Ю., Кознов Д. В. и др. REAL: Методология и CASE-средство разработки информационных систем и программного обеспечения систем реального времени //Программирование. 1999. № 5. 5. Буч Г., Рамбо Д., Джекобсон А. UML. Специальный справочник. СПб.: Питер, 2002. 6. Шалыто А. А., Туккель Н. И. Программирование с явным выделением состояний //Мир ПК. № 8, 9. 7. Шалыто А. А. SWITCH-технология. Алгоритмизация и программирование задач логического управления. СПб.: Наука, 1998. 8. Дьяконов В. Simulink 4. Специальный справочник. СПб.: Питер, 2002. 9. Фридман А. Л. Основы объектно-ориентированной разработки программных систем. М.: Финансы и статистика, 2000. 10. Jacobson I. et al. Object-Oriented Software Engineering. NJ: Addison Wesley, 1992. 11. Шалыто А. А., Туккель Н. И. От тьюрингова программирования к автоматному //Мир ПК. 2002. № 2. 12. Фауллер М., Скотт К. UML в кратком изложении. Применение стандартного языка объектного моделирования. М.: Мир, 1999. 13. Booch G., Rumbaugh J., Jacobson I. The Unified Software Development Process. NJ: Addison-Wesley, 1999. 14. Программы следующего десятилетия //Открытые системы. 2001. № 12. 15. Гамма Э., Хелм Р., Джонсон Р. и др. Приемы объектно-ориентированного проектирования. Паттерны проектирования. СПб.: Питер, 2001. 16. Gyrevich Y. et al. Using Abstract State Machines at Microsoft: A Case Study /Proceeding of ASM'2000 in "Abstract State Machines: Theory and Applications". Lecture Notes in Computer Science. 2000. V.1912.