УНИВЕРСИТЕТ ИТМО
Кафедра «Технологии программирования»

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

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

Предисловие авторов к статье "Автоматы и танки"

Предлагаемая статья была написана почти полтора года назад - в ноябре 2001 года.

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

Были ли эти восемь месяцев потеряны зря? Хочется верить, что не совсем, ведь благодаря замечаниям редактора "Открытых систем" Руслана Богатырева мы сократили и, во многом, улучшили статью, что позволило нам в конце концов ее опубликовать. А еще за это время мы успели закончить и опубликовать в Интернете полную проектную документацию (http://is.ifmo.ru, раздел "Проекты") на рассмотренный в статье пример и начали работу по переводу статьи на английский.

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

До сих пор не совсем понимаем причину отказа. Как может быть неинтересна читателям профессионального программистского журнала статья, которая посвящена изложению новой технологии программирования и в качестве примера рассматривает находящуюся в тот момент на пике популярности программистскую игру "Robocode", количество скачанных копий которой уже давно перевалило за миллион?

Кстати, в данный момент наша статья "существует", а журнал "Программист" - нет.

Нас уже начали было терзать сомнения: а вдруг наша статья действительно неудачная и "дурная"? Но эти сомнения исчезли после появления статьи:

Озеров А.А. Четыре танкиста и компьютер // Магия ПК. - 2002. - № 11. (http://is.ifmo.ru, раздел "О нас").

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

В результате у нас появилось шутливое (отчасти) подозрение, что в отечественных изданиях, посвященных информационным технологиям, существует негласный запрет на публикации с критикой UML - "священной коровы" современного программирования, о которой примерно раз в месяц выходит книга на английском или русском языке. При этом ни в одной из этих книг нет ни одного проекта, выполненного целиком (постановка задачи - проектирование - реализация). Каждый раз чего-то не хватает. То пишут целые книги про одни случаи использования, то толстые книги про спецификации без примеров, то и вовсе нечто невнятное. Другой тип книг - про реализацию без проектирования.

Вспомнили, что в 47-м (декабрьском) номере за 2001 год еженедельника "PC WEEK/RE" мы читали статью Андрея Колесова, в которой он написал, что преподаватели вузов за полтора года его работы в журнале "BYTE/Россия" не представили ни одной статьи. Написав соответствующее письмо, мы отправили ему сокращенную версию статьи, попросив опубликовать ее в указанном журнале. Довольно быстро нам пришел ответ с согласием на публикацию и с уже до боли привычной оговоркой о необходимости ее дальнейшего сокращения и внесения некоторых изменений.

К октябрю 2002 года мы закончили очередную корректировку статьи и, наконец, окончательно ее согласовали.

В январе 2003 года мы получили рецензию из журнала "Программирование" на полную версию нашей статьи. Статья более года находилась на рецензировании в журнале. Полученная рецензия была отрицательной. При этом кроме вполне справедливых замечаний рецензента о, например, некоторой субъективности нашей критики в адрес UML, рецензия содержала и довольно странные замечания. Одно из них заключалось в том, что громоздкость диаграмм, применяемых в UML, является неустранимым недостатком любых графических способов спецификации, и поэтому как недостаток рассматриваться не может. Объяснялось это тем, что всегда найдется система достаточно сложная для того, чтобы ее графическое описание вышло за пределы физиологических способностей человека вне зависимости от используемой графической нотации. Странно, что рецензент упускает из виду тот факт, что при использовании, например, диаграмм Statecharts или SDL указанный физиологический предел достигается гораздо раньше, чем при использовании нотации, предложенной нами, которая в дополнение к этому является еще и более наглядной и строгой. Тем, кто в этом сомневается, в очередной раз предлагаем попробовать перерисовать с использованием Statecharts или SDL граф переходов автомата A0, приведенный в документации на систему управления дизель-генераторами (http://is.ifmo.ru, раздел "Проекты"). Вступать в дискуссию по вопросам применения UML не стали.

В итоге наша статья, сильно изменившаяся и сокращенная более чем в два раза, была опубликована в февральском номере журнала "BYTE/Россия" за 2003 год. Мы хотим выразить благодарность, в первую очередь, заместителю главного редактора этого журнала Андрею Колесову, а также всем, кто помог нам довести эту статью до "победного конца".

Любые совпадения названий журналов и издательств с реально существующими следует рассматривать как случайные :).

Дополнение

Первоначально документация на танк была опубликована на сайте http://www.softcraft.ru, и мы получили по ней несколько замечаний. Основные замечания состояли в следующем:

• реализация является недостаточно объектной, а имеет место "оборачивание" автоматов классами. В частности, предлагалось реализовывать автоматы отдельно от объектов, которыми они управляют (разделить душу и тело :);
• реализацию автоматов целесообразно выполнять не с помощью конструкции switch, а применяя паттерн "State";
• программа должна быть самодокументирующейся. Названия всех переменных должны быть смысловыми.

Для выяснения справедливости этих замечаний студент кафедры "Компьютерные технологии" СПбГИТМО (ТУ) Денис Кузнецов (двукратный призер студенческих командных чемпионатов мира по программированию ACM 2000 и 2001 гг.) выполнил рефакторинг нашего проекта - изменил структуру кода без изменения его функциональности с целью учета указанных замечаний. Это удалось ему сравнительно просто, так как проект-прототип был полностью документирован, что позволило сохранить как схемы связей и графы переходов автоматов, так и практически все функции входных и выходных воздействий.

В приложении к статье содержатся два варианта реализации класса "Стрелок" (на основе паттерна "State" и предложенный в статье, когда автоматы являются методами классов), в которых обозначен путь от запуска автомата до завершения его работы. Авторы считают, что предложенный в статье подход является более целесообразным.

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

Сокращенная версия статьи опубликована с названием "Танки и автоматы" в журнале "BYTE/Россия", 2003. №2. C.69-73.

АВТОМАТЫ И ТАНКИ

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

Анатолий Шалыто, Никита Туккель

Аннотация

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

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

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

Авторы надеются, что предложенный подход внесет определенный вклад в инженерное программирование, в необходимости которого, по словам Г. Буча, многие сомневаются, а Б. Гейтс публично заявляет, что не верит в диаграммы и не желает, чтобы его программисты занимались проектированием (Программы следующего десятилетия // Открытые системы. 2001. №12). И это при наличии огромного числа ошибок в выпускаемом программном обеспечении, которые в системах, управляющих ответственными объектами, недопустимы вовсе.

Следует отметить, что несмотря на использование автоматов в некоторых известных методологиях объектной разработки программ, явное выделение состояний не характерно для объектной парадигмы. Например, одним из критериев объектно-ориентированного языка является "поддержание им объектов как абстракции данных с определенным интерфейсом поименованных операций и скрытым состоянием". Да и само определение объекта, предложенное одним из "трех друзей" (являющихся создателями объектно-ориентированного проектирования) А. Джекобсоном, в этом смысле мало что проясняет: "Объект - это сущность, способная сохранять свое состояние (информацию) и обеспечивающая набор операций (поведение) для проверки и изменения этого состояния".

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

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

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

Исходя из целей настоящей работы, авторов интересовала игра, которая в качестве языка программирования использовала бы не специализированный язык, а один из широко распространенных объектно-ориентированных языков. Единственной известной авторам игрой (в 2001 году), отвечающей этому требованию, являлась разработанная компанией "Alphaworks" игра "Robocode" (http://robocode.alphaworks.ibm.com). В 2002 году эта ситуация несколько изменилась: другая версия этой игры была предложена в качестве "разминки" для участников командного студенческого чемпионата мира по программированию ACM. К играм этого класса относится также и разработанная фирмой Microsoft игра "Terrarium" (http://www.terrariumgame.net).

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

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

Полная проектная документация на рассмотренный в статье пример приведена на сайте http://is.ifmo.ru в разделе "Проекты".