Wednesday, December 10, 2008

Functional Reactive Programming in F# (1)

Hello,

This message is the first of a series describing my exploration of Functional Reactive Programming (FRP).

Although I already had quite a bit of experience with imperative reactive programming, I discovered FRP while reading the book of Paul Hudak: "The Haskell School of Expression".

Articles about FRP have also been published by The Yale Haskell Group . Most of the contents of this message and the followings has been quite largely inspired by these sources of information.

I started my own implementation of a FRP library with 2 goals in mind:

  • To gain a better understanding about this very peculiar domain.
  • To assess F# in a real functional context.
To begin with, here is just a short reminder of what FRP is. A functional, reactive program is a program written in a functional language ( where side effects are inexistent or at least limited to a minimum) and producing results that depend on time, in a continuous manner on one hand and on discrete events on the other hand. I will first introduce a F# type called Behavior. A Behavior willl represent a quantity that vary with time in a continuous way.

Considering that time is a float, a Behavior that corresponds to a quantity of type 'a is:

#light

type Time = float

type 'a Behavior = Time -> 'a
Although this choice is correct, we rather use the next one. The very reason of this will be made clear in a following post.

type 'a Behavior = Beh of (Time -> 'a)
With this simple type, it is already easy to define some behavior.

Kind of Behavior Implementation
The constant 1

let oneB = Beh (fun _ -> 1.0)

The constant "hello world!"

let helloB = Beh (fun _ -> "Hello World!")

The time itself

let timeB = Beh (fun t -> t)

The time times 3

let time3B = Beh (fun t -> t * 3.0)

Sine of the time let sinB = Beh (fun t -> System.Math.Sin t)
Sine of the triple of the time let sin3B = Beh (fun t -> System.Math.Sin (t * 3.0))

To ease the creation of behavior, we can write some useful combinators:

constB: transforms a constant into a Behavior:

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

let constB v = let bf t = v
              in
              Beh bf



let oneB = constB 1
let helloB = constB "Hello World!"

Considering the last 3 Behavior, the situation is a bit more complex. I.e. time3B looks very much like to timeB and it even seems possible to express time3B in terms of timeB:

let time3B = let (Beh time) = timeB
            let bf = fun t -> 3.0 * (time t)
            in Beh bf

time3B can be further modified if timeB and the partial application ((*) 3.0) are moved outside of the body of time3B:

let time3B = let liftB f b = let (Beh bf) = b
                            let lbf = fun t -> f (bft)
                            in Beh lbf
            in liftB ((*) 3.0) timeB
Now, liftB is independent from the rest and can be defined as a stand alone combinator:

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

let liftB f b = let (Beh bf) = b
               let lbf = fun t -> f (bf t)
               in Beh lbf
As a result, not only time3 but also sinB and sin3B can be defined using liftB:

let time3B = liftB ((*) 3.0) timeB
let sinB = liftB System.Math.Sin timeB
let sin3B = liftB System.Math.Sin (liftB ((*) 3.0) timeB)
We see that combinators such as liftB allow us to combine Behavior and functions in order to create new Behavior. However the syntax is still a bit heavy.

The syntax can be simplified quite a lot if we look at the signature of liftB. It is a function that takes as (first) argument a function that maps a value of type 'a to a value of type 'b. liftB then returns a function that maps a value of type 'a Behavior to a value of type 'b Behavior.

liftB is a function that transforms a function defined 'in the world ' of any type (a', 'b) into a function defined in the world of Behavior.

We can then write:

let sinF = liftB System.Math.Sin
let sinB = sinF timeB

let tripleF = liftB ((*) 3.0)

let sin3B = sinF (tripleF timeB)
In the same way, combinators that lift function with many arguments can be defined.

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

let lift2B f b1 b2 = let (Beh bf1) = b1
                    let (Beh bf2) = b2
                    let nbf t = f (bf1 t) (bf2 t)
                    in Beh nbf

//val lift3B : ('a -> 'b -> 'c -> 'd) -> 'a Behavior -> 'b Behavior -> 'c Behavior -> 'd Behavior

let lift3B f b1 b2 b3 = let (Beh bf1) = b1
                       let (Beh bf2) = b2
                       let (Beh bf3) = b3
                       let nbf t = f (bf1 t) (bf2 t) (bf3 t)
                       in Beh nbf
Here are some examples of lifted functions.

// val ( .* ) : (int Behavior -> int Behavior -> int Behavior)

let (.*) = lift2B (*)

// val ( ./ ) : (int Behavior -> int Behavior -> int Behavior)

let (./) = lift2B (/)

// val mapB : ('a -> 'b) Behavior -> 'a list Behavior -> 'b list Behavior

let mapB f b = (lift2B List.map) f b
Rem: because of the (almost) ubiquity of the "Value Restriction" error, mapB must be defined as a real function, its 'f' and 'b' arguments must appear explicitly.

error FS0030: Value restriction. Type inference has inferred the signature
val mapB : (('_a -> '_b) Behavior -> '_a list Behavior -> '_b list Behavior)
Either define 'mapB' as a syntactic function, or add a type constraint to instantiate the type parameters.
Before ending this first post, here are a couple of functions that execute a Behavior, that is, invoque the time to value function held/transported by a Behavior.

// val runOne : 'a Behavior -> Time -> 'a

let runOne b t = let (Beh bf) = b
                in
                bf t

// val runList : 'a Behavior -> Time list -> 'a list

let runList b t = let (Beh bf) = b
                 in
                 List.map bf t


// val runSeq : 'a Behavior -> seq<Time> -> seq<'a>

let runSeq b t = let (Beh bf) = b
                in
                Seq.map bf t