<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta content="text/html; charset=ISO-8859-1" http-equiv="Content-Type">
<title>5. Example: a compile-time FSM generator</title>
<link rel="stylesheet" href="article.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.50.0">
<meta name="keywords" content="template metaprogramming, generic programming, programming languages, C++, STL, type systems, polymorphism, compile-time">
<link rel="home" href="index.html" title="the boost c++ metaprogramming library">
<link rel="up" href="index.html" title="the boost c++ metaprogramming library">
<link rel="previous" href="codegeneration.html" title="4. code generation facilities">
<link rel="next" href="acknowl.html" title="6. acknowledgements">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<div class="navheader">
<table width="100%" summary="Navigation header">
<tr>
<th colspan="3" align="center">5. Example: a compile-time FSM generator</th>
</tr>
<tr>
<td width="20%" align="left"><a accesskey="p" href="codegeneration.html">Prev</a> </td>
<th width="60%" align="center"> </th>
<td width="20%" align="right"> <a accesskey="n" href="acknowl.html">Next</a></td>
</tr>
</table>
<hr>
</div>
<div class="section">
<div class="titlepage">
<div>
<h2 class="title" style="clear: both"><a name="example"></a>5. Example: a compile-time FSM generator</h2>
</div>
</div>
<p>Finite state machines (FSMs) are an important tool for describing and implementing program behavior <span class="citation">[<a class="interlink" href="refs.html#ref.hu79" title="[hu79]">HU79</a>]</span>, <span class="citation">[<a class="interlink" href="refs.html#ref.mar98" title="[mar98]">Mar98</a>]</span>. 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.</p>
<p>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 <tt>process_event</tt> method that is the essence of an FSM.</p>
<p>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 <a class="interlink" href="example.html#example.fsm.stt" title="table 1. player's state transition table with actions">Table 1</a>. 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 <tt>stopped</tt> state and the <tt>play_event</tt> is received, then the <tt>do_play</tt> transition function is called, and the model transitions to the <tt>playing</tt> state’.</p>
<div class="table"><a name="example.fsm.stt"></a>
<table summary="Player's state transition table with actions" border="0">
<colgroup>
<col>
<col>
<col>
<col></colgroup>
<thead>
<tr>
<th align="left">State</th>
<th align="left">Event</th>
<th align="left">Next state</th>
<th align="left">Transition function</th>
</tr>
</thead>
<tbody>
<tr>
<td align="left"><tt>stopped</tt></td>
<td align="left"><tt>play_event</tt></td>
<td align="left"><tt>playing</tt></td>
<td align="left"><tt>do_play</tt></td>
</tr>
<tr>
<td align="left"><tt>playing</tt></td>
<td align="left"><tt>stop_event</tt></td>
<td align="left"><tt>stopped</tt></td>
<td align="left"><tt>do_stop</tt></td>
</tr>
<tr>
<td align="left"><tt>playing</tt></td>
<td align="left"><tt>pause_event</tt></td>
<td align="left"><tt>paused</tt></td>
<td align="left"><tt>do_pause</tt></td>
</tr>
<tr>
<td align="left"><tt>paused</tt></td>
<td align="left"><tt>play_event</tt></td>
<td align="left"><tt>playing</tt></td>
<td align="left"><tt>do_resume</tt></td>
</tr>
<tr>
<td align="left"><tt>paused</tt></td>
<td align="left"><tt>stop_event</tt></td>
<td align="left"><tt>stopped</tt></td>
<td align="left"><tt>do_stop</tt></td>
</tr>
</tbody>
</table>
<p class="title"><b>Table 1. Player's state transition table with actions</b></p>
</div>
<p>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 <tt>event</tt> class <sup><a name="note.fsm" href="#ftn.note.fsm">10</a></sup> , like so:</p>
<pre class="programlisting">
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;
};
</pre>
<p>then the most straightforward way to derive the FSM implementation from the above table would be something like this:</p>
<pre class="programlisting">
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()
);
}
</pre>
<p>Although there is nothing particularly wrong with implementing an FSM's structure using nested <tt>if</tt> (or <tt>switch-case</tt>) 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.</p>
<p>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).</p>
<div class="section">
<div class="titlepage">
<div>
<h3 class="title"><a name="example.impl"></a>5.1. Implementation</h3>
</div>
</div>
<p>To represent the STT in a C++ program, we define a <tt>transition</tt> class template that represents a single line of the table. Then the table itself can be represented as a sequence of such lines:</p>
<pre class="programlisting">
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;
</pre>
<p>Now, the complete FSM will look like this:</p>
<pre class="programlisting">
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;
};
</pre>
<p>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):</p>
<pre class="programlisting">
// event definitions
struct player::play_event
: player::event
{
};
// ...
</pre>
<p>The usage is simple as well:</p>
<pre class="programlisting">
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;
}
</pre>
</div>
<div class="section">
<div class="titlepage">
<div>
<h3 class="title"><a name="example.relatedwork"></a>5.2. Related work</h3>
</div>
</div>
<p>A notable prior work in the field of automation of general-purpose state machine implementation in C++ is the Robert Martin's <span class="emphasis"><em>State Machine Compiler</em></span> <span class="citation">[<a class="interlink" href="refs.html#ref.smc" title="[smc]">SMC</a>]</span>. 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 <span class="citation">[<a class="interlink" href="refs.html#ref.hun91" title="[hun91]">Hun91</a>]</span>, <span class="citation">[<a class="interlink" href="refs.html#ref.ghj95" title="[ghj+95]">GHJ+95</a>]</span>. Lafreniere <span class="citation">[<a class="interlink" href="refs.html#ref.laf00" title="[laf00]">Laf00</a>]</span> presents another approach, where no external tools are used, and the FSMs are table driven.</p>
</div>
<div class="footnotes"><br>
<hr width="100" align="left">
<div class="footnote">
<p><sup><a name="ftn.note.fsm" href="#note.fsm">10</a></sup>The events need to be passed to action functions, as they may contain some event-specific information for an action.</p>
</div>
</div>
</div>
<div class="navfooter">
<hr>
<table width="100%" summary="Navigation footer">
<tr>
<td width="40%" align="left"><a accesskey="p" href="codegeneration.html">Prev</a> </td>
<td width="20%" align="center"><a accesskey="u" href="index.html">Up</a></td>
<td width="40%" align="right"> <a accesskey="n" href="acknowl.html">Next</a></td>
</tr>
<tr>
<td width="40%" align="left" valign="top">4. Code generation facilities </td>
<td width="20%" align="center"><a accesskey="h" href="index.html">Home</a></td>
<td width="40%" align="right" valign="top"> 6. Acknowledgements</td>
</tr>
</table>
</div>
</body>
</html>
