Дизайн шаблона конечного автомата на C++
Эффективное использование STL

Author / Автор: Сергей Сацкий
Publication date / Опубликовано: 12.02.2003
Version / Версия текста: 1.1

Введение

С помощью конечных автоматов (КА) можно успешно решать обширный класс задач. Это обстоятельство подмечено давно, поэтому в литературе по проектированию программного обеспечения часто приводятся рассуждения на тему применения КА ([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]. Составим таблицу переходов для нашего КА:

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

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

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

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

  1. Описание переходов КА (читай - таблица) должно быть сконцентрировано в одном месте. Это даст легкость чтения, понимания и внесения изменений.
  2. Реализация КА должна быть типобезопасной.
  3. Не должно быть ограничений на количество состояний и событий.
  4. События и состояния хотелось бы иметь как абстрактные типы, определяемые пользователем.
  5. По возможности, реализацию КА хотелось бы сделать гибкой и легко расширяемой.
  6. По возможности, хотелось бы проверять описание переходов КА.
  7. По возможности, хотелось бы исключить неправильное использование класса, представляющего КА.

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

class SStateMachine
{
    public:
        SStateMachine( <описание КА> );

        . . .

    private:
        SStateMachine();
};

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

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

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

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

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

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

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

SStateMachine    A( 
                    "empty",

                    "empty",      "number",  "identifier", "unknown",
         letter,    "identifier", "unknown", "identifier", "unknown",
         digit,     "number",     "number",  "identifier", "unknown"
                  );

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

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

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

SStatesListProxy() << "empty" << "number" << "identifier" << "unknown"

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

SStateMachine( const SState &   StartState,

  (SStatesListProxy() << "empty" << "number" << "identifier" << "unknown"),

  STransitionsProxy( <список переходов для события 1> )
  STransitionsProxy( <список переходов для события 2> ),
                 . . .
             );

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

STransitionsProxy(letter) << "identifier" << "unknown" << "identifier" << "unknown"

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

SStatesMachineProxy() << SStatesListProxy << STransitionsProxy

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

SStateMachine( const StateType &          StartState, 
               const SStateMachineProxy & ProxyMachine );

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

SStateMachine  FirstMachine(
                               "empty",
(SStateMachineProxy() << 
(SStatesListProxy()        << "empty"      << "number"  << "identifier" << "unknown") <<
(STransitionsProxy(letter) << "identifier" << "unknown" << "identifier" << "unknown") <<
(STransitionsProxy(digit)  << "number"     << "number"  << "identifier" << "unknown")
)
);

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

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

FSM_BEGIN( "empty" )

FSM_STATES         "empty"      << "number"  << "identifier" << "unknown"

FSM_EVENT(letter)  "identifier" << "unknown" << "identifier" << "unknown"
FSM_EVENT(digit)   "number"     << "number"  << "identifier" << "unknown"

FSM_END

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

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

Среди вспомогательных элементов, которые понадобятся на этапе реализации, находятся исключения. SStateMachine будет генерировать их при обнаружении ошибки в описании КА. При разработке своего класса исключений лучше всего воспользоваться наследованием от класса стандартного исключения. Это даст возможность указывать в блоке 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();
};

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

. . .
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 ) );
}

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

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

и

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

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

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

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

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

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

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 SStateMachine { . . . };

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

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

enum SMachineManipulator { ResetMachine = 0 };

. . .

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

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

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

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

inline StateType GetCurrentState( void ) const { return CurrentState; }


template <class SState, 
          class SEvent, 
          class SFunctor, 
          class SUnknownEventStrategy >
ostream &
operator<< (ostream &  Stream,
            const SStateMachine< 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 "fsm.h"
using namespace FSM;


  // Определим тип для событий
enum  Events { letter = 0, digit = 1 };

int main( int  argc, char **  argv )
{

    #define FSMStateType   string
    #define FSMEventType   Events

    SStateMachine< StateType,
                   EventType,
                   SEmptyFunctor<StateType,EventType>,
                   SThrowStrategy<EventType>
                 >
    MyMachine(

      FSM_BEGIN( "empty" )

      FSM_STATES         "empty"      << "number"  << "identifier" << "unknown"

      FSM_EVENT(letter)  "identifier" << "unknown" << "identifier" << "unknown"
      FSM_EVENT(digit)   "number"     << "number"  << "identifier" << "unknown"

      FSM_END
             );

    #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 классов, прочитать из файла описание КА, а затем создать экземпляр SStateMachine.
  • Нет операций создания и удаления объектов с помощью операторов new и delete.
  • Нет никаких требований к классам состояний и событий (кроме возможности их сравнить).

Недостатки перечислены в списке ниже:

  • Много операций копирования при создании экземпляра объекта, реализующего КА. Однако этот недостаток отчасти нивелируется тем, что обычно объект создается один раз, а затем используется много раз.
  • Надо писать две директивы препроцессора или использовать длинный префикс.

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

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

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

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

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

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

Литература

  1. C/C++ User's Journal, May 2000
  2. Booch G., Rumbaugh J., Jacobson I. The Unified Modeling Language User Guide. Addison-Wesley, 2001
  3. Meyers S. Effective STL. Addison-Wesley, 2001
  4. Alexandrescu A. Modern C++ Design. Addison-Wesley, 2002
  5. Lewis P., Rosenkrantz D., Stearns R. Compiler Design Theory. Addison-Wesley, 1976
  6. Schildt H. С/С++ Programmer's Reference. Second Edition. Williams, 2000
  7. Meyers S. Effective C++. Second Edition. Addison-Wesley, 1998 and More Effective C++. Addison-Wesley, 1996
  8. Sutter G. Exceptional C++. Addison-Wesley, 2002

Verbatim copying and distribution of this entire article is permitted in any medium, provided this notice is preserved.

Разрешается копирование и распространение этой статьи любым способом без внесения изменений, при условии, что это разрешение сохраняется.
Last Updated: September 27, 2005