Wednesday, March 18, 2009

Functional Reactive Programming in F# (3)

In the previous post, I showed how it was possible with the so-called residual state machine to implement a pure function that maintains a internal state. In this post I will apply this technique to the behaviors discussed in my first post on functional reactive programming. First, let's recall what a Behavior is:


type Time = float

type 'a Beh  = Beh of (Time -> 'a)
To add the possibility to manage state, such a Behavior may be simply transformed into the new type below:

type Time = float

type 'a Beh  = Beh of (Time -> ('a * 'a Beh))

Its associated runList evaluator is an exact copy of the one defined for a state machine.
// val runList : 'a Beh -> Time list -> 'a list

let rec runList (Beh bf) times =
   match times with
   |[] -> []
   |h::t -> let (r, nb) = bf h
            r :: runList nb t
Simple Behaviors, that are independent of any state, are then easy to implement:
let rec doubleB =
    let bf t = (2.0 * t, doubleB)
    Beh bf

let rec twoB =
   let bf t = (2, twoB)
   Beh bf

let rec timeB = Beh (fun t -> (t, timeB))
The following function is constB, similar to constB described in the first post. It takes a value and transforms it into a Behavior that always returns that value, whatever the time.

Two equivalent implementations are possible.

The first possibility makes constB explicitly recursive:

// val constB : 'a -> 'a Beh

let rec constB v =
   let bf t = (v, constB v)
   Beh bf

The second creates a non recursive constB and requests the inner bf function to be recursive.
let constB v =
   let rec bf t = (v, Beh bf)
   Beh bf
As far as my experience tells me, the choice between these two possibilities is left free to the developer.

The lifting functions for our new Behaviors are also quite similar to the old ones.

// val liftB : ('a -> 'b) -> 'a Beh -> 'b Beh

let rec liftB f (Beh bf1)=
    let bf t = let (r1, nb1) = bf1 t
               (f r1, liftB f nb1)
    Beh bf

// val lift2B : ('a -> 'b -> 'c) -> 'a Beh -> 'b Beh -> 'c Beh

let rec lift2B f (Beh bf1) (Beh bf2)=
    let bf t = let (r1, nb1) = bf1 t
               let (r2, nb2) = bf2 t
               (f r1 r2, lift2B f nb1 nb2)
    Beh bf

The next function is a good example of how function may be created by simple composition of other functions. The function makeB takes a function from a time to some type 'a and returns the (state independent) Behavior that implements this function.
//val makeB : (Time -> 'a) -> 'a Beh

let makeB f = (liftB f) timeB

As a comparison, here is the same makeB function implemented the usual way.
let makeB f =
   let rec bf t = (f t, Beh bf)
   Beh bf
Now, what comes is an example of Behavior that manages state. Suppose that we have a function that is passed a state in addition to a time variable, makeWithStateB is a combinator that transform that function into a Behavior.
// val makeWithStateB : ('state -> Time -> 'a * 'state) -> 'state -> 'a Beh

let rec makeWithStateB f (previousState:'state) =
 let bf t = let (a1, nextState) = f previousState t  // call f with the previous state
            (a1, makeWithStateB f nextState)         // pass the next state, returned by f to the next Behavior
 in Beh bf
Here is a simple example that returns the delta between the current time and a previous base time. Everytime the delta reaches 10, the delta is reset to zero and the current time becomes the new base time.
let f t0 t = if (t-t0 < 10.0)
            then (t-t0, t0)
            else (0.0, t)

let times = Seq.to_list (seq { for i in 0 .. 100 -> float i })

let r = runList fB times