What is a State Machine?

If you’ve spent much time writing software or if you’ve been through any university computer science program then the term “state machine” is probably a familiar one. You might even recognize the names of some of the variations and specializations of the idea: finite state machine, deterministic finite automaton, etc. These ideas underlie many of the fundamental concepts of software — yet, in my experience, few programmers (myself included) reach for these tools on a regular basis.

Before exploring some of the reasons I think state machines should be used more often I’d like to discuss some of the basics of what makes a state machine and what kind of problems they can be used to solve.

First of all, let’s all get on the same page. In case you didn’t receive any formal computer science training and you’ve managed to avoid bumping into state machines in your professional experience, here’s a (massively abbreviated) primer.

A state machine is a piece of software that accepts input and then (usually) generates a deterministic (probably) output.

If you think that sounds like all software ever — you’re right. All software is a state machine of one sort or another. Digital computers are primarily oriented to facilitate the creation of software state machines. And the hardware of digital computers itself is an implementation of a particular state machine.

The term “state machine” comes from the fact that, distinct from the input and output, the software has settings, values, data (all names for the same thing – in other words, “state”) which may also change when input is accepted and which may change what output is produced for the next input.

To begin, here’s an example of what I’ve decided to call an “ad hoc state machine”:

   class Turnstile(object):
        def __init__(self):
            self.locked = True

        # Two methods to react to real-world events
        def token_inserted(self):
            self.unlock()

        def arm_rotated(self):
            self.lock()

        # Two methods to effect change in the real-world
        def lock(self):
            if self.locked:
                return
            self.locked = True
            # Activate some motors to engage the lock in the real
            # world

        def unlock(self):
            if not self.locked:
                return
            self.locked = False
            # Activate some motors to disengage the lock in the real
            # world

This is a very simple class that might be used to control a simple subway turnstile. As you can see, it keeps track of how the turnstile should behave using a single boolean value (`locked`). This is the “state” referred to above. The class accepts two possible inputs: insertion of a token (represented by the `token_inserted` method) and rotation of the arm (`arm_rotated`). It can generate two outputs: activation of physical hardware to either engage or disengage a lock to allow or disallow rotation of the arm. I think this example is quite representative of the code you might find in most pieces of software written any time in the last several decades.

I call this an ad hoc state machine because the output generated for each input is determined procedurally and no attempt is made to represent the inputs or outputs explicitly. In other words, though this solution is a state machine any interesting properties of state machines are disregarded. As a result, potential benefits in the form of correctness, maintainability, and simplicity are lost.

If this is an ad hoc state machine then I should probably give an example of something that is not an ad hoc state machine. First I’ll give a pattern that seems to be common in Python programs:

    LOCKED, UNLOCKED = range(2)

    class Turnstile(object):
        def __init__(self):
            self.state = LOCKED

        ...

        # Two methods to effect change in the real-world
        def lock(self):
            if self.state == LOCKED:
                return
            self.state = LOCKED
            # Activate some motors to engage the lock in the real world

        def unlock(self):
            if self.state == UNLOCKED:
                return
            self.state = UNLOCKED
            # Activate some motors to disengage the lock in the real
            # world

This is only a minor variation from the first example but it does have one interesting consequence. The determination about whether to generate one of the possible outputs (engaging or disengaging the arm lock) is now based on an explicit single variable with all of its possible values enumerated. The `state` of a `Turnstile` instance is now clearly either `LOCKED` or `UNLOCKED`. The benefits of representing this explicitly are more apparent when the solution becomes more complex. Consider an elaboration on `Turnstile` which accounts for the fact that engaging or disengaging a physical lock is not an instantaneous operation:

    class Turnstile(object):
        def __init__(self):
            self.locked = False
            self.active = False
            self.want_locked = False

        # Two methods to effect change in the real-world
        def lock(self):
            if self.active:
               self.want_locked = True
               return

            if self.locked:
               return

            self.active = True
            # Activate some motors to engage the lock in the real
            # world

        def unlock(self):
            if self.active:
               self.want_locked = False
               return

            if not self.locked:
                return

            self.active = True
            # Activate some motors to disengage the lock in the real
            # world

        # A couple more methods to respond to real world events
        def arm_lock_engaged(self):
            self.active = False
            self.locked = True
            if not self.want_locked:
               self.unlock()

       def arm_lock_disengaged(self):
           self.active = False
           self.locked = False
           if self.want_locked:
              self.lock()

`Turnstile` now has three flags instead of just one. The interactions between these flags is a little bit tricky and at least requires careful attention in order to fully understand. Perhaps more significantly, it requires careful attention to ensure the implementation actually accomplishes the desired result and this attention must be given to the entire class to make sure that each flag manipulation is correct with respect to the rest of the desired behavior. For example, the entire turnstile could be broken if the `unlock` method were to forget to set the `active` flag. At best the motors involved might disregard a signal to engage the lock while they were occupied engaging it. At worst they might suffer physical damage.

Consider this version of the same functionality implemented using the `state` attribute pattern first given above:

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

    class Turnstile(object):
        def __init__(self):
            self.state = UNLOCKED

        def lock(self):
            if self.state == ACTIVE:
                self.state = WANT_LOCKED
                return

            self.state = ACTIVE
            # Activate some motors to engage the lock in the real
            # world

        def unlock(self):
            if self.state == ACTIVE:
                self.state = WANT_UNLOCKED
                return

            self.state = ACTIVE
            # Activate some motors to disengage the lock in the real
            # world

        # A couple more methods to respond to real world events
        def arm_lock_engaged(self):
            state = self.state
            self.state = LOCKED
            if state == WANT_UNLOCKED:
               self.unlock()

       def arm_lock_disengaged(self):
           state = self.state
           self.state = UNLOCKED
           if self.state == WANT_LOCKED:
              self.lock()

Is this better? I think that it is a little bit of an improvement. While there are still a lot of careful attribute checks and manipulations to perform there are also several distinct advantages in this version.

First, all of the states the turnstile can be in are explicit. Notice that there are five possible states. In the three-flag based implementation there were actually eight possible permutations of the flags. What happened to those three extra combinations? They are impossible and nonsensical and neither version of the code can react usefully to them. The difference is that the state-based implementation can’t even represent them. This is a very good thing. If you can represent impossible states then you’ll always be left wondering if they’re really impossible. These are the situations that tempt you to start adding runtime assertions. These might prevent your program from doing something disastrous but only by substituting a (supposedly) less harmful failure (your program exiting prematurely; what are the people waiting in line to go through the turnstile going to think about that?).

Second, there is only one attribute being manipulated. It is easier to think about a single `state` attribute with five possible values than it is to think about three different flags (even ignoring the three extra situations the flags can represent). You can look at any part of this class and see at a glance which states it handles and which it does not. If you add some code that changes the `state` attribute then you can easily find all the other code that might be affected by that change. It’s quite easy to search your code for `WANT_LOCKED` – but just try searching for all of the code that deals with the combination of `active` being true, `want_locked` being true, and `locked` being false!

Despite these advantages, I still find the final implementation of `Turnstile` to be quite clumsy. But don’t worry, this isn’t even the tip of the iceburg when it comes to state machines. After all, only the state of the state machine has been addressed so far. Next time I’ll offer some better patterns that address more of the shortcomings of ad hoc state machines.

One comment on “What is a State Machine?
  1. Pingback: Hybrid Cluster: More Benefits of State Machines | The Black Velvet Room

Leave a Reply

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

— Back to top —