 | Level: Introductory David Mertz (mertz@gnosis.cx), Producer, Gnosis Software, Inc.
01 Jul 2002 Simple generators, introduced in Python 2.2, may be used to simplify state machines and to simulate coroutines. David presented an abstract pattern for state machine processing in an earlier "Charming Python" installment. Since that time, the introduction of simple generators has provided some even more natural paradigms for describing machines. Coroutines are an "exotic" flow mechanism that few widely-used languages allow (not even non-Stackless Python). Python's new generators, however, get you almost all the way to coroutines, and the extra few steps can be faked. In this article, David explains all the relevant concepts through illustrative code samples.
[Due to a mixup, this column is being published out of sequence. It was meant to precede David's prior column, Implementing "weightless threads" with Python generators. We apologize for any confusion. -Ed.]
It takes a while to completely "get" Python 2.2's new
generators. Even after writing an introduction to simple generators in an earlier "Charming Python" installment, I could not say
that I fully understood the "gestalt" of generators. This
article presents some additional patterns for the use of
generators, and hopefully brings both myself and readers
further into the mindset of "resumable functions."
There are a lot of good things about simple generators. In addition to
offering more natural ways of expressing the flow of a class of
problems, generators can dramatically improve many inefficiencies. In Python, function invocation is rather
expensive; among other factors, function arguments lists take a
while to sort out (positional and default arguments need to be
parsed, among other things). Also, initializing a frame object
takes some setup steps (over 100 lines of C, according to Tim Peters on
comp.lang.python; I have not examined the
Python source myself). Resuming a generator, in contrast, is
quite cheap; the arguments have already been parsed, and the
frame object is just sitting around waiting for resumption
(almost no extra initialization is needed). Of course, if
speed is paramount, you should not be using a byte-code
compiled dynamic language; but even where speed is not the
primary concern, faster is better than slower.
Revisiting state machines
In another earlier installment of "Charming Python", I presented a
StateMachine class
that allowed users to add as many state handlers as were needed
for a given machine. In the model, one or more states are
defined as end states, and exactly one state is defined as a
start state (calls to the class methods configure this). Each
handler had a certain required structure; a handler would
perform a series of actions, then, after a while, return to a
loop in the StateMachine.run() method with a flag indicating
the desired next state. As well, a cargo variable was used
to allow one state to pass some (unprocessed) information on to
the next state.
A typical use for the StateMachine class I presented would be
to consume input in a stateful way. For example, a text
processing tool (Txt2Html) I use reads lines from a file; each
line needs to be processed in a particular fashion, depending
on which category the line belongs in. However, you often
need to look at the context provided by immediately prior
lines to determine which category the current line belongs in
(and how it should be processed). An implementation of this
process built around the StateMachine class might define a
handler A that reads lines for a while, and processes them in
an A-like manner. After a while, a condition is satisfied such
that the next batch of lines should be processed by the B
handler. A passes control back to the .run() loop, with
the instruction to transition to the B state -- along with any
extra line(s) that A could not properly handle, and that B
should before reading additional lines. Eventually, some
handler passes its control to some state designated as an end
state, and processing halts.
For the concrete code example in the earlier installment, I used
a simplified application. Rather than process lines, I
processed a stream of numbers that were produced by an
iterative function. Each state handler simply printed those
numbers that were within its desired numeric range (along with
some messages about the operative state). When a number in the
stream passed into a different range, a different handler took
over the "processing." For this installment, we will look at
another way of implementing the same numeric stream handling
using generators (with some extra wrinkles and capabilities).
But a more sophisticated generator example is likely to deal
with something more like the input streams mentioned in the
prior paragraph. Let's review the
earlier state machine with an abridged version of that code:
Listing 1. statemachine_test.py
from statemachine import StateMachine
def ones_counter(val):
print "ONES State: ",
while 1:
if val <= 0 or val >= 30:
newState = "Out_of_Range" ; break
elif 20 <= val < 30:
newState = "TWENTIES"; break
elif 10 <= val < 20:
newState = "TENS"; break
else:
print " @ %2.1f+" % val,
val = math_func(val)
print " >>"
return (newState, val)
# ... other handlers ...
def math_func(n):
from math import sin
return abs(sin(n))*31
if __name__== "__main__":
m = StateMachine()
m.add_state("ONES", ones_counter)
m.add_state("TENS", tens_counter)
m.add_state("TWENTIES", twenties_counter)
m.add_state("OUT_OF_RANGE", None, end_state=1)
m.set_start("ONES")
m.run(1) |
Readers further interested in the imported StateMachine class
and how its methods work should take a look at the earlier
installment.
Using generators
The entire generator-based version of our state machine is
slightly longer than the code samples I prefer to present in
this column. However, the following code sample is the entire
application, and no separate statemachine module is imported for
support. In total, this version is shorter than the
class-based one (and we will see that its does something extra,
and very powerful).
Listing 2. stategen_test.py
from __future__ import generators
import sys
def math_gen(n): # Iterative function becomes a generator
from math import sin
while 1:
yield n
n = abs(sin(n))*31
# Jump targets not state-sensitive, only to simplify example
def jump_to(val):
if 0 <= val < 10: return 'ONES'
elif 10 <= val < 20: return 'TENS'
elif 20 <= val < 30: return 'TWENTIES'
else: return 'OUT_OF_RANGE'
def get_ones(iter):
global cargo
while 1:
print "\nONES State: ",
while jump_to(cargo)=='ONES':
print "@ %2.1f " % cargo,
cargo = iter.next()
yield (jump_to(cargo), cargo)
def get_tens(iter):
global cargo
while 1:
print "\nTENS State: ",
while jump_to(cargo)=='TENS':
print "#%2.1f " % cargo,
cargo = iter.next()
yield (jump_to(cargo), cargo)
def get_twenties(iter):
global cargo
while 1:
print "\nTWENTIES State: ",
while jump_to(cargo)=='TWENTIES':
print "*%2.1f " % cargo,
cargo = iter.next()
yield (jump_to(cargo), cargo)
def exit(iter):
jump = raw_input('\n\n[co-routine for jump?] ').upper()
print "...Jumping into middle of", jump
yield (jump, iter.next())
print "\nExiting from exit()..."
sys.exit()
def scheduler(gendct, start):
global cargo
coroutine = start
while 1:
(coroutine, cargo) = gendct[coroutine].next()
if __name__ == "__main__":
num_stream = math_gen(1)
cargo = num_stream.next()
gendct = {'ONES' : get_ones(num_stream),
'TENS' : get_tens(num_stream),
'TWENTIES' : get_twenties(num_stream),
'OUT_OF_RANGE': exit(num_stream) }
scheduler(gendct, jump_to(cargo)) |
There are a number of observations to make about our
generator-based state machines. A first point is largely
cosmetic. We arranged stategen_test.py to use only
functions, not classes (generators, to my mind at least, have
much more of a functional programming feel than an OOP feel).
But one could easily wrap the same general model in one or more
classes if desired.
The main function in our sample is scheduler(), which is
perfectly generic (while being quite a bit shorter than the
StateMachine class in the earlier pattern). The function
scheduler() requires as arguments a dictionary of
generator-iterator objects ("instantiated" generators). The
string names given to each generator can be whatever one
wants -- the literal names of the generator-factory functions is
one obvious choice, but I use capitalized keyword names in my
example. The scheduler() function also accepts a "start
state" as an argument, although perhaps a default value could
be selected automatically if that was desired.
Each generator "scheduled" obeys some simple conventions. Each
generator runs for a while, then yields a pair that contains
the desired jump and some "cargo" -- just as with the prior
model. No generator is marked specifically as an "end state."
Instead we allow individual generators the option of raising an
error to break out of scheduler(). Specifically, a generator
will raise a StopIteration exception if the generator "falls
off" the end or gets to a return statement. One could catch
that exception (or a different one), if desired. In our case,
we use a sys.exit() to terminate the application, which is
encountered within the exit() generator.
Two more small notes on the code. Instead of an iterative
function to generate our numeric sequence, the above sample
uses a much cleaner looping generator-iterator. Rather than
having continually to pass back in the "last value," the
generator simply issues an (infinite/indefinite) stream of
numbers with each successive call. It is a nice, albeit small,
illustration of a generator. As well, the above isolates the
"state transition" table in a separate function. In a
realistic program, the state transition jumps would be much
more context dependent and would probably be determined in the
actual generator bodies. This approach simplifies the example.
For what it is worth, we could have simplified even further by
producing the generator functions out of a single function
factory; but the general case would not have each generator so
similar to the others as to make this feasible.
Coroutines and semi-coroutines
Careful readers will have noticed that we have actually
smuggled in a much more powerful flow-control structure than
was initially admitted. There is more than a state machine
going on in the sample code. The pattern above is, in fact,
effectively a general system for coroutines. Most readers will
probably need a little bit of background here.
A coroutine is a collection of program functionality that
allows arbitrary branching into other control contexts and
arbitrary resumption of flow from the branch point. The
subroutines familiar in most programming languages are an
extremely limited sub-case of general coroutines. A subroutine
is only entered from a fixed point at the top, and only exits
once (it cannot be resumed). A subroutine also always
passes flow back to its caller. In essence, each coroutine
represents a callable continuation -- although adding a new word
doesn't necessarily clarify things for those who do not know
it. An illustration, "Cocall Sequence Between Two Processes," in Randall Hyde's The Art of Assembly
goes a long way towards explaining coroutines. You'll find a link to this figure in Resources. Also see Resources for a link to Hyde's general discussion, which is good.
Despite the negative associations, one can note that the
infamous goto statment in many languages allows arbitrary
branching too, albeit in a less structured context that
promotes "spagetti code."
Python 2.2+'s generators take a big step towards coroutines.
That is, generators -- unlike functions/subroutines -- are
resumable and can yield values across multiple invocations.
However, Python generators are only what Donald Knuth describes
as "semi-coroutines." A generator is resumable and can branch
control elsewhere -- but it can only branch control back to its
immediate caller. To be precise, a generator context (like any
context) can itself call other generators or functions -- even
itself recursively -- but every eventual return must pass through
a linear hierarchy of return contexts. Python generators do
not allow for the common coroutine usage of "Producers" and
"Consumers" that freely resume into the middle of each other.
Luckily, full-fledged coroutines are quite easy to simulate
with Python generators. The simple trick is a scheduler()
function exactly like the one in the above sample code. In fact,
the state machine presented is itself a much more general
coroutine framework pattern. Adapting to this pattern
overcomes the minor limitations still present in Python
generators (and gives incautious programmers the full power of
spagetti code).
Stategen in action
To see exactly what is going on in stategen_test.py, the
easiest thing is to run it:
Listing 3. Running STATEGEN (with manual jump control)
% python stategen_test.py
ONES State: @ 1.0
TWENTIES State: *26.1 *25.3
ONES State: @ 4.2
TWENTIES State: *26.4 *29.5 *28.8
TENS State: #15.2 #16.3 #16.0
ONES State: @ 9.5 @ 3.8
TENS State: #18.2 #17.9
TWENTIES State: *24.4
TENS State: #19.6
TWENTIES State: *21.4
TENS State: #16.1 #12.3
ONES State: @ 9.2 @ 6.5 @ 5.7
TENS State: #16.7
TWENTIES State: *26.4 *30.0
[co-routine for jump?] twenties
...Jumping into middle of TWENTIES
TWENTIES State:
TENS State: #19.9
TWENTIES State: *26.4 *29.4 *27.5 *22.7
TENS State: #19.9
TWENTIES State: *26.2 *26.8
Exiting from exit()... |
This output is basically identical to that from the earlier
statemachine_test.py. Each line of the results represents flow
spent in one particular state handler or generator; the flow
context is announced at the beginning of the line. However,
rather than simply call a handler function again, the
generator version resumes execution (within a loop) whenever
another coroutine branches into it. Given that the bodies of
all the get_*() coroutines are all contained in infinite
loops, this difference is less evident.
To see what is fundamentally different in stategen_test.py
look at what happens in the exit() generator. On the first
invocation of the generator-iterator, a jump target is
collected from the user (which is a simple case of the
event-driven branching decisions a realistic application might
utilize). However, when exit() is invoked a second time, it
is within a later flow-context in the generator -- an exit
message is displayed, and sys.exit() is called. The user in
the sample interaction could also have jumped directly to
"out_of_range," which would exit without going to another
"handler" (but it would perform a recursive jump into this
same generator).
Conclusion
As was hinted in the introduction, I expect my coroutine
version of a state machine to run significantly faster than the
class-with-callback-handlers version presented earlier.
Resuming a generator-iterator will be notably efficient. The
particular example is so simple as to be hardly worth
benchmarking, but I welcome readers' feedback on concrete
results.
But any speedup the "coroutine pattern" I present might achieve
is shadowed by the startlingly general flow-control it allows.
A number of readers on the comp.lang.python newsgroup have
inquired about just how general Python's new generators are. I
think the availability of the described framework makes the
answer, "as general as one can want!" As with most things
Pythonic, it is usually a lot easier to program the things
than it is to understand them. Give my pattern a try; I
think you will find it useful.
Resources - Read the previous installments of the Charming Python column.
- Early on in this column, I presented an abstract pattern for a
broad class of state machines in Python. That installment is
the touchstone from which I explicate the new concepts here.
-
My interview with Stackless Python creator Christian Tismer
touched on coroutines briefly, along with other exotic flow
structures such as continuations, microthreads, and generators.
The installment hints at some of the issues, before Python 2.2
introduced generators.
-
Of most recent and close connection is my effort to introduce
iterators and simple generators during Python 2.2's alpha
period.
- Several installments of this column have touched on functional programming in Python. Given the somewhat FP feel of generators, these might
be worth looking at:
-
The Art of Assembly also contains an introduction to coroutines (albeit for assembly).
About the author | 
| |
David Mertz would like to write, with Nietzsche, that these are the
musings of an old philologist, but that untruth would unmask itself. But perhaps his (gratuitously plugged) forthcoming book, Text Processing in Python, will someday be
mistaken for a cybernetic variant of philology. David may be reached at mertz@gnosis.cx; his life pored over at http://gnosis.cx/dW/. Suggestions and recommendations on this, past, or future columns are welcome. |
Rate this page
| |
