Implementing a finite state machine with a single coroutine

Question

I'm looking at ways to implement an FSM, which led to my first encounter with coroutines.

I saw several examples (here, here and here) which hint that a state machine can be implemented by a single coroutine. However, what I noticed all these machines have in common is that, excluding cycles, they are trees - that is, there is a single path (excluding cycles) from the start node to every other node - and that maps nicely to the hierarchical control flow provided by nested ifs. The state machine I'm trying to model has at least one state with more than one path from the start node to it (if cycles are eliminated, it's a directed acyclic graph). and I can't imagine what kind of control flow (apart from gotos) can achieve that, or if it's possible at all.

Alternatively, I may use a separate coroutine to handle each state and yield to some sort of dispatcher coroutine. However, I don't see any particular benefit of using coroutines over regular functions in this setup.

Here's a simple state machine that I have trouble modelling:

A --'a'--> B
A --'b'--> C
B --'a'--> C
B --'b'--> A
C --'a'--> A
C --'b'--> B

And here is what I have so far. The final implementation will be in C++ using Boost, but I'm using Python for prototyping.

#!/usr/bin/python3

def StateMachine():
    while True:
        print("  Entered state A")
        input = (yield)
        if input == "a":
            print("  Entered state B")
            input = (yield)
            if input == "a":
                # How to enter state C from here?
                pass
            elif input == "b":
                continue
        elif input == "b":
            print("  Entered state C")
            input = (yield)
            if input == "b":
                continue
            elif input == "a":
                # How to enter state B from here?
                pass

if __name__ == "__main__":
    sm = StateMachine()
    sm.__next__()
    while True:
        for line in input():
        sm.send(line)

Can this coroutine be fixed to correctly model the state machine? Or do I have to go some other way about it?

Answer 1

I would model the state machine explicitly:

def StateMachine():
    state = 'A'
    while True:
        print(state)
        input = (yield)
        if state == 'A':
            if input == 'a':
                state = 'B'
            elif input == 'b':
                state = 'C'
            else:
                break
        elif state == 'B':
            if input == 'a':
                state = 'C'
            elif input == 'b':
                state = 'A'
            else:
                break
        elif state == 'C':
            if input == 'a':
                state = 'A'
            elif input == 'b':
                state = 'B'
            else:
                break
        else:
            break

This should translate very neatly to C++ using nested switch statements or a state transition table.

If you prefer an implicit model, you need a way to handle the cycles in your state machine. In C or C++, this would probably end up being goto. I wouldn't recommend this approach, but if you're more comfortable with it than explicit state, here's what it might look like:

#include <stdio.h>

#define start(state) switch(state) { case 0:;
#define finish default:;}
#define yield(state, value) do { state = __LINE__; return (value); case __LINE__:; } while(0)

struct coroutine {
    int state;
};

int
run(struct coroutine *c, char input)
{
    start(c->state)
    {
A:
        printf("Entered state A\n");
        yield(c->state, 1);
        if(input == 'a') goto B;
        if(input == 'b') goto C;
B:
        printf("Entered state B\n");
        yield(c->state, 1);
        if(input == 'a') goto C;
        if(input == 'b') goto A;
C:
        printf("Entered state C\n");
        yield(c->state, 1);
        if(input == 'a') goto A;
        if(input == 'b') goto B;
    } finish;

    return 0;
}

int
main(void)
{
    int a;
    struct coroutine c = {0};

    while((a = getchar()) != EOF && run(&c, a));

    return 0;
}