title: Implementing a finite state machine with a single coroutine
body: <p>I'm looking at ways to implement an FSM, which led to my first encounter with coroutines.</p>
  
  <p>I saw several examples (<a href="http://eli.thegreenplace.net/2009/08/29/co-routines-as-an-alternative-to-state-machines/" rel="noreferrer">here</a>, <a href="http://www.dabeaz.com/coroutines/Coroutines.pdf" rel="noreferrer">here</a> and <a href="http://www.crystalclearsoftware.com/soc/coroutine/coroutine/finite_state_machines.html" rel="noreferrer">here</a>) 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 <code>if</code>s. 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 <code>goto</code>s) can achieve that, or if it's possible at all.</p>
  
  <p>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.</p>
  
  <p>Here's a simple state machine that I have trouble modelling:</p>
  
  <pre><code>A --'a'--&gt; B
  A --'b'--&gt; C
  B --'a'--&gt; C
  B --'b'--&gt; A
  C --'a'--&gt; A
  C --'b'--&gt; B
  </code></pre>
  
  <p>And here is what I have so far. The final implementation will be in C++ using Boost, but I'm using Python for prototyping.</p>
  
  <pre class="lang-py prettyprint-override"><code>#!/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)
  </code></pre>
  
  <p>Can this coroutine be fixed to correctly model the state machine? Or do I have to go some other way about it?</p>