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

Answer 2

Theoretically, every finite state machine can be implemented with a single coroutine with just one of the following structures:

• tests on auxiliary variables
• goto statements
• multi-level exits from loops

Of course, if-then-else and while structures are considered available. On the other hand, such an implementation is not always feasible with only single-level exits.

Thus, the specific example is written, without state variables and goto' s, as follows:

#!/usr/bin/python3 
# Python doesn't support multilevel exits, so try/except can be used instead.
# However, for this FSM, single-level exits are sufficient.  
def StateMachine():
  while True:
    while True:
      print("  Entered state A")
      input = (yield)
      if input == "a":
          print("  Entered state B")
          input = (yield)
          if input == "a": 
            break
          elif input == "b": 
            pass
      elif input == "b": 
            break    
    while True:
      print("  Entered state C")
      input = (yield)
      if input == "a": 
          break
      elif input == "b": 
          print("  Entered state B")
          input = (yield)
          if input == "a": 
            pass
          elif input == "b": 
            break
if __name__=="__main__":
     sm = StateMachine()
     sm.__next__()
     while True:
       for line in input():
        sm.send(line)