I've recently become enamored with the simplicity of Erlang's actor-based concurrency model, and am playing around with ideas for implementing some parts of it in C++. Along these lines, I also like the idea of implementing a finite state machine as a collection of functions representing states, where transitions are made by tail-calling from one function to the next.
I'd like to try something similar in C++. But a naive implementation of this is likely to run into the fact that tail calling in my compiler (GCC 4.1 with -O0) will eventually cause a stack overflow. So instead, what I'd like to do is have each state/function return a functor (the next state to enter), and have an underlying loop which just sequentially calls a functor, then calls the functor thus returned, then calls the functor thus returned, etc. Something like:
typedef ... context_t;
// A statefunctor is a functor which takes a context_t and
// returns a statefunctor
//
// FIXME: of course, this typedef won't compile.
typedef boost::function<statefunctor (context_t& )> statefunctor;
// NULL boost::function<> represents the exit condition.
static const statefunctor EXIT_FSM;
// primary loop which runs the FSM
void run_fsm(context_t& ctx, statefunctor initial_state)
{
while (initial_state)
{
initial_state=initial_state(boost::ref(ctx));
}
}
// states 'foo', 'bar', and 'baz';
statefunctor foo(context_t& ctx);
statefunctor bar(context_t& ctx, int inval);
statefunctor baz(context_t& ctx);
// State 'foo'
statefunctor foo(context_t& ctx)
{
// act somehow on the external context
int magic_number_1=ctx.get_magic_number();
int magic_number_2=ctx.get_magic_number();
// Always transition to 'bar'
return boost::bind(&bar, _1, magic_number_1-magic_number_2);
}
// State 'bar'
statefunctor bar(context_t& ctx, int inval)
{
inval+=ctx.get_magic_number(); // Act on external context somehow
// transition to foo or baz
if (inval>0) { return &foo; }
else { return &baz; }
}
// State 'baz'
statefunctor baz(context_t& ctx)
{
// Transition to foo or exit
if (ctx.get_magic_number()==5) {return EXIT_FSM;}
else {return &foo;}
}
int main()
{
context_t ctx;
// start the state machine in state 'foo'
run_fsm(ctx, &foo);
}
So, my question is, how do I define statefunctor? In particular, I want it to be capable of holding arbitrary functors (like boost::bind(...) might create), and not just function pointers.
NOTE: I'm using boost::bind, boost::function, boost::ref instead of their std:: counterparts because I'm stuck using GCC 4.1, which has no support for C++11. Solutions valid in C++03 are appreciated ;-).
You can't directly do this through a typedef, but you can wrap the boost::function in a struct / class (thanks to @R. Martinho Fernandes for making me have this insight):
#include <boost/function.hpp>
typedef int context_t;
struct statefunctor
: boost::function<statefunctor(context_t&)>
{
typedef boost::function<statefunctor(context_t&)> base_type;
statefunctor() : base_type(){}
template<class F>
statefunctor(F f) : base_type(f){}
};