Finite state machines -- Elixir and Python implementations

1   Introduction

2   Theory and concepts

An FSM (finite state machine) is composed of a set of states and a set of transitions. Each transition has (1) a from state, (2) a to (destination) state, (3) a condition or set of conditions that must be satisfied before the transition can occur, (4) actions that are performed (executed) when the transition occurs.

States -- An FSM is alway in some state and can be in only one state a any given time. Typically, each state has a name or identifier that is unique across states in a single FSM.

Actions -- One conception of an FSM has actions "attached" to transitions and performed when the transition is taken. However, there are alternatives. For example, the Python transitions library enables us to attach actions to states and to transitions and to the machine itself. The following table listing the different kinds of actions supported by Python transitions give some idea of this (see https://github.com/pytransitions/transitions#execution-order):

Callback	Current State	Comments
'machine.prepare_event'	source	executed once before individual transitions are processed
'transition.prepare'	source	executed as soon as the transition starts
'transition.conditions'	source	conditions may fail and halt the transition
'transition.unless'	source	conditions may fail and halt the transition
'machine.before_state_change'	source	default callbacks declared on model
'transition.before'	source
'state.on_exit'	source	callbacks declared on the source state
<STATE CHANGE>
'state.on_enter'	destination	callbacks declared on the destination state
'transition.after'	destination
'machine.after_state_change'	destination	default callbacks declared on model
'machine.finalize_event'	source/dest.	callbacks will be executed even if no transition took place or an exception has been raised

Graphic representation -- Any specific FSM can be viewed as a digraph (directed graph). It is (1) a set of nodes (vertices) that represent the states and (2) a set of directed edges (arrows) that connect the states and that represent the transitions. Usually there is a "start" state (node) and one or more "end" or "finish" states.

Data representation -- The states can be represented as a set or tuples or records which have the fields: state name, on-enter-actions, on-exit-actions. The transitions can be represented as a set of tuples or records which have fields such as (1) from-state, (2) conditions (tests) that must be satisfied before selecting this transition, (3) actions to be performed when this transition is performed, (4) to-state.

The process -- Although the details may vary, depending on the arrangement of actions (attached to transitions or attached to states), a given FSM performs the same sequence of step over and over:

1. Select a transition -- The source state (from-state) of the transition must match the currect state of the FSM. It may be that the transition is selected based on some (current) input, and there may be other conditions that are attached to the transition that must be satisfied in order for that transition to be selected.
2. Perform the transition -- (1) Perform any exit actions associated with the current state. (2) perform any actions associated with the selected transition. (3) Transfer to the new state: make the target (destination state, to-state) the current state of the FSM. (4) Perform any enter actions associated with the new (current) state.
3. Repeat.

3   Elixir

The source code for this example is here: code_lock.ex.

For this implementation we use the Erlang/Elixir gen_statem FSM support behavior. The documentation and the source code for Erlang/Elixir gen_statem is here:

• https://erlang.org/doc/man/gen_statem.html
• https://erlang.org/doc/design_principles/statem.html

Elixir gen_statem is actually an Erlang module/behavior. However, like most Erlang modules, using it from Elixir is quite straight forward.

The Elixir gen_statem behaviour has two callback modes:

• state_functions -- Events are handled by one callback function per state.
• handle_event_function -- Events are handled by one single callback function.

Our example uses state_functions mode. And, so we implement a separate function for each state to handle events that occur while we are in that state.

Here is a sample session that shows the use of our FSM:

iex> {:ok, pid}  = CodeLock.start('xyz')
Lock
{:ok, #PID<0.160.0>}
iex> CodeLock.button('x')
staying locked
:ok
iex> CodeLock.button('y')
staying locked
:ok
iex> CodeLock.button('z')
unlocking
:ok
Unlock

Here is some explanation of the source code for this example (code_lock.ex):

• First, notice the callback function init/1. It is called by Elixir gen_statem in response to our call to:

  :gen_statem.start_link({:local, @name}, __MODULE__, code, [])
  

  We use init/1 to create and initialize an Elixir Map containing the data that we will want to pass to each of our state functions.

• And, notice the function callback_mode:

  def callback_mode() do
    :state_functions
  end
  

  This puts us in state_functions mode (described above), which means that we will implement a separate event handler callback function for each state.

• Next look at the event callback functions: locked/3 and open/e. One of these functions are called in response to our call to gen_statem.cast/2, that is, when we generate an event. For example:

  def button(button) do
    :gen_statem.cast(@name, {:button, button})
  end
  

  Which callback is called is determined by the current state of our FSM.

• And, now look at the values returned by our state callbacks. These determine the state that the FSM will be put in (by gen_statem) after our callback is executed. For example, the following return value puts our FSM in the :open state:

  {:next_state, :open, data1, [{:state_timeout, 10000, :lock}]}
  

  And, this return value keeps us in the :locked state:

  {:next_state, :locked, data1}
  

One question I had, especially after looking at the callbacks supported by Python transitions (see the Action types table below) is how do we implement these various kinds of callbacks when using Elixir gen_statem? Part of the answer to this question requires that we understand the nature of the callbacks supported by gen_statem. These callbacks are called in response to an event. And, an event happens when we call gen_statem.cast/2. Here is the Erlang documentation on that:

cast(ServerRef :: server_ref(), Msg :: term()) -> ok

Sends an asynchronous event to the gen_statem ServerRef and returns ok immediately, ignoring if the destination node or gen_statem does not exist. The gen_statem calls the state callback with event_type() cast and event content Msg.

Another part of the answer to this question is the support for state enter callbacks:

Whether the state machine should use state enter calls or not is selected when starting the gen_statem and after code change using the return value from Module:callback_mode/0.

If Module:callback_mode/0 returns a list containing state_enter, the gen_statem engine will, at every state change, call the state callback with arguments (enter, OldState, Data) or (enter, OldState, State, Data), depending on the callback mode. This may look like an event but is really a call performed after the previous state callback returned and before any event is delivered to the new state callback. See Module:StateName/3 and Module:handle_event/4. Such a call can be repeated by returning a repeat_state or repeat_state_and_data tuple from the state callback.

If Module:callback_mode/0 does not return such a list, no state enter calls are done.

I interpret this as follows: If you want gen_statem to call one of your state callbacks after the normal event callback returns but before the callback for the destination state is called, then you should implement:

def callback_mode() do
  [:state_functions, :state_enter]
end

And, for any state that you want a callback called before that state is entered, you should implement one the following:

def StateName(:enter, old_state_name, data) do
  ...
end

def StateName(:enter, old_state_name, state_name, data) do
  ...
end

where old_state_name and state_name are atoms that correspond to the source (from) state and the destination (to) state respectively.

In general, we'd like to be able to implement behavior/action that coresponds to the following callbacks supported by Python transitions:

1. 'transition.before'
2. 'state.on_exit'
3. <STATE CHANGE>
4. 'state.on_enter'
5. 'transition.after'

If I interpret it correctly, Elixir gen_statem enables us to implement:

• transition.before and state.on_exit lumped into a single Elixir gen_statem callback -- the normal state callback.
• state.on_enter and transition.after lumped into a single Elixir gen_statem callback -- the enter state callback.

How to receive a reply from a state callback function -- Suppose we want to generate an event (possibly producing a transition) and we want to wait for a response from the callback function that handles the event. In order to do so we would generate the event with :gen_statem.call/2,3 instead of :gen_statem.cast/2. And, we would implement a callback function with this signature:

def some_state_name({:call, from}, event_content, state, data) do

Or:

def some_state_name({:call, from}, event_content, data) do

And, the state callback function, returns a response to the caller by returning an action of the form: {:reply, from, reply_data}. For example:

{:next_state, new_state, new_data, [{:reply, from, reply_data}]}

4   Python

The source code for this example is here: py_fsm01.py.

This example demonstrates the implementation of a simple FSM in Python by implementing a combination lock. The FSM stays in the locked state until the correct code (combination) is entered and the uses "tries" to open the lock.

For this implementation we use the Python transitions FSM support module. The documentation and the source code for Python transitions is here: https://github.com/pytransitions/transitions.