What State Machines Are and Why We Use Them

Robert Vogt
smartive

--

Student pulling his hair out over software bugs. Photo by Tim Gouw on Unsplash

Once upon a time there were two computer science students who coincidentally both work for the same company now. I was one of them. We were attending a class called “User Interfaces 1”, which included a practical exercise: creating a User Interface with Java Swing. More specifically, we were tasked to create a nice to use interface for a library software, which would allow hypothetical librarians to manage books, customers and rentals.

The task involved a few tricky parts intended to lead us down the valley of «damn, that’s not even that easy!» and, hopefully, on to the hill of great insight. A book, for example, could either be in stock, currently lent, damaged or even lost. My fellow student and I were quite eager to get a good grade and, obviously, decided to work on our code in a local, Scandinavian bar. There may or may not have been any beer involved, but after a few hours of happily coding along I was suddenly confronted with the following message:

Terribly faked Java Swing Dialog.

Okay — I’ll be honest with you. There was beer involved, and this was the moment we took a step back and decided to call it a day.

But what went wrong? If I recall correctly, this error message was supposed to be shown when a librarian tried to lend a book which was already lent, but with the expected return date in the dialog. In this case though, we managed to put a book in two states at the same time: lent and lost.

While the example of a book and its possible states is still fairly simple, the mental model that frontend developers have to maintain is becoming more complex as business rules and workflows are increasingly moved to client apps.

Basic Automata Theory and … 🥁 State Machines!

In Basic Automata Theory (at my University the class was called Mathematical Basics of Computer Science) we learnt about Regular Expressions, Context-Free Grammars and — 🥁 drum rolldeterministic finite state machines. At the time I knew I would never need this again in my everyday life as a web developer. But what are they?

It [Finite-state Machine] is an abstract machine that can be in exactly one of a finite number of states at any given time.
Wikipedia

That sounds awfully similar to the irregularity we experience with our book that is both in the states lent and lost. Could it be that I was wrong, and that I actually would use state machines again after graduating?

If we visualise what different states a book can have, we end up with something similar to this:

Simple state diagram showing what states a book can have

Formally speaking, a Finite-state machine is a quintuple (𝜮, 𝑺, 𝑺₀, 𝜹, 𝑭), where:

  • 𝜮 is an input alphabet.
  • 𝑺 is a set of possible states.
  • 𝑺₀ is the initial state.
  • 𝜹 is a state-transition function 𝑺 ⨉ 𝜮 → 𝑺 (a transition from one state to another upon an input from the alphabet 𝜮).
  • 𝑭 is a set of end states.

Trying to transform the above state diagram into code might result in the following snippet:

{
"initial": "In Stock",
"states": {
"In Stock": {
on: {
"Lend": "Lent",
},
},
"Lent": {
on: {
"Return": "In Stock",
"Damage": "Damaged",
"Lose": "Lost",
},
},
"Damaged": {
on: {
"Repair": "In Stock",
},
},
"Lost": {
on: {
"Find": "In Stock",
},
},
},
}

Matching the state diagram, we have a finite number of states (𝑺In Stock, Lent, Damaged and Lost), actions that define possible inputs (𝜮Lend, Return, Damage, Lose, Repair and Find), an initial state (𝑺₀In Stock) and state-transition function definitions (𝜹Lend → Lent, etc.). With an explicit definition of possible states and transitions, it’s now mathematically impossible to be in two states at the same time.

XState

Declaring a state diagram declaratively is wonderful, but how do we transform this object into a state machine? How can we «run» the state machine and ensure that our program is deterministic, as the mathematical concept promises?

The answer is XState. XState is a fantastic JavaScript and TypeScript implementation of finite state machines by David Khourshid. With the above code block as a configuration, a state machine can be instantiated and will adhere to the given rules.

import { Machine } from 'xstate';const bookMachine = Machine({
"initial": "In Stock",
"states": {
"In Stock": {
on: {
"Lend": "Lent",
},
},
"Lent": {
on: {
"Return": "In Stock",
"Damage": "Damaged",
"Lose": "Lost",
},
},
"Damaged": {
on: {
"Repair": "In Stock",
},
},
"Lost": {
on: {
"Find": "In Stock",
},
},
}
});

After the instantiation the state machine will be in the initial state: In Stock. Sending an input from the alphabet 𝜮 will either result in a state transition or do nothing; for example if the state machine is in the initial state and receives a Lend action, the following state will be Lent. If it’s any other input, the state will remain the same.

Implementing our UI-heavy apps with state machines has helped us immensely to reduce complexity. As our applications grew (and still do!), state diagrams also facilitate the entry for new developers on these projects massively in understanding what is going on, and also get a grasp of what the applications include apart from the “obvious” features.

But obviously you want hard facts. You want examples and see real scenarios how we use state machines in apps. And that’s exactly what the next post is about — how we integrate state machines in our React apps, how we connect state transitions to our components and how we render based on what state our state machine currently is in.

A thousand thanks and credits go to David Khourshid for writing XState — an incredible library which is a charm to use. David constantly delivers updates to the code and documentation, and an awesome developer experience by supporting devtools like redux-devtools.

Make sure you read his posts for more insights.

Need an expert team to implement your advanced web application? Check out smartive’s portfolio. At smartive, we build web applications for complex use cases. We are located in Zurich, Switzerland.

--

--

Robert Vogt
smartive

He tried to look ashamed and succeeded simply in looking pleased with himself. — Neil Gaiman