More Benefits of State Machines

Welcome, readers, to the next in my series of posts about state machines.

If you recall, in my last post I began writing about the widely used but little recognized or respected software concept of state machines. I introduced the basic idea and gave an example that demonstrated the benefits that could be achieved by making the state of a state machine explicit and first-class rather than an implicit property of several different variables. This change was an improvement to the example code but it still left something to be desired.

The next logical step is to give the same treatment to the inputs and outputs of the state machine.

The example code which modeled a turnstile dealt with several possible inputs. It could be told to unlock (as would happen when a fare is paid) and to lock again (after it has been turned once). The last version of the example also introduced two more inputs: one indicating that the physical hardware responsible for unlocking the turnstile had completed operation and another similar event for the locking operation. So, four inputs in all: fare paid, arm turned, arm unlocked, arm locked.

The turnstile dealt with just two outputs. One to engage the arm lock and one to disengage the arm lock. Having identified the inputs and outputs, the next step is to make them explicit as we made the states explicit in the previous blog post. Recall the previous example started:

LOCKED, WANT_LOCKED, UNLOCKED, WANT_UNLOCKED, ACTIVE = range(5)

We could define inputs and outputs like this as well. Instead I’m going to switch to a library that makes slightly nicer symbolic constants.

from twisted.python.constants import Names, NamedConstant

class States(Names):
    LOCKED = NamedConstant()
    UNLOCKED = NamedConstant()
    ACTIVE = NamedConstant()

class Inputs(Names):
    FARE_PAID = NamedConstant()
    ARM_UNLOCKED = NamedConstant()
    ARM_TURNED = NamedConstant()
    ARM_LOCKED = NamedConstant()

class Outputs(Names):
    ENGAGE_LOCK = NamedConstant()
    DISENGAGE_LOCK = NamedConstant()

Using a library like this magnifies the benefits of explicitly enumerating states, inputs, and outputs. For example, it’s now possible to programmatically enumerate each:

>>> list(Outputs.iterconstants())
[<Outputs=ENGAGE_LOCK>, <Outputs=DISENGAGE_LOCK>]

This will come in handy later.

With those constants defined, we can proceed to a version of the Turnstile class that’s even easier to read, write, and maintain. Since we now have objects for states, inputs, and outputs we can represent the behavior of the turnstile as data instead of code:

t = namedtuple("transition", "output next_state")

class Turnstile(object):
    _transitions = {
        States.UNLOCKED: {
            Inputs.ARM_TURNED: t(Outputs.ENGAGE_LOCK, States.ACTIVE),
            },
        States.LOCKED: {
            Inputs.FARE_PAID: t(Outputs.DISENGAGE_LOCK, States.ACTIVE),
            },
        States.ACTIVE: {
            Inputs.ARM_LOCKED: t(None, States.LOCKED),
            Inputs.ARM_UNLOCKED: t(None, States.UNLOCKED),
            },
        }

    def __init__(self):
        self.state = State.LOCKED

    def input(self, what):
        try:
            output, next_state = self._transitions[self.state][what]
        except KeyError:
            pass
        else:
            self.state = next_state
            if output is Outputs.ENGAGE_LOCK:
                # Signal the motor to engage the lock
            elif output is Outputs.DISENGAGE_LOCK:
                # Signal the motor to disengage the lock

The amount of procedural logic for this version of Turnstile is vastly reduced compared to the previous implementation. Notice that there are also only three states now. As part of writing this version of the class I realized the extra two states are actually extraneous (a live, actual demonstration of the benefits of making all pieces of the state machine explicit).

Let me break that code down for you a little bit.

First, there’s the _transitions definition. I call this the transition table. It maps every state to another dictionary. The inner dictionaries map inputs to transitions. A transition consists of an output symbol and a state symbol. There are a lot of possible variations on the details of this part of the state machine. For example, I’ve chosen to allow the inner dictionaries to be missing certain inputs. We’ll look at the consequences of that in a moment.

Next, there’s the input method. This replaces all of the methods the previous Turnstile class had. Instead of turnstile.unlock() the API is now turnstile.input(Inputs.FARE_PAID). input uses _transitions to decide what needs to happen for any particular input. It uses the state machine’s current state and the input symbol passed to it to look up a particular transition. Here, you can see the code also handles KeyError in case there is no transition defined for a certain input in the state machine’s current state (think about what happens if you try to pay the fare twice without using the turnstile in between – in this case, nothing at all).

Once the transition has been determined, the state machine’s state changes and the side-effects prescribed by the output symbol are undertaken. In this case, the arm lock motor is told to engage or disengage the lock. Some transitions are also allowed to have no output, such as is the case when the motor finishes engaging or disengaging the lock.

Today I’ll just share one final advantage of structuring code this way. Since the state transitions are data, it is now easy to write other programs that operate on them. For example, we can write a program that renders all of the state transitions as an image:

visual representation of the turnstile state machine

Since both the image and the implementation are driven by the same data, the two will never diverge and the reader can be confident they’re learning how the software will actually behave just by looking at the picture. The information being conveyed visually is much easier to consume than page or so of procedural Python that the explicit state machine is replacing.

That’s it for this entry. Stay tuned for some tips about how state machines can also help you write better unit tests with less effort.

One comment on “More Benefits of State Machines
  1. Consider encoding your state machine in a two-dimensional table (States x Events), with each cell holding a three-tuple (New State, Action to perform on transition, Transition allowed[1]). In my day job I write machine controls for automatic sorting systems, where the handling of the individual item being sorted, is handled by a state-action machine[2]. Over the last 25 years, the way of expressing the states and events have evolved from a form not unlike your example above, to the full matrix. In terms of maintainability, the total matrix is superior to the previous stages of sparse representation.

    1. In our case 0, or a unique error code.
    2. Typically 8 to 10 states and 20-35 events.

    Reply to this comment

Leave a Reply

Your email address will not be published. Required fields are marked *

— Back to top —