Python state-machine design

Question

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

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 while leveraging Python's dynamic nature (e.g. dynamic dispatching).

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

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

Solution 2

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

Solution 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).

Solution 4

I also was not happy with the current options for state_machines so I wrote the state_machine library.

You can install it by pip install state_machine and use it like so:

@acts_as_state_machine
class Person():
    name = 'Billy'

    sleeping = State(initial=True)
    running = State()
    cleaning = State()

    run = Event(from_states=sleeping, to_state=running)
    cleanup = Event(from_states=running, to_state=cleaning)
    sleep = Event(from_states=(running, cleaning), to_state=sleeping)

    @before('sleep')
    def do_one_thing(self):
        print "{} is sleepy".format(self.name)

    @before('sleep')
    def do_another_thing(self):
        print "{} is REALLY sleepy".format(self.name)

    @after('sleep')
    def snore(self):
        print "Zzzzzzzzzzzz"

    @after('sleep')
    def big_snore(self):
        print "Zzzzzzzzzzzzzzzzzzzzzz"

person = Person()
print person.current_state == person.sleeping       # True
print person.is_sleeping                            # True
print person.is_running                             # False
person.run()
print person.is_running                             # True
person.sleep()

# Billy is sleepy
# Billy is REALLY sleepy
# Zzzzzzzzzzzz
# Zzzzzzzzzzzzzzzzzzzzzz

print person.is_sleeping                            # True

Solution 5

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",
    #...
  }

View more solutions

Comments

[jldupont]

+1: thanks, I was contemplating this possibility too. I haven't settled on an implementation just yet.

[user1066101]

@jldupont: Right out of the book. Didn't invent it, just copied it from the GoF Design Patterns book. That's why I still don't get your question -- they cover this completely.

[jldupont]

@scott: I do not have this book. By asking the question, I am hoping to tap the SO community collective wisdom. You can of course choose to ignore the question or contribute: that's your choice.

[jldupont]

@scott: ... and I thank you for your contribution. I do not believe I have "complained" but of course the definition of "complaining" falls in the "qualitative territory". Have a good day!

[jldupont]

@scott: come to think of it, my previous "complaint" might have been triggered by your insistence in stating that you don't get my question. No hard feelings on my side.

[dbr]

Although you copied it out the book, it seems "nicer" to use something like globals()[self.map[input]]() (or a dict like {'S1': S1}) instead of eval? To further nitpick, it's redefining the built-in next`

[jldupont]

@Jason: as far as I am concerned, any (but the trivial) piece of software acts as a "state-machine" in some form or another. The statement that an FSM is of limited use falls in bottomless pit on my territory. Of course, if you are referring to a particular FSM pattern, that might be the case but I tend to be flexible when it comes to applying patterns.

[user1066101]

@jldupont. I don't get your question. It's vague and confusing. It seems like you're trying to use a SAX parser for something, but I can't tell what. A context stack is generally all that's needed to construct a DOM object that represents the original XML.

[Robert Rossney]

Just about any algorithm can be implemented as a state machine. Very few of them should be.

[Jason Orendorff]

@jldupont: The ranty part of my answer refers to a specific technique where you actually design part of your program as a finite state machine in the ordinary sense of the term, states and transitions are explicit in the code, and some logic is encoded in a state transition table. Like your example and all the other answers. :)

[jldupont]

@scott: the question isn't about XML parsing per-se... and yes it is vague on purpose: that's why I asked suggestion on "design techniques" (in general) and not specifically on XML SAX based parsing. Sorry for the confusion.

[PaulMcG]

Matt Anderson submitted this version of my statemachine code to the pyparsing wiki (pyparsing.wikispaces.com/message/view/Publications/18439845‌​) which is compatible with Py2.7 and up.

[erikbstack]

Love the code but hate the naming, i.e. wouldn't AbstractState not be a better name than SuperState? And you didn't copy the state transition part. The book actually leaves the transition open and mentions different implementation variations (Context method with big if-else, your implementation, or state transtion dict)

[erikbstack]

Great mention. Always wondered how I would implement exactly that!

[Fake Name]

I've written a few python state machines using this design, and I have to say I think it's the cleanest one out of all the options here. It doesn't require a external library, the internal mechanics are quite simple and concise, and it works very well.

[PaulMcG]

wikispaces is no longer online. This code is now at the pyparsing GitHub repo: github.com/pyparsing/pyparsing/tree/master/examples/…

[keios]

Ha, I wasn't happy either - so I wrote this instead, github.com/kashifrazzaqui/themstates

[keios]

Here is a completely different way of doing this. github.com/kashifrazzaqui/themstates

[Wolfgang Fahl]

the link to the post is broken