Hangman ~ an exploration into finite state machines with XState

finite state machinesjavascript

Since the Coronavirus panademic has us all homebound (#stayhome), I thought I would take this opportunity to try out a library that had piqued my interest — XState by @DavidKPiano.

I built a game of hangman with it. For the curious, check out the code.

Why is this library interesting to me?

During the last couple of years, I have worked on single page applications of different sizes. One common theme I have found is that managing state can get complex and messy. This isn't a new revelation and has been heavily discussed within the community.

Regardless of your ecosystem (React, Angular, Vue or insert your framework of choice here), there are a myriad of options for state management. I believe this library provides a unique approach to managing state, but first we need to understand some of its concepts.

What is XState?

As per the library's docs:

XState is a library for creating, interpreting, and executing finite state machines and statecharts, as well as managing invocations of those machines as actors.

That is a lot of jargon! Let's try to simplify it.

What is a finite state machine?

A finite state machine is officially defined as a mathematical model of computation. A finite state machine is way to describe the behaviour of a system. This is a broad definition, so let's try to narrow it down.

A finite state machine has the following properties:

  • There are a finite number of states.
  • The state machine starts in an initial state.
  • The state machine can only be in one state at any point of time.
  • The state machine can have finite number of final states.

    • In a final state the state machine comes to a stop.
    • State machines can operate in a never-ending loop, where there aren't final states.
  • There are a finite number of events.

    • An event is input provided to the state machine, which can trigger a transition from the current state to the next.

Let's look at an example of a finite state machine that models a basic traffic light.

Example state machine: a simple traffic light
  • The states are red, green and amber.

    • The initial state is red
    • There are no final states in this example.
  • The events are GO, SLOW.DOWN and STOP.
  • To transition from one state to another, a valid event must be sent.

    • For example, if the state machine is in the red state. An event of type GO will trigger the transition to the green state. An event of type STOP will be ignored.

A real traffic light is far more complexed. It contains a lot more states and events.

So what?

A system (or program) can be defined by its variables. In theory, the possible states of the system are function of the different values of its variables. As an example, if a system has 3 independent variables of boolean type (true or false) then there are in 23 (8) unique states that the system can be in. Some of these states could be invalid from the perspective of the author of the system.

Traditionally preventing a system from ending up in invalid states involves checking and manipulating the variables in the possible code paths. This can be error prone. Over time most systems increase in complexity. This results in an increase of states and code paths. This makes the system more susceptible to errors.

In contrast, a state machine models the system as a set of discrete states and predefined transitions. The states replace the combinations of the variable values, except we only define valid states and transitions.

Statecharts

The original definition provided by XState contains statecharts — what are they? Statecharts are an extension of state machines. Some of the key concepts they introduce are:

  • Nested states

    • This is where a state can have it's own state machine.
    • They are often referred to as substates.
    • This allows a state machine to be organised in a hierarchical manner.
  • Actions

    • They allow behaviour to be executed when entering/exiting a state or transiting between states.
    • This allows modelling side effects as part of a state machine.
  • Guards

    • They prevent a transition unless a predefined condition is met.
    • This allows you to encode logic directly into the state machine.

These features allow state machines to be more succinct and prevent them from becoming unruly, also referred to as state explosion.


My findings on XState

XState is a robust state management library from my initial foray into using it. There is a learning curve to understanding state machines and statecharts on top of the library. The documentation is thorough and provides good examples, which helped me a lot.

Key takeaways from using XState
  • A state machine is represented as a JavaScript object.
  • States are represented as the property names (strings) of a JavaScript object.
  • For storing any extra state (XState refers to this as extended state) the library provides a property called context to store it within the state machine.

    • I prefer to only include state that will be changed as a part of the transitions in the state machine. This is to prevent the extended state from bloating. For example, I stored the state for word, lettersGuessed and guessesLeft in the context for the game.
    • An alternative to context is to keep the extra state outside of the state machine. I am against this idea because I like to keep state and the logic that changes it close together.
  • When transitioning between states, the library provides a mechanism called actions to perform side-effects.

    • This is where a large part of the application behaviour lives.
    • This is where you can mutate the state machine's extended state. For example, I decremented the guessesLeft property when a guess was unsuccessful.
  • XState provides a mechanism called guards, which allows you to define conditional state transitions.

    • This allowed me to encode core logic into the state machine. For example, I used this to determine whether to transition to the won state by verifying if all the letters in the word have been guessed.
  • Events are simple JavaScript objects. They trigger the transitions between states.

    • They must contain property called type with a string value to identify the event.
    • The event can optionally hold extra data. For example, the GUESS event holds the guessed letter.
    • The state machine will reject an event that is not valid for the current state.
    • A rejected event is logged to the developer tools in the browser but otherwise is transparent to the user.
  • XState provides a tool to visualise a state machine.

    • Visualising a state machine is helpful when modelling a system.
  • XState provides a react hook to integrate with a react application. They also have integrations for other popular front-end ecosystems.

The state machine from the hangman game:

const hangmanMachine = Machine({
    id: 'hangman',
    context: {
        guessesLeft: 10,
        lettersGuessed: buildAlphabet(),
        word: [],
        streak: 0,
    },
    initial: 'loading',
    states: {
        loading: {
            invoke: {
                src: () => fetchWords(),
                onDone: {
                    target: 'start',
                },
                onError: {
                    target: 'failure',
                },
            },
        },
        failure: {
            on: {
                RETRY: 'loading',
            },
        },
        start: {
            on: {
                '': {
                    target: 'playing',
                    actions: 'initialiseGame',
                },
            },
        },
        playing: {
            on: {
                '': [{
                        target: 'won',
                        cond: 'hasGuessedCorrectly',
                    },
                    {
                        target: 'lost',
                        cond: 'haveRunOutOfGuesses',
                    },
                ],
                GUESS: [{
                    target: 'playing',
                    actions: 'applyGuess',
                    cond: 'haveGuessesLeft',
                }, ],
            },
        },
        won: {
            entry: ['incrementStreak'],
            on: {
                RESET: {
                    target: 'start',
                },
            },
        },
        lost: {
            entry: ['resetStreak'],
            on: {
                RESET: {
                    target: 'start',
                },
            },
        },
    },
}, {
    guards: {
        hasGuessedCorrectly: ctx => ctx.word.every(letter => letter.hasBeenGuessed),
        haveRunOutOfGuesses: ctx => ctx.guessesLeft === 0,
        haveGuessesLeft: ctx => ctx.guessesLeft > 0,
    },
    actions: {
        initialiseGame: assign({
            guessesLeft: () => 10,
            lettersGuessed: () => buildAlphabet(),
            word: () => {
                const word = words[Math.floor(Math.random() * words.length)];
                return word
                    .toUpperCase()
                    .split('')
                    .map(letter => ({
                        value: letter,
                        hasBeenGuessed: false
                    }));
            },
        }),
        applyGuess: assign((ctx, event) => ({
            guessesLeft: ctx.word.some(letter => letter.value === event.data.letter) ?
                ctx.guessesLeft :
                ctx.guessesLeft - 1,
            lettersGuessed: {
                ...ctx.lettersGuessed,
                [event.data.letter]: true,
            },
            word: ctx.word.map(letter => {
                if (letter.value !== event.data.letter) {
                    return letter;
                }

                return {
                    ...letter,
                    hasBeenGuessed: true,
                };
            }),
        })),
        incrementStreak: assign(ctx => ({
            streak: ctx.streak + 1,
        })),
        resetStreak: assign(() => ({
            streak: 0,
        })),
    },
});

Conclusion

My first attempt of the game used React's built in component state — useState, which was more than adequate. There wasn't a need to involve a library such as XState but this was an exploration of the library and finite state machines.

As I added more functionality I noticed verifying the game's functionality became more tedious. I know, I know, I should add some tests at some point. I found using a state machine and also XState's visualiser helped me model the game with more confidence.

For a more complex component or application, I believe this library can be useful alongside other solutions to state management. It isn't a silver bullet for state management but it certainly will be a valuable tool in my toolbox.


Extra resources for the inqusitive