Help with coroutine-based state machines?

[Steven Taschuk]

Quoth Alan Kennedy:
> Steven Taschuk wrote:
  [...]
> > But this is not a state in the normal sense of "state machine";
  [...]
> But if that principle is correct, i.e. that "states" in a "machine"
> should not have "after-effects", then surely that same argument could
> be applied to the concept of coroutines as a whole? 
> 
> At some level, every object/module/codeobject+data is a state-machine.
> But objects that use coroutines have "after-effects", so they perhaps
> should not be used to implement state-machines (i.e. objects). Hmmm.
> 
> How to resolve this paradox?

No paradox.  It's just a question of what represents the state of
the machine; for your FSM objects, it might not be as simple as
"the value of the state attribute", but might also include the
internal state of the iterator which that attribute refers to.

For example:

    x = True
    def foo():
        global x
        while True:
            yield x
            x = not x

In this boring state machine, the state is the present value of x;
knowing that, you can predict the entire future behaviour of the
machine.  But in this other boring state machine:

    x = True
    def foo():
        global x
        while True:
            yield x
            yield not x
            x = not x

the state is a combination of the present value of x and whether
the iterator is about to resume from the first or the second
yield.  Knowing x doesn't tell you enough to predict the future
behaviour of the machine.

In the former case it would be clear to rename 'x' to 'state',
since that's what that variable means.  But in the latter such a
name would be misleading, since that variable is not the complete
state.

In the same way, with an implementation of your FSM class in which
the generator iterators preserve information across .next
invocations, such as

    def pseudostate(self):
        for next in [self.state0, self.state1, self.state2]:
            yield next

the value of the state attribute is not the whole story, so it's a
bit misleading imho to call that the state of the machine.

(Also it's easy to make state machines which are not *finite*
state machines using the FSM class.  For example,

    def state_foo(self):
        n = 0L
        while True:
            yield n
            n += 1

Now the machine has an infinite number of states (theoretically;
in practical terms n will eventually consume all memory).  Another
way to see that state_foo represents not a single state, but a
family of states.)

  [...]
> > In part, yes.  But even with the dispatcher, you can't call
> > another function and have *it* transfer control to another
> > coroutine, suspending the whole call stack.  (Not transparently,
> > anyway; it could be done by replacing all calls to functions with
> > yields to a dispatcher.)
> 
> I don't understand.

Perhaps I can make this clearer with some code that doesn't work:

    queue = []

    def read():
        if not queue: # queue empty
            yield 'producer'
        return queue.pop(0)

    def write(value):
        if len(queue) >= 5: # queue full
            yield 'consumer'
        queue.append(value)

    def producer():
        i = 0
        while True:
            write(i)
            i += 1

    def consumer():
        while 1:
            print read()

What this broken code is intended to do is this:  The consumer
process reads from the queue and prints values.  When the queue is
empty, the call to read() will transfer control to the producer
process, which will then write new values to the queue.  When the
queue gets full, the producer's call to write() will transfer
control back to the consumer, which -- and this is the important
bit -- will resume in the middle of its call to read(), and
continue as if nothing had happened.

There's no dispatcher function we can write which will make this
work as written, because the yields in read() and write() can't
yield to a dispatcher which invoked producer and consumer; they
can only yield to their immediate caller.

Now, if the calls to read() and write() were done using a
dispatcher, rather than using the normal Python call mechanism, it
could be done:

    queue = []
    _returned = None

    def read():
        if not queue:
            print 'queue empty, transferring to producer'
            yield 'transfer', 'producer'
        assert queue
        value = queue.pop(0)
        print 'read %r from queue' % (value,)
        yield 'return', value

    def write(value):
        if len(queue) >= 5:
            print 'queue full, transferring to consumer'
            yield 'transfer', 'consumer'
        assert len(queue) < 5
        queue.append(value)
        print 'wrote %r to queue' % (value,)
        yield 'return', None

    def producer():
        for i in range(23):
            yield 'call', 'write', i
        print 'no more values; transferring to consumer to flush queue'
        yield 'transfer', 'consumer'

    def consumer():
        while True:
            yield 'call', 'read'
            print _returned

    def run():
        global _returned
        coroutines = { # call stacks
            'producer': [producer()],
            'consumer': [consumer()],
            }
        functions = {
            'read': read,
            'write': write,
            }

        current = 'producer' # 'consumer' works just as well
        while True:
            stack = coroutines[current]
            prefix = '    '*len(stack)
            try:
                command = stack[-1].next()
            except (StopIteration, IndexError):
                print 'halt!'
                break
            if command[0] == 'transfer':
                current = command[1]
            elif command[0] == 'call':
                func = functions[command[1]]
                if len(command) > 2:
                    it = func(command[2])
                else:
                    it = func()
                stack.append(it)
            elif command[0] == 'return':
                _returned = command[1]
                stack.pop()
            else:
                raise ValueError('unknown command %r' % (command[0],))

    if __name__ == '__main__':
        run()

This is kind of neat imho, but it has lots of disadvantages.  Most
notably, it's not transparent -- you can't write normal calls and
normal returns and expect everything to just work.  You have to
know you're running under the dispatcher and make calls
appropriately.  (Also a real version of this idea should provide
tracebacks which refer not to the actual Python call stack but to
the call stack implemented by the dispatcher.)

(One of my blue-sky ideas is a tool which would transform a normal
program into the form above (perhaps by bytecode translation).
Then you could write normal calls and returns, but still have
coroutines.  Or you could just use Stackless's microthreads.)

-- 
Steven Taschuk              Aral: "Confusion to the enemy, boy."
staschuk at telusplanet.net    Mark: "Turn-about is fair play, sir."
                             -- _Mirror Dance_, Lois McMaster Bujold