c++ tips - Finite state machine parsing

[ben2ong2]

RESPONSE: You are not allowed to view links. Register or Login (Robert Martin), 3 Jun 93

Finite state machines in C++ are easy to create.  However, the
mechanisms is not immediately obvious.

The mechanism shown below is based upon an article in the January 1991
C++ report by Immo Huneke.  I have written a simple compiler which
takes state transition tables like the one below and writes the C++
code in the format described below.  I'll be happy to email this
compiler to anybody who is interested. 

[ I have the latest version of this. -adc ]

Consider the canonical "Subway Turnstyle" example.  It has an
State/Transition table that looks something like this:

[ Current    Event    Next         Action ]

  Locked     Coin     Unlocked     Unlock
  Locked     Pass     Locked       Alarm
  Unlocked   Pass     Locked       Lock
  Unlocked   Coin     Unlocked     ThankYou

Thus, the machine can have two states (Locked and Unlocked) and
accepts two events.  The Coin event indicates that someone has
deposited a coin.  The Pass event indicates that someone has "passed
through" the turnstyle.  There are also four behaviors that the
machine invokes.  It can lock the turnstyle, unlock the turnstyle,
sound an alarm, and thank the user for extra money.

So, in the Locked state, when a Coin event is received, the machine
transitions to the Unlocked state and invokes the Unlock behavior.
etc.

Now imagine a C++ class:

   Class TurnStyleContext
   {
           public:
       void Lock();
            void Unlock();
            void Alarm();
            void ThankYou();
   };

This class captures all the behavior of the state machine.  Now
consider the following class:

class TurnStyleState
{
  public:
    virtual void Coin(TurnStyleContextFSM*) {};
    virtual void Pass(TurnStyleContextFSM*) {};
};

This class captures all the events as virtual functions.  This class
is a base class, and not one of the actual states of the FSM. 

Now we connect this particular state class to the TurnStyleContext as
follows.

class TurnStyleContextFSM : public TurnStyleContext
{
  public:
    static UnlockedTurnStyleState Unlocked;
    static LockedTurnStyleState   Locked;
    void Coin() {itsState.Coin(this);}
    void Pass() {itsState.Pass(this);}

    TurnStyleState* GetState() {return itsState;}
    void SetState(TurnStyleState* s) {itsState = s;}
  private:
    TurnStyleState* itsState;
};

This augments the inherited behaviors of the turnstyle with the state
machine.  The first to variables are static state variables which
represent the states of the FSM.  Then there are transition functions
which simply defer the transitions to the current state variable (itsState).

Now we write the individual states:

class LockedTurnStyleState : public TurnStyleState
{
  public:
    virtual void Coin(TurnStyleContextFSM* c)
    {c->SetState(TurnStyleContextFSM::unlocked); c->Unlock();}

    virtual void Pass(TurnStyleContextFSM* c)
    {c->Alarm();}
};

class UnlockedTurnStyleState : public TurnStyleState
{
  public:
    virtual void Coin(TurnStyleContextFSM* c)
    {c->ThankYou();}

    virtual void Pass(TurnStyleContextFSM* c)
    {c->SetState(TurnStyleContextFSM::locked); c->Lock();}
};

These classes implement the transitions for each state using virtual
deployment.  The TurnStyleContextFSM::itsState variable points at the
current state object.  Event functions are virtually deployed to
these state objects.

Now the main program is anticlimactic:

main()
{
  TurnStyleContextFSM fsm;
  fsm.SetState(TurnStyleContextFSM::locked);  // initial state;
  fsm.Lock();  // Make sure the gate is locked.

  for(;
  {
    if (a coin has been dropped) fsm.Coin();
    if (the user passes) fsm.Pass;
  }
}

-----------------------------------------------------------------

The state machine compiler that I mentioned above takes a simple state
transition table and writes the C++ classes for you.  The new version
supports substates and a slightly enhanced syntax.  However, tables
like the one in the early part of this article are valid syntax for
the compiler.