Charming Python: Generator-based state machines

Increasing efficiency with generator-based state machines and coroutines

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.]

Share:

David Mertz (mertz@gnosis.cx), Producer, Gnosis Software, Inc.

David Mertz photo 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.



01 July 2002

Also available in Russian Japanese

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

Comments

developerWorks: Sign in

Required fields are indicated with an asterisk (*).


Need an IBM ID?
Forgot your IBM ID?


Forgot your password?
Change your password

By clicking Submit, you agree to the developerWorks terms of use.

 


The first time you sign into developerWorks, a profile is created for you. Information in your profile (your name, country/region, and company name) is displayed to the public and will accompany any content you post, unless you opt to hide your company name. You may update your IBM account at any time.

All information submitted is secure.

Choose your display name



The first time you sign in to developerWorks, a profile is created for you, so you need to choose a display name. Your display name accompanies the content you post on developerWorks.

Please choose a display name between 3-31 characters. Your display name must be unique in the developerWorks community and should not be your email address for privacy reasons.

Required fields are indicated with an asterisk (*).

(Must be between 3 – 31 characters.)

By clicking Submit, you agree to the developerWorks terms of use.

 


All information submitted is secure.

Dig deeper into Linux on developerWorks


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=1
Zone=Linux
ArticleID=11225
ArticleTitle=Charming Python: Generator-based state machines
publish-date=07012002