|
|
|
|
|
Design of a Finite State Machine C++ Template
|
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.
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]:
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.
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.
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.
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.
The advantages are listed below:
Drawbacks are listed below:
Personally I am ready to put up with this short list of disadvantages for the sake of acquainted advantages.
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:
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.
