Async Superpowers: State Machines

It seems that every UI in existence has to deal with doing something asynchronous. If you don’t know what that means, think back to every time you’ve seen one of these:

Hang on, we’re loading stuff…

Any time you see a “spinner” like the above, it’s probably an indication that some asynchronous stuff is happening. Programming UIs that do asynchronous stuff can be difficult. What often seems even more difficult is testing those UIs. And when I say, “testing,” I mean real tests. Automated tests. And… many programmers just don’t bother with those. Instead, we just slap some spinners into the code, do a bit of manual testing (ewww… 🤢), and call it good. I’m here to tell you, there’s a better way. A way to write UIs with complex asynchronous logic that you can test easily.

But, to get there, I’ve got to teach you some computer science fundamentals. So buckle up, we’re going to learn about state machines, also called discrete finite automata or DFAs.

Part 1: Intro to State Machines

A state machine is a way to model a specific kind of computation problem. It can be a system that changes over time, parsing text a character at a time, or a number of other kinds of similar problems. We can model each phase of that computation over time in precise steps, called states, and then define how the system moves from one state to another using something called transitions. So… states and transitions.

Let’s look at an example. Let’s say that we need to figure out if a given string is the string “ab”, that is, a single “a” followed by a single “b”. We can model this using a state machine that looks like this:

A simple state machine for parsing the string “ab”

You see, the way a state machine works is simply this: Given a current state and some input, a state machine decides what the next state is. Our states, start, s1, ands2, are represented by circles, and our transitions are the arrows that point between these three states. Notice that each transition has a letter associated with it. This is our input. One last observation is that s2 is marked green, to indicate that it’s our “success” state. Now, we’ll go through a few examples.

First, let’s try the string “ab”. We begin at the start state, and follow the transition from start to s1 for input a, arriving at s1. Then, at state s1, we follow the transition to s2 for input b. Since we’ve processed all the input and arrived at the “success” state, the state machine has shown us that this, indeed, is the string “ab”. Underwhelmed? Just hang in there.

Now, let’s see what happens when we give it input that doesn’t match. For instance, if we tried the string “ac”, we’d go from start to state s1, and then have input c that we need to process. But there is no transition from state s1 for input c. Put another way, there’s no arrow that starts at state s1 that is labeled with the input c. When we arrive at a state where there’s no transition away from that state for whatever input we’re looking at, the machine is “stuck”. When a state machine is stuck for a parsing problem like this, it means that the state machine is telling us “this input doesn’t match what I expect.”

Let’s try another failing example. Let’s parse the string “a” using our state machine. Again, we follow the transition for a from start to s1, but then we have no more input to process. The state machine is done processing the input, but it’s not at the “success” state of s2. This, again, means the state machine has told us that the input string we processed doesn’t match.

Now, let’s look at a more complex example:

Zero or more ‘a’s followed by zero or more ‘b’s followed by at least one ‘c’.

We can design a state machine¹ that solves this problem, and it looks like this:

A state diagram for parsing the string with the above rules.

This state machine is, obviously, a bit more complex. Let’s go through some examples. See if you can follow along from state to state as the machine processes each letter. First, let’s look at the steps for processing string “abbbc”:

• At state start, input a: follow transition for ato s1
• At state s1, input b: follow transition for b to s2
• At state s2, input b: follow transition for b to s2
  Note: some transitions start and end at the same state, like this one. This is one of the ways that state machines can handle repetitive input.
• At state s2, input b: follow transition for b to s2
• At state s2, input c: follow transition for c to s3
• At state s3, no remaining input: s3 is a success state; SUCCESS

Now, let’s look at the string “acd”:

• At state start, input a: follow transition for ato s1
• At state s1, input c: follow transition for c to s3
• At state s3, input d: no transition from s3 for d; stuck; FAIL

Now, try a few examples of your own that match the rules:

Zero or more ‘a’s followed by zero or more ‘b’s followed by at least one ‘c’.

More Than Parsing

State machines can model more things than just parsing text. Let’s say we’d like to model the operational controls for a rollercoaster using a state machine. We have gates that allow the queued passengers into the loading area, we have restraints that keep people in the cars while the rollercoaster is moving, and we have a launch motor that gets the stopped rollercoaster moving onto the track. We also have a number of safety-related scenarios that we want to prevent:

• Open gates while the rollercoaster is moving — this could cause crowding near the loading platform and allow someone to be struck by a moving coaster
• Restraints released while the rollercoaster is in motion — this could cause someone to fall out of the ride!
• Open gates while the previous riders are still restrained and waiting to exit — this could cause sneaky passengers to ride multiple times in a row

So, we could model the operational controls like this:

A potential model for safe operation of a rollercoaster.

Starting with an empty rollercoaster with open gates (the Loading state), the operator ensures that passengers get seated and no other passengers are on the loading platform. Next, the operator closes the gates and begins securing the passengers (the Securing state). Once the passengers are secured, the operator launches the rollercoaster and the passengers enjoy their ride (the Riding state). When the coaster returns to the loading platform a sensor is triggered (the Waiting for exit state). The operator can then release the restraints (moving to the Exiting state) and wait for the platform to clear before opening the gates and allowing a new set of passengers to board (moving back to Loading). We also have the additional option while in the Securing state to release the restraints and let terrified would-be passengers out of the ride at the last moment. Don’t ask me why I know this is a thing.

If you remember, the transitions between states represent input, and state machines only accept certain inputs at certain states. For instance, this state machine only accepts the input Release restraints in the Waiting for exit and Securing states, since it would be obviously dangerous to release the restraints on a moving rollercoaster! If the operator were to press the “release restraints” button while the coaster is moving, the state machine would not become “stuck” like parsing strings. Instead, the state machine would simply ignore that input. So, in cases like parsing, state machines are “stuck” on unexpected input. In cases like safety controls and UIs, state machines often ignore invalid or irrelevant input.

Next Up

So, what do rollercoaster rides have to do with UIs that do asynchronous things? They both have to wait for things to finish, accept user input, and ignore invalid input. In the next few articles, we’ll talk through how to model a UI that does asynchronous stuff using a state machine. Next up: Part 2!

¹ Fun fact: many regular expression engines use DFAs to parse strings, and there is a mathematical relationship between DFAs and the kinds of strings that regular expressions can parse.

For further reading: great examples of why a state machine would be better than a big pile of if/else statements