← Distance Coaching and a New Program | Released django-hotrunner →

Dynamic State Machines

I was talking with my coworkers Jeff and Randy yesterday about some work Randy was doing implementing a finite state machine in django, and I was reminded of a pattern I've previously used to implement state machines using Python's dynamic typing to do it.

In more static languages, an object is forever bound to its type, and implementing state-dependent behavior often requires using supporting classes which can be switched out to implement the variable behavior of different states. Python's dynamic nature makes this much simpler.

Implementing state with dynamic typing

In python, an object's type is determined simply by looking at the value of it's __class__ attribute. Conveniently, but also rather frighteningly, this attribute is mutable. That means you can change the fundamental class of an object simply by assigning a new class to it's __class__ attribute.

This pattern is very powerful, and could easily be abused, but it expresses what is happening clearly and effectively, and matches the problem domain straightforwardly. Conceptually, as the object changes states, it becomes a different type of object. Implementation-wise, as the object changes states, we change the type of the object. The classes we use can be subclasses of a common base class, if we wish to implement common behavior across the states, but this is completely optional. Python doesn't care if our states are related or not.

A Blue morpho butterfly (Morpho menelaus)

Under the hood, when you try to access attributes on an object, python will first look to see if the attributes exist on the object itself. If they do, it uses them directly, but if not, it will check the class, and then the superclass, and on up the method resolution order to the base class, object. This is a bit of a simplification, which ignores the power python gives the programmer to override attribute access using __getattr__ and __getattribute__, but it works for our purposes

As the object changes states, it will continue to be the same object. It will have all the same attributes it had before, but now any operations that look for the object's class will find the newly assigned class, rather than the one that was used to create the object in the first place.

The life-cycle of a Butterfly

As an example, let's look at a state machine implementing the life-cycle of a butterfly:

class Egg(object):
    def __init__(self, species):
        self.species = species

    def hatch(self):
        self.__class__ = Caterpillar

class Caterpillar(object):
    legs = 16
    def crawl(self): pass
    def eat(self): pass
    def pupate(self):
        self.__class__ = Pupa

class Pupa(object):
    def emerge(self):
        self.__class__ = Butterfly

class Butterfly(object):
    legs = 6
    def fly(self): pass
    def eat(self): pass
    def reproduce(self):
        return Egg(self.species)

The object begins its life as an Egg, which hatches and becomes a Caterpillar, which becomes a Pupa, and finally a Butterfly, which can reproduce, creating a new Egg.

In practice, it looks like this:

>>> import butterfly
>>> critter = butterfly.Egg('Morpho menelaus')
>>> id(critter), type(critter), critter.species
(10376583L, <class 'butterfly.Egg'>, 'Morpho menelaus')
>>> hasattr(critter, 'legs')

We create an egg object which is a perfectly normal python object in all ways. The instance has one user-space attribute: species, which will stick with the object for its entire life. As an egg, it doesn't have a legs attribute, because we haven't assigned one. The only thing the egg can do is hatch, at which point, it becomes a Caterpillar.

>>> critter.hatch()
>>> id(critter), type(critter), critter.species
(10376583L, <class 'butterfly.Caterpillar'>, 'Morpho menelaus')
>>> critter.legs
>>> critter.crawl()
>>> critter.eat()
>>> critter.hatch()

Note the id of our critter is still the same after hatching as it was before. We also still have a species attribute, which holds the value we assigned to it as an Egg. It now has a class attribute named legs, which indicates that the Caterpillar has 16 legs. It can crawl and eat, as those methods are defined on the Caterpillar class, but it can no longer hatch.

>>> critter.pupate()
>>> id(critter), type(critter), critter.species
(10376583L, <class 'butterfly.Pupa'>, 'Morpho menelaus')
>>> dir(critter)
['__class__', '__delattr__', '__dict__', '__doc__', '__format__',
'__getattribute__', '__hash__', '__init__', '__module__', '__new__',
'__reduce__', '__reduce_ex__', '__repr__', '__setattr__', '__sizeof__',
'__str__', '__subclasshook__', '__weakref__', 'emerge', 'species']

The Pupa has the same id still as the Egg and the Caterpillar. Looking inside, it has two regular attributes, the instance attribute species (still 'Morpho menelaus' of course), and a method, emerge(), which turns our critter into a fully grown Butterfly.

>>> critter.emerge()
>>> id(critter), type(critter), critter.species
(10376583L, <class 'butterfly.Butterfly'>, 'Morpho menelaus')
>>> critter.legs
>>> critter.eat()
>>> critter.fly()
>>> 'reproduce' in dir(critter)
>>> critterling = critter.reproduce()
>>> id(critterling), type(critterling), critterling.species
(10377274L, <class 'butterfly.Egg'>, 'Morpho menelaus')

Now the fully grown critter has six legs. It can eat, and fly, but no longer crawl (Technically a butterfly in the real world can crawl, but a Butterfly object cannot). It can also reproduce, creating critterlings that go through the same life cycle.

Implementation details

This is a powerful pattern for implementing state. It allows drastic changes in behavior simply by changing a single attribute on the model. It does has a few quirks that are worth bearing in mind:

  • __init__ methods will not be called at state time. Thus, you will need to take care that any instance attributes you will need are available as the object changes state. If there is any extra tinkering that needs to be done at transition time, that will have to be managed by in the methods that implement the transition.
  • Instance attributes will stay with the object throughout its life cycle, and class attributes will be available to any object in that state at the time. If you need an attribute that exists on a particular object, but only in a particular state, you will need to manage that yourself. Either by creating and destroying the attribute at the appropriate times, or by limiting access to that attribute in some way. (This could probably be done with creative use of @property decorators on the different states).
  • Once you know how it works overriding the __class__ attribute on objects can also be a powerful technique for testing, debugging, or pranking fellow developers. The flipside of this is that it is often smarter to avoid using clever tricks in favor of clearer code, so use this technique sparingly, and under well-controlled circumstances.

Happy coding!

Comments !