Python state-machine design

Question

Related to this SO question (C state-machine design), could you SO folks share with me (and the community!) your Python state-machine design techniques?

Update3: At the moment, I am going for an engine based on the following:

class TrackInfoHandler(object):
    def __init__(self):
        self._state="begin"
        self._acc=""

    ## ================================== Event callbacks

    def startElement(self, name, attrs):
        self._dispatch(("startElement", name, attrs))

    def characters(self, ch):
        self._acc+=ch

    def endElement(self, name):
        self._dispatch(("endElement", self._acc))
        self._acc=""

    ## ===================================
    def _missingState(self, _event):
        raise HandlerException("missing state(%s)" % self._state)

    def _dispatch(self, event):
        methodName="st_"+self._state
        getattr(self, methodName, self._missingState)(event)

    ## =================================== State related callbacks

But I am sure there are tons of ways of going at it whilst leveraging Python's dynamic nature (e.g. dynamic dispatching).

Update2: I am after design techniques for the "engine" that receives the "events" and "dispatches" against those based on the "state" of the machine.

Answer 1

I don't really get the question. The State Design pattern is pretty clear. See the Design Patterns book.

class SuperState( object ):
    def someStatefulMethod( self ):
        raise NotImplementedError()
    def transitionRule( self, input ):
        raise NotImplementedError()

class SomeState( SuperState ):
    def someStatefulMethod( self ):
        actually do something()
    def transitionRule( self, input ):
        return NextState()

That's pretty common boilerplate, used in Java, C++, Python (and I'm sure other languages, also).

If your state transition rules happen to be trivial, there are some optimizations to push the transition rule itself into the superclass.

Note that we need to have forward references, so we refer to classes by name, and use eval to translate a class name to an actual class. The alternative is to make the transition rules instance variables instead of class variables and then create the instances after all the classes are defined.

class State( object ):
    def transitionRule( self, input ):
        return eval(self.map[input])()

class S1( State ): 
    map = { "input": "S2", "other": "S3" }
    pass # Overrides to state-specific methods

class S2( State ):
    map = { "foo": "S1", "bar": "S2" }

class S3( State ):
    map = { "quux": "S1" }

In some cases, your event isn't as simple as testing objects for equality, so a more general transition rule is to use a proper list of function-object pairs.

class State( object ):
    def transitionRule( self, input ):
        next_states = [ s for f,s in self.map if f(input)  ]
        assert len(next_states) >= 1, "faulty transition rule"
        return eval(next_states[0])()

class S1( State ):
    map = [ (lambda x: x == "input", "S2"), (lambda x: x == "other", "S3" ) ]

class S2( State ):
    map = [ (lambda x: "bar" <= x <= "foo", "S3"), (lambda x: True, "S1") ]

Since the rules are evaluated sequentially, this allows a "default" rule.

Answer 2

It probably depends on how complex your state machine is. For simple state machines, a dict of dicts (of event-keys to state-keys for DFAs, or event-keys to lists/sets/tuples of state-keys for NFAs) will probably be the simplest thing to write and understand.

For more complex state machines, I've heard good things about SMC, which can compile declarative state machine descriptions to code in a wide variety of languages, including Python.

Answer 3

There is this design pattern for using decorators to implement state machines. From the description on the page:

Decorators are used to specify which methods are the event handlers for the class.

There is example code on the page as well (it is quite long so I won't paste it here).

Answer 4

I think S. Lott's answer is a much better way to implement a state machine, but if you still want to continue with your approach, using (state,event) as the key for your dict is better. Modifying your code:

class HandlerFsm(object):

  _fsm = {
    ("state_a","event"): "next_state",
    #...
  }

Answer 5

I wouldn't think to reach for a finite state machine for handling XML. The usual way to do this, I think, is to use a stack:

class TrackInfoHandler(object):
    def __init__(self):
        self._stack=[]

    ## ================================== Event callbacks

    def startElement(self, name, attrs):
        cls = self.elementClasses[name]
        self._stack.append(cls(**attrs))

    def characters(self, ch):
        self._stack[-1].addCharacters(ch)

    def endElement(self, name):
        e = self._stack.pop()
        e.close()
        if self._stack:
            self._stack[-1].addElement(e)

For each kind of element, you just need a class that supports the addCharacters, addElement, and close methods.

EDIT: To clarify, yes I do mean to argue that finite state machines are usually the wrong answer, that as a general-purpose programming technique they're rubbish and you should stay away.

There are a few really well-understood, cleanly-delineated problems for which FSMs are a nice solution. lex, for example, is good stuff.

That said, FSMs typically don't cope well with change. Suppose someday you want to add a bit of state, perhaps a "have we seen element X yet?" flag. In the code above, you add a boolean attribute to the appropriate element class and you're done. In a finite state machine, you double the number of states and transitions.

Problems that require finite state at first very often evolve to require even more state, like maybe a number, at which point either your FSM scheme is toast, or worse, you evolve it into some kind of generalized state machine, and at that point you're really in trouble. The further you go, the more your rules start to act like code—but code in a slow interpreted language you invented that nobody else knows, for which there's no debugger and no tools.

Answer 6

Check this and this.

Answer 7

In the April, 2009 issue of Python Magazine, I wrote an article on embedding a State DSL within Python, using pyparsing and imputil. This code would allow you to write the module trafficLight.pystate:

# trafficLight.pystate

# define state machine
statemachine TrafficLight:
    Red -> Green
    Green -> Yellow
    Yellow -> Red

# define some class level constants
Red.carsCanGo = False
Yellow.carsCanGo = True
Green.carsCanGo = True

Red.delay = wait(20)
Yellow.delay = wait(3)
Green.delay = wait(15)

and the DSL compiler would create all the necessary TrafficLight, Red, Yellow, and Green classes, and the proper state transition methods. Code could call these classes using something like this:

import statemachine
import trafficLight

tl = trafficLight.Red()
for i in range(6):
    print tl, "GO" if tl.carsCanGo else "STOP"
    tl.delay()
    tl = tl.next_state()

(Unfortunately, imputil has been dropped in Python 3.)