Finite state machines (FSMs) are an important tool for describing and implementing program behavior [HU79], [Mar98]. They also are a good example of a domain in which metaprogramming can be applied to reduce the amount of repetitive and boilerplate operations one must perform in order to implement these simple mathematical models in code. Below we present a simple state machine generator that has been implemented using Boost Metaprogramming Library facilities. The generator takes a compile-time automata description, and converts it into C++ code that implements the FSM at run-time.

The FSM description is basically a combination of states and events plus a state transition table (STT), which ties them all together. The generator walks through the table and generates the state machine's process_event method that is the essence of an FSM.

Suppose we want to implement a simple music player using a finite state machine model. The state transition table for the FSM is shown in Table 1. The STT format reflects the way one usually describes the behavior of an FSM in plain English. For example, the first line of the table can be read as follows: ‘If the model is in the stopped state and the play_event is received, then the do_play transition function is called, and the model transitions to the playing state’.

The transition table provides us with a complete formal definition of the target FSM, and there are several ways to transform that definition into code. For instance, if we define states as members of an enumeration type, and events as classes derived from some base event class ¹⁰ , like so:

class player
{
 public:
    // event declarations
    struct event;
    struct play_event;
    struct stop_event;
    struct pause_event;

    // "input" function
    void process_event(event const&); // throws

 private:
    // states
    enum state_t { stopped, playing, paused };

    // transition functions
    void do_play(play_event const&);
    void do_stop(stop_event const&);
    void do_pause(pause_event const&);
    void do_resume(play_event const&);

 private:
    state_t m_state;
};

then the most straightforward way to derive the FSM implementation from the above table would be something like this:

void player::process_event(event const& e)
{
    if (m_state == stopped)
    {
        if (typeid(e) == typeid(play_event))
        {
            do_play(static_cast<play_event const&>(e));
            m_state = playing;
            return;
        }
    }
    else if (m_state == playing)
    {
        if (typeid(e) == typeid(stop_event))
        {
            do_stop(static_cast<stop_event const&>(e));
            m_state = stopped;
            return;
        }

        if (typeid(e) == typeid(pause_event))
        {
            do_pause(static_cast<pause_event const&>(e));
            m_state = paused;
            return;
        }
    }
    else if (m_state == paused)
    {
        if (typeid(e) == typeid(stop_event))
        {
            do_stop(static_cast<stop_event const&>(e));
            m_state = stopped;
            return;
        }

        if (typeid(e) == typeid(play_event))
        {
            do_play(static_cast<play_event const&>(e));
            m_state = playing;
            return;
        }
    }
    else
    {
        throw logic_error(
            boost::format("unknown state: %d")
                % static_cast<int>(m_state)
            );
    }

    throw std::logic_error(
        "unexpected event: " + typeid(e).name()
        );
}

Although there is nothing particularly wrong with implementing an FSM's structure using nested if (or switch-case) statements, the obvious weakness of this approach is that most of the above code is boilerplate. What one tends to do with boilerplate code is to copy and paste it, then change names etc. to adjust it to its new location; and that's where the errors are most likely to creep in. Since all the lines of event processing look alike (structurally), it's very easy to overlook or forget something that needs to be changed, and many such errors won't appear until the runtime.

The transition table of our FSM is just five lines long; ideally, we would like the skeleton implementation of the automata's controlling logic to be equally short (or, at least, to look equally short, i.e. to be encapsulated in some form so we never worry about it).

typedef mpl::list<
      transition<stopped, play_event,  playing, &player::do_play>
    , transition<playing, stop_event,  stopped, &player::do_stop>
    , transition<playing, pause_event, paused,  &player::do_pause>
    , transition<paused,  play_event,  playing, &player::do_resume>
    , transition<paused,  stop_event,  stopped, &player::do_stop>
    >::type transition_table;

class player
    : state_machine<player>
{
 private:
    typedef player self_t;

    // state invariants
    void stopped_state_invariant();
    void playing_state_invariant();
    void paused_state_invariant();

    // states (invariants are passed as non-type template arguments,
    // and are called then the FSM enters the corresponding state)
    typedef state<0, &self_t::stopped_state_invariant> stopped;
    typedef state<1, &self_t::playing_state_invariant> playing;
    typedef state<2, &self_t::paused_state_invariant> paused;

 private:
    // event declarations; events are represented as types, 
    // and can carry a specific data for each event;
    // but it's not needed for generator, so we define them later
    struct play_event;
    struct stop_event;
    struct pause_event;

    // transition functions
    void do_play(play_event const&);
    void do_stop(stop_event const&);
    void do_pause(pause_event const&);
    void do_resume(play_event const&);

    // STT
    friend class state_machine<player>;
    typedef mpl::list<
          transition<stopped, play_event,  playing, &player::do_play>
        , transition<playing, stop_event,  stopped, &player::do_stop>
        , transition<playing, pause_event, paused,  &player::do_pause>
        , transition<paused,  play_event,  playing, &player::do_resume>
        , transition<paused,  stop_event,  stopped, &player::do_stop>
        >::type transition_table;
};

// event definitions
struct player::play_event
    : player::event
{
};

// ...

int main()
{
    // usage example
    player p;
    p.process_event(player::play_event());
    p.process_event(player::pause_event());
    p.process_event(player::play_event());
    p.process_event(player::stop_event());
    return 0;
}