State Machine Construction Kit for F#

NOTE: There is a lot of code in this article, as it is repeated and iteratively added. The final version is just 28 lines near the end, but I think you should read the whole thing anyway.

Once upon the time I needed to implement state machine. To not reinvent the wheel I reviewed what’s available: Windows Workflow Foundation, Appccelerate.StateMachine, bbv.Common.StateMachine, Stateless, SimpleStateMachine, Solid.State, and StateMachineToolkit. Windows Workflow Foundation was just scary, apart from the fact that State Machine is not available in .NET 4.0. It didn’t look lightweight either.

None of the others satisfied my requirements either:

• Events should be able to carry data - for example, hypothetical event KeyPressed should also carry information which key has been actually pressed;
• States should be able hold data - for example, state collecting key presses (let’s call it EnteringText) should be able to hold a list of keys pressed so far;
• Guard statements should have access to both current state and event - for example, KeyPressed event may cause transition to different state depending which key has been pressed;
• Transition rules should be implemented outside states - states should be more like POCO/DTO object with no logic in them;

I’ve implemented it in C#, and I’m relatively happy with it, and you can find it on GitHub. As an exercise I implemented it for Kotlin as well, also on GitHub. Then I had to implement one for work, in Java this time.

I decided that maybe it’s time to do something for F# community, and implement nice functional State Machine Construction Kit. I dropped the “transition rules should be implemented outside states” requirement as it was adding some messy reflection code.

To make it more F#y and functional I started with fundamental question: what is the state? What is its essence?
It is actually a function which will take an event and produce new state:

type State<'Event> = 'Event -> State<'Event>

This would actually not compile, because it would create infinite recursive type alias, but:

type State<'Event> = | State of ('Event -> State)

will do just fine.
Actually it would be a little but nicer if it would be possible to return State option to handle termination:

type State<'Event> = | State of ('Event -> State option)

…but, I decided to make it rather with explicit state case:

type State<'Event> =
    | Next of ('Event -> State)
    | Stop

So we have transitive state (Next for State (Some state)) and terminal state (Stop for State None).
Please note, that we could add more cases, for example:

type State<'Event, 'Result> =
    | Next of ('Event -> State)
    | Stop of 'Result
    | Fail of Exception

but this would introduce some complexity which I don’t want in this example, but you are more than welcome to introduce yourself.
So, let’s go back to my State Machine Construction Kit. We already have a state but we also need a function to fire events and transition from state to state, let’s call it feed, we feed a state with event. It’s actually almost done as state is a transition function:

let feed state event =
    match state with
    | Stop -> failwith "Terminal state reached"
    | Next handler -> event |> handler

For this example I will use some trivial state machine handling opening and closing doors:

So we have Open and Close events:

type Event = | Open | Close

…and have two states: opened and closed. The states themselves are functions which take events and produce new states:

let rec opened event =
    match event with
    | Open -> Next opened
    | Close -> printfn "closing"; Next closed
and closed event =
    match event with
    | Open -> printfn "opening"; Next opened
    | Close -> Next closed

Let’s define an initial state, a let’s say it is closed:

let mutable state = Next closed

Now we can send Open event to it and store new state:

state <- Open |> feed state

Ta-dah! Done.

Please note, that to handle sequence of events easily, the only thing you need to is to use fold:

events |> Seq.fold feed state

For my personal use I actually created a class to encapsulate mutability. It is, of course, still there but hidden:

type StateMachine<'Event>(initial: State<'Event>) =
    let mutable current = initial
    member this.Feed event =
        current <- feed current event
    member this.IsStopped
        with get () = match current with | Stop -> true | _ -> false

What about context (data shared by all states) and state’s state (state internal data) you might ask? By the power of closures and currying there is nothing special to implement. For example, let’s imagine a door state machine which makes sounds (with injected sound emitter) and can be locked or unlocked when closed (state’s internal data):

type Event = | Open | Close | Lock | Unlock

let configureDoor sound =
    let rec opened event =
        match event with
        | Close -> sound "bang"; Next (closed false)
        | Lock -> sound "clack"; Next opened
        | _ -> Next opened
    and closed locked event =
        match event with
        | Open when locked -> sound "dumdum"; Next (closed locked)
        | Open -> sound "squeak"; Next opened
        | Lock -> sound "click"; Next (closed true)
        | Unlock -> sound "clack"; Next (closed false)
        | _ -> Next (closed locked)
    Next (closed false)

Note, there is a sound function passed and all states have access to it and this is your context. Additionally closed state has a locked ‘property’ and behaves differently depending on the value is this property (cannot be opened when closed, and needs to be unlocked first). You can call it substate if you want.

What if I don’t like mutable variables and I want my state machine to be an actor / agent? Let’s just wrap it:

let createAgent initial =
    MailboxProcessor.Start (fun inbox ->
        let rec loop state = async {
            let! event = inbox.Receive ()
            match event |> feed state with
            | Stop -> ()
            | Next _ as next -> return! loop next
        }
        loop initial
    )

So, the full module, already a little bit bloated with helper functions, is:

module StateMachine =
    type State<'Event> =
        | Next of ('Event -> State<'Event>)
        | Stop

    let feed state event =
        match state with
        | Stop -> failwith "Terminal state reached"
        | Next handler -> event |> handler

    type StateMachine<'event>(initial: State<'event>) =
        let mutable current = initial
        member this.Fire event = current <- feed current event
        member this.IsStopped
            with get () = match current with | Stop -> true | _ -> false

    let createMachine initial = StateMachine(initial)

    let createAgent initial =
        MailboxProcessor.Start (fun inbox ->
            let rec loop state = async {
                let! event = inbox.Receive ()
                match event |> feed state with
                | Stop -> ()
                | Next _ as next -> return! loop next
            }
            loop initial
        )

I can run this now with:

let agent = printfn "%s" |> configureDoor |> StateMachine.createAgent
agent.Post Lock // click
agent.Post Unlock // clack
agent.Post Open // squeak
agent.Post Close // bang

I have to admit. I failed. There is no such thing as State Machine Construction Kit for F#, at least not the one worth releasing, in short, there is just a function:

type StateMachineConstructionKit = 'State -> 'Event -> 'State

but I just can’t put it on GitHub. Maybe gist?