How can I get a boost::function (or other generic function wrapper) that returns itself?

Question

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 ;-).

Ameba

Only semi-related, but the C functions longjmp and setjmp are used to do this sort of non-stack-based function calling. It is a common mechanism for implementing coroutines, for example. – Mentality

Clarified the title on (what I think) is the focus of the question, hope you don't mind. – Applicative

@Rook: Only if you're suicidally inclined. – Reactionary

Have you looked at libcppa, a C++11 actor library? It provides various types of actors, including a context-switching one based on Boost Context. – Weitman

After he specifies no C++11? Nais. – Reactionary

@Xeo: I'm not married to using boost::function<>, which your edit of my title implies. Using a common library instead of writing the whole template metaprogramming mess myself would be nice, though. – Ameba

@Rook: that sounds sort of scary in C++ (if maybe not so much in C). Wouldn't playing around with the stack like that tend to interfere with RAII and exception handling? – Ameba

@MatthiasVallentin, C++11 is out of scope for my current effort. But I do appreciate the reference, I hadn't found it in my previous searching. Thanks! – Ameba

Answer 1

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

Live example.

Applicative

This is similar to what I'd come up with so far, but much nicer. (rubber duck problem solving:codinghorror.com/blog/2012/03/rubber-duck-problem-solving.html). I'll probably accept this if something better doesn't come along. – Ameba

Does the forwarding constructor in your struct statefunctor incur an additional copy of the functor F? – Ameba

@Managu: Yeah, but functors are copied everywhere in C++ and expected to be rather lightweight (a std::function for example only has 12 bytes or so). – Applicative

Answer 2

This is impossibru. The type would be infinite, and the problem is identical to the one you would encounter defining a function pointer that returns itself. The only way to do this is to manually write your own function object with an operator(), this can return *this, and chain() calls. You can also use operator chaining in other ways, like you can see in std::cout.

Reactionary

Answer 3

You cannot. The problem is that the definition of the returned type would have to be recursive and that is not possible.

Gooden