Is there a typical state machine implementation pattern?

Question

I prefer to use a table driven approach for most state machines:

typedef enum { STATE_INITIAL, STATE_FOO, STATE_BAR, NUM_STATES } state_t;
typedef struct instance_data instance_data_t;
typedef state_t state_func_t( instance_data_t *data );

state_t do_state_initial( instance_data_t *data );
state_t do_state_foo( instance_data_t *data );
state_t do_state_bar( instance_data_t *data );

state_func_t* const state_table[ NUM_STATES ] = {
    do_state_initial, do_state_foo, do_state_bar
};

state_t run_state( state_t cur_state, instance_data_t *data ) {
    return state_table[ cur_state ]( data );
};

int main( void ) {
    state_t cur_state = STATE_INITIAL;
    instance_data_t data;

    while ( 1 ) {
        cur_state = run_state( cur_state, &data );

        // do other program logic, run other state machines, etc
    }
}

This can of course be extended to support multiple state machines, etc. Transition actions can be accommodated as well:

typedef void transition_func_t( instance_data_t *data );

void do_initial_to_foo( instance_data_t *data );
void do_foo_to_bar( instance_data_t *data );
void do_bar_to_initial( instance_data_t *data );
void do_bar_to_foo( instance_data_t *data );
void do_bar_to_bar( instance_data_t *data );

transition_func_t * const transition_table[ NUM_STATES ][ NUM_STATES ] = {
    { NULL,              do_initial_to_foo, NULL },
    { NULL,              NULL,              do_foo_to_bar },
    { do_bar_to_initial, do_bar_to_foo,     do_bar_to_bar }
};

state_t run_state( state_t cur_state, instance_data_t *data ) {
    state_t new_state = state_table[ cur_state ]( data );
    transition_func_t *transition =
               transition_table[ cur_state ][ new_state ];

    if ( transition ) {
        transition( data );
    }

    return new_state;
};

The table driven approach is easier to maintain and extend and simpler to map to state diagrams.

You might have seen my answer to another C question where I mentioned FSM! Here is how I do it:

FSM {
  STATE(x) {
    ...
    NEXTSTATE(y);
  }

  STATE(y) {
    ...
    if (x == 0) 
      NEXTSTATE(y);
    else 
      NEXTSTATE(x);
  }
}

With the following macros defined

#define FSM
#define STATE(x)      s_##x :
#define NEXTSTATE(x)  goto s_##x

This can be modified to suit the specific case. For example, you may have a file FSMFILE that you want to drive your FSM, so you could incorporate the action of reading next char into the the macro itself:

#define FSM
#define STATE(x)         s_##x : FSMCHR = fgetc(FSMFILE); sn_##x :
#define NEXTSTATE(x)     goto s_##x
#define NEXTSTATE_NR(x)  goto sn_##x

now you have two types of transitions: one goes to a state and read a new character, the other goes to a state without consuming any input.

You can also automate the handling of EOF with something like:

#define STATE(x)  s_##x  : if ((FSMCHR = fgetc(FSMFILE) == EOF)\
                             goto sx_endfsm;\
                  sn_##x :

#define ENDFSM    sx_endfsm:

The good thing of this approach is that you can directly translate a state diagram you draw into working code and, conversely, you can easily draw a state diagram from the code.

In other techniques for implementing FSM the structure of the transitions is buried in control structures (while, if, switch ...) and controlled by variables value (tipically a state variable) and it may be a complex task to relate the nice diagram to a convoluted code.

I learned this technique from an article appeared on the great "Computer Language" magazine that, unfortunately, is no longer published.

I also have used the table approach. However, there is overhead. Why store a second list of pointers? A function in C without the () is a const pointer. So you can do:

struct state;
typedef void (*state_func_t)( struct state* );

typedef struct state
{
  state_func_t function;

  // other stateful data

} state_t;

void do_state_initial( state_t* );
void do_state_foo( state_t* );
void do_state_bar( state_t* );

void run_state( state_t* i ) {
    i->function(i);
};

int main( void ) {
    state_t state = { do_state_initial };

    while ( 1 ) {
        run_state( state );

        // do other program logic, run other state machines, etc
    }
}

Of course depending on your fear factor (i.e. safety vs speed) you may want to check for valid pointers. For state machines larger than three or so states, the approach above should be less instructions than an equivalent switch or table approach. You could even macro-ize as:

#define RUN_STATE(state_ptr_) ((state_ptr_)->function(state_ptr_))

Also, I feel from the OP's example, that there is a simplification that should be done when thinking about / designing a state machine. I don't thing the transitioning state should be used for logic. Each state function should be able to perform its given role without explicit knowledge of past state(s). Basically you design for how to transition from the state you are in to another state.

Finally, don't start the design of a state machine based on "functional" boundaries, use sub-functions for that. Instead divide the states based on when you will have to wait for something to happen before you can continue. This will help minimize the number of times you have to run the state machine before you get a result. This can be important when writing I/O functions, or interrupt handlers.

Also, a few pros and cons of the classic switch statement:

Pros:

• it is in the language, so it is documented and clear
• states are defined where they are called
• can execute multiple states in one function call
• code common to all states can be executed before and after the switch statement

Cons:

• can execute multiple states in one function call
• code common to all states can be executed before and after the switch statement
• switch implementation can be slow

Note the two attributes that are both pro and con. I think the switch allows the opportunity for too much sharing between states, and the interdependency between states can become unmanageable. However for a small number of states, it may be the most readable and maintainable.

In Martin Fowler's UML Distilled, he states (no pun intended) in Chapter 10 State Machine Diagrams (emphasis mine):

A state diagram can be implemented in three main ways: nested switch, the State pattern, and state tables.

Let's use a simplified example of the states of a mobile phone's display:

Nested switch

Fowler gave an example of C# code, but I've adapted it to my example.

public void HandleEvent(PhoneEvent anEvent) {
    switch (CurrentState) {
    case PhoneState.ScreenOff:
        switch (anEvent) {
        case PhoneEvent.PressButton:
            if (powerLow) { // guard condition
                DisplayLowPowerMessage(); // action
                // CurrentState = PhoneState.ScreenOff;
            } else {
                CurrentState = PhoneState.ScreenOn;
            }
            break;
        case PhoneEvent.PlugPower:
            CurrentState = PhoneState.ScreenCharging;
            break;
        }
        break;
    case PhoneState.ScreenOn:
        switch (anEvent) {
        case PhoneEvent.PressButton:
            CurrentState = PhoneState.ScreenOff;
            break;
        case PhoneEvent.PlugPower:
            CurrentState = PhoneState.ScreenCharging;
            break;
        }
        break;
    case PhoneState.ScreenCharging:
        switch (anEvent) {
        case PhoneEvent.UnplugPower:
            CurrentState = PhoneState.ScreenOff;
            break;
        }
        break;
    }
}

State pattern

Here's an implementation of my example with the GoF State pattern:

State Tables

Taking inspiration from Fowler, here's a table for my example:

Source State    Target State    Event         Guard        Action
--------------------------------------------------------------------------------------
ScreenOff       ScreenOff       pressButton   powerLow     displayLowPowerMessage  
ScreenOff       ScreenOn        pressButton   !powerLow
ScreenOn        ScreenOff       pressButton
ScreenOff       ScreenCharging  plugPower
ScreenOn        ScreenCharging  plugPower
ScreenCharging  ScreenOff       unplugPower

Comparison

Nested switch keeps all the logic in one spot, but the code can be hard to read when there are a lot of states and transitions. It's possibly more secure and easier to validate than the other approaches (no polymorphism or interpreting).

The State pattern implementation potentially spreads the logic over several separate classes, which may make understanding it as a whole a problem. On the other hand, the small classes are easy to understand separately. The design is particularly fragile if you change the behavior by adding or removing transitions, as they're methods in the hierarchy and there could be lots of changes to the code. If you live by the design principle of small interfaces, you'll see this pattern doesn't really do so well. However, if the state machine is stable, then such changes won't be needed.

The state tables approach requires writing some kind of interpreter for the content (this might be easier if you have reflection in the language you're using), which could be a lot of work to do up front. As Fowler points out, if your table is separate from your code, you could modify the behavior of your software without recompiling. This has some security implications, however; the software is behaving based on the contents of an external file.

Edit (not really for C language)

There is a fluent interface (aka internal Domain Specific Language) approach, too, which is probably facilitated by languages that have first-class functions. The Stateless library exists and that blog shows a simple example with code. A Java implementation (pre Java8) is discussed. I was shown a Python example on GitHub as well.

there is also the logic grid which is more maintainable as the state machine gets bigger