Finite State Machines

GenFSM

What a Finite State Machine (FSM) is
An example FSM that we'll be implementing
How to implement an FSM using GenFSM

Finite State Machines

What they are

defmodule Something do
  use GenFSM.Behaviour
end

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.

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

It can be in one of a limited number of states; [advance]
It has an initial state; [advance]
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.

I've also used them to model a financial transaction in a customer system, where there were multiple external systems that had to be updated in response to a charge being created in our system, and it had to happen in very specifically ordered ways, with logic that could handle various potential error cases.

Finite State Machines

Our example FSM

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: [advance]

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 starts 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.

LIVE LIVE LIVE LIVE LIVE

CODING CODING CODING

ZOMG ZOMG ZOMG ZOMG

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.

LIVE CODING ZOMG

Example FSM

Here...

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.

LIVE CODING ZOMG

Example FSM

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.

The return values for these functions are replies - they consist of a tuple containing the atom :reply, the reply to send, the new state that the FSM should be in next, and the state data (which we aren't really making use of here)

Also, it's worth noting that the state machine responds to inbound messages by invoking a function with the same name as the state machine's current state - this is how we're describing the 'arrows out of the state' in the diagram.

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:

LIVE CODING ZOMG

Example FSM

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:

LIVE CODING ZOMG

Example FSM

Hey...

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:

LIVE CODING ZOMG

Example FSM

Hey...

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.

Finite State Machines

Summary

Example FSM

It would also be nice to know at what point in the input string the first occurrence of sips happened. I'll leave that as an exercise for you, but the bit about state_data that we aren't fiddling with should be highly interesting :)

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.

So pretty quickly, 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 :)