Finite State Machines (FSMs) are a popular model of computation in a number of fields. Erlang has a behaviour for modelling FSMs that abstracts away the concurrency model and allows for the state-machine to be modelled as a sequence of pure functions that respond to events in given state with a sequence of actions and a new state. It’s straightforward to reproduce this in F#.

First we define a recursive data structure that captures a state transition:

type NextState<'s,'e> = NextState of ('s -> 'e -> NextState<'s,'e>) * 's

Here, the type variables ‘s and ‘e represent the possible states and possible events respectively. NextState is 2-tuple of a function and the current state. The function (‘s –> ‘e –> NextState<’s,’e>) takes a state and event and produces a new NextState. These functions represent the logical state of the FSM whereas the state variable represents the physical state of the FSM. For example, a traffic light may have the logical state Stop and the physical state { Red=true ; Amber=false ; Green=false }.

So far, so good. But we still need an active object / agent / actor to run the FSM for us. Here we can leverage F# mailboxes and write a generalised reactive loop that works with any sequence of functions that return a NextState<’s,’e>. The result of calling spawn is a function ‘e –> unit, that allows events to be triggered and dispatched to the FSM via the mailbox.

let spawn init = 
    MailboxProcessor.Start(fun inbox ->
        let rec loop ns =
            async {
                let! input = inbox.Receive()
                return! loop <| match ns with NextState(f,s) -> f s input
            }
        init() |> loop).Post

This is pretty much all we need at this point to model an FSM is a reasonably succinct way. As an exercise, let’s borrow from the example in the Erlang documentation:

A door with a code lock could be viewed as an FSM. Initially, the door is locked. Anytime someone presses a button, this generates an event. Depending on what buttons have been pressed before, the sequence so far may be correct, incomplete or wrong. If it is correct, the door is unlocked for 30 seconds (30000 ms). If it is incomplete, we wait for another button to be pressed. If it is is wrong, we start all over, waiting for a new button sequence.

First, let’s define the events that the door lock recognises along with its state.

type Event =
    | Key of char
    | Timeout

type State = {
    Code  : string
    SoFar : string option
}

Next, let’s write the function that determines whether the current state, which includes any digits entered so far, combined with another digit is enough to unlock the door. We can use an active pattern for this:

let (|Complete|Incomplete|Wrong|) (state,nextDigit) =
    let sofar' = 
        match state.SoFar with
        | Some digits -> String.Concat(digits, nextDigit.ToString())
        | None -> nextDigit.ToString()
    if state.Code = sofar' then
        Complete 
    elif sofar'.Length < state.Code.Length then
        Incomplete sofar'
    else
        Wrong

Finally, we can write the actual functions that move the door lock from state to state. We need a function that puts the door lock into a valid initial state and then a function for each of the valid states (locked or unlocked). Because functions are used to model the logical states, we have to use the let rec … and … syntax to declare these functions such that they can refer to each other in a mutually recursive manner. The only actions performed are those on a state change where a message is printed out.

let rec init code = 
    printfn "Initialised and locked."
    NextState (locked, { Code = code; SoFar = None })

and locked state = function
    | Key nextDigit ->
        match (state,nextDigit) with
        | Complete -> 
            printfn "Unlocked."
            NextState (unlocked, { state with SoFar = None })
        | Incomplete digits -> 
            NextState (locked, { state with SoFar = Some digits })
        | Wrong -> 
            NextState (locked, { state with SoFar = None })
    | Timeout ->
        NextState (locked, state)
        
and unlocked state = function
    | Key k ->
        NextState (unlocked, state)
    | Timeout ->
        printfn "Locked."
        NextState (locked, { state with SoFar = None })

We can run this altogether in FSI with a little test like this:

> let pid = spawn (fun() -> init "1234");;

val pid : (Event -> unit)

>
Initialised and locked.

> Key '1' |> pid;;
val it : unit = ()
> Key '2' |> pid;;
val it : unit = ()
> Key '3' |> pid;;
val it : unit = ()
> Key '4' |> pid;;
Unlocked.
val it : unit = ()
> Timeout |> pid;;
val it : unit = ()
>
Locked.

Conclusion

The model is quite a nice way to approach FSMs but there’s still a few deficiencies in this model compared to the Erlang support. There’s no support for a default handler that can process events in any state and nor is there any support for actually triggering a timeout. We’ll address these in a later post along with other more minor enhancements.