A Functional-Style State Machine in C++

Tamir Bahar May 26, 2017

If you go to any of your colleagues now and ask them, "can a function in C++ return itself?" they will probably give you the wrong answer.
Now ask them what the return type of the function is going to be. Here, let me help you:

using SelfReturning = SelfReturning (*)();

SelfReturning A() { return A; }

Great!
But it doesn't compile. and neither does

auto A() { return A; }

It turns out that C++'s type-system does not allow for recursive types. This is annoying. There is no reason why a function should not be able to return itself. It is even more annoying given that object methods can return the objects that hold them:

struct A {
    A operator()() { return A(); }
};

This code works. And for obvious reasons. Object methods are not a part of the object. They do not affect the object size or its construction. They are just a syntactic utility. There is no type-system recursion going on here.

With functions there is obvious type-recursion. But if you look at the work the compiler actually has to do - it seems absurd. A function is never constructed, it just is. It is not allocated. The function's signature changes nothing about the type.

void* A() {
    return reinterpret_cast<void*>(A);  // Same as C's `(void*)A`
}

int main() { 
    auto a = A;

    while (true) {
        // Cast back to function pointer
        a = reinterpret_cast<void*(*)()>(A());
    }

    return 0;
}

See? No missing information. The compiler has all the knowledge it needs, but the type-system still prevents us from writing our code (or, in this case, from writing it in a type-safe manner). We can do better.

We already know that objects can be used to break type recursion. Let's see if we can use them here without creating so much boiler-plate code:

struct SelfReturning {
    using FuncType = SelfReturning(*)(); // (1)

    SelfReturning(FuncType func) : _func{func} {} // (2)
    SelfReturning operator() () { return _func(); } // (3)

    private:
        FuncType _func;
};

The answer is yes. We can. Just substitute this class for the failed type definition of the first example and everything works as advertised. But how does it work?
To break the type-recursion, we create a proxy object. Its sole purpose is to hold a function pointer and call it.
Line (1) defines the function type that we expect to hold. Note that there is no direct recursion there. (2) is the constructor, taking the function pointer and storing it. (3) is where we forward the call to the function pointer. Note that here, too there is no type recursion as the type of the class is distinct from the type of its operator() function.
As a bonus, this compiles identical to the reinterpret_cast<void*> version in both Clang and GCC when using -O3 (see here and here), and at the same time maintaining type-safety. Zero-cost abstraction at work.

But why is that interesting? What are the use-cases?

Well, during the last few months, I've routinely consumed one programming-related talk per day. I find it a great way to expand my knowledge, and far easier to do than reading an article every day.

Last week, while working on some minor state-machine, I came across Declarative Thinking, Declarative Practice by Kevlin Henney. Upon seeing this slide:

I thought - bare functions instead of the State design pattern? I have to try that! So I went ahead and wrote my code, iterating through the steps described above.
At a quick glance, the functor solution may seem satisfying. But in effect functors, unlike functions, have different types and cannot be assigned to the same variable. To bridge the gap, we use an abstract base-class and polymorphism. Once we do that, we are forced to use pointers to hold the states. I use std::unique_ptr as I don't want to manage the memory myself.

#include <memory>

struct IState {
    virtual std::unique_ptr<IState> operator()() = 0;
    virtual ~IState() {};
};

struct A : public IState { std::unique_ptr<IState> operator()(); };
struct B : public IState { std::unique_ptr<IState> operator()(); };

std::unique_ptr<IState> A::operator()() { return std::make_unique<B>(); }
std::unique_ptr<IState> B::operator()() { return std::make_unique<A>(); }

int main() {
    std::unique_ptr<IState> state = std::make_unique<A>();

    while (true) { state = (*state)(); }

    return 0;
}

The proxy-object trick, however, has no such overhead. We know that we are using objects, but the code does not show it. The compiled version is far simpler as well (see here and here).

struct State {
    using FuncType = State(*)();
    State(FuncType func) : _func{func} {};
    State operator()() { return _func(); }
    FuncType _func;
};

State A();
State B();

State A() { return B; }
State B() { return A; }

int main() {
    State state = A;

    while (true) { state = state(); }

    return 0;
}

Enhancing it a bit, to handle events and operate on a context, we still maintain very simple, straight-forward code. For the purpose of this example, abort() and printf() are used instead of throw std::runtime_error and std::cout because the compiled output is easier to read. See compilation here and execution here.

#include <cstdio>
#include <cstdlib>

enum class Event{ A, B, };

struct Context {
    int counter = 0;
};

struct State {
    using FuncType = State(*)(Context&, Event);
    State(FuncType func) : _func{func} {};
    State operator()(Context& ctx, Event evt) { return _func(ctx, evt); }
    FuncType _func;
};

State A(Context&, Event);
State B(Context&, Event);

State A(Context& ctx, Event evt) {
    printf("State A, counter = %d\n", ctx.counter);
    ++ctx.counter;
    switch (evt) {
        case Event::A :
            return A;
        case Event::B :
            return B;
        default:
            abort();
    }
}

State B(Context& ctx, Event evt) {
    printf("State B, counter = %d\n", ctx.counter);
    ++ctx.counter;
    switch (evt) {
        case Event::A :
            return A;
        case Event::B :
            return B;
        default:
            abort();
    }
}

int main() {
    State state = A;
    Context ctx{};
    Event events[] = {Event::B, Event::A, Event::B, Event::A, };

    for (auto evt : events) {
        state = state(ctx, evt);
    }

    return 0;
}

For those keen on functional programming, we can even pass in a const reference to the context, and return a new context along with the new state. Compilation, execution.

#include <tuple>
#include <cstdio>
#include <cstdlib>

enum class Event{ A, B, };

struct Context {
    Context Inc() const {
        return Context{counter + 1};
    }
    int counter = 0;
};

struct State {
    using RetType = std::pair<State, const Context>;
    using FuncType = RetType(*)(const Context&, Event);
    State(FuncType func) : _func{func} {};
    RetType operator()(Context& ctx, Event evt) { return _func(ctx, evt); }
    FuncType _func;
};

State::RetType A(const Context&, Event);
State::RetType B(const Context&, Event);

State::RetType A(const Context& ctx, Event evt) {
    printf("State A, counter = %d\n", ctx.counter);
    switch (evt) {
        case Event::A :
            return {A, ctx};
        case Event::B :
            return {B, ctx.Inc()};
        default:
            abort();
    }
}

State::RetType B(const Context& ctx, Event evt) {
    printf("State B, counter = %d\n", ctx.counter);
    switch (evt) {
        case Event::A :
            return {A, ctx.Inc()};
        case Event::B :
            return {B, ctx};
        default:
            abort();
    }
}

int main() {
    State state = A;
    Context ctx{};
    Event events[] = {Event::B, Event::A, Event::B, Event::A, };

    for (auto evt : events) {
        std::tie(state, ctx) = state(ctx, evt);
    }

    return 0;
}

And that's it. We have a state machine based on pure-, bare-functions, in C++. It has a nice, simple look to it and as we've seen, compiles into far simpler code than the alternatives. On the way, we've also learned a bit about C++'s type system and how to use objects to overcome its limitations.
In the next post (soon to be populated) I will show some exciting (read: never use in production) dark template magic to both generalize the State object and to get some compile-time guarantees. Stay tuned!

Tamir Bahar

david-sackstein

Link e52c429ee7fe82bfec2d6542cc7b4a04b7d9f886827998833080ac23fcd2f169

Hi Tamir,

This is an interesting post, and masterfully presented.

I think you might agree with this high level comparison of your approach with that of the traditional State pattern:

In the traditional State pattern, each state is represented by a polymorphic type (state is data) and events are represented as (virtual) methods of that type (events are methods).
You represent state as a function, and events are represented as data.
In a way, this inverses the traditional approach because states are methods, events are data.

So which is more desirable?
Traditional: (state, event) = (data, method) or
Function Style: (state, event) = (method, data)

I think that the Traditional approach is more desirable for two main reasons.
Maybe you can comment on these:

Reason 1:

In the traditional approach, the compiler enforces the requirement that every state must handle every event (a no-op is also a handler)
But in your approach, you write the dispatch code in each state function as a switch.
It is therefore easy to omit a case and in doing so to fail to handle an event in a particular state.
In general, switches have this weakness, and many design patterns prefer to convert switches on values to dispatching on a virtual type for this reason.

Reason 2:

You have not entirely addressed the handling of context.
The context object that you pass to each state is context information that pertains to all the states. But often, each state has, in addition, its own internal state (example below). This state-specific-state must necessarily be passed around to each of the state functions, so that if ever we return to the state that created it this information can read, used and updated by the state that it belongs to.

This not only requires adding another argument to the signature of the state function, it also requires that all states use the same type to store their state information. This would be awkward to implement.

So here is an example.
Consider an application that manages one document.
The document can be open or closed (two states).
The document has three functions (open, close, delete)
Some functions are illegal in some of the states.
Using the traditional approach, each state is in instance of an abstract type with at least three methods (open, close, delete). Each may implement these 3 methods differently.
It is natural that all states hold a reference to the same document, because in fact there is only one document. This is state wide context and I believe is what you refer to with your IContext interface.
But in addition, each state may have its own specific data that needs to be persisted even when the state is not current.
Continuing this example, imagine that you want to enforce a limit on the number of times the document can be opened.
Using the traditional approach, this would probably be implemented as a counter stored in the closed state class which is the only state that actually opens the document in its implementation of open.
Closed would increment that counter in closed::open() and fail the open call if that counter ever reached its limit. This would work even though the application moved out of the closed state to the open state and then back to the closed state (as long as the states themselves are persisted - a reasonable and common approach).

Similarly, you might have other such state-specific-data in the other states. Again, using the traditional approach, this data are simply fields of each individual state.
Those fields do not need to be passed out of one state into another. No other state needs to know the shape of that data and states do not need to shape their specific data in the same way as other states do. Therefore, each state can change its representation of its state without effecting the types or implementations of other states.

Back to your approach, you would need to add some state neutral container of state-specific-context to the signature of the state function and pass it to from state to state. Furthermore, this object would need to change every time state specific information changes.
This is a brittle design and rather awkward to implement.

My conclusion:

I agree that the concept of a function returning an object of its own type is interesting but I think that it is less desirable as an implementation of a state-machine than that of the traditional State pattern.

What do you think?

Hi David,

I would like to address your analysis, as well as add some of my insights.

Reason 1: Switch Statements & Compile-Time Guarantees

In the past, switch statements provided very weak compile time guarantees. It used to be impossible to ensure case exhaustion (as enum types were ints)
and you could always get accidental fallthroughs.

With moden C++ and recent compilers, this is changing. Enum classes allow compilers to check for case exhaustion (-Wswitch). Then can also ensure that all cases are handled explicitly (-Wswitch-enum). Additionally, C++17's [[fallthrough]] helps ensure that there are no accidental fallthroughs (-Wimplicit-fallthrough). See here.

In my opinion, those are fairly good guarantees. Additionally, the switch statement design makes the code easier to hold in your head and reason about. You can clearly see all the state transitions at the same time.

Reason 2: Context

The State pattern allows for the different states to hold their own contexts internally. It is not, however, a critical part of the design. You can either hold the context in each individual state, or hold a state-machine wide context and pass it around. This can be done either by the States holding a reference to the context as a private member, or by using stateless states and passing the context on each call.
In my design, the state-functions are stateless and the context is passed into them with every call. This decouples the context from the state functions, and allows for far easier testing. To test a state function, I simply pass it a context representing a given situation, and an event to handle. No need for any further set-up. Were the States holding internal context, it would have had to be set up before every test, and therefore would have had to be exposed in one way or another, complicating the design.

Conclusion

Given the switch-related compiler warnings, it seems to me that both options are reasonably sound. With that in mind, I think that the choice between the functional-style state machine and the State pattern is mainly a stylistic one. I much prefer this solution as it has less textual-overhead. That said, the State pattern is well known and well used - so it very well might solve some issues not-yet addressed here.