Источник: http://www.rsdn.ru/article/alg/Static_Finite_State_Machine.xml
Машина с конечным числом состояний (FSM, Finite State Machine, или как принято называть по-русски, конечный автомат, КА) представляет собой одну из наиболее полезных концепций в арсенале разработчика. Существует несколько методик реализации конечных автоматов, но, забегая вперед, хочется сказать, что достойный результат дают только те из них, которые связаны с генерацией кода. Возможности, предоставляемые последней версией стандарта C++ и реализованные в последних версиях компиляторов, позволяют генерировать код во время компиляции основного кода проекта. Это дает возможность избежать использования отдельных утилит или расширений IDE и, оставаясь в рамках единого языка (C++), создавать приемлемые для практического использования реализации КА, которые при этом легко поддерживать и развивать.
Однако обо всем по порядку.
Ценность программы заключается не только в том, что она умеет делать сегодня, а, главным образом, еще и в том, что она сможет сделать завтра. Kent Beck.
Простым примером КА является турникет в метрополитене (пример взят из [1]). Этот пример будет рассматриваться как отправная точка в дальнейших рассуждениях.
Рисунок 1
Представленная выше диаграмма перехода между состояниями (state transition diagram, STD) читается следующим образом:
Первый способ реализации заключается в использовании вложенных операторов switch/case (или if/else).
Листинг 1. switch/case реализация.class Turnstile { public: enum State { Locked, Unlocked }; enum Event { COIN, PASS}; void postEvent(Event event) { switch(currentState_) { case Locked : switch(event) { case COIN: currentState_ = Unlocked; unlock(); break; case PASS: alarm(); break; } case Unlocked : switch(event) { case COIN: thankyou(); break; case PASS: currentState_ = Locked; lock(); break; } } } private: State currentState_; private: // block A ‘activities’ void lock() {/*…*/}; void unlock() {/*…*/}; void alarm() {/*…*/}; void thankyou() {/*…*/}; }; |
Данная реализация очень проста и эффективна, но она может быть применима только к КА, взятому нами в качестве примера и, что очень важно, при условии, что спецификация КА не будет подвержена изменениям в дальнейшем. Известно, что, как правило, сопровождением ПО занимаются люди, изначально не принимавшие участие в его создании. Код, написанный в таком стиле и реализующий несколько десятков событий и состояний, практически становится не поддерживаемым, поскольку логика сильно размыта и не ясна. Опасность внесения ошибок очень велика, а их исправление, в свою очередь, может привести к появлению новых (код реализации КА может генерироваться автоматически по высокоуровневому описанию, что снимает проблемы поддержки и изменения спецификации, а поскольку реализация КА с использованием switch является одной из самых эффективных, то этот способ давно и успешно используется в различных генераторах кода, например, в генераторах парсеров YACC/LEX – прим.ред.).
Вторая неприятность – это непостоянство, свойство, очень часто не принимаемое в расчет. Непостоянство – это проявление реальности. Природа данного феномена вполне очевидна – изменение бизнеса, неполные и противоречивые требования на всех этапах производства ПО, наличие компонентов стороннего производителя, не соответствующих спецификации, человеческий фактор и многое другое. Устойчива ли предложенная спецификация нашего турникета к изменениям? Реальна ли в будущем ситуация, что наряду с жетоном, турникет должен будет “понимать” магнитную карточку или должен будет иметь состояние “аварийного открытия” в случае пожара (или аналогичного форс-мажора)? Сколько изменений необходимо будет сделать в существующем коде? Будем ли мы уверены, в том, что после этого, ранее работающий код не будет “испорчен”? Предложенная выше реализация (Листинг 1) наглядно иллюстрирует нарушение одного из основных принципов проектирования – открытости\закрытости (OCP, The Open Closed Principle [2]) – программные объекты (классы, модули, функции, и т.д.) должны быть открыты для расширения, и, одновременно, закрыты для модификации.
Проблема очевидна, нужно разработать такую реализацию КА, которую можно было бы легко модифицировать при изменении его спецификации. Изменения спецификации могут привести к изменениям различных аспектов реализации - состояний, событий, переходов между состояниями и действий, которые необходимо выполнить при тех или иных условиях. Эти аспекты можно представить как направления, или оси изменчивости на некоторой воображаемой многомерной диаграмме. Крайне желательно, чтобы реализация КА была устойчивой к изменениям по всем этим осям.
Одним из способов упрощения модификации кода является использование паттернов проектирования – структур и методов, испытанных и применяемых на практике опытными программистами. Паттерны зачастую выражают то, что напрямую недоступно языкам программирования. Паттерны говорят, что делать, зачем и каковы могут быть последствия. Паттерны существуют в разных формах, но всегда описывают проблему и решение. К сожалению, в большинстве случаев паттерны проектирования способны решить проблему изменчивости только в направлении одной из осей. Однако для лучшего понимания проблемы стоит разобрать и этот вариант. Листинг 2 демонстрирует возможную реализацию турникета, основанного на паттерне "State" (GoF [3]).
Листинг 2. Реализация, основанная на паттерне "State".class Turnstile { public: Turnstile() : lockedState_(this), unlockedState_(this), currentState_(&lockedState_) {} void coin() { currentState_->coin(); } void pass() { currentState_->pass(); } private: struct State { explicit State(Turnstile* owner) : turnstile_(owner) {} virtual ~State() {} virtual void coin() = 0; virtual void pass() = 0; protected: Turnstile* turnstile_; }; struct LockedState : State { explicit LockedState(Turnstile* owner) : State(owner) {} // overridables virtual void coin() { turnstile_->currentState_ = &turnstile_->unlockedState_; turnstile_->unlock(); } virtual void pass() { turnstile_->alarm(); } }; struct UnlockedState : State { explicit UnlockedState(Turnstile* owner) : State(owner) {} // overridables virtual void coin() { turnstile_->thankyou(); } virtual void pass() { turnstile_->currentState_ = &turnstile_->lockedState_; turnstile_->lock(); } }; private: LockedState lockedState_; UnlockedState unlockedState_; State* currentState_; private: // block A ‘activities’ void lock() { cout << "lock()" << endl; }; void unlock() { cout << "unlock()" << endl; }; void alarm() { cout << "alarm()" << endl; }; void thankyou() { cout << "thankyou()" << endl; }; }; |
Отметим преимущества данного решения. Данная реализация упростила внесение изменений по оси "Состояние". Мы ввели новую абстракцию – State и две ее реализации (LockedState, UnlockedState), соответствующие состояниям, описанным в STD. Действия (block A ‘activities’) и логика механизма состояний строго разделяются. Действия реализуются в классе Turnstile, а логика – с помощью производных модулей класса State. Довольно легко изменять одно, не оказывая воздействия на другое. Например, несложно повторно использовать действия (класс Turnstile), применяя различную логику состояний. Добавление нового состояния приведет к добавлению (не модификации) новой реализации класса State с логикой, присущей данному состоянию.
Однако все вышеизложенные рассуждения справедливы при условии, что со временем список событий не изменяется. Проблема этого подхода в том, что добавление нового события приведет к модификации существующего кода. Мы будем вынуждены добавить новую функцию-член в класс State и, как следствие, модифицировать все его производные модули. Поскольку логика переходов распределена (отсутствует какое-либо одно место, где можно посмотреть всю конструкцию в целом, как на рисунке 1, поддержка данного решения остается весьма затруднительной. Кроме того, в глаза бросается непропорциональное увеличение объема кода.
В документе [4] представлен внушительный каталог паттернов, используемых для реализации КА, в зависимости от специфики требований той или иной предметной области. Следует отметить, что паттерны – это основа дизайна для решения некоторой (конкретной) проблемы в некотором (конкретном) контексте, при этом паттерн не дает нам ни строчки готового работающего кода. В нашем случае он не избавляет разработчика от рутинной работы по созданию производных классов (модулей) состояний, событий или чего-то еще, в зависимости от того, какой паттерн был положен в основу решения, и тем самым максимально настроить каждый конкретный экземпляр КА под свои нужды и/или адаптировать его под давлением изменяющихся требований.
Одним из классических подходов к созданию КА является использование генераторов кода. В общем случае технология, основанная на генерации кода, может быть представлена следующим образом (рисунок 2).
| ПРИМЕЧАНИЕ В [5] представлены наиболее известные реализации на сегодняшний день: каркасы, библиотеки, генераторы кода (компиляторы), редакторы, средства для проверки согласованности и непротиворечивости спецификации КА. |
Рисунок 2
На основе высокоуровневой спецификации генератор:
Такой подход обладает гибкостью, универсальностью и … “тяжеловесностью”. В определенных ситуациях, с точки зрения здравого смысла и соотношения затрат к ожидаемым результатам, использование инструментария стороннего производителя (или разработка своего собственного) может быть неоправданной. К примеру, такая ситуация характерна для реализаций простых вариантов КА, аналогичных приведенному выше турникету.
Мы вообще не будем писать программ, а заставим компилятор это делать за нас. Andrei Alexandresku, Modern C++ Design
Аббревиатура SFSM расшифровывается как static finite state machine, то есть статический КА. Обращаясь к встроенным средствам языка C++ (метапрограммирование на основе шаблонов) мы “научим” компилятор выполнять функции генератора кода. Иными словами, мы создадим код, который на основе спецификации будет порождать код реализации КА, соответствующего спецификации. Единственным отличием этого подхода от использования генераторов кода является то, что нам не придется создавать отдельное приложение, генерирующее код – его функции возьмет на себя компилятор C++.
Шаблоны C++ являются полный по Тьюрингу подъязык C++ периода компиляции. Другими словами, шаблоны C++ позволяют создать программы, которые выполняются в процессе компиляции C++-кода. Таким образом, одна часть кода будет за нас “писать” другую часть кода, т.е. реализацию КА. В данном случае наш генератор в виде шаблона, принимающий спецификацию КА в качестве параметра, будет возвращать готовую реализацию в виде класса наподобие следующего:
class Turnstile : public fsm::Builder<TransitionTable> { }; int main(int argc, char* argv[]) { TurnstileSM machine; cout << "SM current state: " << machine.state()<< endl; machine.postEvent(E_COIN); |
Осталось определиться с таинственным параметром TransitionTable.
Таблица переходных состояний (STT, state transition table) [5] представляет собой альтернативный, но такой же простой и элегантный, как STD, способ описания поведения КА.
| Событие/Текущее состояние | Locked | Unlocked |
|---|---|---|
| COIN | Unlocked | Unlocked |
| PASS | Locked | Locked |
Комбинация текущего состояния с входным сообщением дает нам следующее состояние, в которое КА должен перейти. Данному описанию присущи следующие недостатки:
Этих недостатков можно избежать, если STT будет основана на описании самих переходов (см. таблицу 2) [1]. Несуществующие (или неразрешенные) переходы в ней просто не будут отражены. А добавления новых событий и состояний, как следствие, будут приводить к добавлению новых строк-переходов. Таблица будет “расти только вглубь”.
| Текущее состояние | Событие | Конечное состояние | Действие | |
|---|---|---|---|---|
| 1 | Locked | COIN | Unlocked | unlock() |
| 2 | Locked | PASS | Locked | alarm() |
| 3 | Unlocked | PASS | Locked | lock() |
| 4 | Unlocked | COIN | Unlocked | thankyou() |
Итак, описание КА находится в одном месте (STT), что значительно облегчает дальнейшую поддержку. STT строго изолирована от реализации действий, поэтому вносимые в нее изменения не требуют пересмотра реализации действий (обратное тоже верно). Листинг 3 показывает, как легко STT может быть перенесена в код реализации КА.
Листинг 3. STT турникета и обработка событий. Динамическая версия. class Actions { public: // Блок A "действия" void lock(); void unlock(); void alarm(); void thankyou(); }; class Turnstile : private Actions { public: void postEvent(Event event); // ... private: class TransitionTable { // ... }; TransitionTable transitions_; void addTransition(State, Event, State, void (Turnstile::*)() ); }; Turnstile::Turnstile() { // State Transition Table addTransition(Locked, COIN, Unlocked, unlock); addTransition(Locked, PASS, Locked, alarm); addTransition(Unlocked, PASS, Locked, lock); addTransition(Unlocked, COIN, Unlocked, thankyou); } void Turnstile::postEvent(Event event) { const Transition* tran(0); for(int i = 0; i < transitions_.size(); ++i) { tran = transitions[i]; if(currentState_ == tran->stateFrom_ && event == tran->event_) { currentState_ == tran->stateTo_; // Здесь будет вызвано ассоциированное действие. tran->execute(this); break; } } } |
Обратите внимание, реализация всех действий была вынесена в отдельный класс Actions, тем самым мы четко разграничиваем обязанности между классами: Turnstile контролирует логику конечного автомата, а Actions реализует все необходимые действия. Чтобы подчеркнуть отношения между классами Turnstile и Actions как "реализуется посредством" было использовано private-наследование.
Если действия будут сгруппированы в независимые контексты, мы получим более обобщенное решение, представленное в Листинге 4.
Листинг 4. Динамическая реализация КА, основанная на множестве контекстов.class Actions { public: // Блок A "действия" void lock() {/*…*/}; void unlock() {/*…*/}; void alarm() {/*…*/}; void thankyou() {/*…*/}; private: // поля класса // ... }; class ForceMajeurActions { public: // Блок B "другие действия" void emergencyUnlock(); // ... private: // ... }; class Turnstile : private Actions, private ForceMajeurActions { public: void postEvent(Event event); // ... }; |
Поскольку STD и STT по своей природе статичны, т.е. описываемая ими логика известна на стадии компиляции остается неизменной в период выполнения, то логично генерировать все необходимые структуры и код, а также выполнять все проверки еще на стадии компиляции.
Мы будем представлять переходы как типы, а STT – как тип типов-переходов. Прежде всего, мы создадим шаблон, на основе которого будем создавать конкретные типы-переходы. С каждой строкой в STT будет ассоциирован соответствующий тип:
Листинг 5. STT в терминах C++.typedef FSM_TRANSITION(Locked, COIN, Unlocked, Actions, unlock) tran1; typedef FSM_TRANSITION(Locked, PASS, Locked, Actions, alarm) tran2; typedef FSM_TRANSITION(Unlocked, PASS, Locked, Actions, lock) tran3; typedef FSM_TRANSITION(Unlocked, COIN, Unlocked, Actions, thankyou) tran4; |
где сам шаблон и макрос выглядят следующим образом:
Листинг 6. Переход как конкретный тип на основе TransitionT шаблона.template < // Пользовательский класс, инкапсулирующий действия для конкретного КА typename CONTEXT_T > class TransitionT { // Предопределенная сигнатура метода: void* (*)() typedef void (CONTEXT_T::*ActionT)(); public: template < // идентификатор начального состояния int STATE_FROM, // идентификатор события, инициирующего переход int EVENT_VALUE, // идентификатор состояния, в которое производится переход // при получении события EVENT_VALUE int STATE_TO, // Ссылка на выполняемое действие ActionT ACTION > struct DefineT { typedef CONTEXT_T ContextT; enum { BASE_STATE = STATE_FROM, TARGET_STATE = STATE_TO, EVENT = EVENT_VALUE }; static void invoke(ContextT* context) { (*context.*ACTION)(); } }; }; // Для упрощения определения переходов можно использовать макрос // FSM_TRANSITION #define FSM_TRANSITION(BaseState, Event, TargetState, \ ContextClass, ContextMethod) \ fsm::TransitionT<ContextClass>::DefineT<BaseState, Event, \ TargetState, ContextClass::ContextMethod> |
Поскольку наша реализация КА будет основана на множестве контекстов, где каждый контекст является местом локализации четко сгруппированных действий, формат STT (Таблица 2) претерпел незначительные изменения и для нашего рабочего примера принял следующий вид:
| Начальное состояние | Событие | Конечное состояние | Контекст | Действие | |
|---|---|---|---|---|---|
| 1 | Locked | COIN | Unlocked | Actions | unlock() |
| 2 | Locked | PASS | Locked | Actions | alarm() |
| 3 | Unlocked | PASS | Locked | Actions | lock() |
| 4 | Unlocked | COIN | Unlocked | Actions | thankyou() |
Так как запись в данной таблице описывается отдельным типом, чтобы реализовать приведенную выше таблицу, необходимо создать список. Для этого можно воспользоваться идиомой "список типов" из библиотеки Loki [10]. Список типов – это тип, содержащий информацию о других типах. Обработка списков типов возможна лишь на этапе компиляции. Списки типов не предназначены для создания объектов, хотя это и не запрещено. Все, что касается списков типа и примитивов для работы с ними, было взято из [Loki, 11].
Листинг 7. Таблица переходов как список типов.template <class T, class U> struct Typelist { typedef T Head; typedef U Tail; }; // NullType используется как заглушка, идентифицирующая конец списка class NullType { public: struct Head { private: Head(); }; struct Tail { private: Tail(); }; }; typedef Typelist<tran1, Typelist<tran2, Typelist<tran3, Typelist<tran4, NullType> > > > TransitionTable; // Для определения списка типов TransitionTable // можно использовать эквивалентный макрос // typedef TYPELIST_4(tran1, tran2, tran3, tran4 ) TransitionTable; // TYPELIST_4 macro definition please see in LokiPort.h file |
Таким образом, STT представлена в виде типа, который полностью описывает логику КА.
typedef TYPELIST_4(tran1, tran2, tran3, tran4) TransitionTable;
|
или
typedef TYPELIST_4
(
FSM_TRANSITION(Locked, COIN, Unlocked, Actions, unlock),
FSM_TRANSITION(Locked, PASS, Locked, Actions, alarm),
FSM_TRANSITION(Unlocked, PASS, Locked, Actions, lock),
FSM_TRANSITION(Unlocked, COIN, Unlocked, Actions, thankyou)
)
TransitionTable;
|
Отладка сама по себе в два раза сложнее, чем создание кода с белого листа. Следовательно, если вы пишете код недостаточно чистым, Вы, по определению, недостаточно умны, что бы избежать его отладки в будущем. Brian Kernighan.
Проверка на непротиворечивость КА во время компиляции имеет одно явное преимущество перед динамической версией (листинг 3) – возможность обнаружения ошибок на стадии компиляции. Раннее обнаружение ошибок – это один из главных факторов успешности проекта в целом. На рисунке 3 представлены наиболее распространенные ошибки при проектировании детерминированного КА (ДКА). Эти ошибки равновероятно появляются при составлении как STD, так и STT. Отображение же STT в C++-тип заставляет компилятор проверять таблицу переходов (как “научить” его делать это, показано ниже) на непротиворечивость и “отказывать” нам в создании реализации КА при обнаружении ошибок.
Рисунок 3
С этой целью в декларацию шаблонного класса TransitionT были добавлены две строки с определением дружественных функций.
template <...> class TransitionT { // ... public: template< ... > struct DefineT { private: friend void CHECK_DUPLICATION( Loki::Int2Type<BASE_STATE>, Loki::Int2Type<EVENT_VALUE>) {} friend void CHECK_DUPLICATION( Loki::Int2Type<BASE_STATE>, Loki::Int2Type<TARGET_STATE>, MemberFunction2Type<ACTION> ) {} }; }; |
Основная идея заключается в том, что компилятор C++ генерирует уникальные внутренние имена для всех методов. В приведенном выше фрагменте мы используем перегрузку методов (в данном случае метода CHECK_DUPLICATION) по их сигнатуре. Дружественная функция, в соответствии со стандартом имеет область видимости, совпадающую с областью видимости класса, в котором она определена. Другими словами, определения из листинга 8 эквивалентны.
Листинг 8. Определение дружественной функции внутри класса// Определение: // ...эквивалентно определению: class Foo class Foo { { friend void doSomething(int) friend void doSomething(int); { /*...*/ } }; }; inline void doSomething(int) { /*...*/ } |
Следовательно, разные конкретизации TransitionT (имеющего пять входных параметров) могут быть проверены на непересекаемость по заданным критериям. Например, определение:
CHECK_DUPLICATION(Loki::Int2Type<BASE_STATE>, Loki::Int2Type<EVENT_VALUE>) |
гарантирует, что из состояния State1 может существовать только один переход по событию Event1. Если это не так, компилятор сообщит об ошибке: функция CHECK_DUPLICATION уже определена и имеет тело. В качестве состояний и событий используются целочисленные константы. Перегрузку же можно осуществить только на основе типов аргументов. Шаблон Int2Type<…> (позаимствованный из Loki) позволяет преобразовать целочисленное значение в тип.
Сигнатура второй дружественной функции устанавливает другую уникальность для перехода, а именно, линия, соединяющая State1 и State2 должна быть уникальна действием Action1, которое является следствием данного перехода. Другими словами, запрещается существование событий-синонимов, имеющих различные имена (константы), но приводящих к одному и тому же результату. Данное утверждение, прежде всего, было введено для того, что бы обнаруживать дефекты дизайна и не допускать неочевидного дублирования знаний.
| ПРИМЕЧАНИЕ В общем случае, ситуация, когда разные события являются источником перехода с вызовом одного и того же действия, не является ошибкой (крайнее справа изображение на рисунке 3). Следующий пример иллюстрирует это. Если разбито окно (событие 1), и если выломана дверь (событие 2), и новым состоянием является включенная сирена, единственное действие, которое разумно предпринять – подать ток на эту самую сирену. В коде этот пример может быть представлен как: class Flat { …. void windowBroken(); … // достаточно много методов, что бы, не держать их все в голове void doorDestroyed(); … }; Оба метода семантически эквивалентны, т.е. выполняют одну и ту же функцию (подавать ток на сирену). Эти методы могут быть реализованы по-разному и могут содержать разные ошибки. Налицо нежелательное дублирование знаний. Такая ситуация довольно типична в программировании, как следствие невнимательности или результат работы нескольких программистов. Человеку свойственно ошибаться и, к сожалению, с точки зрения логики упомянутая ошибка может не являться таковой. Заниматься же профилактикой значительно дешевле, чем лечить хроническое заболевание. Введение такого ограничения позволяет переложить контроль подобных ошибок на компилятор. Если по логике КА понадобится выполнить одно действие в ответ на два события, то можно создать одно общее событие, с которым и ассоциировать нужное действие. Вернувшись к нашему примеру, мы можем добавить ОДНО событие (“Попытка взлома”), вместо двух “Разбито окно” и “Взломана дверь”. |
template < // Список типов переходов typename TRANSITION_TABLE_T, typename STATE_T = int, typename EVENT_T = int, template <class, class> class MONITOR_T = DefaultMonitor > // Класс Builder должен быть унаследован от всех классов-контекстов class Builder : protected MultipleInheritance // исключает дублирование классов-контекстов <typename Loki::TL::NoDuplicates <typename ContextEnumeratorT<TRANSITION_TABLE_T>::Result>::Result >, protected MONITOR_T<STATE_T, EVENT_T> { public: STATE_T state() const; void postEvent(EVENT_T event); //... private: template <typename TRANSITION_TABLE_ARG_T> void execTransition(STATE_T baseState, EVENT_T event) {/**/} template <> void execTransition<Loki::NullType>(STATE_T state, EVENT_T event) {/**/} }; |
Шаблон Builder принимает список типов (содержащий спецификацию КА в формате STT (Листинг 7)) в качестве параметра TRANSITION_TABLE_T. При конкретизации данного шаблона компилятор выполняет следующие действия:
Листинг 9. Реализация шаблона MultipleInheritancetemplate<typename TList> struct MultipleInheritance : public TList::Head, public MultipleInheritance<typename TList::Tail> { }; template<> struct MultipleInheritance<Loki::NullType> { }; |
Статический аналог динамической версии турникета с двумя контекстами (Листинг 4) представлен на диаграмме классов ниже (Рис.4). Обнаруживая конструкцию MultipleInheritance<Typelist<Actions, Typelist<ForceMajeurActions, Loki::NullType> > > компилятор конкретизирует шаблон класса MultipleInheritance для списка типов, содержащего три типа (Actions, ForceMajeurActions, Loki::NullType). При этом тип базового класса должен быть уже известен. Теперь компилятору приходится конкретизировать еще и MultipleInheritance<Typelist<ForceMajeurActions, Loki::NullType> > и, затем, MultipleInheritance< Loki::NullType>. Последний вариант конкретизации с параметром Loki::NullType соответствует специализации шаблона MultipleInheritance с пустым телом и без спецификации наследования. На этой специализации шаблона рекурсия шаблона завершается, и компилятор развертывает свой внутренний стек областей (в этот стек проталкивались области действия всех генерируемых экземпляров шаблона), в результате чего создается окончательный тип с иерархией наследования, представленной на Рис. 4. Таким образом, опосредованно мы получили терминальный класс, производный от двух базовых: Actions и ForceMajeurActions.
Рисунок 4
Реализация метода postEvent(…)основана также на рекурсивной конкретизации шаблонной фукции-члена template<…> execTransition(…) шаблонного класса template<…> fsm::Builder с конечной специализацией в качестве точки останова. Псевдокод, сгенерированный компилятором для рабочего примера с турникетом STT – Таблица 3, будет выглядеть следующим образом:
Листинг 10. postEvent(…) реализация (псевдокод).template<...> class Builder : protected ... { public: void postEvent(EVENT_T event) { execTransition_1(event); } private: void execTransition_1(EVENT_T event) { // Locked (1) == state_ && COIN (1) == event if(tran1::BASE_STATE == state_ && tran1::EVENT == event) { state_ = tran1::TARGET_STATE // Unlocked - 2 tran1::invoke(this); // Unlock(); return; } execTransition_2(event); } void execTransition_2(EVENT_T event) { // Locked (1) == state_ && PASS (2) == event if(tran2::BASE_STATE == state_ && tran2::EVENT == event) { state_ = tran2::TARGET_STATE // Locked - 1 tran1::invoke(this); // Alarm(); return; } execTransition_3(event); } void execTransition_3(EVENT_T event) { // Unlocked (2) == state_ && PASS (2) == event if(tran3::BASE_STATE == state_ && tran3::EVENT == event) { state_ = tran3::TARGET_STATE // Locked - 1 tran1::invoke(this); // Lock(); return; } execTransition_4(event); } void execTransition_4(EVENT_T event) { // Unlocked (2) == state_ && COIN (1) == event if(tran4::BASE_STATE == state_ && tran4::EVENT == event) { state_ = tran4::TARGET_STATE // Unlocked - 2 tran1::invoke(this); // Thankyou(); return; } execTransition_5(event); } void execTransition_5(EVENT_T event) { } private: STATE_T state_; }; ///////////////////////////////////////////////////////////// // !!! // Имейте в виду! // // Поскольку все методы execTransition_... объявлены как inline, после // оптимизации тело postEvent(EVENT_T event) будет выглядеть так, // как показано ниже: // void postEvent(EVENT_T event) // { // if(1==state_ && 1==event) // { state_ = 2; // Unlock(); // return; // } // // if(1==state_ && 2==event) // { state_ = 1; // Alarm(); // return; // } // // if(2==state_ && 2==event) // { state_ = 1; // Lock(); // return; // } // // if(2==state_ && 1==event) // { state_ = 2; // Thankyou(); // return; // } // } |
На рисунке 5 показано, как будет выглядеть созданный компилятором класс.
Рисунок 5.
Начальное состояние объекта полученного класса будет соответствовать спецификации первого перехода в TransitionTable.
Для нашего примера (Листинг 5, 7) начальное состояние – Locked.
Мониторинг дает возможность полностью отслеживать все изменения, происходящие внутри КА, и причины, вызвавшие их. Это позволяет обеспечить дополнительную гибкость и настраиваемость приложения. Ниже приведены типичные задачи, для решения которых нужен мониторинг:
Листинг 11. Пример использования мониторинга для сохранения истории в журнале регистрации.enum STATE {/*...*/}; enum EVENT {/*...*/}; template < typename STATE_T, typename EVENT_T > class Monitor { public: void on_received(STATE_T currentState, EVENT_T receivedEvent) { output_ << receivedEvent << " event was received. Current state is " << currentState << endl; } void on_state_changed(STATE_T currentState, STATE_T previousState, EVENT_T overEvent ) { if(currentState != previousState) output_ << "state was changed from " << previousState << " to " << currentState << endl; else output_ << "state remained unchangeable" << endl; } void on_completed(STATE_T currentState, STATE_T previousState, EVENT_T overEvent ) { output_ << "transition completed." << endl; } void unhandled_event(STATE_T currentState, EVENT_T receivedEvent) { output_ << "there is no transition which can accept " << receivedEvent << " event on " << currentState << " state." << endl; } }; class TurnstileSM : public fsm::Builder<TransitionTable, STATE, EVENT, Monitor> { }; |
Чтобы использовать свой собственный мониторинг, необходимо определить шаблонный тип с двумя параметрами – "Состояние" (STATE_T) и "Событие" (EVENT_T), который, в свою очередь, будет использоваться в качестве параметра шаблона fsm::Builder<…> наряду с уже известным типом TransitionTable. Данный шаблонный тип должен быть также определен с четырьмя обязательными методами:
| ПРЕДУПРЕЖДЕНИЕ Поток управления может быть пройден только по двум ветвям: on_received -> unhandled_event on_received -> on_state_changed -> on_completed Во втором случае последовательность on_state_changed -> on_completed может быть нарушена, если реализованное клиентом действие сгенерирует исключение. |
Если тип монитора не будет передан в шаблон fsm::Builder как аргумент, то он будет конкретизирован с монитором fsm::DefaultMonitor, используемым по умолчанию. При создании конкретного типа на основе фактически переданных шаблонному типу fsm::Builder аргументов будет создаваться тип монитора на основе шаблона fsm::DefaultMonitor, в котором все вышеперечисленные методы пусты. Однако если компилятор обнаружит подходящую специализацию для fsm::DefaultMonitor с требуемыми аргументами STATE_T и EVENT_T, он предпочтет именно ее. Таким образом, можно настроить мониторинг альтернативным способом, используя механизмы статического полиморфизма. Листинг 12 демонстрирует это решение.
Листинг 12. Пример использования мониторинга для сохранения истории в журнале регистрации. Специализация шаблона fsm::DefaultMonitor. enum STATE {/*...*/}; enum EVENT {/*...*/}; template<> class fsm::DefaultMonitor<STATE, EVENT> { public: void on_received(STATE currentState, EVENT receivedEvent) { output_ << receivedEvent << " event was received. Current state is " << currentState << endl; } // ... }; // спецификация аргументов шаблона монитора не нужна class TurnstileSM : public fsm::Builder<TransitionTable, STATE, EVENT> { }; |
| ПРИМЕЧАНИЕ Дополнительные примеры можно найти в проектах ./turnstileWithMonitor (main.cpp), ./logging (logging.h, logging.cpp). |
Создание КА в виде составного (композитного) типа на основе контекстов с использованием механизма множественного наследования обязывает классы-контексты иметь конструктор без параметров. Что же делать, если инициализация некоего контекста требует передачи внешних аргументов? К сожалению, решить эту проблему в лоб не удалось, в силу того, что количество контекстов не ограничено, и каждый из них может иметь произвольное число конструкторов с различным набором параметров. Чтобы разрешить данную проблему, необходимо:
В листинге 11 был представлен пример регистрации действий КА в журнале средствами мониторинга. Вопрос о том, какой тип у поля output_, и как произошла его инициализация, был намеренно опущен. Сейчас самое время к этому вернуться. Нужно отметить, что подобъект монитора становится такой же частью класса КА, как любой из контекстов (рисунок 5). Поэтому пример монитора из листинга 13 может быть использован для инициализации контекстов.
Листинг 13. Инициализация подобъектов FSM типа// Класс Output должен иметь публичный интерфейс, аналогичный std::ostream #include "output.h" template<...> class Monitor { private: Output& output_; public: // Добавлено. Для инициализации объекта Monitor нужен новый метод. void init(Output* out) { output_ = *out; } public: void on_received(STATE_T currentState, EVENT_T receivedEvent) // ... }; class TurnstileSM : public fsm::Builder<TransitionTable, STATE, EVENT, Monitor> { public: TurnstileSM(Output* log) { // Если контексты или монитор имеют методы с одинаковыми именами // вы должны будете указывать их с полным квалификатором доступа, // как показано ниже Monitor<STATE, EVENT>::init(log); // если конфликта имен нет вы можете вызывать метод без квалификатора // init(log); } }; |
| ПРИМЕЧАНИЕ Дополнительный пример можно найти в проекте ./logging (logging.h, logging.cpp). |
До сих пор мы рассматривали ситуацию, когда источником событий являлся внешний компонент, т.е. клиентский код, использующий КА. В этом нет ничего удивительного, поскольку это полностью соответствует классическому представлению конечного автомата. Тем не менее, во многих практических случаях хотелось бы иметь возможность посылки так называемых “внутренних” событий, т.е. возможность КА посылать сообщения самому себе. Такое поведение характерно архитектуре Microsoft Windows, когда щелчок мышкой (в зависимости от контекста) приводит к генерации целой цепочки сообщений.
Послать сообщение самому себе можно только из кода реализации действий. В конце концов, реализация действий – это единственное место, которое мы пишем вручную. Следовательно, вопрос должен быть сформулирован следующим образом: “Как получить указатель на объект конечного автомата из кода, реализующего действие, если контексты не должны зависеть от реализации КА?”. Однако реализовать посылку сообщения (из действия) без использования метода postEvent невозможно. Так как каждое действие реализовано в пределах определенного контекста, а контекст является частью конкретного композитного типа КА (рисунок 5), то чтобы добраться из контекста до композитного типа можно воспользоваться понижающим приведением типа с помощью оператора static_cast<...>(). Компилятор согласится выполнить эту инструкцию только при условии видимости производного класса. В нашем случае это будет выглядеть так, как показано в листинге 14.
Листинг 14. Отправка сообщения самому себе.// Реализация класса ContextImpl // Здесь нужно добавить ссылку на конкретный тип КА!!! #include "MyFSM.h" void ContextImpl::action1 () { // ... static_cast<MyFSM*>(this)->postEvent(MY_INTERNAL_EVENT); } // ... |
Добавление новой зависимости между контекстом и реализацией КА отражено на рисунке 6.
| ПРИМЕЧАНИЕ Дополнительные примеры можно найти в проектах ./logging (logging.cpp) и ./VendingMachine (actionImpl.cpp). |
Рисунок 6
При реализации КА рекомендуется следующая последовательность действий:
Все описанное выше приводит к реализации КА в виде конкретного типа. Собственно, это и было нашей целью.
Программист, создающий STT и использующий fsm::Builder для реализации КА, выступает в роли разработчика КА. Программист, который будет использовать КА, выступает в роли пользователя КА. В большинстве случаев, программисту-пользователю нет необходимости знать “внутренности” реализации КА. Например, код программиста-пользователя не должен зависеть от таблицы переходов и состояний, в которых КА может находится, этот код посылает сообщения для КА и только! Скрытие реализации КА показано на рисунке 6 как некая ассоциация между классами FSMImplementation и FSM. Один из способов реализации данного отношения может основываться на идиоме классов-оберток. Например, в листинге 15 мы использовали идиому Pimpl (pointer to implementation) [12].
Листинг 15. Сокрытие реализации с использованием идиомы Pimpl./////////////////////////////////////// // fsm.h внешнее представление КА для программиста-пользователя // Обратите внимание, код, который будет использовать этот класс // полностью изолирован от таких понятий как TRANSITION_TABLE, STATE, etc. class FSM { public: FSM(); ~FSM(); void pass(); void coin(); private: class Implementor; // предварительная декларация Implementor& impl_; }; /////////////////////////////////////// // fsm.cpp – реализация FSM::Implementor как подтипа FSMImplementation #include "FSMImplementation.h" class FSM::Implementor : public FSMImplementation { }; FSM::FSM() : impl_(*new Implementor) { } FSM::~FSM() { delete &impl_; } void FSM::coin() { impl_.postEvent(COIN); } void FSM::pass() { impl_.postEvent(PASS); } |
Код в fsm.h полностью соответствует Стандарту. Другой вопрос, как хорошо согласуется со Стандартом ваш компилятор.
Прилагаемые к данной статье примеры были откомпилированы и протестированы на следующих платформах:
| OS | Компилятор | Компилируется? | Комментарии | |
|---|---|---|---|---|
| 1 | Microsoft Windows | Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 13.10.3077 for 80x86 (Visual Studio NET 2003) | Да | |
| 2 | Microsoft Windows | Borland C++ 5.6 for Win32 Copyright (c) 1993, 2002 (Borland C++ Builder 6.0) | Нет | Компилятор выдает ошибку "Fatal F1004 LokiPort.h 431: Internal compiler error". * |
| 3 | AIX Power PC 32/64-bit, ver. 4.3 | VisualAge C/C++ 6.0 / 5.0 | Да | |
| 4 | HP-UX PA 32(64)-bit, ver. 11.0 | HP Softbench D.06.30 | Нет | Не понимает шаблонные параметры шаблонов. |
| 5 | Red Hat Enterprise Linux AS 32-bit Intel, ver 3.0 | gcc 3.2.3 | Да | |
| 6 | Red Hat Linux ver. 9 | Intel C++ Compiler 8.1 | Да | |
| 7 | Solaris Sparc 32/64-bit, ver. 9 | Forte Developer 7 C/C++ 5.4 | Нет | Не понимает шаблонные параметры шаблонов. |
| 8 | Tru64 UNIX Alpha 64-bit | Compaq C V6.5 | Да |
* Необходимо отметить, что предшествующая версия этого компилятора (Borland C++ 5.5 for Win32) выдает более дружелюбное сообщение “LokiPort.h 431: Specialization within template classes not yet implemented”
Пример взят из [6, Chapter: State pattern], где, основываясь на нем, демонстрируются преимущества использования шаблона "State". А в источнике [7] приведена одна из возможных реализаций данной задачи с использованием XML и интерпретацией STT в период выполнения. Сравните эту реализацию с реализацией на основе SFSM, предлагаемой ниже.
Предположим, что нужно реализовать автомат по продаже некоего прохладительного напитка или чашки горячего кофе. Автомат способен принимать монеты номиналом в 5 (Nickel), 10 (Dime) и 25 (Quarter) центов, и выдает чашку напитка, если сумма превысит 25 центов. Каждая монетка, опускаемая в монетоприемник, переводит автомат в новое, отличное от предыдущего, состояние до тех пор не будет достигнута требуемая сумма. Как только это произойдет, автомат выдаст напиток и перейдет в исходное состояние. Из-за простоты примера соответствующая STD здесь не приводится. Решение сразу можно описать в терминах C++ (листинг 16).
Листинг 16. Автомат газировки. Реализация оригинального примера.// VendingMachine.h enum State { Start, Five, Ten, Fifteen, Twenty }; enum Event { Nickel, Dime, Quarter }; class Impl { public: void dispense(); // реализовано в другом модуле }; typedef TYPELIST_15( FSM_TRANSITION_NO_ACTION(Start, Nickel, Five), FSM_TRANSITION_NO_ACTION(Start, Dime, Ten), FSM_TRANSITION(Start, Quarter, Start, Impl, dispense), FSM_TRANSITION_NO_ACTION(Five, Nickel, Ten), FSM_TRANSITION_NO_ACTION(Five, Dime, Fifteen), FSM_TRANSITION(Five, Quarter, Start, Impl, dispense), FSM_TRANSITION_NO_ACTION(Ten, Nickel, Fifteen), FSM_TRANSITION_NO_ACTION(Ten, Dime, Twenty), FSM_TRANSITION(Ten, Quarter, Start, Impl, dispense), FSM_TRANSITION_NO_ACTION(Fifteen, Nickel, Twenty), FSM_TRANSITION(Fifteen, Dime, Start, Impl, dispense), FSM_TRANSITION(Fifteen, Quarter, Start, Impl, dispense), FSM_TRANSITION(Twenty, Nickel, Start, Impl, dispense), FSM_TRANSITION(Twenty, Dime, Start, Impl, dispense), FSM_TRANSITION(Twenty, Quarter, Start, Impl, dispense) ) TransitionTable; class VendingMachine : public fsm::Builder<TransitionTable, State, Event> { }; // VendingMachine.cpp #include "VendingMachine.h" #include "display.h" int main(int argc, char* argv[]) { VendingMachine machine; // display() эмулирует экран торгового автомата... display(machine); // ...где prompt() предоставляет взаимодействие. for(Event event = prompt(); event != Exit; event = prompt()) { machine.postEvent(event); display(machine); } return 0; } |
Хотя данный пример и надуман, попробуем изменить требования к спецификации автомата, тем самым придав ему более реальные очертания. Реальность заключается не в схожести моделируемой системы с железным ящиком в углу буфета вашего офиса, а в том, что требования к системе изменились, хотим мы этого или нет. Итак, вас информируют о том, что в первоначальных требованиях была допущена ошибка: забыли указать, что автомат обязан также возвращать наряду с чашкой кофе (напитком) сдачу, если сумма, введенная пользователем, превысила требуемое значение (25 центов). Вот как будет выглядеть решение с учетом этих требований (рисунок 7).
Рисунок 7. А вот как будет выглядеть реализация с учетом новых требований.
Листинг 17. Автомат газировки. Реализация на основе изменения требованийenum State { Start, Five, Ten, Fifteen, Twenty, Change // <- новое состояние }; enum Event { Nickel, Dime, Quarter, Restart // <- новое состояние }; class Impl { public: void dispense(); }; // Добавлен новый класс контекста. Реализован в другом модуле. class ChangeImpl { public: void returnNickel(); void returnDime(); void returnDimeAndNickel(); void returnDimeAndDime(); }; // <- TYPELIST_16 вместо ... _15. Не беспокойтесь, если вы забудете об этом, // компилятор выдаст предупреждение. typedef TYPELIST_16( FSM_TRANSITION_NO_ACTION(Start, Nickel, Five), FSM_TRANSITION_NO_ACTION(Start, Dime, Ten), FSM_TRANSITION(Start, Quarter, Start, Impl, dispense), FSM_TRANSITION_NO_ACTION(Five, Nickel, Ten), FSM_TRANSITION_NO_ACTION(Five, Dime, Fifteen), FSM_TRANSITION(Five, Quarter, Change, ChangeImpl, returnNickel), FSM_TRANSITION_NO_ACTION(Ten, Nickel, Fifteen), FSM_TRANSITION_NO_ACTION(Ten, Dime, Twenty), FSM_TRANSITION(Ten, Quarter, Change, ChangeImpl, returnDime), FSM_TRANSITION_NO_ACTION(Fifteen, Nickel, Twenty), FSM_TRANSITION(Fifteen, Dime, Start, Impl, dispense), FSM_TRANSITION(Fifteen, Quarter, Change, ChangeImpl, returnDimeAndNickel), FSM_TRANSITION(Twenty, Nickel, Start, Impl, dispense), FSM_TRANSITION(Twenty, Dime, Change, ChangeImpl, returnNickel), FSM_TRANSITION(Twenty, Quarter, Change, ChangeImpl, returnDimeAndDime), // <- добавлен новый переход FSM_TRANSITION(Change, Restart, Start, Impl, dispense) ) TransitionTable; class VendingMachine : public fsm::Builder<TransitionTable, State, Event> { }; // VendingMachine.cpp остался неизменным |
Обратите внимание:
| ПРИМЕЧАНИЕ Полная версия данного примера находится здесь – каталог ./VendingMachine. |
| ПРИМЕЧАНИЕ Полная версия данного примера находится здесь – каталог ./logging. |
Рассмотрим машину состояний, STD которой представлена на рисунке 8.
Рисунок 8. STD. Система регистрации.
Эта машина контролирует GUI для регистрационной части приложения. Данный пример демонстрирует реализацию условных переходов. Обратите внимание на внутреннее состояние CheckingPassword, на основе которого принимается решение о переходе:
Собственно, это – все.
В любом деле совершенство достигается не тогда, когда нечего больше добавить, а тогда, когда нечего больше отнять Antione de Saint-Exupery
Если предполагается, что SFSM будет использоваться, как широко применяемая библиотека, то пользователям обязательно нужно предоставить возможность его настройки, с тем чтобы каждый мог приспособить проект к своим нуждам.
КА – это совокупность состояний с конечным множеством значений. Переменная состояния может быть целого или перечислимого типа, но также может быть строкой или пользовательским типом. SFSM-реализация не удовлетворяет данным требованиям. Можно использовать только состояния целочисленного и перечислимого типа.
КА меняет состояние в ответ на сообщение. Обычно каждое сообщение реализуется функцией-членом; термин отправить сообщение КА означает вызов функции-члена. С другой стороны интерфейс КА может быть представлен одной единственной функцией, принимающей сообщения как аргумент. SFSM реализация поддерживает только второй вариант.
КА выполняет действия. Выполняемое действие – это функция текущего состояния и входного сообщения. Программист реализует действия (т.е. создает соответствующие тела функций-действий в программном коде), с тем, чтобы система выполнила эту работу. SFSM обязывает чтобы функции-действия являлись методами пользовательского типа (в этой статье они названы контекстами) и, более того, они все должны иметь одинаковую сигнатуру void (*)(). Таким образом, SFSM-реализация вынуждает пользователя создавать контексты как отдельные типы и, при необходимости, продумывать механизмы инициализации объектов этих типов, так как определение контекстов имеет свои ограничения, – контекст обязан иметь конструктор по умолчанию, который будет вызван при конструировании объекта SFSM-типа. Если создание контекста зависит от внешних аргументов, нельзя воспользоваться дополнительным конструктором, и приходится применять “отложенную” инициализацию.
Для описания STD использовалась UML-нотация. Однако, UML-диаграммы состояний и STD не тождественны, хотя и имеют некоторое визуальное сходство. Для описания всех возможных состояний, в которых может находиться объект, а также изменений состояния объекта, которые происходят в результате влияния некоторых событий на этот объект, UML предлагает более богатые средства. В UML существует понятие внутренних переходов для каждого определенного состояния. Например, существует два специальных события, которые могут использоваться во внутренних переходах: событие входа и событие выхода. Эти события также могут вызывать выполнение соответствующих действий. SFSM, использующая STD как высокоуровневую спецификацию, не поддерживает внутренних переходов. Более того, следует обратить внимание на различиях в толкованиях понятия действия, ассоциированного с переходом, в UML и STD. Вернее, на то, в какой момент времени действие происходит. В UML действие происходит после выхода из текущего состояния, и должно быть закончено перед входом в целевое состояние. В STD действие выполняется после того, как переход был совершен, т.е. целевое состояние было достигнуто.
SFSM реализуется посредством метапрограммирования на основе шаблонов. Эта область C++ отнюдь несовершенна. Приходится сталкиваться со следующими проблемами. Отлаживать метакод чрезвычайно сложно (отладчика процесса компиляции в C++ просто не существует). Невозможно получить внятные сообщения об ошибках. Например, при определении дублирующегося перехода в STT (рисунок 3) вместо сообщения “Обнаружен неразрешенный переход из состояния X в состояние Y для сообщения Z. Данный переход конфликтует с ...”, мы получим сообщение о невозможности определения какой-то CHECK_DUPLICATION функции. Далее, метапрограммирование на основе шаблонов базируется на ряде новаторских характеристик языка C++ [13], с поддержкой которых компиляторами в настоящее время существуют определенные трудности. Следовательно, проблема переносимости теоретически очевидна.
Одним из важнейших моментов в принятии того или другого решения является понимание того, что это решение должно быть достаточно хорошим, а не безупречным. В нашем случае мы стоим перед выбором, какой реализации, в конечном счете, быть. Максимальная универсальность, практическая применимость и простота - к сожалению, эти характеристики не ортогональны, а в большей степени, взаимоисключающие. Обладает ли SFSM максимальной гибкостью, чтобы удовлетворять потребности любого пользователя? Нет. Но, с прагматической точки зрения, достаточно ли SFSM универсальна, что бы быть полезной большому количеству пользователей? По всей видимости, да. А как насчет простоты? Для тех, кто не знаком с техникой метапрограммирования на основе шаблонов, ответ очевиден. Но, как известно, незнание закона... Исходный код SFSM (fsm.h) занимает приблизительно 170 строк (три экрана при скролировании), данная статья – ~40 экранов. Что может быть более лаконичным?! Простое решение прекрасно работает большую часть времени, и, поскольку, решение простое, его легко реализовать. Многое, что способствовало бы большей универсальности, было сознательно опущено, что, безусловно, упростило реализацию и сэкономило значительную часть времени и сил. Если вам, как пользователю, такого решения недостаточно, его легко будет дополнить.
