When writing code, our classes often go through a series of transformations. What starts out as a simple class will grow as behavior is added. And if you didn’t take the necessary precautions, your code will become difficult to understand and maintain. Too often, the state of an object is kept by creating multiple boolean attributes and deciding how to behave based on the values. This can become cumbersome and difficult to maintain when the complexity of your class starts to increase.

This is a common problem on most projects, and it is wise to model it with a Finite State Machine (a.k.a FSM). In fact, there is a design pattern called State that address this very well, so you can find hundreds of gems implementing this pattern.

A great description of the problem can be found on SourceMaking.org:

A monolithic object’s behavior is a function of its state, and it must change its behavior at run-time depending on that state. Or, an application is characterized by large and numerous case statements that vector flow of control based on the state of the application.

What is a Finite State Machine?

Finite state machines are an incredibly useful tool for modeling objects that change their behavior based on the state they happen to be in. As I mentioned, this is a situation that happens in a lot of projects, so if you hadn’t already heard about FSM, I strongly recommend you check out Basics of Automata Theory which is a great starting point.

That being said, here’s a quick informal definition anyway:

A finite state machine is a mathematical abstraction used to design algorithms. The machine is in only one state at a time. It can change from one state to another when initiated by a triggering event or condition; this is called a transition. A particular FSM is defined by a list of its states, and the triggering condition for each transition.

In practice, state machines are often used for:

  • Design purposes
  • Natural language parsers
  • String parsing
  • Communication protocols
  • Algorithms
  • etc

In fact, here is a list of real life examples modeled with FSM:

What does a Finite State Machine look like?

A picture is worth a thousand words, maybe more on this topic.

Pac-Man's ghosts FSM

The Pac-Man’s ghosts FSM caught my attention.

It is so simple to read and understand the ghosts behavior on Pac-Man’s game that anyone who can speak English can understand it, no programming skills required!

The ghosts in Pac-Man have four behaviors:

  1. Randomly wander the maze
  2. Chase Pac-Man, when he is within line of sight
  3. Flee Pac-Man, after Pac-Man has consumed a power pellet
  4. Return to the central base to regenerate

These four behaviors correspond directly to a four-state FSM. Transitions are dictated by the situation in the game. For instance, a ghost FSM in state 2 (Chase Pac-Man) will transition to state 3 (Flee) when Pac-Man consumes a power pellet.

Designing a State Machine with State pattern

The state pattern is a behavioral object design pattern. The idea is to change an object’s behavior depending on its state. In the state pattern, we have the following classes:

  • Context class: This class has a state reference to a Concrete State instance.

  • State base class: Declares particular methods that represent the behaviors of a particular state.

  • Concrete States class: Implement the behaviors of a particular state.

By changing a Context’s Concrete State, we change its behavior. This is an elegant solution because it encapsulates the set of behaviors that are specific to a certain state.

Some benefits using this design pattern are:

  • Avoiding inconsistent states
  • Putting all associated behavior together in one state object
  • Removes monolithic if or case statements

Summarizing: The state design pattern allows for full encapsulation of an unlimited number of states on a context for easy maintenance and flexibility.

Because this is a common, repeatable problem that engineers find themselves encountering I have put together a step-by-step process for architecting your own finite state machine. There are four simple steps:

  1. Identify the domain model
  2. Enumerate the valid states
  3. Describe the state-related events
  4. Specify transitions

1. Identify the domain model

Let’s go through an example and say that we want to model a Lamp. A Lamp have many attributes, like brand, price, voltage, watts, etc but for this example I want to use the state of a Lamp, the simple on/off I don’t care about other possible states like broken for this example. It is very important to identify the real object that owns a state machine or later you will find your code hard to maintain and understand and may end up refactoring.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Lamp
  attr_accessor :state, :brand, :voltage

  def turn_on
    fail 'It is already on' if state == :on

    state = :on
  end

  def turn_off
    fail 'It is already off' if state == :off

    state = :off
  end
end

2. Enumerate the valid states

Keep in mind that the purpose of State pattern is to “represent the state of an object”. In our Lamp example, we would create two concrete state classes: OnLampState, OffLampState.

State classes will only model valid states of the lamp, removing the problem when there is one combination of values that does not correspond to a valid state for your lamp (generally, when the object uses multiple booleans to represent a state).

In the Lamp example, those states are

  • :on
  • :off

So make a list with all the states you want to identify, or expect different behavior. As simple as that.

3. Describe the events which change or involve the state

Every model with a state has a method where it changes a value, or behaves differently depending on the state. Those methods are potential events.

In our example, I evaluated these to be:

  • turn_on
  • turn_off

In this step, you have to list the events that will trigger a state transition.

4. Specify the transitions between states

Finally, we have to write down every single branch of the state machine. When I say branch I mean the process to fire an event from a state A and move to the state B.

The transitions are composed by two states: from and to, and there are triggered when an event is fired.

The Lamp example shows us only two possbile transitions:

  • from :off to :on
  • from :on to :off

List every possible ending state from each valid state. At this point you should have three lists:

1. Lamp States

  • :on
  • :off

2. State Events

  • turn_on
  • turn_of

3. Transitions

  • from :off to :on
  • from :on to :off

Ruby implementation using aquam

You already been through the hardest part: you were thinking about the states, every possible transition, you argued with your teammates, you did some sketches (if you didn’t, you should try) until you reached the solution. Your Finite State Machine is ready, now you only have to code it!

You probably are anxious to test your FSM, so I will be short.

Introducing aquam

aquam simplifies the design by introducing the various parts of a real state machine, including states, events and it meets our criteria for this problem

  • Full object oriented
  • Framework-agnostic
  • No dependencies
  • Allows the developer to make important design decisions

I’m gonna use this gem that we developed for a past project because it suits perfectly with our criteria.

Write your FSM guidelines

Taking the three lists you build in the design step, use aquam DSL to write it down. It will look like

1
2
3
4
5
6
7
8
9
10
11
12

class LampStateMachine < Aquam::Machine
  state :on, OnLampState
  state :off, OffLampState

  event :turn_on do
    transition from: :off, to: :on
  end

  event :turn_off do
    transition from: :on, to: :off
  end
end

Represent the different states

The State pattern does not specify where the state transitions will be defined.

There are two choices: the context object, or each individual State class. The advantage of the latter option is ease of adding new State classes. The disadvantage is each State class has knowledge of its siblings, which introduces dependencies between them.

Every bit of behavior that is state-dependent should become a method in the concrete state classes. Also, aquam transforms every event defined into a method in the concrete state class.

Example Option 1 - Context Object Class

1
2
3
4
5
6
7
8
9
10
11
12
13

class Lamp
  def turn_off
    current_state.turn_off

    self.state = :off
  end

  def turn_on
    current_state.turn_on

    self.state = :on
  end
end

Example Option 2 - State Classes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class OnLampState < Aquam::State
  use_machine LampStateMachine

  def turn_off
    # Do something

    @object.state = :off
  end
end

class OffLampState < Aquam::State
  use_machine LampStateMachine

  def turn_on
    # Do something

    @object.state = :on
  end
end

Delegate to the state

In order to allow an object to alter its behavior when its internal state changes we need to delegate the events to the current state class. The object will appear to change its class.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Lamp
  attr_accessor :state, :brand, :voltage

  def turn_on
    state_machine.current_state.turn_on
  end

  def turn_off
    state_machine.current_state.turn_off
  end

  def state_machine
    @state_machine ||= LampStateMachine.new self
  end

  def state
    @state ||= :off
  end
end

NOTE: Remember to always set the initial state

Play with your Lamp

And that’s it! You can play with your lamp, using a real state machine. Try to turn it on when it is already on, add a few more states and see how it changes it behavior!

Good reading

If you enjoyed this article, you should know that Finite State Machines are studied in the more general field of Automata theory, a theoretical branch of computer science.

Here are some links that you might want to read: