24 мая 2009 в 20:48

Implementing FSM

В статье рассказывается о разработанной автором миниатюрной Java библиотеке, позволяющей коротко и наглядно определять конечные автоматы. Библиотека, назовем ее AkerFSM, доступна в Google Code.
В первой части статьи сформулированы предпосылки и требования к библиотеке. Во второй части приводится абстрактный пример использования библиотеки. В третьей части рассмотрены важные моменты устройства самой библиотеки. Четвертая часть посвящена рассмотрению упрощенного примера из реальной жизни, в котором с помощью конечного автомата задается поведение одного из контроллеров в GWT-приложении.


Предпосылки


Существуют различные способы реализации конечного автомата. До момента создания предлагаемой библиотеки, самым удачным я считал способ, при котором используется оператор switch, осуществляющий выбор по текущему номеру состояния. Пример кода можно посмотреть здесь, а сам подход, фигурирующий под названиями «SWITCH-технология» и «Автоматное программирование», подробно описан в находящихся на упомянутом сайте статьях Шалыто и Туккеля.
При всей своей простоте, реализация оператором switch совсем не вписывается в объектно-ориентированную парадигму и из-за этого не позволяет в полной мере использовать возможности современных языков. Поэтому я задался целью создать реализацию, отвечающую следующим требованиям:
  • автомат задается также наглядно и лаконично, как и при использовании оператора switch
  • реализация является объектно-ориентированной
  • реализация поддерживает все возможности автоматного программирования

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

Абстрактный пример


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



Теперь определим сам автомат и метод, который его создаст:



Чтобы использовать автомат, остается создать его объект и вызывать для обработки событий метод handleEvent(), передавая событие в качестве параметра:



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

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


Особенности устройства библиотеки


Основными классами библиотеки являются State и FSM, назначение которых очевидно. Оба класса легко могут быть расширены, что будет продемонстрировано ниже.
Классы объявлены следующим образом:




Дженерик STATES задает enum, в котором хранится множество состояний автомата. Дженерик EVENT задает класс для обрабатываемых автоматом событий. В реальном приложении в EVENT будет указываться базовый класс события, используемый в вашем событийном механизме. В рассматриваемых примерах для упрощения используется String.
Три метода класса State: enter(), handleEvent() и exit(), предназначены для переопределения при создании конкретных состояний. enter вызывается, когда автомат переходит в рассматриваемое состояние, handleEvent — при обработке события, и exit, соответственно, когда автомат покидает рассматриваемое состояние. Эти методы реализуют паттерн Template Method, поэтому при их переопределении вызов super не обязателен.
Вместе с классом State при определении автомата может использоваться его потомок, класс SuperState (State и SuperState совместно реализуют аналог паттерна Composite). Назначение SuperState — реализация общего поведения для группы состояний, например группового перехода.
Метод State.toString() возвращает название и порядковый номер состояния (да здравствует enum!) Аналогичным образом определены и методы FSM.toString() и SuperState.toString().
Поведение класса FSM при вызове метода handleEvent() следующее:
  • вызвать handleEvent() текущего состояния и текущих групп состояний
  • определить следующее состояние (групповые переходы имеют приоритет над обычными)
  • вызвать exit() текущего состояния и всех групповых состояний, которые будут покинуты при переходе
  • вызвать enter() нового состояния и всех групповых состояний, в которые попадаем при переходе
  • выполнять переходы до тех пор, пока результат определения следующего состояния не станет равен null

Кроме этого, FSM реализует 14 событий, для которых можно назначить обработчики, переопределяя либо конкретные методы-обработчики событий, либо метод, вызываемый при возникновении любого из событий. Примером использования обработчиков событий являются классы MonitoredFSM и LoggedFSM.
Наилучший способ более детально разобраться в поведении библиотечных классов — прогнать в отладчике JUnit-тесты, идущие в комплекте с библиотекой. Эти тесты специально были написаны таким образом, чтобы быть примером использования библиотеки и иллюстрацией логики ее работы.

Бонус Исходные коды библиотеки нормально компилируются GWT


Пример из реальной жизни


Теперь рассмотрим пример, более приближенный к реальной жизни. Создадим GWT-приложение, по нажатию кнопки отображающее на экране некую форму. При отображении формы необходимо в два этапа загрузить данные с сервера — сначала выполняется загрузка конфигурации формы, а потом — загрузка данных для отображения на форме. Форма может быть закрыта по нажатию кнопки. Процесс загрузки может быть прерван пользователем. В процессе загрузки должен отображаться прогресс-индикатор с названием выполняемой операции.
Автомат будет иметь пять состояний:



Кроме обычных состояний, определим также два групповых состояния. Первое будет включать состояния LOADCONFIG и LOADDATA и служить для обработки события «RPCFailure». Второе будет включать состояния LOADCONFIG, LOADDATA и SHOW и служить для обработки события «HideEvent».
Осталось реализовать прогресс-бар. Сделать это можно очень элегантным и универсальным способом, который подойдет не только для нашего абстрактного приложения, но и для большинства аналогичных задач.
Во-первых, используем вместо FSM класс MonitoredFSM, который реализует паттерн Observer. Это позволит нам подключить свой обработчик события смены состояния автомата (другой способ — самим переопределить метод onAfterSwitchState() класса FSM).
Во-вторых, породим от класса State класс ProgressState. Он будет отличаться от предка наличием задаваемого в конструкторе описания состояния.
В-третьих, определим callback для нашего экземпляра класса MonitoredFSM следующим образом:



При каждом переходе в состояние типа ProgressState этот callback будет отображать прогресс-индикатор, в котором будет указано описание текущего состояния, номер текущего состояния и общее количество состояний. При переходе в обычное состояние прогресс-индикатор будет исчезать.
Как можно заметить, я слегка схалявил с отображаемыми номерами текущего состояния и общего количества состояний (будет выводиться «2/5» и «3/5», в то время как более логичным с точки зрения пользователя было бы выводить «1/2» и «2/2»). Возможные решения этой проблемки описывать не буду, лишь скажу, что полезным может оказаться класс EnumSet и его статические методы.
Собрав все вместе, получим следующее определение автомата (в состояниях LOADCONFIG и LOADDATA проиллюстрированы разные способы обработки внешних воздействий):



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



Обработчики RPC-запросов будут иметь следующий вид:



Как следует из двух последних фрагментов кода, мы одним махом разобрались с задачей аккуратной реализации асинхронной части GWT-приложения, создав для этого простой и универсальный паттерн. Причем паттерн этот идентичен и для обработчиков RPC-запросов, и для обычных обработчиков событий.
Исходные тексты библиотеки доступны в Google Code. В папке trunk/fsm находится сама библиотека и JUnit-тесты, а в папке trunk/gwt_fsm — рассмотренное в качестве примера GWT-приложение.

Выводы


Библиотека AkerFSM поддерживает все возможности автоматного программирования:
  • явное выделение и кодирование состояний конечного автомата
  • наглядное и лаконичное определение конечного автомата, внешне похожее на оператор switch
  • поддержка автоматов разных типов (Мили, Мура, смешанный)
  • поддержка событийных и вычислительных автоматов (причем с возможностью смешивать две эти модели в одном автомате)
  • поддержка вложенных автоматов
  • поддержка групповых переходов
  • возможность логгирования в терминах конечного автомата

Кроме поддержки перечисленных возможностей автоматного программирования, библиотека AkerFSM обладает двумя принципиальными достоинствами:
  1. Бизнес-логика отделена от технологического кода. Действительно, логика работы конкретного автомата (бизнес-логика) задается отдельно от кода, реализующего саму модель конечного автомата. Реализацию модели при этом можно переопределять и расширять независимо от конкретных автоматов, «декорируя» бизнес-логику требуемыми технологическими операциями.
  2. Библиотека является объектно-ориентированной, при этом базовые классы библиотеки сделаны легко расширяемыми.

Благодаря этим достоинствам, возникает множество преимуществ и возможностей для расширения. Перечислим некоторые из них
  1. Возможность в одном блоке кода определять действия, выполняемые при проверке условий перехода, при входе в состояние и при выходе из него.
  2. В отличие от упомянутых выше публикаций по автоматному программированию, в которых «групповой переход» присутствует лишь в виде элемента графической нотации, и никак не подержан в имплементации, библиотека AkerFSM полноценно реализует понятие «группового состояния». Для группового состояния, также как и для обычного, можно определить условия переходов, а также действия, выполняемые при входе в групповое состояние и выходе из него.
  3. Переход от модели конечного автомата к модели сети Петри осуществляется несложным расширением класса FSM.
  4. Также просто можно создать модель автомата, умеющую хранить историю переходов.
  5. Реализация паттерна Strategy совместно с классом FSM позволяет отделить автомат от класса, которым он управляет. Это, в частности, дает возможность проводить JUnit тестирование автомата, полностью изолировав его от остальной части приложения.
  6. Класс State (совместно с классом FSM) реализует паттерн State. Простейший вариант его использования в этой роли требует лишь определить интерфейс со специфическими для вашей задачи операциями и реализовать этот интерфейс в необходимом количестве потомков класса State. Хотя «Банда четырех» в описании паттерна State и пишет о том, что определение логики переходов внутри конкретных состояний вносит «реализационные зависимости между подклассами», архитектура библиотеки AkerFSM лишена этого недостатка. В нашем случае логика переходов между состояниями определяется конечным автоматом и записывается в конкретных классах состояний, но зависимость между ними при этом отсутствует.
  7. Возможно расширение класса FSM, которое позволит изменять определение автомата в процессе выполнения (добавлять, удалять и заменять состояния).


Подводя итог, можно утверждать, что библиотека AkerFSM существенно превосходит реализации, описанные в книге Полкарповой, Шалыто «Автоматное программирование».

PS. Уверен, что на Groovy или на Ruby аналогичную реализацию можно сделать еще более красивой.

Cynical @Red_Dragon_DVL
карма
20,0
рейтинг 0,0
Похожие публикации
Самое читаемое Разработка

Комментарии (31)

  • +4
    Шалыто будет счастлив :)
    • 0
      Я так думаю, что уже рад =))
  • 0
    Какие недостатки у этой библиотеки? Интересны примеры систем, где UI реализован на конечных автоматах?
    • 0
      Имхо это слишком накладно ;) Даже простое приложение насчитывает десятки событий, какой смысл описывать их с помощью КА? В конце-концов, та же стандартная событийная система — это тот же автомат.
    • 0
      Недавно реализовал Веб-интерфейс приложения используя конечный автомат. Бибилиотекой не делал, все реализовал в одном классе. Главной целями ставил:
      — Чтобы можно бы было нарисовать удобночитаемую диагррамку состояний интерфейса.
      — Чтобы код соответствовал диаграмме.
      — Чтобы легко было бы перемещаться от кода к диаграмме и наоборот.
      — Чтобы легко можно бы было разбираться/добавлять/удалять состояния и действия.
      Думаю, что поставленные цели достигнуты.
      • 0
        Можно ссылку или код класса с конечной машиной?
        • +1
          Хочу вот статеечку в блог родить по этому поводу.
          Сейчас могу вкратце на пальцах объяснить. Реализовано на Python. Все на стороне сервера.
          1. Переходы из состояния в состояние по запросу от браузера. В запросе параметр tostate=«state to go to». FSM помнит предыдущее состояние.
          2. Есть словарь переходов. В этом словаре ключом является строка вида «prev_state» + «next_state». Значением строки является массив названий функций, которые необходимо выполнить при выполнении перехода. Функции работают с атрибутами класса и являются интерфейсом к ядру программы.
          3. Метод обработки переходов запоминает предыдущее состояние и последовательно исполняет функции из массива функций перехода.
          4. Состояния сделаны двух видов одни состояния условно называются «Show» (показать страницу), другие «Action» они например выполняют проверку формы и в зависимости от результатов переходят в одно из состояний типа «Show».
          5. Последняя функция в массиве функций перехода возвращает для перехода в состояние типа «Show» html код для передачи серверу, для состояния типа «Action» — имя состояния, в которое перейти.
          Ну вот, вроде и все. Пока готова первая версия. Она включает 20 состояний и 38 переходов.
          • 0
            Дополнено к пункту 3.:
            Конечно совершенно необязательно было делать массивы функций. Можно было сделать переходы и через вложенные вызовы функций. Массивы были выбраны для того, чтобы в совокупности с говорящими названиями исполняемых функций получить в одном месте (в словаре перехода) удобочитаемые цепочки исполняемых для перехода действий.
            Пример, один ключ/значение словаря (значение тоже словарь):
                        # 23
                        'page_pg_block_add':{'type':'Act','methods':[self.fsm_pg_block_add,
                                                                     self.fsm_diag_files_rm,
                                                                     self.fsm_create_cur_page_diag_files,
                                                                     self.fsm_page_cur_save,
                                                                     self.fsm_go_to_page]},
            

            # 23 — номер перехода по диаграмме
      • 0
        У меня есть знакомый, который сделал веб-интерфейс на конечных автоматах на лиспе :)
        • 0
          Чтобы убить окончательно, надо дописать «в реальном проекте» :-)
          • 0
            Говорил, что пока готов только движок :)
            Кроме этого он реализовал на лиспе движок 3d моделлирования. К сожалению не знаю имени, знаю только что он преподаёт в Политехе.
  • 0
    Шалыто набивает себе references для Википедии.
    • 0
      Шалыто не имеет к этой статье отношения. Не считая того, что он в ней упомянут.
      Ну а тебе, судя по-всему, очень хотелось высказать мнение, не имеющее отношения к содержанию статьи.
      • +2
        Шалыто — довольно примечательная личность, встреча с ним — всегда мини-спектакль :)
  • НЛО прилетело и опубликовало эту надпись здесь
  • 0
    Очень интересно. Я, правда, не очень понимаю где в web-разработке применять FSM. Вот во встроенных системах раздолье.
  • 0
    Спасибо за библиотеку!
    (Прелестно! Просто прелестно! Получите заслуженный плюс)

    0. Надеюсь вы будете её дальше поддерживать и развивать?

    1. Ещё не разобрался, ответьте, пожалуйста, содержательно:

    Как там с шаблоном «Команда» (pattern «Command») для представления смен состояния как команд? Как проще всего сделать этот шаблон на вашей библиотеке?

    Конкретно интересует такая особенность «Команды» как возможность кэширования команд, направить их в очередь, в очередь с приоритетами, сохранить, сделать транзакции и откат транзакции.
    • –1
      Пожалуйста.
      Развивать не буду, если не понадобится в рамках работы. В данный момент всего хватает.

      Насчет паттерна Command, не совсем понял, что ты имеешь ввиду. Мне в голову приходит только команда, у которой в имплементации самой команды встречается вызов автомата.
      Насчет аналога отката транзакций, в ИТМО народ при разработке обучающего портала для иллюстрации алгоритмов придумал делать автоматы, которые моделируют как движение «вперед» по алгоритму, так и движение «назад». На is.ifmo.ru про это когда-то давно была статья.
      • 0
        На мой взгляд, в исходном коде не хватает комментариев, что является неким неудобством в понимании принципов работы.
        Раз уж развитие библиотеки Вами не предвидится, то может дадите толчек к развитию некоторого сообщества разработчиков? Ибо предвижу: скачивания из SVN вечной(???) 6й ревизии, и локальные разработки будет лишь плодить бесчисленные клоны, итерация за итерацией теряя основную нить…

        Я бы поддержал этот проект. Если что — напишите в ЛС. Тем более тема подобной библиотеки для меня актуальна.
        • 0
          Не комментировал исходя из принципа «не комментируйте очевидное». Сам по себе код там очень простой, его мало, неочевидных моментов нет. А чтобы в целом понять, как работает FSM, смотрите юнит-тесты (они, в отличие от комментариев, не врут).
          Сообщество, развитие библиотеки и т.п. — это мне неинтересно. Я в данном случае просто поделился удачной идеей, но каких-либо качественных направлений в развитии библиотеки пока не вижу.

          Если тебе интересно заняться централизованной поддержкой и развитием библиотеки — ничего не имею против. Могу дать доступ в проект на Google Code, а коллеги с www.devprom.net уже предлагали захостить проект у них.
  • 0
    Насколько просто составить композицию двух и более FSM?
    • 0
      Технически – несложно. Есть три способа.
      1. Один автомат в своих условиях переходов проверяет, в каком состоянии находится другой автомат. Можно делать это явно (что-то вроде a1.y() == A.READY), но обычно такие проверки спрятаны в методах – getter'ах того класса, которым управляет автомат a1.
      2. Один автомат вызывает другой автомат из своих действий, выполняемых в enter() или в exit(). Как и в предыдущем случае, можно явно вызвать a1.handleEvent(), но обычно этот вызов спрятан в методах того класса, которым управляет автомат a1.
      3. Третий вариант самый интересный – вложенные автоматы. Один автомат как-бы расширяет поведение другого автомата для одного (или нескольких) из его состояний. В этом случае handleEvent() одного автомата вызывается из handleEvent() другого (а также, при необходимости, и их enter() и exit()). Пример в файле FSMTestIncl.java.
  • 0
    Я так понимаю в ExtGWT реализован похожий подход?
    • 0
      Не видел… Можно линк?
      • 0
        Сори, я почемуто подумал что ExtGWT также известен для GWT разработки, как Spring и Hibernate для серверной java.
        Линк: extjs.com/products/gxt/
        • 0
          Я не это имел ввиду. Естественно я знаю и про GXT, и слегка внутри GXT. Но реализации конечного автомата там не видел. Именно на описание этой реализации я и просил линк — интересно посмотреть, как сделано у них. И сделано ли вообще, повторю, что не заметил в этой библиотеке подобных классов.
          • 0
            • 0
              Ни разу не оно.
              В GXT есть простенькая база для реализации MVC (Observable, Event Dispatcher, Binding), не более того.
              • 0
                я поэтому и спрашиваю что не пойму отличается или нет, реализация там конечная иная (как минимум инты вместо енумов) но по сути ведь тоже самое? или есть важная какаято тонкость которую я не могу заметить?
                • 0
                  Есть тонкость — моя библиотека это про конечные автоматы, а в GXT своей имплементации конечных автоматов нет.
  • 0
    > PS. Уверен, что на Groovy или на Ruby аналогичную реализацию можно сделать еще более красивой.

    Если кого-то это интересует, вот довольно яркий пример, как это выглядит с использованием предметно-ориентированных языков (DSL): www.youtube.com/watch?v=KTmwXr52cwM

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.