Simplify Logic With State Machines

Your code will be simpler, and you won’t need any extra libraries or design pattern implementations.

As a rule, data is easier to change than code, so when I develop, I look for opportunities to express things using data structures and not control structures. A lot of the stuff I produce is driven by tables and by little minio-interpreters.

State machines take this to a new level; they add context and the ability to decide which code to run in particular circumstances. (you may see state machines referred to as Finite State Automata (FSA) or Finite State Machines (FSM)).

However, there’s a lot of FUD spread about the implementation of state machines, and as a result many developers avoid them. That’s just plain silly: a simple state machine can make your code far easier to understand and change.

Unlocking The State Machine

We’re writing the software for a keypad lock, which unlocks when the user hits four numbers in the correct sequence. Any leading numbers are ignored. If the code was 1417, then the sequence 1231417 will unlock the device.

Before we go further, try writing come code that accepts keypresses, one at a time. It should notify you when it sees the unlocking sequence.

Cool. It’s not terribly difficult, but the code can be a little ugly.

A State-Based Lock

Let’s create a state machine that implements this lock.

A state machine is defined by events, states, and transitions.: The machine sits in a particular state until an event comes along. This may cause a tran- sition into a different state.

We draw state machines with the states in boxes or circles, and the transitions as arrows between states. The transitions are labelled with the event that triggers them.

Here’s a state machine that describes a retractable ball-point pen.

If the pen is extended and the top is clicked, we transition to the retracted state, and vice-versa.

Let’s draw the diagram for our lock:

I introduced a new concept here. The transitions labelled “else” are default transitions, triggered when an event occurs and the current state doesn’t have an explicit transition that handles it. You’ll also see that the initial, locked, state, has an else transition that loops back to itself. This means than when locked, the state machine will ignore key presses until it sees a “1”.

One nice thing about state machines is that you can try them out with your finger—no code required. Put your finger on the locked state. Now imagine a “9” key is pressed. There’s no transition labelled with that event, so you take the “else” transition back to “Locked.”

Now a “1” is pressed. You finger follows the “1” transition; you’re in a new state. If the next event isn’t a “4”, you’ll find yourself back in the locked state. If it was a “4”, you’ll move on to the next. The next event is a “1”, followed by a “7”. Your finger will be on the unlocked state.

There’s a bug in out state machine, though. See what happens if you feed it the events 1, 4, 1, 4, 1, 7. You expect your finger will be on the unlocked state, because the sequence contained 1417, but you find it back pointing at locked.

Can you see why?

After handling the first three events, “1”, “4”, “1”, we’re in the “Second 1 seen” state, eagerly awaiting the arrival of a “7”. Instead we get a “4”. It turns out that the second “1” in the event stream was actually the first “1” of the unlocking sequence. When it is followed by a “4”, we have to move back to the second state, “4 seen”. At this point we’re back on track.

The cool thing is that we found a bug and we haven’t written any code yet.

State machines clarify your thinking before you code

When faced with implementing a state machine, most developers look for a library. Don’t bother. The diagram can be represented using a simple hash (or dictionary or map, depending on your language), and the interpreter is a handful of lines of code.

Here’s the hash that describes the machine:

It’s actually a hash of hashes. At the top level, the key represents the current state, and the value contains the transitions away from that state. Each transition is keyed with an event, and the value is the of the next state.

And here’s the code that traverses this data structure as when you type key presses, on per line, on the console.

After setting the initial state, we loop, stopping when there are no possible transitions out of the current state or when our input is exhausted.

After removing the trailing newline from the input, we implement the transition to the next state in a single line of code: we either take the transition for the event or we take the default “ELSE” transition.

We can report our status when the loop terminates:

And that’s all there is to a basic state machine.

Adding Actions

Let’s go back to the retractable pen. The state machine happily transitions between the extended and retracted states, but it doesn’t actually do anything to the pen itself. We need to add some actions. Perhaps counter intuitively, these actions are associated with transitions, and not states. Just to make that clear: Actions happen on events

This diagram tells us that when we’re in the retracted state and the button on the pen is clicked, we transition to the extended state, and along the way we call the extend action.

In our state machine definition, we’ll make each transition an object with a next_state and an action.

Then we can define the actions. Here I chose to stick them into a JavaScript object, just to give them a namespace. You could also create create functions and use their names in the previous table, or look up the action using some kind of switch; whatever is idiomatic in your language du-jour.

For the event handling, I thought I’d try running under Deno, as I haven’t really played with it. It has a convenient prompt function which writes text to the console and then returns any input. If you respond to the prompt with an empty string (just hit return), then this will be falsy, and the event will be "half-click", otherwise it will be "click". (A half-click corresponds to those annoying times you don’t push hard enough and the pen stays in the same state.)

Let’s run it.

Long-Running State Machines

When our code interacts with the outside, we often have to keep track of the state, which changes based on what the world does. If we’re creating a new user in our system, we’ll pass through a sign up flow, which might have half- a-dozen steps, some optional. If we’re shipping an order, we may be interacting with different carriers. Again, the order will move through different states as they respond.

State machines are perfect for this kind of application. All you need is a way of persisting the state between external events. The state will contain the state name, but will likely also hold information that’s been generated to date while processing this request.

When a new event is generated, we find that persisted state. We do a transition using a couple of lines of code, and invoke the action, passing it the request state that we stored. When it returns, it will pass an updated state which you can persist while waiting for a new event.

Workflows are just state machines

You can extent this basic idea in a number of ways.

• The actions could return either new state values or an event. If an event is returned, the code will immediately perform another transition using it. This can be useful for exception and error handling, and for merging different paths into some common trailing path.

• You can run the actions asynchronously, as long as you ensure that a new event for a particular request doesn’t start a new action until any previous action completes.

• You can alter the workflow that handles the request by just changing the state transition table. You could even A/B test workflows by having mul- tiple tables that are chosen dynamically.

Simplifying Events

Let’s start with a generous definition: an event occurs when information becomes available to your code. Clearly an event might be a task finishing, or an I/O operation completing. It could also be an error being detected. But we can also think of events being triggered by each element being fetched by an iterator, or by records arriving via an API. If it can potentially change your application’s state, then it’s an event.

Squint hard enough, and just about anything can be an event.

Traditionally, we handled events sequentially: our waited for the next event to occur. Increasingly we’re writing asynchronous code, where events trigger event handling functions. This improves concurrency, but at the expense of additional complexity. In a fully event-driven system it’s almost impossible to know what is going on, and if you discover some invalid values in the cur- rent state, tracking back where they came from can be difficult.

Give Them a Try

State machines impose some order on event handling, whether synchronous or asynchronous. I find myself creating a state machine perhaps once a month; when I do, I know I’m saving myself days of future frustration.