Сергей Сацкий

Введение

С помощью конечных автоматов (далее просто автомат) можно успешно решать обширный класс задач. Это обстоятельство подмечено давно, поэтому в литературе по проектированию программного обеспечения часто приводятся рассуждения на тему применения автоматов ([2], [5], [8]). Однако в процессе моделирования автомат рассматривается с более высокого уровня, нежели это делается в момент его реализации с использованием конкретного языка программирования.

Последний раз журнал C / C++ User’s Journal обращался к проблеме проектирования конечных автоматов (Finite State Machine) в майском выпуске 2000 года ([1]). В этом номере была напечатана статья Дэвида Лафренье (David Lafreniere), где автор описывал использованный им подход. С тех пор прошло много времени, и в данной статье будет сделана попытка применить другой подход к проектированию конечного автомата с учетом современных тенденций в проектировании программного обеспечения.

Для удобства рассмотрим простой пример, который будет использоваться далее. Допустим, что необходимо определить, является ли входная последовательность символов целым числом, допустимым идентификатором, или недопустимой строкой. Под допустимыми идентификаторами будем понимать такие идентификаторы, которые начинаются с буквы и далее содержат буквы и "/", или цифры. Автомат, который поможет решить задачу, показан на рисунке 1. На рисунке используется нотация UML (Unified Modeling Language).

 

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

Следует отметить, что различные источники наделяют подобный автомат различными атрибутами. Чемпионом по их количеству, наверное, является UML ([2]). Здесь можно найти отложенные события (deferred events), внутренние переходы (internal transitions), параметризованные триггеры событий (event triggers with parameters), дополнительные условия переходов (guard conditions), входные функции (entry action), выходные функции (exit action), события, генерируемые по таймеру (time events) и т.д. Однако здесь мы для простоты изложения опустим дополнительные атрибуты (к некоторым из них мы вернемся позже) и сосредоточимся на простой модели, где есть состояния, события и переходы между состояниями.

На данный момент все, что мы имеем – это наглядная и удобная для внесения изменений модель. Как теперь перейти от нее к коду на языке С++? Самый простой из способов реализации – это набор операторов if в том или ином виде. Например:

switch ( CurrentState ) {   case State1: if ( CurrentEvent == Event1 )                {                  . . .                }                if ( CurrentEvent == Event2 )                {                  . . .                }                . . .   case State2: . . .

Не слишком наглядно, не так ли? А теперь представим себе, что мы имеем десятки событий и десятки состояний. Такой код просматривать трудно. Особенно тяжкие проблемы возникают при сопровождении кода, когда к нему надо вернуться через несколько месяцев и внести исправления.

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

Подойдем к проблеме немного с другой стороны. Картинка – это хорошо, но в исходном виде она никаким образом не может быть перенесена в исходный текст. Значит, даже, если решение будет найдено, то это будет нечто промежуточное между картинкой и обычным текстом.

Подход к реализации автомата

Таким промежуточным вариантом представления автомата может быть таблица. Этот способ известен давно, например [5]. Составим таблицу переходов для нашего автомата (таблица 1).

События / состояния	Пусто	число	идентификатор	недопустимая строка
буква	идентификатор	недопустимая строка	идентификатор	недопустимая строка
цифра	Число	число	идентификатор	недопустимая строка

Таблица 1.

Здесь в первой строке перечислены возможные состояния, а в первом столбце – возможные события. На пересечениях указаны состояния, в которые должен осуществиться переход.

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

Предположим, что удалось переложить таблицу на код. Каким бы хотелось видеть этот код? Сформулируем требования к нему ([7]):

Описание автомата (читай – таблица) должно быть сконцентрировано в одном месте. Это даст легкость чтения, понимания и модификации автомата.

Представление автомата должно быть типобезопасным.

Не должно быть ограничений на количество состояний и событий.

События и состояния хотелось бы представить в виде абстрактных типов, определяемых пользователем.

По возможности, автомат хотелось бы сделать гибким и легко расширяемым.

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

По возможности, хотелось бы исключить неправильное использование автомата.

Требования 1 и 7 означают, что все описание автомата хорошо бы поместить в конструктор. В конструкторе же надо проверять правильность описания – требование 6.

class SFiniteStateMachine {     public:         SFiniteStateMachine( <описание автомата> );         . . .     private:         SFiniteStateMachine(); };

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

template <class SState, class SEvent> class SFiniteStateMachine {   . . . };

Требование 2 означает, что не должно использоваться никаких небезопасных операций вида reinterpret_cast.

О требовании 5 поговорим позже, а сейчас обсудим требование 3. В общем случае количество возможных состояний (то есть количество столбцов в таблице) неизвестно. Неизвестно также и количество событий (то есть количество строк в таблице). Получается, что у конструктора класса, который будет представлять собой автомат, переменное количество аргументов. С первого взгляда кажется, что эту проблему легко решить с помощью функций языка C va_arg(), va_copy(), va_end() и va_start() ([6]). Однако, не все так просто. Для этих функций обязательно нужно предусмотреть признаки окончания списков, а у нас количество элементов в строках и столбцах неизвестно. Размерность же задавать нежелательно. Кроме того, эти функции работают гарантированно только для POD (Plain Old Data), а для произвольных типов возможны неприятности.

Подойдем с другой стороны. Напишем, каким хотелось бы видеть конструктор автомата:

SFiniteStateMachine    A(                           <Стартовое состояние>,                           <Список состояний>,                           <Список переходов для состояний>                         );

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

SFiniteStateMachine    A(                           “empty”,                           “empty”,      “number”,  “identifier”, “unknown”,                letter,    “identifier”, “unknown”, “identifier”, “unknown”,                digit,     “number”,     “number”,  “identifier”, “unknown”                         );

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

SFiniteStateMachine(                      const SState &   StartState,                      SStatesListProxy( <список состояний> ),                      STransitionsProxy( <список переходов для события 1> ),                      STransitionsProxy( <список переходов для события 2> ),                      . . .                    );

Рассмотрим список состояний. Здесь остается та же проблема – неопределенное количество состояний. Помочь в ее решении может перегрузка операторов и конструктор по умолчанию. Перечислить аргументы через запятую все равно не удалось бы, но вместо запятой подошел бы и другой разделитель. Таким разделителем может быть <<, то есть обработку списка состояний можно записать так:

SStatesListProxy() << “empty” << “number” << “identifier” << “unknown”

Перегруженный operator<< для SStatesListProxy проверит, что среди состояний нет повторяющихся, а кроме того обеспечит типобезопасность для состояний. Переменное количество состояний при такой записи тоже не проблема. Конструктор для SFiniteStateMachine теперь можно записать так:

SFiniteStateMachine( const SState &   StartState,        (SStatesListProxy() << “empty” << “number” << “identifier” << “unknown”),         STransitionsProxy( <список переходов для события 1> )         STransitionsProxy( <список переходов для события 2> ),                      . . .                    );

Аналогичным образом поступим со списком переходов для одного события. Отличие будет лишь в том, что каждый список переходов имеет еще один атрибут – событие, для которого описываются переходы. Конструктор STransitionsProxy будет принимать один аргумент: событие, а перегруженный operator<< будет принимать состояния.

STransitionsProxy( letter ) << “identifier” << “unknown” << “identifier” << “unknown”

Вернемся к конструктору автомата. У него тоже есть список переменной длины – строки таблицы описания переходов или STransitionsProxy. Решим эту задачу уже известным способом: создание временного объекта и перегрузка operator<< для SStatesListProxy и STransitionsProxy.

SStatesMachineProxy() << SStatesListProxy << STransitionsProxy

Перегруженный operator<< проверит, что сначала идет список состояний, что список состояний только один, что в списках переходов нет повторяющихся событий и в переходах указаны только состояния, указанные в списке состояний. operator<< также проверит, что количество состояний в списках переходов равно количеству состояний в списке состояний. В результате конструктор SFiniteStateMachine будет выглядеть так:

SFiniteStateMachine( const StateType & StartState,                      const SFiniteStateMachineProxy & ProxyMachine );

Теперь очередь за реализацией описанных выше идей. Запишем конструктор автомата для рассматриваемого примера полностью.

SFiniteStateMachine  FirstMachine(                                “empty”, (SFiniteStateMachineProxy() << (SStatesListProxy()        << “empty”      << “number”  << “identifier” << “unknown”) << (STransitionsProxy(letter) << “identifier” << “unknown” << “identifier” << “unknown”) << (STransitionsProxy(digit)  << “number”     << “number”  << “identifier” << “unknown”) ) );

На конструктор SFiniteStateMachine будет возложена задача проверки начального состояния. Оно должно быть в списке состояний.

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

FSMBEGIN( “empty” ) FSMSTATES           “empty”      << “number”  << “identifier” << “unknown” FSMEVENT(letter)    “identifier” << “unknown” << “identifier” << “unknown” FSMEVENT(digit)     “number”     << “number”  << “identifier” << “unknown” FSMEND

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

Детали реализации

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

class SStateMachineException : public std::exception {     private:         const std::string      Message;     public:         SStateMachineException( const std::string &  Msg ) : Message( Msg ) {}         SStateMachineException( const char *         Msg ) : Message( Msg ) {}         virtual ~SStateMachineException() throw() {}         virtual const char * what( void ) const throw() { return Message.c_str(); }     private:         SStateMachineException(); };

В основной программе, использующей класс автомата, можно будет написать так:

. . . try {    . . .   создание и использование автомата    . . . } catch ( std::exception &  Exception ) {   // Поймаем и стандартное исключение и исключение, сгенерированное автоматом }

Вернемся к конструкторам. Поскольку они имеют дело со списками переменной длины, то для сохранения элементов логично воспользоваться контейнерами, предоставляемыми библиотекой STL ([3]). Для хранения одномерного списка воспользуемся контейнером vector, а для таблицы переходов – вектором векторов:

std::vector< std::vector<StateType> >    Transitions;

Алгоритмы STL помогут находить событие в списке событий:

std::vector<EventType>::const_iterator  k( std::find( Events.begin(),   Events.end(), EntryEvent ) );

Поскольку контейнер vector поддерживает operator [], то для поиска состояния, в которое необходимо совершить переход, в таблице переходов можно воспользоваться подобной конструкцией:

NewState = Transitions[ EventIndex ] [ StateIndex ];

где соответствующие индексы могут быть вычислены с помощью алгоритма STL distance:

inline int GetStateIndex( const StateType &  State ) const {     return std::distance( States.begin(), std::find( States.begin(), States.end(), State ) ); }

Разумеется, класс автомата должен будет иметь функцию, принимающую и обрабатывающую событие. Существует два варианта. Первый – это функция, второй – перегрузка какого-либо оператора. Для придания дополнительной гибкости реализуем оба варианта:

SFiniteStateMachine &  AcceptEvent( const EventType &  Event ) {    . . . }

и

inline SFiniteStateMachine & operator << ( const EventType & Event ) { return AcceptEvent( Event ); }

Перегрузка operator << даст возможность использовать автомат в таком стиле:

// Принять события Event1, Event2 и Event3 MyMachine << Event1 << Event2 << Event3;

Остается вопрос: что делать, если придет событие, для которого у автомата нет описания переходов? Возможны варианты: просто проигнорировать такое событие, сгенерировать исключение или сделать что-то, определяемое пользователем. Воспользуемся идеей стратегий ([4]) и включим в число аргументов шаблона функтор, который будет определять нужную стратегию поведения. Такой подход вполне соответствует требованию 5. При этом можно задать стратегию по умолчанию – например, генерировать исключение. Теперь заголовок шаблона выглядит так:

template <class SState, class SEvent, class SUnknownEventStrategy = SThrowStrategy<SEvent> > class SFiniteStateMachine { . . . };

В числе заготовленных стратегий есть и стратегия игнорирования неизвестного события:

template <class SEvent> class SIgnoreStrategy {     public:         inline void operator() ( const SEvent & ) const { return; } };

Если понадобятся другие действия, всегда можно написать собственный функтор по образу и подобию SIgnoreStrategy и передать его шаблону.

Многие источники, описывающие конечные автоматы, упоминают о возможности вызова функций при входе и выходе из состояния. Такую возможность легко предоставить, используя тот же подход стратегий. Функции входа и выхода из состояний удобно определять для класса, представляющего конкретное состояние. Вспоминая о требовании 5, дадим возможность гибкого управления такой возможностью. Предполагая, что функции класса состояния будут называться OnEnter и OnExit, можно написать несколько готовых функторов: не вызывающий ни одну из функций, вызывающий только OnEnter, вызывающий только OnExit и вызывающий обе функции.

template <class SState, class SEvent> class SEmptyFunctor {     public:        inline void operator() ( SState &  From, const SEvent &  Event, SState &  To ) { return; } }; template <class SState, class SEvent> class SOnEnterFunctor {   public:   inline void operator() ( SState &  From, const SEvent &  Event, SState &  To )   { To.OnEnter( From, Event ); } }; template <class SState, class SEvent> class SOnExitFunctor {     public:         inline void operator() ( SState &  From, const SEvent &  Event, SState &  To )         { From.OnExit( Event, To ); } }; template <class SState, class SEvent> class SOnMoveFunctor {     public:         inline void operator() ( SState &  From, const SEvent &  Event, SState &  To )         { From.OnExit( Event, To ); To.OnEnter( From, Event ); } };

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

template <class SState, class SEvent,           class SFunctor = SEmptyFunctor<SState,SEvent>,           class SUnknownEventStrategy = SThrowStrategy<SEvent> > class SFiniteStateMachine { . . . };

Еще один вопрос, связанный с событиями, состоит в том, что событие может быть сгенерировано внутри функции, вызываемой при выходе или входе в состояние. Для обработки таких событий надо соответствующим образом спроектировать функцию, принимающую событие. С учетом таких “внутренних” событий, надо предусмотреть очередь, в которую будут помещаться события. Код, который обрабатывает переходы, должен будет делать это до тех пор, пока очередь не опустеет. В качестве контейнера, подходящего для хранения событий, воспользуемся deque из STL. Поскольку нам нужны только вставка элементов в начало и исключение из конца контейнера, без произвольного доступа, контейнер deque подойдет лучше всего.

Осталось совсем немного. Иногда нужно привести автомат в исходное состояние. Как и в случае с событиями предусмотрим два варианта: обычная функция и перегруженный operator <<. Для перегруженного operator << нужно определить специальный манипулятор:

enum SMachineManipulator {   ResetMachine = 0 }; . . . inline SFiniteStateMachine & operator << ( SMachineManipulator Manipulator )   {     if ( Manipulator == ResetMachine )     return Reset();     return *this;   }

Теперь можно будет написать так:

// Принять событие Event1 и сбросить автомат в начальное состояние MyMachine << Event1 << RestMachine;

Результатом работы автомата является состояние, в которое он перешел. Для получения текущего состояния напишем функцию и перегрузим оператор вывода в поток класса автомата:

inline StateType GetCurrentState( void ) const { return CurrentState; } template <class SState,           class SEvent,           class SFunctor,           class SUnknownEventStrategy > ostream & operator<< (ostream &  Stream,             const SFiniteStateMachine<_SState, _SEvent,               _SFunctor,_SUnknownEventStrategy> & Machine ) {   return Stream << Machine.GetCurrentState(); }

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

MyMachine << Event1 << RestMachine; cout << MyMachine;  // Эквивалентно cout << MyMachine.GetCurrentState();

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

#define FSMStateType   string     // Тип состояния #define FSMEventType   int        // Тип события . . . #undef FSMStateType #undef FSMEventType

Альтернатива есть: полностью указывать все типы.

Осталось поместить шаблон в пространство имен. После этого им можно пользоваться.

Пример использования шаблона

Напишем код для решения поставленной в начале статьи задачи.

#include <iostream> #include <string> using namespace std; #include "FiniteStateMachine.h" using namespace FSM; // Определим тип для событий enum  Events { letter = 0, digit = 1 }; int main( int argc, char ** argv ) {   #define FSMStateType   string   #define FSMEventType   Events   SFiniteStateMachine< StateType,                        EventType,                        SEmptyFunctor<StateType,EventType>,                        SThrowStrategy<EventType>                      >   MyMachine(     FSMBEGIN( "empty" )     FSMSTATES           "empty"      << "number"  << "identifier" << "unknown"     FSMEVENT(letter)    "identifier" << "unknown" << "identifier" << "unknown"     FSMEVENT(digit)     "number"     << "number"  << "identifier" << "unknown"     FSMEND          );   #undef FSMStateType   #undef FSMEventType   cout << "StartState is: " << MyMachine << endl;   MyMachine << digit << digit << letter;   cout << "The 'unknown' state is expected. Current state is: " << MyMachine << endl;   // Внимание: круглые скобки в следующей строке обязательны. Они обеспечат   // правильный порядок выполнения операторов   cout << "Reset the machine. Current state is: " << (MyMachine << ResetMachine) << endl;   MyMachine << letter << digit << letter;   cout << "The 'identifier' state is expected. Current state is: " << MyMachine << endl;   return 0; }

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

Требования к клиентским приложениям

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

Если клиент пользуется предоставленным функтором для вызова функций входа и выхода, то класс состояния должен реализовывать соответствующие функции: OnExit и OnEnter.

Преимущества и недостатки предложенного решения

Преимущества:

Шаблон строго типизирован. Это означает, что неправильно написанный код не будет принят компилятором, и ошибка не дойдет до времени выполнения программы.

Расширены понятия состояния и события. Теперь это произвольные классы, написанные пользователем.

Не используется оператор reinterpret_cast<…>, способный привести к неправильным результатам.

Все описание автомата сосредоточено в одном месте. Нет привязки к последовательности описания реакций на события.

Гибкость поведения определяется пользовательскими функторами. Предоставляется набор уже готовых функторов.

Возможно динамическое создание описания конечного автомата. Например, можно создать экземпляры Proxy-классов, прочитать из файла описание автомата, а затем создать экземпляр SFiniteStateMachine.

Нет операций создания и удаления объектов с помощью операторов new и delete.

Нет никаких требований к классам состояний и событий (кроме возможности их сравнения).

Недостатки:

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

Надо писать две директивы препроцессора или использовать длинный префикс. Однако это лишь проблема набивки текста.

Лично я готов мириться с этим коротким списком недостатков ради полученных преимуществ.

Возможные пути усовершенствования шаблона

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

Можно отказаться от промежуточного класса SFiniteStateMachineProxy. Это позволит сэкономить на копированиях, но внесет потенциальную возможность неправильного использования шаблона.

Можно ввести манипуляторы, которые позволят в явном виде при описании переходов указывать такие, которые надо игнорировать, или генерировать исключение при их появлении.

Потоковая безопасность

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

Список литературы

C/C++ User’s Journal, May 2000

Booch G., Rumbaugh J., Jacobson I. The Unified Modeling Language User Guide. Addison-Wesley, 2001

Meyers S. Effective STL. Addison-Wesley, 2001

Alexandrescu A. Modern C++ Design. Addison-Wesley, 2002

Lewis P., Rosenkrantz D., Stearns R. Compiler Design Theory. Addison-Wesley, 1976

Schildt H. С/С++ Programmer’s Reference. Second Edition. Williams, 2000

Meyers S. Effective C++. Second Edition. Addison-Wesley, 1998 and More Effective C++. Addison-Wesley, 1996

Sutter G. Exceptional C++. Addison-Wesley, 2002