In my previous post about Functional Reactive Programming, we have seen how a continuous function of time could be implemented in F# (Behaviors) and how it was possible to create more complex Behaviors by combining simpler Behaviors. However, such Behaviors are in fact 'pure' functions of time, without any state. In this post, we will see how Behaviors can handle state in a functional way (without side effects). We start by considering a very simple state machine that consumes unit values () and produces a succession of boolean values: true, false, true, false... Let's start with a classic, imperative implementation:
type 'a StateMachine = unit -> 'a
let TogglingMachine =
let state = ref true
let bf evt = state := not (!state)
in (bf :bool StateMachine)
let eventList = [(); (); (); ()]
let r = List.map TogglingMachine eventList
Here, a state machine that produces results of type 'a is simply represented as a function from unit to 'a.
Here is a second example.
The next machine accepts a unit option as input value and returns a result which is defined as follows:
type 'a StateMachine = unit option -> 'a
let CountingMachine : int StateMachine =
let nbNone = ref 0
let bf evt = match evt with
|None -> nbNone := !nbNone + 1;
|Some _ -> let res = !nbNone;
nbNone := 0;
let eventList = [None; None; Some(); None; Some(); Some(); None]
let r = List.map CountingMachine eventList
In both examples above, we see that the machine needs to retain some state between two invocations and it does it with the help of some side effects (ref 0 and ref true).
There are several solutions to create state machines without side effects. The general idea is to design a machine that externalizes its state. In practice, that means:
Let's illustrate this with the previous example (the CountingMachine above).
First, we have to modify the type representing the machine. It is now a function that takes 2 arguments. The first one is the previous state of the machine (the state before the call) and the second is the usual unit option value. The state is simply the current count of None values.
This function returns a pair made of the count of None as explained above and the new state of the machine after the call.
type StateMachine = int -> unit option -> (int * int)
let CountingMachine : StateMachine =
let bf previousCount evt =
match evt with
|None -> (-1, previousCount+1)
|Some _ -> (previousCount, 0)
It is now the responsibility of the caller to make sure that the right state is passed to the Machine. For this, we can define a runList function which runs the machine against a list of inputs.
let rec runList previousCount machine events =
match events with
| -> 
|event::t -> let (res, nextCount) = machine previousCount event
nextRes :: runList nextCount machine t
let r = runList 0 CountingMachine eventList
We see clearly the drawbacks of such a solution. The runList function must be aware of two things:
Of course, the type for the machine presented above may be made generic:
type StateMachine<'a, 'state> = 'state -> unit option -> ('a * 'state)
Last solution, based on residual state machines.
This solution is based on a simple fact. Since a State Machine is basically a function of one argument, let's imagine that this function returns both its expected value and new State Machine. This a new State Machine acts a bit like the state in the previous example.
The type of such a machine is:
type 'a StateMachine = SM of (unit option -> ('a * 'a StateMachine))
We can already define some simple state machines:
A machine that always returns true. Two implementation are possible, depending on which definition is recursive.
let AlwaysTrueMachine = let rec bf evt = (true, SM bf)
let rec AlwaysTrueMachine = let bf evt = (true, AlwaysTrueMachine)
The Toggling Machine in the beginning of this post becomes.
let TogglingMachine = let rec bf previous evt = (previous, SM (bf (not previous)))
SM (bf true)
To be able to run these machines, we must again define a runList function:
let rec runList (SM bf) events =
match events with
| -> 
|h::t -> let (r, nb) = bf h
r :: runList nb t
let r = runList TogglingMachine eventList
This runList function is somewhat similar to the one already defined above but with 2 advantages:
So we come to the end of this post. As a last note, I must admit that there could be another way to model state machines, which is based on sequences but I have not explored this direction yet.
In a next post, I will make the connection between state machines and Behaviors.