NOTE: GenFSM is now deprecated. There are various FSM libraries you might use instead. I don't have a great suggestion yet, but you might look at plain_fsm.

Hello again, and welcome to Episode 15 - OTP Part 2: Finite State Machines.

In today's episode, we're going to briefly discuss:

  • What a Finite State Machine (or FSM) is.
  • An example FSM that we'll be implementing.
  • How to implement an FSM in Elixir using OTP's GenFSM.

Let's get started.

What are Finite State Machines

A Finite State Machine is a means of modelling some computation:

  • It can be in one of a limited number of states;
  • It has an initial state;
  • It can transition from one state to another based on some event or condition.

They can be used to solve a wide range of problems, and often they make thinking about the problem more clear than it would be with other available solutions. For example, I've used FSMs in the past to help less experienced developers change a black box, scary-looking regular expression from doom into a tight, meaningful class in which the error in their logic became glaringly obvious.

Our example FSM

It's always good to have a problem domain, so we're going to build a Finite State Machine to match some input and see if it contains the string 'sips' anywhere in it. Let's see what that machine would look like:

(see FSM diagram)

This is known as an acceptor state machine. We'll consider a given machine as 'successful' if it ends up in the got_sips state, and anything else we consider unsuccessful. If it's fed the string 'sips' at any point, it falls into the got_sips state, and can't get out.

It start out in starting and proceeds if it is passed an s as input. Any other input from that state will just transition it into the starting state again. An s takes it to the got_s state.

From got_s, anything but an i will transition it back to the starting state. An i will make it proceed to the got_si state.

This repeats for p.

Finally, from got_sip, if another s is received it proceeds to the got_sips state. At that point, any other input doesn't affect the state of the machine.

Anyway, let's go forward with the FSM implementation.

Implementing an FSM using GenFSM

Now that we've got the theory and the domain for our project out of the way, let's go ahead and start implementing. Make a new project:

mix new gen_fsm_playground && cd gen_fsm_playground

Now open up a new test file, test/sips_matcher_test.exs and add the following:

defmodule SipsMatcherTest do
  use ExUnit.Case

  test "[:starting] it successfully consumes the string 's'" do
    fsm = SipsMatcher.start_link
    assert SipsMatcher.consume_s(fsm) == :got_s
  end

  test "[:starting] it successfully consumes strings other than 's'" do
    fsm = SipsMatcher.start_link
    assert SipsMatcher.consume_not_s(fsm) == :starting
  end
end

Here we're just defining the beginnings of our SipsMatcher GenFSM. We expect our public api to consist of start_link/0, consume_s/1, and consume_not_s/1 at the very least. If we were to run the tests now, we know they would fail as there's no SipsMatcher module, so let's go ahead and define that module at the top of the file.

defmodule SipsMatcher do
  use GenFSM.Behaviour

  # Public API
  def start_link do
    {:ok, fsm} = :gen_fsm.start_link(__MODULE__, [], [])
    fsm
  end

  def consume_s(fsm) do
    :gen_fsm.sync_send_event(fsm, :s)
  end

  def consume_not_s(fsm) do
    :gen_fsm.sync_send_event(fsm, :not_s)
  end
end

Now, this is a little bit to take in. First, we make ourselves a nice start_link function that hides some of the gen_fsm interface from our consumers. Next, we define a couple of functions for consuming s and not_s. Here, we're using the gen_fsm sync_send_event/2 interface. Generally, you want to use async here (just send_event/2). However, it's a bit harder to test async things, so for the sake of demonstration and testability we'll make this synchronous. You can look into the docs to find an async example. No one's really documented this synchronous-style example anywhere as far as I could find.

Anyway, this won't work yet because we aren't supporting the GenFSM expected behaviours yet. Let's see what that looks like:

  # GenFSM API
  def init(_) do
    { :ok, :starting, [] }
  end

  def starting(:s, _from, state_data) do
    { :reply, :got_s, :got_s, state_data }
  end
  def starting(:not_s, _from, state_data) do
    { :reply, :starting, :starting, state_data }
  end

Here we're defining an init/1 function, which is called when the FSM is initialized, and then we're defining two functions for handling different transitions out of the starting state. In those transitions, we're replying to the caller with the next state, then specifying the next state and passing on our (unused, really) state_data. You can find the full range of return values that GenFSM knows how to deal with in the docs for GenFSM.Behaviour, which are linked in the episode notes.

Let's go ahead and run our tests, and they should be passing.

In the interest of time, I'm only going to follow up with two more tests - one for success, and one for failure. Let's see what that looks like:

  test "it successfully consumes the string 'sips'" do
    fsm = SipsMatcher.start_link
    SipsMatcher.consume_s(fsm)
    SipsMatcher.consume_i(fsm)
    SipsMatcher.consume_p(fsm)
    assert SipsMatcher.consume_s(fsm) == :got_sips
  end

  test "it successfully consumes strings without a match" do
    fsm = SipsMatcher.start_link
    SipsMatcher.consume_s(fsm)
    SipsMatcher.consume_i(fsm)
    SipsMatcher.consume_p(fsm)
    assert SipsMatcher.consume_not_s(fsm) == :starting
  end

If you go ahead and run the tests, they fail because we don't have consume_i functions, etc. Let's define those and their corresponding state machine handling functions for the GenFSM.Behaviour:

  def consume_i(fsm) do
    :gen_fsm.sync_send_event(fsm, :i)
  end

  def consume_p(fsm) do
    :gen_fsm.sync_send_event(fsm, :p)
  end

  def got_s(:i, _from, state_data) do
    { :reply, :got_si, :got_si, state_data }
  end

  def got_si(:p, _from, state_data) do
    { :reply, :got_sip, :got_sip, state_data }
  end

  def got_sip(:s, _from, state_data) do
    { :reply, :got_sips, :got_sips, state_data }
  end
  def got_sip(:not_s, _from, state_data) do
    { :reply, :starting, :starting, state_data }
  end

If you run the tests now, they should pass. We can also add a test real quick to verify that after consuming 'sips', it can successfully consume anything else and stay in the successfully accepting state (got_sips). Let's see what that looks like:

  test "it can't fall out of the `got_sips` state" do
    fsm = SipsMatcher.start_link
    SipsMatcher.consume_s(fsm)
    SipsMatcher.consume_i(fsm)
    SipsMatcher.consume_p(fsm)
    SipsMatcher.consume_s(fsm)
    assert SipsMatcher.consume_i(fsm) == :got_sips
  end

If you run the tests, it fails because it expects a got_sips function to be defined for the GenFSM.Behaviour. Let's define that:

  def got_sips(_, _from, state_data) do
    { :reply, :got_sips, :got_sips, state_data }
  end

Go ahead and run the tests, and they'll pass.

Take Home Exercise

It would also be nice to know at what point in the input string the first occurrence of sips happened at. I'll leave that as an exercise for you, because this is already going to take longer than our ideal episode length.

If you're going to do it, I'd suggest tracking the number of characters encountered, incrementing it at each step regardless. Then you'd track the first s you ran into in an occurence field, and only update that field (to match the number_of_characters field) in the transition from starting to got_s.

Summary

In today's episode, we covered the basics of Finite State Machines, saw how to implement one with GenFSM.Behaviour as well as how to put a nicer face on it, and drove our implementation with tests. I also gave you some homework, and if you follow through with it I'd love to see what it looks like :) See you soon!

Links