State Machine Implementation

27Mar 2015

State Machine Implementation

In a previous post, we discussed the concept of state machines. This was an abstract look at what state machines are, why they are useful, and what semantics they have. In this post, we want to create an implementation in C++ of such a state machine.

The code is available on Github. It is already used in many different commercial applications. Feel free to use it. Please contact us in case of any question or comments. We are also happy to support you with your code.


We discussed different representations of state machines already. For our implementation, we limit the set of features to the following list.

  • An initial state.
  • A (possibly empty) set of final states.
  • A finite, non-empty set of states.
  • A set of state transitions where a transition consists of
    • A trigger event
    • A (possibly empty) guard
    • A (possibly empty) transition action

High Level Properties

Clearly, an implementation can be done in many different ways. The most obvious and probably most often used solution is an ad-hoc translation of a state machine to code. Even though this might sound not very attractive, it can be a fast solution and is usually not difficult to do. However, an ad-hoc implementation has the problem that it is not re-usable or generic in any way. Therefore, the work of the translation has to be done for each state machine.

For this reason, we want to state the following properties that should be satisfied with our implementation.

  1. Generic and reusable
  2. Easy translation from a state diagram possible
  3. Correct and flexible

Generic means that the state machine implementation does not need to be changed when the definition changes. Only client code needs to be adapted. This implies we want to specify the state machine in a declarative way in the code.

An easy translation is desirable because it facilitates certain tasks. Firstly, it is much easier to review code given a state diagram (a drawing) as source. Secondly, it allows one to create tools that translate from a diagram to code much more easily.

Also, an implementation must enforce the semantics it specifies. By doing this, it shall still be flexible and put the user in control of the adaption points such as guards and actions.

While maybe not a complete list, these properties proved to be useful in practice.

What Clients Want

One way of specifying a state machine in code is to use a table-like notation. This maps naturally to the core of a state machine, states and transitions. The following is an example of how such a declaration could be done from a client side perspective.

transition1: stateA -> stateB | trigger1 [guard1] / action1
transition2: stateB -> stateC | trigger2 [guard2] / action2

Translation to C++

The above is not valid C++ code, but it is not difficult to translate it to valid code. But first, we create a data structure with all the required fields.

struct Trans {
	States from_state;
	States to_state;
	Triggers trigger;
	std::function<bool()> guard;
	std::function<void()> action;

This structure naturally maps to the pseudo code lines above. With this structure, we can define a state machine, or rather, the transitions of a state machine, with valid C++ code as follows.

enum class States {A, B, C};
enum class Triggers {a, b};
bool guard1() {...}
bool guard2() {...}
void action1() {...}
void action2() {...}

std::array<2, Trans> transitions = {
	{ States::A, States::B, Triggers::a, guard1, action1},
	{ States::B, States::C, Triggers::b, guard2, action2},

Here we create an array of transitions. Each transition consists of the fields defined in the Trans structure. Guards and actions are simple callback functions which will be invoked by the state machine implementation.

Recheck the Properties

This notation is, we believe, very simple and satisfies the properties we stated at the beginning. Firstly, an implementation that takes this notation must be generic, and secondly, it is not very difficult to create a tool that produces this notation.

The third property, that an implementation must be correct and flexible, is not automatically guaranteed. But this notation facilitates an implementation that enforces the correct semantics, because the implementation can be nicely shielded from user code without giving up flexibility.

Available Implementation

An implementation for C++ that works with our proposed notation is available on Github. Please check the doxygen documentation for more detailed information about the implementation.

Tags: programming