Transition Tables

A common technique for implementing FSMs is to create a data table that describes the transitions. This table is interpreted by an engine that handles the events. The engine looks up the transition that matches the event, invokes the appropriate action, and changes the state. Listing 36-4 shows the code that creates the transition table, and Listing 36-5 shows the transition engine. Both of these listings are snippets from the full implementation (Listing 36-6).

Listing 36-4. Building the turnstile transition table

public Turnstile(TurnstileController controller) {   Action unlock = new Action(controller.Unlock);   Action alarm = new Action(controller.Alarm);   Action thankYou = new Action(controller.Thankyou);   Action lockAction = new Action(controller.Lock);   AddTransition(     State.LOCKED,   Event.COIN, State.UNLOCKED, unlock);   AddTransition(     State.LOCKED,   Event.PASS, State.LOCKED,   alarm);   AddTransition(     State.UNLOCKED,   Event.COIN, State.UNLOCKED, thankYou);   AddTransition(     State.UNLOCKED,   Event.PASS, State.LOCKED,   lockAction); }

Listing 36-5. The transition engine

public void HandleEvent(Event e) {   foreach(Transition transition in transitions)   {     if(state == transition.startState &&       e == transition.trigger)     {       state = transition.endState;       transition.action();     }   } }

Using Table Interpretation

Listing 36-6 is the full implementation showing how a finite state machine can be implemented by interpreting a list of transition data structures. This code is completely compatible with TurnstileController (Listing 36-2) and the TurnstileTest (Listing 36-3).

Listing 36-6. Turnstile.cs full implementation

Turnstile.cs using table interpretation. public enum State {LOCKED, UNLOCKED}; public enum Event {COIN, PASS}; public class Turnstile {   // Private   internal State state = State.LOCKED;   private IList transitions = new ArrayList();   private delegate void Action();   public Turnstile(TurnstileController controller)   {     Action unlock = new Action(controller.Unlock);     Action alarm = new Action(controller.Alarm);     Action thankYou = new Action(controller.Thankyou);     Action lockAction = new Action(controller.Lock);     AddTransition(       State.LOCKED,   Event.COIN, State.UNLOCKED, unlock);     AddTransition(       State.LOCKED,   Event.PASS, State.LOCKED,   alarm);     AddTransition(       State.UNLOCKED, Event.COIN, State.UNLOCKED, thankYou);     AddTransition(       State.UNLOCKED, Event.PASS, State.LOCKED,   lockAction);   }   public void HandleEvent(Event e)   {     foreach(Transition transition in transitions)     {       if(state == transition.startState &&         e == transition.trigger)       {         state = transition.endState;         transition.action();       }     }   }   private void AddTransition(State start, Event e, State end, Action action)   {     transitions.Add(new Transition(start, e, end, action));   }   private class Transition   {     public State startState;     public Event trigger;     public State endState;     public Action action;     public Transition(State start, Event e, State end,Action a)     {       this.startState = start;       this.trigger = e;       this.endState = end;       this.action = a;     }   } }

Costs and Benefits

One powerful benefit is that the code that builds the transition table reads like a canonical state transition table. The four AddTransition lines can be very easily understood. The logic of the state machine is all in one place and is not contaminated with the implementation of the actions.

Maintaining an FSM like this is very easy compared to the nested switch/case implementation. To add a new transition, one simply adds a new AddTransition line to the Turnstile constructor.

Another benefit of this approach is that the table can easily be changed at runtime. This allows for dynamic alteration of the logic of the state machine. I have used mechanisms like that to allow hot patching of FSMs.

Still another benefit is that multiple tables can be created, each representing a different FSM logic. These tables can be selected at runtime, based on starting conditions.

The cost of the approach is primarily speed. It takes time to search through the transition table. For large state machines, that time may become significant.