Implementing a finite state machine with Erlang and gen_fsm

1   Preliminaries

Note: Beginning with OTP v. 19 there is a new behavior for creating FSMs -- gen_statem. It is intended to replace gen_fsm. See: http://erlang.org/doc/man/gen_statem.html and http://erlang.org/doc/design_principles/statem.html.

By using gen_fsm we get the benefits of an OTP behavior plus some structure within which to implement our FSM (finite state machine).

A few of the benefits of using an OTP behavior:

  • Lots of code for error checking, handling soft failure, and re-start are provided for us.
  • Our FSM can exist within an Erlang OTP supervisor-worker tree, that is, within a tree in which supervisor modules provide support for their child/worker modules.

References -- There is useful information here:

In what follows we discuss an example FSM that has two states: lower and upper. This code converts a sequence (list) of characters to lower or upper case depending on the commands embedded in that sequence. You can find the complete example here: test_gen_fsm.erl

2   Set-up

Start with a skeleton

3   Procedure

First, do some planning:

  • You will want to figure out what data items you will need your FSM to carry from one FSM state to another. You will code these in the #state{} record in your skeleton.
  • You will want to list the various states in your FSM, what action (if any) each state performs, and which FSM state is transitioned to.

3.1   Step 1 -- Define the #state record

Imagine that your FSM is processing a stream of data and collection information while doing so. The #state record definition in your module might be modified to look like this:

-record(state, {count,        % count of items processed so far
                outdata       % information collected so far
                }).

3.2   Step 2 -- Define the API for your module

The API is the interface that you intend the users of your module to see. It is a set of functions that you want them to be able to call. You should:

  • List each function and its arity in the export statements near the top of your module. For example, it might look like this:

    %% API functions
    -export([start_link/1,
              stop/0,
              process/1
              ]).
    
  • Define a prototype for each function. Basically, the function header and a bit of the body to remind yourself on what to fill in later. Here are examples:

    %%--------------------------------------------------------------------
    %% @doc
    %% Creates a gen_fsm process which calls Module:init/1 to
    %% initialize. To ensure a synchronized start-up procedure, this
    %% function does not return until Module:init/1 has returned.
    %%
    %% @spec start_link() -> {ok, Pid} | ignore | {error, Error}
    %% @end
    %%--------------------------------------------------------------------
    start_link(FromPid) ->
        %gen_fsm:start_link({local, ?SERVER}, ?SERVER, [Data], []).
        gen_fsm:start_link({local, ?SERVER}, ?SERVER, [FromPid, false], []).
    start_link(FromPid, Debug) ->
        case Debug of
            debug ->
                gen_fsm:start_link({local, ?SERVER}, ?SERVER, [FromPid, true], []);
            _ ->
                gen_fsm:start_link({local, ?SERVER}, ?SERVER, [FromPid, false], [])
        end.
    
    %%--------------------------------------------------------------------
    %% @doc
    %% Process an input sequence and return a result string.
    %% Sample call:
    %%     test_gen_fsm:start_link(MyPid),
    %%     Data = [
    %%             {chr "a"},
    %%             {chr "b"},
    %%             {chr "c"},
    %%             {cmd, upper},
    %%             {chr "d"},
    %%             {chr "e"},
    %%             {chr "f"},
    %%             {cmd, lower},
    %%             {chr "g"},
    %%             {chr "h"},
    %%             {chr "i"},
    %%             'end'
    %%            ],
    %%     test_gen_fsm:process(Data),
    %%     receive
    %%         {ok, Result} ->
    %%         ...
    %%
    %% @spec process(Data) -> ok
    %% @end
    %%--------------------------------------------------------------------
    process(Data) ->
        process_items(Data).
    
    process_items([]) ->
        ok;
    process_items([Item | Rest]) ->
        gen_fsm:send_event(?SERVER, Item),
        process_items(Rest).
    

Notes:

  • The process function in our API is called by the user to feed the items in a list to our FSM. It calls gen_fsm:send_event/2 for each item in the list. Each call to gen_fsm:send_event/2 causes gen_fsm to call the function that implements the next state.

3.3   Define an init/1 callback function

Your init/3 callback will be called when you call gen_fsm:start_link. In init you can, for example, initialize state information and specify which FSM state function should be your "start" state, that is called first. For example:

%%--------------------------------------------------------------------
%% @private
%% @doc
%% Whenever a gen_fsm is started using gen_fsm:start/[3,4] or
%% gen_fsm:start_link/[3,4], this function is called by the new
%% process to initialize.
%%
%% @spec init(Args) -> {ok, StateName, State} |
%%                     {ok, StateName, State, Timeout} |
%%                     ignore |
%%                     {stop, StopReason}
%% @end
%%--------------------------------------------------------------------
init([FromPid, Debug]) ->
    State = #state{frompid=FromPid, outdata=[], debug=Debug},
    {ok, lower, State}.

Notes:

  • The list of arguments was passed in the call to gen_fsm:start_link/4.
  • In our example, we use the arguments to initialize the state information.
  • The return value is a tuple that specifies:
    1. The atom ok.
    2. An atom that specifies the name of the initial state. In our example this is lower. That is the function that will be called to handle the first event (that is, the call to gen_fsm:send_event/2.
    3. The record we have constructed containing the state information.

3.4   Define a callback function for each of your FSM states

Define a function for each of the states in your FSM. You can find a template for these functions (and its comment block) in your skeleton module. Here are examples:

%%--------------------------------------------------------------------
%% @private
%% @doc
%% There should be one instance of this function for each possible
%% state name. Whenever a gen_fsm receives an event sent using
%% gen_fsm:send_event/2, the instance of this function with the same
%% name as the current state name StateName is called to handle
%% the event. It is also called if a timeout occurs.
%%
%% @spec state_name(Event, State) ->
%%                   {next_state, NextStateName, NextState} |
%%                   {next_state, NextStateName, NextState, Timeout} |
%%                   {stop, Reason, NewState}
%% @end
%%--------------------------------------------------------------------
lower(Event, #state{frompid=FromPid, outdata=OutData, debug=Debug} = State) ->
    case Debug of
        true ->
            io:format("(lower) Event: ~p~n", [Event]);
        _ ->
            ok
    end,
    Item = Event,
    {StateName, OutData1} = case Item of
        'end' ->
            OutData2 = lists:reverse(OutData),
            FromPid ! {ok, OutData2},
            {'lower', []};
        {cmd, Cmd} ->
            case Cmd of
                lower ->
                    {lower, OutData};
                upper ->
                    {upper, OutData}
            end;
        {chr, Chr} ->
            OutData2 = [string:to_lower(Chr) | OutData],
            {lower, OutData2}
    end,
    {next_state, StateName, State#state{outdata=OutData1}}.

upper(Event, #state{frompid=FromPid, outdata=OutData, debug=Debug} = State) ->
    case Debug of
        true ->
            io:format("(upper) Event: ~p~n", [Event]);
        _ ->
            ok
    end,
    Item = Event,
    {StateName, OutData1} = case Item of
        'end' ->
            FromPid ! {ok, OutData},
            {'lower', []};
        {cmd, Cmd} ->
            case Cmd of
                lower ->
                    {lower, OutData};
                upper ->
                    {upper, OutData}
            end;
        {chr, Chr} ->
            OutData2 = [string:to_upper(Chr) | OutData],
            {upper, OutData2}
    end,
    {next_state, StateName, State#state{outdata=OutData1}}.

Notes:

  • The value of Event is whatever was passed in the gen_fsm:send_event(?SERVER, Event) call.
  • The return value should be a tuple containing:
    1. The atom next_state.
    2. An atom that is the name of the next state. The gen_fsm process will call this function when it receives the next event. In our example, it should be one of lower or upper.
    3. The (possibly updated) state information.

3.5   Implement the terminate function

You will find a skeleton for the terminate function near the bottom of the file (assuming that you are using a gen_fsm skeleton file).

The terminate function is called by gen_fsm when you call (1):

gen_fsm:stop(?SERVER),

or (2):

gen_fsm:stop(?SERVER, Reason, Timeout),

If you use the first form, the default for Reason is normal.

Remember that this function is called when the entire process is about to end. That may be different from what the user of your FSM understands as the end of a single task.

Here is an example:

%%--------------------------------------------------------------------
%% @private
%% @doc
%% This function is called by a gen_fsm when it is about to
%% terminate. It should be the opposite of Module:init/1 and do any
%% necessary cleaning up. When it returns, the gen_fsm terminates with
%% Reason. The return value is ignored.
%%
%% @spec terminate(Reason, StateName, State) -> void()
%% @end
%%--------------------------------------------------------------------
terminate(Reason, _StateName, _State) ->
    io:format("Terminated with Reason: ~p~n", [Reason]),
    ok.

3.6   Testing

In some cases, running a tests is simple enough so that you can run tests in the erl shell. In other cases you will want to implement one or more functions. Here is one that I wrote for our example FSM:

%%%===================================================================
%%% Internal functions
%%%===================================================================

test() ->
    Data = [
            {chr, "a"},
            {chr, "b"},
            {chr, "c"},
            {cmd, upper},
            {chr, "d"},
            {chr, "e"},
            {chr, "f"},
            {cmd, lower},
            {chr, "g"},
            {chr, "h"},
            {chr, "i"},
            'end'
           ],
    % test without debug
    ?MODULE:start_link(self(), nodebug),
    ?MODULE:process(Data),
    receive
        {ok, Output1} ->
            io:format("Output: ~p~n", [Output1]),
            ok
    end,
    ?MODULE:stop(),
    % test with debug
    io:format("-------------------------------------------~n"),
    ?MODULE:start_link(self(), debug),
    ?MODULE:process(Data),
    receive
        {ok, Output2} ->
            io:format("Output: ~p~n", [Output2]),
            ok
    end,
    ?MODULE:stop(),
    ok.

4   Additional notes and suggestions

4.1   rlwrap

If you are on UNIX/Linux and use the erl shell frequently and heavily, you might consider installing rlwrap. I believe that it gives you better access to command history, and in particular saves history across sessions. I use the following bash alias:

alias erlrl='rlwrap -a -c -r erl'

4.2   Vim, Vim mode, Syntastic, etc

If you are using Vim as your text editor, it has a pretty decent Erlang mode.

I'd also recommend installing Syntastic. It will do automatic checking for Erlang errors each time you write a file. That makes it more convenient to catch syntax errors, unbound variables, etc. More information is here: http://www.vim.org/scripts/script.php?script_id=2736.

links