Design of a Finite State Machine C++ Template
Effective STL usage

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

Introduction

Finite state machines can help to solve various tasks. That feature was noticed long ago so there are many discussions of the finite state machine applications in software design articles and books ([2], [5], [8]). However, finite state machines are considered on a software design stage on a much higher stage than they are by a particular programming language on a coding stage.

Last time the C/C++ User's Journal discussed a finite state machine implementation in May 2000 issue ([1]). David Lafreniere described the approach he used in his article. Some time has passed since that time and the present article describes a different approach to a finite state machine implementation bearing in mind modern tendencies in software design.

To simplify the further discussion let us take a simple example. Let us assume that it is necessary to determine whether an input sequence of symbols is an integer number, an identifier or an unknown string. Let us also suppose that an identifier starts with a letter. A transition graph of a finite state machine that helps to solve the task is shown in figure 1. The UML notation is used in the figure.


Figure 1. A finite state machine transition graph which recognizes what an input sequence of symbols is.

It is necessary to say that different sources introduce different attributes into a similar graph. Most probably the champion in the attributes amount is UML ([2]). It adds deferred events, internal transitions, event triggers with parameters, guard conditions, entry actions, exit actions, time events, etc into a transition graph. However, to simplify the discussion we leave out auxiliary attributes (we will get back to some of them later) and concentrate on a simple model where there are states, events and transitions.

At the moment all we have is a transition graph which is easy to understand and modify. How can we move to a C++ code? The simplest way is some sort of if statements. For example:

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

It is not as clear as the transition graph, is it? Now let us imagine for a moment that there are dozens of events and transitions. Such a code is difficult to read. More serious problems appear at a support stage when the code is modified some months or years later. A transition graph is much easier to modify.

Another possible implementation of a finite state machine is a set of functions. Each of them represents a state. Each function returns a pointer to a function, which represents a new state. Such an implementation is not easy to support either.

Let us try to look at the problem from another point of view. A transition graph is a nice idea however there is no way to have it directly in a C++ source code. Therefore even if a suitable solution is found it will be something between a picture and a regular text.

The Approach

A table can be such a suitable solution of a transition graph representation. This way is well known for a long time, see [5] for example. Let us complete a table for the taken example:

Events / states Empty A number An identifier An unknown string
A letter An identifier An unknown string An identifier An unknown string
A digit A number A number An identifier An unknown string

The first row in the table lists all the possible states while the first column lists all the possible events. A column is selected by the current state. An incoming event selects a cell in the current column. The cell gives a state, which the finite state machine moves to.

A table representation of a finite state machine transition graph is clearer than its spread representation in a form of if statements or a set of functions. It is quite reasonable to try to transfer a table into a C++ code.

Let us imagine for a moment that a table has been successfully transferred into a C++ code. What are the requirements to such code? Let us write those [7]:

  1. A transition graph description (that is a table) must be concentrated in one place. It provides easy reading, understanding and modifications abilities.
  2. A finite state machine implementation must be type safe.
  3. There should not be any limitations on number of states and events.
  4. A state and an event types should be user defined ones.
  5. A finite state machine implementation should be flexible and easy to extend.
  6. A transition graph description should be checked if it is possible.
  7. An illegal usage of a finite state machine template should be prevented as far as it is possible.

Requirements #1 and #7 mean that all the finite state machine description should be in a constructor. The constructor should also check a transition graph description (requirement #6).

class SStateMachine
{
    public:
        SStateMachine( <finite state machine description> );

        . . .

    private:
        SStateMachine();
};

Requirement #4 means that a template should be used and it will have at least two parameters - a state type and an event type.

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

Requirement #2 means that no unsafe operations like reinterpret_cast should be used.

Leave requirement #5 for later discussion and concentrate on requirement #3. In a common case a number of possible states (that is a number of columns in a table) is unknown. A number of events (that is a number of rows in a table) is also unknown. That means that the SStateMachine constructor has a variable number of arguments. The first impression is that this problem could be easily solved with va_arg(), va_copy(), va_end() and va_start() C functions ([6]). However it is not so easy. These functions require having end-of-list markers while we have an unknown number of elements in both rows and columns. Moreover these functions work perfect for POD (Plain Old Data) while for user types they can lead to unpredicted behavior.

Let us try to consider the finite state machine template from another side. Let us write a constructor prototype as we want to have it:

SStateMachine    A( 
                    <Start state>,
                    <List of states>,
                    <Transitions list for each of the events>
                  );

If we have a constructor as shown above we can format the source code typed by a monospaced font as a table. Switch a fantasy on:

SStateMachine    A( 
                    "empty",

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

There is no problem with the start state. It is simply an object of a state type. The states list and the transitions lists are more complicated issues. There is no option to give the states as a comma separated one. Moreover it would be very convenient to have a fixed number of arguments for the SStateMachine constructor. Luckily it is possible. Temporary objects could be created and each of them will be responsible for processing its own list.

SStateMachine( 
               const SState &   StartState,
               SStatesListProxy( <states list> ),
               STransitionsProxy( <transitions list for event 1> ),
               STransitionsProxy( <transitions list for event 2> ),
               . . .
             );

Let us consider the states list. There is the same problem here - a number of states is unknown. An operator overloading and a default constructor can help to solve the problem. There is no option to use a comma-separated list any way however another list elements separator will also be suitable. The << can be used as a separator. So the states list processing could be written as follows:

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

The overloaded operator<< for the SStatesListProxy will check that the states are unique and will provide a type safety for the states. The variable length list is not a problem here either. Now the SStateMachine constructor can be written as follows:

SStateMachine( const SState &   StartState,

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

    STransitionsProxy( <transitions list for event 1> )
    STransitionsProxy( <transitions list for event 2> ),
                 . . .
             );

Let us do the similar things with the transitions list for a single event. The only difference is that the transitions list has an additional attribute - an event that triggers the described transitions. The STransitionsProxy constructor will accept an argument: an event. The overloaded operator<< will accept states.

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

Let us come back to the SStateMachine constructor. It also has a list of variable length - the transitions table rows that are STransitionsProxy. Let us solve this task by an already known way: a temporary object creation and the operator<< overloading for SStatesListProxy and STransitionsProxy.

SStatesMachineProxy() << SStatesListProxy << STransitionsProxy

The overloaded operator<< will check that a states list comes first, that the list is the only, that states are unique in the transitions lists and that transitions mention the states which are from the list of states. The operator<< will also check that a number of states in the transitions list is equal to a number of states in the list of states. So the SStateMachine constructor will be written as follows:

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

Now it is a time to implement all the described ideas. Let us write the complete SStateMachine constructor for the taken example.

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

The SStateMachine constructor will check if the start state is in the list of states.

We imitated a table for the SStateMachine constructor arguments earlier using the text formatting. However it is not everything. The entire template related details of a state machine transitions description were left out of considering. In practice it means that we will have to specify user types in the object constructing code which leads to a "messy" code. In spite of the preprocessor problems it can help here. The constructor arguments get similar to the following:

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

Such a code is acceptable for an everyday usage.

Implementation Details

There are some auxiliary things which will be needed on an implementation stage including exceptions. SStateMachine will generate exceptions if errors are found in a finite state machine description. It is the best way to derive our own exceptions from the standard one. It gives ability to specify a reference to the standard base exception class only in a catch block. Our own exception class could be defined as follows:

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

A code which uses SStateMachine can be similar to the following:

. . .
try
{
   . . .
  creation and usage of SstateMachine
   . . .
}
catch ( std::exception &  Exception )
{
  // Catch both the standard and our own exception 
  // generated by SStateMachine
}

Let us come back to the constructors. As soon as they are working with variable length lists it is logical to store the elements in the STL containers ([3]). To store one dimensional list we can use a vector container. To store transition table we can use vector of vectors:

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

The STL algorithms will help to find an event in the list of events:

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

As soon as the vector container provides the operator [] we can use the following expression to find a new state in the transition table:

NewState = Transitions[ EventIndex ] [ StateIndex ];

Where the corresponding indexes can be calculated using the distance STL algorithm:

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

Surely the SStateMachine class must have a function that accepts an event and processes it. There are two options. The first one is a function. The second is an overloaded operator. In order to provide better flexibility both options will be implemented:

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

and

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

Overloaded operator<< gives ability to write the following code:

    // Accept Event 1, Event2 and Event3 events
MyMachine << Event1 << Event2 << Event3;

There is still a question, what to do if an event for which SStateMachine has not a transitions list comes? There are three options:

- Ignore such an event

- Generate an exception

- Execute a user defined action

Let us employ an idea of strategies ([4]) and include a function object to the template arguments list. The function object will define a suitable strategy for an unknown event. This approach meets requirement #5. A default strategy - generate an exception - is also provided. Now the template looks as follows:

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

The ignoring an unknown event strategy is also included into the template package:

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

If there is a necessity to do something else in case of an unknown event then a template users can write their own function object similar to SIgnoreStrategy and pass it to the template.

Many sources which describe implementations of finite state machines mention a possibility to call functions at the enter into and at the exit from a state. This feature is easy to implement employing the strategies idea. It is quite convenient to define entry and exit functions for a state representing class. Bearing in mind requirement #5 let us provide flexibility in the feature control. Assuming that the corresponding functions are called OnEnter and OnExit we can write some ready to use function objects which call no functions, call one or both of them.

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

A default strategy - call no functions - can be passed as a default value of a template argument. The call functions strategy most probably will be changed more often than the unknown event strategy. Therefore it is reasonable to put the call functions strategy before the unknown event strategy in the list of the template arguments:

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

One more events related issue is that an event can be generated in the OnEntry or OnExit function. In order to support this feature the accepting event function must be designed in appropriate manner, which provides such an "internally generated" event processing. Using a queue, which holds all the incoming events, can do this. The event processing code should do its job till the last event in the queue.

There is not too much left. Sometimes it is necessary to reset a finite state machine. Similar to the vents accepting feature let us to implement both a regular function and an overloaded operator<<. For the overloaded operator<< it is necessary to define a manipulator:

enum SMachineManipulator { ResetMachine = 0 };

. . .

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

Now we can write something similar to the following:

    // Process the Event1 and reset the machine
MyMachine << Event1 << RestMachine;

The result of finite state machine job is a state, which the machine reached after a sequence of events. In order to get a current state let us write a function and overload a stream output operator for 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(); }

Now if the state representing class has a stream output operator we can write a code similar to the following:

MyMachine << Event1 << RestMachine;
cout << MyMachine;  // Equal to cout << MyMachine.GetCurrentState();

As we discussed before to reduce code typing and improve readability some macroses are defined. They request a preliminary #define directive for event and state types. This requirement is raised by the fact that nested preprocessor directives are forbidden. The template uses proxy classes that are also in need to know event and state types. So in order to use macroses it is necessary to do the similar:

#define FSMStateType   string     // State type
#define FSMEventType   int        // Event type

. . .

#undef FSMStateType
#undef FSMEventType

There is an alternative - to give fully qualified types in the finite state machine description.

There is one thing left - to put the template into a namespace and the template is ready to use.

The Template Usage Example

Let us write the complete code for the taken at the very beginning example.

#include <iostream>
#include <string>
using namespace std;

#include "fsm.h"
using namespace FSM;


  // Events type definition
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;

        // Attention: brackets in the line below are obliged.They provides
        //            the right sequence of execution
    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;
}

Some details are left out of the example. These are exception handling, introducing on-enter and on-exit functions, etc. In order to demonstrate a user strategies usage all the arguments of the MyMachine constructor are explicitly specified including default arguments.

Requirements To Clients

There are not too much requirements. The event and state classes must implement operator==, operator= and a copy constructor. operator= is used to find events and states in the corresponding lists by the STL algorithm find. A copy constructor is used in a lists and other elements initialization.

If a client uses a function object to call on-enter and/or on-exit functions the state class has to implement the corresponding functions: OnExit and/or OnEnter.

Advantages and Drawbacks of The Proposed Solution

The advantages are listed below:

  • The template is type safe. It means that a compiler will reject an incorrect code.
  • Event and state types are user defined.
  • There are no reinterpret_cast< . . . > or C-style casts in the template which could lead to incorrect results.
  • All the finite state machine description is concentrated in one place. There is no link to a sequence of event-triggered actions.
  • The template flexibility is defined through user function objects. A set of the useful function objects is also provided.
  • There is a possibility to form a finite state machine behavior dynamically. For example, it is possible to create proxy classes instances then read a finite state machine description from a file and finally create a SStateMachine instance.
  • There are no creation and destruction operations that use the new and delete statements.
  • There are no special requirements to the state and event types (except a possibility to compare copies).

Drawbacks are listed below:

  • There are many copy operations during SStateMachine construction. However this pit stop is partially compensated by the fact that usually an object is created once and then used many times.
  • It is necessary to give two preprocessor directives or to use a long prefix for the event and state types. However it is a code typing problem only.

Personally I am ready to put up with this short list of disadvantages for the sake of acquainted advantages.

The Ways to Even More Flexibility

An attentive reader could note that the template could be modified to provide more flexibility and improve a performance. The list below gives some of the ways which are on a surface:

  • It is possible to decline the SStateMachineProxy class usage. It saves copy operations by the price of potential template misuse.
  • It is possible to introduce manipulators which allow to specify explicitly transitions that should be ignored or should raise an exception.

Thread Safety

The STL containers are used in the template. A multithreaded access to the containers could lead to program crashes. As soon as the template is purposed to be a platform independent no synchronization objects were used. The synchronization objects could be an advantage or a drawback depending on a particular situation. If the multithreaded access is not needed the overheads will appear. However an experienced developer can easily add synchronization objects to provide a safe multithreaded access.

References

  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 29, 2005