Help with coroutine-based state machines?
Alan Kennedy
alanmk at hotmail.com
Thu May 29 11:10:02 EDT 2003
Greetings all,
I've got a few questions about generators, coroutines, etc, that
I've been meaning to ask for several weeks. But I knew it would take
time to explain. So I left it until I had the time to write it up
properly. And it turned out that there was a lot more to it than I
originally foresaw, mainly because I wanted the concepts to be as
clear as possible. As I wrote it and rewrote it and rewrote it, it
quickly grew to be a length more suitable for an article than a
Usenet post. But because I was asking questions about stuff I didn't
know, an article wasn't appropriate.
So, the post/thing itself is given below. It's quite long, and a
little rambling in parts. You'll probably need some time available
to work through it all, if you're interested.
If any of the good people in the group can help me anwser some of
the questions, I'll write this all up more concisely, and put it on
it's own web page.
Thanks for any assistance you can offer.
Alan.
===============================================================
State machines.
---------------
I've been playing around with state machine paradigms, seeking an
optimum paradigm with three primary requirements in mind.
1. That the paradigm be as simple to code as possible.
2. That machines developed using the paradigm be as flexible as
possible, and ideally inheritable.
3. That the paradigm be as resource-efficient as possible. (not so
important).
"Traditional" Paradigms.
------------------------
I played around with a few traditional state-machine paradigms, the
kind you see posted, for example, in the Cookbook. They were mostly
based on declaring machines or even individual states as objects,
and sometimes requiring explicit declaration of all state
transitions and events.
To me, most of them seemed difficult to work with, because of the
need to modify up to 3 or 4 different variables (in different
sections of the code) in order to make the simplest modification to
a state or event. While I recognise the benefit of such approaches
in more formal or rigourous circumstances, I needed more
flexibility.
So, none of more "traditional" paradigms (that I found) really stood
out as what I was looking for in terms of simplicity and
expressiveness.
Generators and state machines.
------------------------------
But then I came across David Mertz excellent article describing the
use of generators to implement state machines, and I was bigtime
impressed.
http://www-106.ibm.com/developerworks/linux/library/l-pygen.html
This article was the "dawning point" for me, when (I think) I
finally "got" generators, and the flexibility that they offer.
If you haven't read David's article before, I recommend that you do
if you are going to continue reading this post, because I'll be
continually referring to the generator-based state machine
implementation in that article.
Simplifying the model.
----------------------
However, once I did finally "get it", when I looked back at the
example code in the article, I found myself easily confused by the
code. Trying to get my head around the important difference between
the generator-function and the generator-iterator, while also trying
to follow the dictionaries and tuples needed for dispatch, mixed in
with a non-generator function (using classic 'return's) for state
classification and namespace declarations to access data, left me a
little spun out.
So I decided to try and simplify the model a little. Code for a full
working example (but a different state machine) is given below. I
left it all in one piece rather than split it up and sprinkle it
through the discussion points. I have included code snippets where
it is necessary to illustrate a point.
Eliminating global data.
------------------------
The first thing that I found confusing was the use of global data.
Instead, it seemed more natural to me to encapsulate the state
machine in a class, and to use instance variables of objects of that
class to contain instance data. That way, no namespace (i.e.
"global") declarations would be required: the data could be simply
accessed through the self object.
Cleaning up the dispatch table.
-------------------------------
When I wrapped it all in a class, and removed the "cargo" and
namespace declarations, I realised that the generators were all
yielding a simple string, containing the name of the next state,
like so
yield 'newstate'
This would be then looked up in a "jump table", i.e. a dictionary
mapping the state names to generator-iterators representing the
states, like so
while 1:
newstate = jumptable[newstate].next()
This jumptable, containing the instantiated generator-iterator
objects, would be set up at start time.
This seemed to me superfluous, since I had already named all of the
states, through the names of the generator-functions themselves: why
should I need a string to identify them as well? Also, having a jump
table means that I have to maintain state names in three different
places: the name of the generator-function, the name of the state in
the jump-table and when instantiating the generator-iterator.
So, if I wanted to do away with the jumptable, I would have to yield
the generator-iterator for the next state directly to the
dispatcher, and have the dispatcher call its .next() method. But how
would I refer to the generator-iterator, when the states name in the
instance dictionary (self) referred to the generator-function, not a
generator-iterator. I would have to come up with some way to
directly yield the generator-iterator object for the state, but
accessing them using their generator-function names. A state change
could then be declared as
yield newstate
And dispatching would then simply become
while 1:
newstate = newstate.next()
Sweet. Much simpler :-)
Turning generator-functions into generator-iterators.
-----------------------------------------------------
In order to do away with the jump table, I decided that all names
(in the instance dictionary) which referred to generator-functions
be changed so that they referred instead to the corresponding
instantiated generator-iterators. This would mean that state changes
would be indicated by a statement like
yield self.newstate
To do this, here is the little bit of hackery that I came up with:
at __init__ time of the state-machine object, it modifies the
instance dictionary, replacing generator-functions with their
instantiated generator-iterators.
def __init__(self):
statenames = ['state1', 'state2', 'state3', 'state4']
for name in statenames:
# Turn each generator-function into an instantiated
# generator-iterator
self.__dict__[name] = eval ('self.%s()' % name)
# Obviously, there must be a generator-function
# in the class corresponding to each element of statenames list,
e.g.
def state1(self):
while 1:
if self.readytogo:
yield self.state2
else:
yield self.state3
This turns every reference to a generator-function into a reference
to the corresponding instantiated generator-iterator.
Differentiating generator-functions from functions.
---------------------------------------------------
I'm not happy with the way that I have to explicitly list the state
names. I tried to find a way to differentiate between functions and
generator-functions while reflecting on the instance' dictionary.
Pseudo code for this would look like
import types
for k in self.__dict__.keys():
if type(self.__dict__[k]) is types.GeneratorType:
self.__dict__[k] = eval ('self.%s()' % k)
But there isn't a generator type in the types module? So, that's a
question I'd like to ask: can anyone tell me how to discover the
generator-functions of an object, and differentiate them from
ordinary functions?
A full working example.
-----------------------
Now's the time for a full example. In order to simplify it, I chose
a different state machine from that in David's article. It's a very
simple state machine: one that counts from one number to another in
a specified increment, and then stops. The paradigm is capable of a
lot more than that (I've just used it very successfully to control
multiple independent automated users in a load testing simulation,
for example): but I want this example to be short and concise.
#----------------------------------------------
# This code is also available at
# http://xhaus.com/alan/python/FSMgenpy.html
#
class FSM:
def __init__(self, startnum, incrnum, stopnum):
for name in ['idle','start','increment','checkfinished','finished']:
self.__dict__[name] = eval ('self.%s()' % name)
self.startnum = startnum
self.incrnum = incrnum
self.stopnum = stopnum
self.counter = 0
self.exit = 'exitsentinel'
def idle(self):
while 1:
# We could wait for some condition here.
print "Idle state: %d" % self.counter
yield self.start
def start(self):
while 1:
self.counter = self.startnum
print "Start state: %d" % self.counter
yield self.increment
def increment(self):
while 1:
self.counter = self.counter + self.incrnum
print "Increment state: %d" % self.counter
yield self.checkfinished
def checkfinished(self):
while 1:
if self.counter >= self.stopnum:
yield self.finished
else:
yield self.increment
def finished(self):
while 1:
print "Finished state: %d" % self.counter
yield self.exit
def dispatch(self, startstate):
newstate = startstate
while 1:
next = newstate.next()
if next == self.exit:
return
else:
newstate = next
if __name__ == "__main__":
m = FSM(1,5,50)
m.dispatch(m.idle)
m.dispatch(m.idle)
#----------------------------------------------
Pausing or stopping from the state machine.
-------------------------------------------
You will notice that I have slightly modified the dispatch function,
compared to the one described above. It now looks for a sentinel
value signifying exit from the state machine. This is because the
only way in which the state machine can suspend operation and
relinquish control is to return from a non-generator function. If
any form of return is attempted from inside a generator-iterator, or
an exception such as a StopIteration() is raised, then that
generator-iterator will be destroyed and the state-machine will stop
working. Furthermore, it won't be possible to create a new
generator-iterator, because we've overwritten the reference to the
generator-function in the instance dictionary! Hmm, maybe that is
too much a hack :-| Anyway.
The addition of the sentinel value for exiting or suspending the
state machine means that we can now suspend and resume the machine
at will. It can be suspended by yielding a "suspend" state (which
would be a simple string sentinel value to the dispatcher), and then
resumed by calling the dispatch method with a new or saved starting
state. The example "main" function given above runs the example
state machine through its paces twice. When you run it, take a look
at the value of the counter in the "idle" state, and how it differs
between invocations.
Combinining with threads.
-------------------------
In the example usage I described above, where I used this paradigm
to control automated testers, each automated tester ran in its own
thread. Each had a dedicated input Queue.Queue, through which it
would receive commands. Which would then be carried out by setting
instance data and transferring to the relevant state.
In order to check for messages in the incoming queue, at least one
of the states must check if there any entries in the queue. In
simple cases, this can be a blocking wait, where the
Queue.Queue.get() does not return until a message is available.
If you need the machine to be going off doing tasks in its parallel
thread, but still checking for messages, e.g. stop commands, then a
non-blocking .get(), carried out at a regular interval, is
recommended. However, making the time intervals too short can
significantly consume your cpu cycles. Also, I found that
threading.Condition() variables were very useful as a mechanism for
synchronisation between threads, and integrated well with the
"resumable function" concept.
Paradigm found.
---------------
To me, this paradigm of state machines is simplicity itself. Thus,
it fulfills my primary goal of having a simple paradigm: I really
can't see any way for the code to be simpler, in textual terms at
least. Furthermore, because all of the parameter parsing involved in
function calls is avoided, it should be also more cpu-efficient than
a "procedurally" based model. (Actually, I haven't done any timing
to validate this, but I can't see how the generator version could be
slower?)
Parameter passing.
------------------
However, this avoidance of parameter parsing has a downside: you
can't pass parameters between states :-) Which would be a problem in
most real-world state-machines, which would most likely be
processing external data streams of some form. The two ways that I
can think of for getting data into the state-machine are
1. Sending parameters wrapped up in a message object on a
Queue.Queue. This would be recommended in a multi-threaded
situation.
2. By setting instance variables of the state-machine object
directly. This could be dangerous in a multi-threaded situation.
I am aware of Raymond Hettingers PEP 288: Generator Attributes, and
now appreciate the problem that it is trying to solve. And I also
appreciate the "cargo" problem David was trying to solve in his
article. If anyone has any improved methods to passing parameters in
the paradigm I've described above, I'd like to hear about it.
Generator Gestalt.
------------------
It was only while stepping through the execution path of the code
above that I finally understood some of the sophisticated
flow-control mechanisms that generators offer: if you temporarily
"forget" that there is a dispatcher function involved, you see the
thread of execution far more naturally: named units of python code
where the data and the code that manipulates it are very closely
associated: The flow of control passes seamlessly back and forth
between the named units: There is no stack giving you an ancestry or
history of invocations: Each "state" in the state-machine
implementation really *is* an encapsulated, resumable state.
The "temporal locality" of the code (as opposed to the "spatial
locality" of traditional code) greatly aids readability, and
modifiability, IMHO. The code seems more natural, more
"encapsulated", because data is generally only modified in code that
is "close" to the declaration of the state machine "event" to which
it relates. Also, the ease with which the flow between states can be
modified (i.e. no mucking with state or transition declarations,
lookup tables or parameter values) greatly increases the flexibility
of the code.
It also seems to me that this paradigm should have significant
cpu-efficiency advantages over other paradigms, and potentially make
python-implemented algorithms cpu-competitive with statically typed
and compiled languages based on a traditional function paradigm,
such as Java or C.
At the beginning, when writing real state machines with the above
paradigm, I found myself getting weird bugs and subtle deviations
from expected behaviour. For example, a counter might start at 2,
rather than an expected, recently initialised, 1. But mostly they
weren't bugs at all, they were inherent flaws I designed into the
state-machine. Sometimes when writing and debugging the code, I
mistakenly assumed that the code was being entered from the top each
time, i.e. directly after the while statement, as it would be in
"procedural" code. But rather, the real situation was that the code
was being resumed in the statement immediately after the last
executed yield statement. Once I had discarded this last
preconception, it all fell into place (anybody know a Buddha smilie
O:-)
Generators: powerful stuff, to be sure, to be sure. Although I know
there was at some stage controversy about the rate at which new
features were/are being introduced into python, I'm convinced that
advanced features like generators are a necessary step for python to
remain competitive in conceptual terms, compared to other languages.
New concepts in computer hardware, such as massively parallel
computing or hyperthreading, and new classes of computational
problems such as protein folding, will require new conceptual
approaches from computer languages. Generators are those concepts,
or are at least the precursors of the future concepts. (I hope that
one day I will also "get" Continuations, and Co-Routines, and am now
at least in the position of having identified some of what I don't
know about Stackless Python %~} <= my brain is seriously starting to
wobble.......
Sorry, wrong meeting ;-) For a moment there, I thought I was at the
"Stackless Revolution" meeting, which is on *Tuesday* nights, down
the docks.......
Ah, the Zen of Python :-)
Inheritance.
------------
Lastly, about my final requirement: That hopefully my state-machine
paradigm should support extensibility, or ideally inheritance.
Although I haven't yet tried to do it, I imagine that subclassing
these state-machine classes should work perfectly well, as long as
the instantiation of generator-functions to generator-iterators is
properly managed.
Request for comments.
---------------------
As I mentioned above, there are a number of questions in this post
which prevent it from being an explanatory article about this
paradigm. However, if (as I hope :-) the great and knowledgable
people in this group help me out with ironing out the wrinkles, I'll
write it up and post it on its own page.
And finally: infinite loops.
----------------------------
Another question I just thought of: Each of the state
generator-functions must be wrapped inside an infinite while loop,
so that the states never "run out of values". These while loops
clutter the code somewhat, and it would be nice to not need them. I
wonder if it would be possible to remove them? On second thoughts,
maybe not. At least not without fundamentally changing the meaning
of the yield keyword (is that what "yield every" is for?). Or maybe
some incantation with __metaclasses__?
And really finally: notification of state change.
-------------------------------------------------
Since I've still got your attention ;-) another thing that I plan to
address, perhaps with __metaclasses__, is sending notification about
state changes to registered objects, without having to stick in
explicit callback notifications in every state. This could be simply
done by putting a name attribute on every generator-iterator, and
notifying the notifiable objects in the dispatch loop. So the
__init__ would be like this
statenames = ['state1', 'state2', 'state3', 'state4']
for state in statenames:
self.__dict__[state] = eval ('self.%s()' % state)
self.__dict__[state].name = state
and the dispatch would become
while 1:
next = newstate.next()
for o in self.notifiableobjects:
o.notifystatechange(next.name, self)
newstate = next
But it would be cooler to use __metaclasses__ B-)
Really really finally: event-driven processing loops.
-----------------------------------------------------
And for the last moebius-twist of all, I've been trying to picture
how I could integrate state-machines like this with an asynchronous
event-driven server framework like twisted, medusa or asyncore. I
read some posts about "sources" and "sinks", but methinks it may be
more complex than that. Particularly, it is the "psuedo-threading"
which I don't quite get. Any pointers to relevant
articles/emails/postings/sourcecode greatly appreciated.
No, really, really finally: light bulb switches on...
-----------------------------------------------------
A very interesting thought just struck me.
The state changes in the examples above always 'yield'ed the next
state from the current state machine, i.e. 'yield self.newstate'.
But if there were multiple objects all operating this state machine
paradigm, they could yield back and forth to each other, simply by
saying "yield other.newstate" (obviously they must hold a reference
to 'other').
If 'other's dispatching mechanism operated by the same principle,
and was capable of suspending the state machine through 'return'ing
a value instead of generating the next state, then input could be
processed by being fed into one state-machine object and the final
processed output being returned from another connected state-machine
object. So I could build a network of mutually 'yield'-ing state
machines to process a stream of input.
Also, the interim states in the state-machine network could be
suspended when no input was available, by 'yield'ing a
generator-iterator which generates the resume state, when its
.next() method is called. This would have the effect of resuming the
state machine network directly in place from where it 'yield'ed,
when the input becomes available. I think I see the beginnings of
the answer to my asycnore question. O-) <= brain settles back down
to a bose-einstein state of calm awareness
Ah! So that's what full coroutines are? One or more objects,
'yield'ing control back and forth between a set of resumable states,
without the need for a dispatcher function? Which would mean that
you could call a "function" on one object and get the return value
from a different "function" on the same object, or even a different
"function" on a different object. Which could make a right mess of a
traditional function call stack. Which is why Stackless python is as
it is. Ah, the soft chink of the penny dropping.......why is my head
suddenly full of Feynmann diagrams.......?
Which is why python generators are only "semi"-coroutines, as
opposed to full coroutines. Because, without a dispatcher function,
you can only yield control to the calling function, rather than any
resumable state that you have a reference to. So how would the
interface between "procedural" and coroutine code work in the full
coroutine world? Presumably, there would be no difference between a
generator-function and a generator-iterator: or at least, there
would be no need to explicitly instantiate the generator-iterator?
And they could be passed parameters on each invocation? And the
top-of-stack data structure would have to be designed to represent
the free flow back and forth between resumable states of multiple
objects. And generator-iterators would not be "broken" by
'return'ing a value or raising an exception? Implementation
question: Why does this asymmetry exist in the current (c)python
generator implementation? It seems to me that it should be
reasonably straightforward to get around.........
Continuations.
--------------
If I've got it right about coroutines, then what is the last step of
understanding required for Continuations?
What do continuations offer that coroutines don't?
Is it that continuations allow resumption of states across thread
boundaries?
Thanks for reading this far through my ramblings :-)
kind regards,
--
alan kennedy
-----------------------------------------------------
check http headers here: http://xhaus.com/headers
email alan: http://xhaus.com/mailto/alan
More information about the Python-list
mailing list