c++ tips - What is an FSM?

[ben2ong2]

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

A Finite State Machine (FSM) is a map of the way a system changes
state based upon external stimuli, and what actions it take as a
result of those state changes.  For example, consider a subway
turnstyle:


Current State       Event        New State        Action
------------------------------------------------------------------
Locked              Coin         Unlocked         Unlock the gate
Unlocked            Passthrough  Locked           Lock the gate
Unlocked            Coin         Unlocked         Say thank you.
Locked              Passthrough  Locked           Sound Alarm.

The table above is called a state transition table (stt) or more
commonly a state map.  It is read as follows:

When the system is in the "Locked" state, and receives the "Coin"
event, then the system goes to the "Unlocked" state and performs the
"Unlock the gate" action.   etc...

State machines are often drawn diagramatically using a notation called
state transition diagrams (STD).


  Passthru / Alarm                                    Coin / Thank you
   +--------+                             +--------------+
   |        |            Coin / Unlock the gate        |         |
   |    +---+----+--------------------------------->+-----+----+    |
   +--->| Locked |                                  | Unlocked |<--------+
   +--------+<---------------------------------+----------+
             Passthru / Lock the gate


The boxes are called "states", the arrows are called "Transitions".
Each arrow is labeled with an event an an action. 

This typifies the "Moore" model of FSMs.  In the "Mealy" model,
actions are peformed upon entry to states, not upon transitions.  It
can be proven that the two forms are isomorphic, i.e. you can
transform every Moore Model FSM into a corresponding Mealy model FSM
and vice versa.

Finite state machines are often implemented as nested switch/case
statements:

enum state {locked, unlocked};
enum event {coin, passthru};

void UnlockGate();
void LockGate();
void ThankYou();
void Alarm();

static state theState = locked;

void Transition(event e)
{
    switch (theState)
    {
    case locked:
        switch(e)
        {
        case coin:
            theState = unlocked;
            UnlockGate();
        break; // coin

        case passthru:
            Alarm();
        break; // passthru
        }
    break; // locked

    case unlocked:
        switch(e)
        {
        case coin:
            ThankYou();
        break; // coin

        case passthru:
            theState = locked;
            LockGate();
        break; // passthru
        }
    break; // unlocked
    }
};


However, this kind of code can rapidly get out of control.  The more
states and events there are, the more difficult the nesting of the
switches is to manage.  Therefore, some engineers have adopted the
approach of creating a true state table:

typedef void (*pfv)();

struct Transition
{
    state currentState;
    event itsEvent;
    state newState;
    pfv action;
}

Transition statemap[4] =
{
  {locked,   coin,     unlocked, UnlockGate},
  {locked,   passthru, locked,   Alarm},
  {unlocked, coin,     unlocked, ThankYou},
  {unlocked, passthru, locked,   LockGate}
};

Then you can write a very simple driver which scans this table for the
transition that matches the current state and the event, sets the new
state and calls the event function.

I have written a simple compiler which takes a text file very similar
to this:

locked
{
  coin     unlocked    UnlockGate
  passthru locked      Alarm 
}

unlocked
{
  coin     unlocked    ThankYou
  passthru locked      LockGate
}

And translates it to a C++ program which treats states as classes
which have event functions that are polymorphic.  If anybody would
like a copy, just mail me a request and I'll send it to you.  It
should run on most unix systems and it also runs on Borland if you
have a decent yacc/lex tool (e.g. MKS).

FSMs are of great use in most forms of programming.  In fact, I don't
think I have written a major system that did not make prolific use of
FSM in the last ten years.  The reason is simple.  An FSM respresents
all the details of a control situation, without being entangled in the
implementation of the actions.  The FSM references the actions, but
knows them only by name.  Thus, the control mechanism can be changed,
in one place (the FSM) without changing the implementations of the
actions.  Likewise the actions can be changed without influencing the
control mechanism.  This is an extremely useful separation of
concerns.

I have used FSMs to control the tasks within GUIs (i.e. every button
press, or menu selection spawns off a task which is controlled by a
FSM).  I have used them to control communications protocols.  (i.e.
which packet is due when, and what should I do when this packet comes
and I am doing that job...)  I have also used them to control the
respons of an application to hardware stimuli, or user demands.

In fact, I think FSMs are drastically underused by the software
community at large.  A solid consideration of the control mechamism of
an application will almost always yeild a set of finite state
machines.

Now, to tie this all togehter with OO and C++.  What is an object?  An
object is an entity which has three fundamental attributes:  State,
Behavior and Interface.  That is, objects remember information about
their current state.  They have behaviors that they peform based upon
the state that they are in.  They also have interfaces by which users
manipulate them.    There is a simple equivalence that can be set up:


    Object       FSM
       ----------------------
         state        state
         behavior     actions
         interface    events

In fact, nearly every object can be modeled as a FSM.  It is true that
some objects are not best represented as FSMs.  But many are.  When
designing a class of objects, it is wise to consider if a FSM
representation is appropriate.  If it is, you will find that it
simplifies the conceptualization and implementation of that class
nicely.