States and Transition Tables
The condition of an FSM at any instance is known as the "state." The state in Listing Three contains information pertinent to how the state machine behaves when an event is received. One of the things that may or may not appear intuitive from the class diagram is how loosely coupled the states are from the state machine. The state machine is only concerned with the current state. At construction, a start state is passed in, implying that the states are created prior to the state machine (which makes sense if you think about it). Navigation from state to state occurs through the transaction table that is contained within each state.
Listing Three: The state.
template <class T, class EV, class CMP>
class Transition
{
friend State<T,EV,CMP>;
public:
State<T,EV,CMP>* operator()( const T& _T, const EV& ev ) throw() {
(*m_evAction)(_T,ev);
return m_stNext;
}
protected:
Transition( const State<T,EV,CMP>& stNext, Action<T,EV>* evAction ) :
m_stNext(const_cast<State<T,EV,CMP>*>(&stNext)), m_evAction(evAction) {
}
... // Other member information
};
template <class T, class EV, class CMP = std::less<EV> >
class State
{
// State Transition Table Type
typedef std::map<const EV,const Transition<T,EV,CMP>*,CMP>
TransitionTable;
public:
typedef State<T,EV,CMP> state_type;
typedef EventAction<T,EV>::HANDLE HANDLE;
public:
State( HANDLE hEnter = 0, HANDLE hExit = 0 ); {
if ( hEnter == 0 ) {
m_evEnter = new NoAction<T,EV>;
}
else { m_evEnter = new EventAction<T,EV>(hEnter); }
if ( hExit == 0 ) {
m_evExit = new NoAction<T,EV>;
}
else { m_evExit = new EventAction<T,EV>(hExit); }
}
~State() {
TransitionTable::iterator iter;
for ( iter = m_stTable.begin(); iter != m_stTable.end(); iter++ ) {
delete const_cast<Transition<T,EV,CMP>*>( iter->second );
}
delete m_evEnter; delete m_evExit;
}
... // other API functions not shown
private:
TransitionTable m_stTable;
Action<T,EV>* m_evEnter;
Action<T,EV>* m_evExit;
};
</pre
<P>
<p>The state transaction table (STT) is a sorted associative container (STL <code>map</code>) where the event (EV) is the key and an instance of a transition is the data. As events are passed into the state machine, the transition is retrieved from the transition table, if the event is valid for this state. The STL <code>map</code> was an obvious choice because events associate with transitions to the next state and are portable in the C++ Standard Library. </p>
<P>
<p>I initially considered the hash version of STL's <code>map</code> (<code>hash_map</code>) because the order of the event-transition pairs was not important. The worst-case complexity of most operations in a hashed associative container is linear in the size of the container, but the average time complexity is constant [3]. This is ideal for a situation in which information is simply stored and retrieved without regard to ordering. The drawback, though, is that <code>hash_map</code>s are not Standard Library entities from an ANSI perspective and could create portability problems for our state-machine framework. Since the number of transitions from a given state is typically not large, the time difference appears to be minimal at best, considering that events are typically integral values.</p>
<P>
<P>
<h3>Action Handling</h3>
<p>Transition from state to state has little merit, other than behavior modeling, unless something is performed on object <code>T</code>. In this framework, you hide <code>T</code>, but how <code>T</code> is accessed is left to the action handlers. While the state machine manages the behavior of <code>T</code>, the action objects manipulate the data and attributes of that object during transition. It is only through the action objects that the state machine can alter the data within <code>T</code>. In other words, the state machine resembles a container class that manages behavior.</p>
<p>Actions are typically invoked when an event occurs forcing a state transition. You may recall Mealy and Moore machines from your college textbooks. The handling of the output or action, in this case, is based on what model of state machine we use. In the framework presented, actions are associated with both transitions and states, so does this make us a Mealy-Moore Machine? (Okay, just a little Automata Theory humor.)</p>
<P>
<p>For each transition there is an action handler. By default, if no action is to be performed on it, and in some cases this can very well happen, then the default action handler is imposed (more on this in a bit). There are also action handlers for states: on <code>Entry</code> and on <code>Exit</code>. As with transitions these are optional as well, but provide this added flexibility (in which you will also find doing UML modeling) for the developer.</p>
<P>
<p>Now comes an interesting situation that I am sure will draw fire from C++ purists. As mentioned, a default action handler (which does nothing) is used when no action by <code>T</code> is required for a given transition or state entry/exit. I am not a big fan of using conditionals, especially in real time when an alternate, faster solution presents itself — especially one that seems more object oriented. In the case of a default handler, I don't want to query the <code>State</code> or <code>Transition</code> if it has a valid handler, as that is left to those objects. However, action handlers take a <code>this</code> pointer of type <code>T</code> and store a member function pointer into <code>T</code>, <code>T::*fp</code>.</p>
<P>
<p>Because of this, I could not find a clean way of forcing <code>T</code> to have a default null handler, and had to create a scheme in which the function <code>operator ()</code>, was overridden. The function operator requires a pointer to <code>T</code> to invoke the action, but in situations where no action was required and to avoid conditional event processing, I ended up making <code>operator ()</code> virtual and created an abstract base template class for <code>Action<></code>, as in Listing Four. So let the tomato throwing begin! Of course, it's not like I am the first to do both dynamic and static binding of an object in a language that supports it.</p>
<P>
<h4>Listing Four: Base action class.</h4>
<P>
<pre class="brush: cpp; html: collapse;" style="font-family: Andale Mono,Lucida Console,Monaco,fixed,monospace; color: rgb(0, 0, 0); background-color: rgb(238, 238, 238); font-size: 12px; border: 1px dashed rgb(153, 153, 153); line-height: 14px; padding: 5px; overflow: auto; width: 100%;">
// Base action class
template <class T, class EV>
struct Action
{
virtual void operator()( const T&, const EV& ) throw() = 0;
};
// No Action default
template <class T, class EV>
struct NoAction : public Action<T,EV>
{
void operator()( const T&, const EV& ) throw() {};
};
// Action Handler for "T"
template <class T, class EV>
struct EventAction : public Action<T,EV>
{
typedef void (T::*HANDLE)( const EV& ev );
explicit EventAction( HANDLE hAction ) :
m_hAction(hAction) {}
void operator()( const T& _T, const EV& ev ) throw() {
(_T.*m_hAction)(ev);
}
private:
HANDLE m_hAction;
};
A first approach was not letting the T parameter propagate any further than the StateMachine<> class to avoid code bloating. This initially worked, but required a pointer to T in the action objects and the bloating occurred in the many instances of action objects of the many instances of T (admittedly, this can be confusing). As this framework matures, I am sure there will be a better implementation that saves both execution time and space.
Putting It All Together
So when do you use an FSM during software development? The heuristic I tend to follow is this straightforward: If you are developing a subsystem or object that runs in its own context or thread that is control oriented in its implementation, then a state machine is a candidate for managing it.
Figure 2 is a state transition diagram (STD) of a phoneline. This is not a fully functional phoneline, but suffices for demonstration purposes. The source code for this implementation, available at ftp://ftp.drdobbs.com/sourcecode/cuj/2004/cujapr2004.zip, uses both versions of the framework.
Figure 2: State transition diagram of a phoneline.
In the included software I have three important member functions: start, halt, and reset. Even though the state machine does not provide synchronization in form of semaphores or mutexes, it does require itself to be running prior to accepting input. In this, the state machine itself has its own state transition diagram consisting of just two states: running and stopped. Only in the running state can events be processed. Resetting the state machine allows a restart mechanism, which is why during object creation the initial start state is stored.
Synchronization
The most obvious weakness to the framework is synchronization of entry into the state machine. The whole intent for this framework was to work in the context of its own thread, and (as Microsoft did originally with COM) leave the handling of synchronizing threads to you. State machines are invoked on a first-come/first-served basis, so entry into it should be handled in a critical section. One way of doing this is to protect each call in the state machine, by inserting an entry and exit in each method that is public to users.
A better solution is to have a single entry point via dispatchers — the obvious choice would be the event handler (Figure 2). Recall I said that events are not handled in the state machine; they are only routed and used to invoke a response. The biggest reason for separating the event handling from the event processing is that event handlers typically use system synchronization and FIFOs or queues.
Conclusion
This approach is by no means a silver bullet to writing state machines. One drawback in the approach with either version of the state machine is the chicken and egg problem. Since the states are not tightly coupled to the state machine, except via the current state, initialization becomes a problem. You will note in the example software that the states, actions, and state machines are created dynamically, and in the case of using aggregation, object T. This could be perceived as a flaw in the framework, since it should support both static and dynamic implementations. In fact it does, but not to the fullest extent.
I can see room for improvement, but I feel I am on the right path. No software is always the most correct solution. As software engineers and architects, we often find ourselves refining, tuning, and in some cases, rewriting our designs over time. It's like buying a computer at times. Either you want to wait until the prices are just right or you are waiting for that new technology. This can be a perpetual nightmare until you finally tell yourself, just buy it and realize it will be obsolete the minute you unpack it. I guess the same can be said about software design.
References
[1] Martin, Robert C. "UML Tutorial: Finite State Machines," C++ Report (June 1998).
[2] Stroustrup, Bjarne. The C++ Programming Language, Special Edition, Addison-Wesley 1997.
[3] Musser, David R. STL Tutorial and Reference Guide: C++ Programming with the Standard Template Library, Second Edition, Addison-Wesley 2001.
P. Dale Mason has focused on embedded real-time and desktop application software development for over 15 years. He holds a Masters in Computer Science Engineering and Mathematics from the University of Louisville and is presently working with Visual Studio.NET and C++. Dale can be contacted at [email protected].
