Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

This is an old version of boost. Click here for the latest version's documentation home page.

5. Example: a compile-time FSM generator

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’.

State Event Next state Transition function
stopped play_event playing do_play
playing stop_event stopped do_stop
playing pause_event paused do_pause
paused play_event playing do_resume
paused stop_event stopped do_stop

Table 1. Player's state transition table with actions

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 10 , 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).

5.1. Implementation

To represent the STT in a C++ program, we define a transition class template that represents a single line of the table. Then the table itself can be represented as a sequence of such lines:

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;

Now, the complete FSM will look like this:

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;
};

That's all - the above will generate a complete FSM implementation according to our specification. The only thing we need before using it is the definition of the event types (that were just forward declared before):

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

// ...

The usage is simple as well:

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;
}

5.2. Related work

A notable prior work in the field of automation of general-purpose state machine implementation in C++ is the Robert Martin's State Machine Compiler [SMC]. The SMC takes an ASCII description of the machine's state transition table and produces C++ code that implements the FSM using a variation of State design pattern [Hun91], [GHJ+95]. Lafreniere [Laf00] presents another approach, where no external tools are used, and the FSMs are table driven.



10The events need to be passed to action functions, as they may contain some event-specific information for an action.