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
In fact, here is a list of real life examples modeled with FSM:
- Traffic Light
- Vending Machine
- Android’s class: MediaRecorder
- Rails router: journey
- Transmission Control Protocol (TCP)
- AI algorithms: Pac-Man’s ghosts
What does a Finite State Machine look like?
A picture is worth a thousand words, maybe more on this topic.
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:
- Randomly wander the maze
- Chase Pac-Man, when he is within line of sight
- Flee Pac-Man, after Pac-Man has consumed a power pellet
- 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:
Contextclass: This class has a state reference to a
Statebase class: Declares particular methods that represent the behaviors of a particular state.
Concrete Statesclass: Implement the behaviors of a particular state.
By changing a
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
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:
- Identify the domain model
- Enumerate the valid states
- Describe the state-related events
- Specify transitions
1. Identify the domain model
Let’s go through an example and say that we want to model 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
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:
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).
Lamp example, those states are
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:
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:
to, and there
are triggered when an event is fired.
Lamp example shows us only two possbile transitions:
List every possible ending state from each valid state. At this point you should have three lists:
1. Lamp States
2. State Events
Ruby implementation using
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.
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
- 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!
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: