Mixing monadic and direct-style code with delimited continuations

The Lwt library is a really nice way to write concurrent programs. A big downside, however, is that you can’t use direct-style libraries with it. Suppose we’re writing an XMPP server, and we want to parse XML as it arrives over a network connection, using Daniel Bünzli’s nice xmlm library. Xmlm can read from a string, or from a Pervasives.in_channel, or you can give it a function of type (unit -> int) to return the next character of input. But there is no way to have it read from an Lwt thread; that is, we can’t give it a function of type (unit -> int Lwt.t), since it doesn’t know what do with an Lwt.t. To keep track of the parser state at the point the input blocks, the whole library would need to be rewritten in Lwt style (i.e. monadic style).

Now, Lwt does provide the Lwt_preemptive module, which gives you a way to spin off a preemptive thread (implemented as an ordinary OCaml thread) and wait for its result in the usual Lwt way with bind. This is useful, but has two drawbacks: preemptive threads are preemptive, so you’re back to traditional locking if you want to operate on shared data; and preemptive threads are threads, so they are much heavier than Lwt threads, and (continuing the XMPP hypothetical) it may not be feasible to use one per open connection.

Fibers

What we would really like is to be able spin off a cooperative, direct-style thread. The thread needs a way to block on Lwt threads, but when it blocks we need to be able to schedule another Lwt thread. As a cooperative thread it of course has exclusive access to the process state while it is running. A cooperative, direct-style thread is sometimes called a coroutine (although to me that word connotes a particular style of inter-thread communication as well, where values are yielded between coroutines), or a fiber.

Here’s an API for mixing Lwt threads with fibers:

  val start : (unit -> 'a) -> 'a Lwt.t 
  val await : 'a Lwt.t -> 'a 

The start function spins off a fiber, returning an Lwt thread which is woken with the result of the fiber once it completes. The await function (which may be called only from within a fiber) blocks on the result of an Lwt thread, allowing another Lwt thread to be scheduled while it is waiting.

With this API we could implement our XMPP server by calling xmlm from within a fiber, and passing it a function that awaits the next character available on the network connection. But how do we implement it?

Delimited continuations

Oleg Kiselyov’s recent announcement of a native-code version of his Delimcc library for delimited continuations in OCaml reminded me of two things:

1. I should find out what delimited continuations are.
2. They sound useful for implementing fibers.

The paper describing the library, Delimited Control in OCaml, Abstractly and Concretely, has a pretty good overview of delimited continuations, and section 2 of A Monadic Framework for Delimited Continuations is helpful too.

The core API is small:

  type 'a prompt 
  type ('a,'b) subcont 
  
  val new_prompt   : unit -> 'a prompt 
  
  val push_prompt  : 'a prompt -> (unit -> 'a) -> 'a 
  val take_subcont : 
    'b prompt -> (('a,'b) subcont -> unit -> 'b) -> 'a 
  val push_subcont : ('a,'b) subcont -> (unit -> 'a) -> 'b 

I find it easiest to think about these functions as operations on the stack. A prompt is an identifier used to mark a point on the stack (the stack can be marked more than once with the same prompt). The function new_prompt makes a new prompt which is not equal to any other prompt.

The call push_prompt p f marks the stack with p then runs f, so the stack, growing to the right, looks like

 
  ABCDpEFGH

where ABCD are stack frames in the continuation of the call to push_prompt, and EFGH are frames created while running f. If f returns normally (that is, without calling take_subcont) then its return value is returned by push_prompt, and we are back to the original stack ABCD.

If take_subcont p g is called while running f, the stack fragment EFGH is packaged up as an ('a,'b) subcont and passed to g. You can think of an ('a,'b) subcont as a function of type 'a -> 'b, where 'a is the return type of the call to take_subcont and 'b is the return type of the call to push_prompt. Take_subcont removes the fragment pEFGH from the stack, and there are some new frames IJKL from running g, so we have

 
  ABCDIJKL

Now g can make use of the passed-in subcont using push_subcont. (Thinking of a subcont as a function, push_subcont is just a weird function application operator, which takes the argument as a thunk). Then the stack becomes

 
  ABCDIJKLEFGH

Of course g can call the subcont as many times as you like.

A common pattern is to re-mark the stack with push_prompt before calling push_subcont (so take_subcont may be called again). There is an optimized version of this combination called push_delim_subcont, which produces the stack

 
  ABCDIJKLpEFGH

The idea that a subcont is a kind of function is realized by shift0, which is like take_subcont except that instead of passing a subcont to g it passes an ordinary function. The passed function just wraps a call to push_delim_subcont. (It is push_delim_subcont rather than push_subcont for historical reasons I think—see the Monadic Framework paper for a comparison of various delimited continuation primitives.)

Implementing fibers

To implement fibers, we want start f to mark the stack, then run f; and await t to unwind the stack back to the mark, wait for t to complete, then restore the stack. Here is start:

  let active_prompt = ref None 
  
  let start f = 
    let t, u = Lwt.wait () in 
    let p = Delimcc.new_prompt () in 
    active_prompt := Some p; 
  
    Delimcc.push_prompt p begin fun () -> 
      let r = 
        try Lwt.Return (f ()) 
        with e -> Lwt.Fail e in 
      active_prompt := None; 
      match r with 
        | Lwt.Return v -> Lwt.wakeup u v 
        | Lwt.Fail e -> Lwt.wakeup_exn u e 
        | Lwt.Sleep -> assert false 
    end; 
    t 

We make a sleeping Lwt thread, and store a new prompt in a global (this is OK because we won’t yield control to another Lwt thread before using it; of course this is not safe with OCaml threads). Then we mark the stack with push_prompt and run the fiber. (The let r = ... match r with ... is to avoid calling Lwt.wakeup{,_exn} in the scope of the try; we use Lwt.state as a handy type to store either a result or an exception.) If the fiber completes without calling await then all we do is wake up the Lwt thread with the returned value or exception.

Here is await:

  let await t = 
    let p = 
      match !active_prompt with 
        | None -> failwith "await called outside start" 
        | Some p -> p in 
    active_prompt := None; 
 
    match Lwt.poll t with 
      | Some v -> v 
      | None -> 
          Delimcc.shift0 p begin fun k -> 
            let ready _ = 
              active_prompt := Some p; 
              k (); 
              Lwt.return () in 
            ignore (Lwt.try_bind (fun () -> t) ready ready) 
          end; 
          match Lwt.poll t with 
            | Some v -> v 
            | None -> assert false 

We first check to be sure that we are in the scope of start, and that t isn’t already completed (in which case we just return its result). If we actually need to wait for t, we call shift0, which capture the stack fragment back to the push_prompt call in start (this continuation includes the subsequent match Lwt.poll t and everything after the call to await), then try_bind so we can restore the stack fragment when t completes (whether by success or failure). When t completes, the ready function restores the global active_prompt, in case the fiber calls await again, then restores the stack by calling k (recall that this also re-marks the stack with p, which is needed if the fiber calls await again).

It’s pretty difficult to follow what’s going on here, so let’s try it with stacks. After calling start we have

 
  ABCDpEFGH

where ABCD is the continuation of push_prompt in start (just the return of t) and EFGH are frames created by the thunk passed to start. Now, a call to await (on an uncompleted thread) calls shift0, which packs up EFGH as k and unwinds the stack to p. The function passed to shift0 stores k in ready but doesn’t call it, and control returns to start (since the stack has been unwound).

The program continues normally until t completes. Now control is in Lwt.run_waiters running threads that were waiting on t; one of them is our ready function. When it is called, the stack is re-marked and EFGH is restored, so we have

 
  QRSTpEFGH

where QRST is wherever we happen to be in the main program, ending in Lwt.run_waiters. Now, EFGH ends with the second call to match Lwt.poll in await, which returns the value of t and continues the thunk passed to start. The stack is now marked with p inside Lwt.run_waiters, so when await is called again control returns there.

Events vs. threads

We have seen that we can use fibers to write Lwt threads in direct style. Should we abandon Lwt’s monadic style entirely, and use Lwt only for its event handling?

First, how does each style perform? Every time a fiber blocks and resumes, we have to copy, unwind, and restore its entire stack. With Lwt threads, the “stack” is a bunch of linked closures in the heap, so we don’t need to do anything to block or resume. On the other hand, building and garbage-collecting the closures is more expensive than pushing and popping the stack. We can imagine that which style performs better depends on the thread: if it blocks infrequently enough, the amortized cost of copying and restoring the stack might be lower than the cost of building and garbage-collecting the closures. (We can also imagine that a different implementation of delimited continuations might change this tradeoff.)

Second, how does the code look? The paper Cooperative Task Management without Manual Stack Management considers this question in the context of the “events vs. threads” debate. Many of its points lose their force when translated to OCaml and Lwt—closures, the >>= operator, and Lwt’s syntax extension go a long way toward making Lwt code look like direct style—but some are still germane. In favor of fibers is that existing direct-style code need not be rewritten to work with Lwt (what motivated us in the first place). In favor of monadic style is that the type of a function reflects the possibility that it might block, yield control to another thread, and disturb state invariants.

Direct-style FRP

We could apply this idea, of replacing monadic style with direct style using delimited continuations, to other monads—in particular to the froc library for functional reactive programming. (The Scala.React FRP library also uses delimited continuations to implement direct style; see Deprecating the Observer Pattern for details.)

Here’s the API:

  val direct : (unit -> 'a) -> 'a Froc.behavior 
  val read : 'a Froc.behavior -> 'a 

Not surprisingly, it’s just the same as for Lwt, but with a different monad and different names (I don’t know if direct is quite right but it is better than start). There is already a function Froc.sample with the same type as read, but it has a different meaning: sample takes a snapshot of a behavior but creates no dependency on it.

The implementation is very similar as well:

  let active_prompt = ref None 
  
  let direct f = 
    let t, u = Froc_ddg.make_changeable () in 
    let p = Delimcc.new_prompt () in 
    active_prompt := Some p; 
  
    Delimcc.push_prompt p begin fun () -> 
      let r = 
        try Froc_ddg.Value (f ()) 
        with e -> Froc_ddg.Fail e in 
      active_prompt := None; 
      Froc_ddg.write_result u r 
    end; 
    (Obj.magic t : _ Froc.behavior) 

This is essentially the same code as start, modulo the change of monad. However, some of the functions we need aren’t exported from Froc, so we need to use the underlying Froc_ddg module and magic the result at the end. Froc_ddg.make_changeable is the equivalent of Lwt.wait: it returns an “uninitialized” monadic value along with a writer for that value. We use Froc_ddg.result instead of Lwt.state to store a value or exception, and Froc_ddg.write_result instead of the pattern match and Lwt.wakeup{,_exn}.

  
  let read t = 
    let p = 
      match !active_prompt with 
        | None -> failwith "read called outside direct" 
        | Some p -> p in 
    active_prompt := None; 
  
    Delimcc.shift0 p begin fun k -> 
      Froc.notify_result_b t begin fun _ -> 
        active_prompt := Some p; 
        k () 
      end 
    end; 
    Froc.sample t 

And this is essentially the same code as await. A Froc.behavior always has a value, so we don’t poll it as we did with Lwt.t, but go straight to shift0. We have Froc.try_bind but it’s a little more compact to use use notify_result_b, which passes a result.

Monadic reflection

The similarity between these implementations suggests that we could use the same code to get a direct style version of any monad; we only need a way to create an uninitialized monadic value, then set it. The call to Lwt.poll in await is an optimization which we would have to forgo. (In both these examples we have a monad with failure, and try_bind, but we could do without it.)

A little googling turns up Andrzej Filinski’s paper Representing Monads, which reaches the same conclusion, with a lot more rigor. In that work start/direct are called reify, and await/read are called reflect. Reflect is close to the implementations above, but in reify the paper marks the stack inside a function passed to bind rather than creating an uninitialized monadic value and later setting it.

This makes sense—inside bind an uninitialized monadic value is created, then set from the result of the function passed to bind. So we are partially duplicating bind in the code above. If we mark the stack in the right place we should be able to use bind directly. It is hard to see how to make the details work out, however, since Lwt.bind and Froc.bind each have some cases where uninitialized values are not created.

(You can find the complete code for Lwt fibers here and direct-style froc here.)

(revised 10/22)

How froc works

I am happy to announce the release of version 0.2 of the froc library for functional reactive programming in OCaml. There are a number of improvements:

• better event model: there is now a notion of simultaneous events, and behaviors and events can now be freely mixed
• self-adjusting computation is now supported via memo functions; needless recomputation can be avoided in some cases
• faster priority queue and timeline data structures
• behavior and event types split into co- and contra-variant views for subtyping
• bug fixes and cleanup

Development of froc has moved from Google Code to Github; see

• project page
• documentation
• downloads

Thanks to Ruy Ley-Wild for helpful discussion, and to Daniel Bünzli for helpful discussion and many good ideas in React.

I thought I would take this opportunity to explain how froc works, because it is interesting, and to help putative froc users use it effectively.

Dependency graphs

The main idea behind froc (and self-adjusting computation) is that we can think of an expression as implying a dependency graph, where each subexpression depends on its subexpressions, and ultimately on some input values. When the input values change, we can recompute the expression incrementally by recursively pushing changes to dependent subexpressions.

To be concrete, suppose we have this expression:

  let u = v / w + x * y + z 

Here is a dependency graph relating expressions to their subexpressions:

The edges aren’t directed, because we can think of dependencies as either demand-driven (to compute A, we need B), or change-driven (when B changes, we must recompute A).

Now suppose we do an initial evaluation of the expression with v = 4, w = 2, x = 2, y = 3, and z = 1. Then we have (giving labels to unlabelled nodes, and coloring the current value of each node green):

If we set z = 2, we need only update u to 10, since no other node depends on z. If we then set v = 6, we need to update n0 to 3, n2 to 9 (since n2 depends on n0), and u to 11, but we don’t need to update n1. (This is the change-driven point of view.)

What if we set z = 2 and v = 6 simultaneously, then do the updates? We have to be careful to do them in the right order. If we updated u first (since it depends on z), we’d use a stale value for n2. We could require that we don’t update an expression until each of its dependencies has been updated (if necessary). Or we could respect the original evaluation order of the expressions, and say that we won’t update an expression until each expression that came before it has been updated.

In froc we take the second approach. Each expression is given a timestamp (not a wall-clock time, but an abstract ordered value) when it’s initially evaluated, and we re-evaluate the computation by running through a priority queue of stale expressions, ordered by timestamp. Here is the situation, with changed values in magenta, stale values in red, and timestamps in gray:

If we update the stale nodes from their dependencies in timestamp order, we get the right answer. We will see how this approach gives us a way to handle control dependencies, where A does not depend on B, but A’s execution is controlled by B.

Library interface

The core of froc has the following (simplified) signature:

  type 'a t 
  val return : 'a -> 'a t 
  val bind : 'a t -> ('a -> 'b t) -> 'b t 

The type 'a t represents changeable values (or just changeables) of type 'a; these are the nodes of the dependency graph. Return converts a regular value to a changeable value. Bind makes a new changeable as a dependent of an existing one; the function argument is the expression that computes the value from its dependency. We have >>= as an infix synonym for bind; there are also multi-argument versions (bind2, bind3, etc.) so a value can depend on more than one other value.

We could translate the expression from the previous section as:

  let n0 = bind2 v w (fun v w -> return (v / w)) 
  let n1 = bind2 x y (fun x y -> return (x * y)) 
  let n2 = bind2 n0 n1 (fun n0 n1 -> return (n0 + n1)) 
  let u = bind2 n2 z (fun n2 z -> return (n2 + z)) 

There are some convenience functions in froc to make this more readable (these versions are also more efficient):

  val blift : 'a t -> ('a -> 'b) -> 'b t 
  val lift : ('a -> 'b) -> 'a t -> 'b t 

Blift is like bind except that you don’t need the return at the end of the expression (below we’ll see cases where you actually need bind); lift is the same as blift but with the arguments swapped for partial application. So we could say

  let n0 = blift2 v w (fun v w -> v / w) 
  let n1 = blift2 x y (fun x y -> x * y) 
  let n2 = blift2 n0 n1 (fun n0 n1 -> n0 + n1) 
  let u = blift2 n2 z (fun n2 z -> n2 + z) 

or even

  let (/) = lift2 (/) 
  let ( * ) = lift2 ( * ) 
  let (+) = lift2 (+) 
  let u = v / w + x * y + z 

Now, there is no reason to break down expressions all the way—a node can have a more complicated expression, for example:

  let n0 = blift2 v w (fun v w -> v / w) 
  let n2 = blift3 n0 x y (fun n0 x y -> n0 + x * y) 
  let u = blift2 n2 z (fun n2 z -> n2 + z) 

There is time overhead in propagating dependencies, and space overhead in storing the dependency graph, so it’s useful to be able to control the granularity of recomputation by trading off computation over changeable values with computation over ordinary values.

Dynamic dependency graphs

Take this expression:

  let b = x = 0 
  let y = if b then 0 else 100 / x 

Here it is in froc form:

  let b = x >>= fun x -> return (x = 0) 
  let n0 = x >>= fun x -> return (100 / x) 
  let y = bind2 b n0 (fun b n0 -> if b then return 0 else n0) 

and its dependency graph, with timestamps:

(We begin to see why bind is sometimes necessary instead of blift—in order to return n0 in the else branch, the function must return 'b t rather than 'b.)

Suppose we have an initial evaluation with x = 10, and we then set x = 0. If we blindly update n0, we get a Division_by_zero exception, although we get no such exception from the original code. Somehow we need to take into account the control dependency between b and 100 / x, and compute 100 / x only when b is false. This can be accomplished by putting it inside the else branch:

  let b = x >>= fun x -> return (x = 0) 
  let y = b >>= fun b -> if b then return 0 
                              else x >>= fun x -> return (100 / x) 

How does this work? Froc keeps track of the start and finish timestamps when running an expression, and associates dependencies with the timestamp when they are attacheed. When an expression is re-run, we detach all the dependencies between the start and finish timestamps. In this case, when b changes, we detach the dependent expression that divides by 0 before trying to run it.

Let’s walk through the initial run with x = 10: Here is the graph showing the timestamp ranges, and on the dependency edges, the timestamp when the dependency was attached:

First we evaluate b (attaching it as a dependent of x at time 0) to get false. Then we evaluate y (attaching it as a dependent of b at time 3): we check b and evaluate n0 to get 10 (attaching it as a dependent of x at time 5). Notice that we have a dependency edge from y to n0. This is not a true dependency, since we don’t recompute y when n0 changes; rather the value of y is a proxy for n0, so when n0 changes we just forward the new value to y.

What happens if we set x = 20? Both b and n0 are stale since they depend on x. We re-run expressions in order of their start timestamp, so we run b and get false. Since the value of b has not changed, y is not stale. Then we re-run n0, so its value (and the value of y by proxy) becomes 5.

What happens if we set x = 0? We run b and get true. Now y is also stale, and it is next in timestamp order. We first detach all the dependencies in the timestamp range 4-9 from the previous run of y: the dependency of n0 on x and the proxy dependency of y on n0. This time we take the then branch, so we get 0 without attaching any new dependencies. We are done; no Division_by_zero exception.

Now we can see why it’s important to handle updates in timestamp order: the value which decides a control flow point (e.g. the test of an if) is always evaluated before the control branches (the then and else branches), so we have the chance to fix up the dependency graph before the branches are updated.

Garbage collection and cleanup functions

A node points to its dependencies (so it can read their values when computing its value), and its dependencies point back to the node (so they can mark it stale when they change). This creates a problem for garbage collection: a node which becomes garbage (from the point of view of the library user) is still attached to its dependencies, taking up memory, and causing extra recomputation.

The implementation of dynamic dependency graphs helps with this problem: as we have seen, when an expression is re-run, the dependencies attached in the course of the previous run are detached, including any dependencies for nodes which have become garbage. Still, until the expression that created them is re-run, garbage nodes remain attached.

Some other FRP implementations use weak pointers to store a node’s dependents, to avoid hanging on to garbage nodes. Since froc is designed to work in browsers (using ocamljs), weak pointers aren’t an option because they aren’t supported in Javascript. But even in regular OCaml, there are reasons to eschew the use of weak pointers:

First, it’s useful to be able to set up changeable expressions which are used for their effect (say, updating the GUI) rather than their value; to do this with a system using weak pointers, you have to stash the expression somewhere so it won’t be GC’d. This is similar to the problem of GCing threads; it doesn’t make sense if the threads can have an effect.

Second, there are other resources which may need to be cleaned up in reaction to changes (say, GUI event handler registrations); weak pointers are no help here. Froc gives you a way to set cleanup functions during a computation, which are run when the computation is re-run, so you can clean up other resources.

With froc there are two options to be sure you don’t leak memory: you can call init to clean up the entire system, or you can use bind to control the lifetime of changeables: for instance, you could have a changeable c representing a counter, do a computation in the scope of a bind of c (you can just ignore the value), then increment the counter to clear out the previous computation.

In fact, there are situations where froc cleans up too quickly—when you want to hang on to a changeable after the expression that attached it is re-run. We’ll see shortly how to avoid this.

Memoizing the previous run

Here is the List.map function, translated to work over lists where the tail is changeable.

  type 'a lst = Nil | Cons of 'a * 'a lst t 
 
  let rec map f lst = 
    lst >>= function 
      | Nil -> return Nil 
      | Cons (h, t) -> 
          let t = map f t in 
          return (Cons (f h, t)) 

What happens if we run

  map (fun x -> x + 1) [ 1; 2; 3 ] 

? (I’m abusing the list syntax here to mean a changeable list with these elements.) Let’s see if we can fit the dependency graph on the page (abbreviating Cons and Nil and writing just f for the function expression):

(The dependency edges on the right-hand side don’t mean that e.g. f0 depends directly on f1, but rather that the value returned by f0—Cons(2,f1)—depends on f1. We don’t re-run f0 when f1 changes, or even update its value by proxy as we did in the previous section. But if f1 is stale it must be updated before we can consider f0 up-to-date.)

Notice how the timestamp ranges for the function expressions are nested each within the previous one. There is a control dependency at each recursive call: whether we make a deeper call depends on whether the argument list is Nil.

So if we change t3, just f3 is stale. But if we change t0, we must re-run f0, f1, f2, and f3—that is, the whole computation—detaching all the dependencies, then reattaching them. This is kind of annoying; we do a lot of pointless work since nothing after the first element has changed.

If only some prefix of the list has changed, we’d like to be able to reuse the work we did in the previous run for the unchanged suffix. Froc addresses this need with memo functions. In a way similar to ordinary memoization, a memo function records a table of arguments and values when you call it. But in froc we only reuse values from the previous run, and only those from the timestamp range we’re re-running. We can define map as a memo function:

  let map f lst = 
    let memo = memo () in 
    let rec map lst = 
      lst >>= function 
        | Nil -> return Nil 
        | Cons (h, t) -> 
            let t = memo map t in 
            return (Cons (f h, t)) in 
    memo map lst 

Here the memo call makes a new memo table. In the initial run we add a memo entry associating each list node (t0, t1, …) with its map (f0, f1, …). Now, suppose we change t0: f0 is stale, so we update it. When we go to compute map f t1 we get a memo hit returning f1 (the computation of f1 is contained in the timestamp range of f0, so it is a candidate for memo matching). F1 is up-to-date so we return it as the value of map f t1.

There is a further wrinkle: suppose we change both t0 and t2, leaving t1 unchanged. As before, we get a memo hit on t1 returning f1, but since f2 is stale, so is f1. We must run the update queue until f1 is up-to-date before we return it as the value of map f t1. Recall that we detach the dependencies of the computation we’re re-running; in order to update f1 we just leave it attached to its dependencies and run the queue until the end of its timestamp range.

In general, there can be a complicated pattern of changed and unchanged data—we could change every other element in the list, for instance—so memoization and the update loop call one another recursively. From the timestamp point of view, however, we can think of it as a linear scan through time, alternating between updating stale computations and reusing ones which have not changed.

The memo function mechanism provides a way to keep changeables attached even after the expression that attached them is re-run. We just need to attach them from within a memo function, then look them up again on the next run, so they’re left attached to their dependencies. The quickhull example (source) demonstrates how this works.

Functional reactive programming and the event queue

Functional reactive programming works with two related types: behaviors are values that can change over time, but are defined at all times; events are defined only at particular instants in time, possibly (but not necessarily) with a different value at each instant. (Signals are events or behaviors when we don’t care which one.)

Events can be used to represent external events entering the system (like GUI clicks or keystrokes), and can also represent occurrences within the system, such as a collision between two moving objects. It is natural for events to be defined in terms of behaviors and vice versa. (In fact they can be directly interdefined with the hold and changes functions.)

In froc, behaviors are just another name for changeables. Events are implemented on top of changeables: they are just changeables with transient values. An incoming event sets the value of its underlying changeable; after changes have propagated through the dependency graph, the values of all the changeables which underlie events are removed (so they can be garbage collected).

Signals may be defined (mutually) recursively. For example, in the bounce example (source), the position of the ball is a behavior defined in terms of its velocity, which is a behavior defined in terms of events indicating collisions with the walls and paddle, which are defined in terms of the ball’s position.

Froc provides the fix_b and fix_e functions to define signals recursively. The definition of a signal can’t refer directly to its own current value, since it hasn’t been determined yet; instead it sees its value from the previous update cycle. When a recursively-defined signal produces a value, an event is queued to be processed in the next update cycle, so the signal can be updated based on its new current value. (If the signal doesn’t converge somehow this process loops.)

Related systems

Froc is closely related to a few other FRP systems which are change-driven and written in an imperative, call-by-value language:

FrTime is an FRP system for PLT Scheme. FrTime has a dependency graph and update queue mechanism similar to froc, but sorts stale nodes in dependency (“topological”) rather than timestamp order. There is a separate mechanism for handling control dependencies, using a dynamic scoping feature specific to PLT Scheme (“parameters”) to track dependencies attached in the course of evaluating an expression; in addition FrTime uses weak pointers to collect garbage nodes. There is no equivalent of froc’s memo functions. Reactivity in FrTime is implicit: you give an ordinary Scheme program, and the compiler turns each subexpression into a changeable value. There is no programmer control over the granularity of recomputation, but there is a compiler optimization (“lowering”) which recovers some performance by coalescing changeables.

Flapjax is a descendent of FrTime for Javascript. It implements the same dependency-ordered queue as FrTime, but there is no mechanism for control dependencies, and there are no weak pointers (since there are none in Javascript), so it is fairly easy to create memory leaks (although there is a special reference-counting mechanism in certain cases). Flapjax can be used as a library; it also has a compiler similar to FrTime’s, but since it doesn’t handle control dependencies, the semantics of compiled programs are not preserved (e.g. you can observe exceptions that don’t occur in the original program).

React is a library for OCaml, also based on a dependency-ordered queue, using weak pointers, without a mechanism for control dependencies.

Colophon

I used Mlpost to generate the dependency graph diagrams. It is very nice!

Sudoku in ocamljs, part 3: functional reactive programming

In part 1 and part 2 of this series, we made a simple Sudoku game and connected it to a game server. In this final installment I want to revisit how we check that a board satisfies the Sudoku rules. There's a small change to the UI: instead of a "Check" button, the board is checked continuously as the player enters numbers; any conflicts are highlighted as before. Here's the final result.

Let's review how we want checking to work: a cell is colored red if any other cell in the same row, column, or square (outlined in bold) contains the same number; otherwise the cell is colored white. Now take another look at the check_board function from part 1. Is it obvious that this code meets the specification? The function is essentially stateful, clearing all the cell colors then setting them red when it discovers a conflict. In fact, I had a bug in it related to state--I was clearing the background color in the None arm of check_set, so each checked constraint would overwrite the highlighting of the previous ones where they overlapped.

It would be easier to convince ourselves that we'd gotten it right if the code looked more like the specification. What we want is a function that maps each cell and its "adjacent" cells (the ones in the same row, column, or square) to a boolean (true if the cell is highlighted). Abstracting from the DOM details, suppose a cell is an int option and we have a function adjacents i j that returns a list of cells adjacent to the cell at (i, j). Then the check function is just:

let highlighted cell i j =
  cell <> None && List.mem cell (adjacents i j)

So how do we hook this function into the UI? We could just call it for every cell, every time we get a change event for some cell. That seems like a lot of needless computation, since almost all the cells haven't changed. On the other hand, if we manually keep track of which cells might be affected by a change, our code is no longer obviously correct. It would be nice to have some kind of incremental update, like a spreadsheet.

This is where functional reactive programming comes in. The main idea is to write functions over behaviors, or values that can change. If you change an input to a function, the output (another behavior) is automatically recomputed. The dependency bookkeeping is taken care of by the framework; we'll use the froc library.

It turns out to be convenient to give behaviors a monadic interface. So we have a type 'a behavior; we turn a constant into a behavior with return, and we use a behavior with bind. We saw in part 2 that the monadic interface of Lwt enables blocking: since bind takes a function to apply to the result of a thread, the framework can wait until the thread has completed before applying it. With froc, the framework applies the function passed to bind whenever the bound behavior changes. With both Lwt and froc you can think of a computation as a collection of dependencies rather than a linear sequence.

There's another important piece of functional reactive programming: events. An 'a event in froc is a channel over which values of type 'a can be passed. You can connect froc events to DOM events to interact with the stateful world of the UI. The library includes several functions for working with events (e.g. mapping a function over an event stream) and in particular for mediating between behaviors and events, such as:

val hold : 'a -> 'a event -> 'a behavior

which takes an initial value and an event channel, and returns a behavior that begins at the initial value then changes to each successive value that's sent on the channel, and

val changes : 'a behavior -> 'a event

which takes a behavior and returns an event channel that has a value sent on it whenever the behavior changes.

This all probably seems a bit abstract, so let's dive into the example code:

module D = Dom
let d = D.document

module F = Froc
module Fd = Froc_dom
let (>>=) = F.(>>=)

We set up some constants we'll need below. The Froc module contains the core FRP implementation, not tied to a particular UI toolkit; Froc_dom contains functions that are specific to DOM programming (with the Dom module we saw before).

let make_cell v =
  let ev = F.make_event () in
  let cell = F.hold v ev in
  let set v = F.send ev v in
  (cell, set)
let notify_e e f =
  F.notify_e e (function
    | F.Fail _ -> ()
    | F.Value v -> f v)

These are a couple of functions that really should be part of froc (and will be in the next version). The first makes a cell, which is a behavior (the hold of an event channel) along with a function to set its value (which sends the value on the channel). It's like a ref cell, but we can bind it so changes are propagated. We'll have one of these for each square on the Sudoku board, but it is a generally useful construct.

The second papers over a design error in the froc API: like with Lwt threads, a froc behavior or event value can be either a normal value or an exception (together, a result). The notify_e function sets a callback that's called when an event arrives on the channel, but most of the time we just want to ignore exceptional events.

let attach_input_value i b =
  notify_e (F.changes b) (fun v -> i#_set_value v)
let attach_backgroundColor e b =
  notify_e
    (F.changes b)
    (fun v -> e#_get_style#_set_backgroundColor v)

These are functions that should be part of Froc_dom. To attach a DOM element to a behavior means to update the DOM element whenever the behavior changes. But there are lots of ways to update a DOM element, and Froc_dom doesn't include them all. (This design contrasts with that of Flapjax, where you work with behaviors whose value is an entire DOM element. It's certainly possible to do this in froc, but more tedious because of the types.)

let (check_enabled, set_check_enabled) = make_cell false

Now we're in the application code. The check_enabled cell controls whether checking is turned on--we'll see below what this is for, as you may have noticed that there is no such switch in the actual UI.

let make_board () =
  let make_input () =
    let input = (d#createElement "input" : D.input) in
    input#setAttribute "type" "text";
    input#_set_size 1;
    input#_set_maxLength 1;
    let style = input#_get_style in
    style#_set_border "none";
    style#_set_padding "0px";

    let (cell, set) = make_cell None in
    attach_input_value input
      (cell >>= function
        | None -> F.return ""
        | Some v -> F.return (string_of_int v));
    let ev =
      F.map
        (function
          | "1" | "2" | "3" | "4" | "5"
          | "6" | "7" | "8" | "9"  as v ->
            Some  (int_of_string v)
          | _ -> None)
        (Fd.input_value_e input) in
    notify_e ev set;
    (cell, set, input) in

Here we make the game board much as we did in part 1. The main difference is that instead of working directly with DOM input nodes, we connect each input to a cell of type int option. The attach_input call sets the value of the DOM input node whenever the cell changes, and the notify_e call sets the cell whenever the input node changes. (This doesn't loop, because Fd.input_value_e makes an event stream from the "onchange" events of the input, and "onchange" events are only sent when the user changes the input, not when it's changed from Javascript.) We take the stream of strings and map it into a stream of int options, validating the string as we go.

  let rows =
    Array.init 9 (fun i ->
      Array.init 9 (fun j ->
        make_input ())) in

  let adjacents i j =
    let adj i' j' =
      (i' <> i || j' <> j) &&
        (i' = i or j' = j or
            (i' / 3 = i / 3 && j' / 3 = j / 3)) in
    let rec adjs i' j' l =
      match i', j' with
        | 9, _ -> l
        | _, 9 -> adjs (i'+1) 0 l
        | _, _ ->
            let l =
              if adj i' j'
              then
                let (cell,_,_) = rows.(i').(j') in
                cell::l
              else l in
            adjs i' (j'+1) l in
    adjs 0 0 [] in

We make the game board as a matrix of inputs as before, but now each element of the matrix contains a cell (an int option behavior), the function to set that cell, and the actual DOM input element. Next we set up the rule-checking. The adjacents function returns a list of cells adjacent to the cell at (i, j) (adjacent in the sense we discussed above). All my bugs when I wrote this example were in this function, but it clearly embodies the specification we're trying to meet: a cell is adjacent to the current cell if it is not the same cell and is in the same row, column, or square. (The loop would be clearer if we had Array.foldi.)

  ArrayLabels.iteri rows ~f:(fun i row ->
    ArrayLabels.iteri row ~f:(fun j (cell, _, input) ->
      let adjs = adjacents i j in
      attach_backgroundColor input
        (check_enabled >>= function
          | false -> F.return "#ffffff"
          | true ->
              F.bindN adjs (fun adjs ->
                cell >>= fun v ->
                  if v <> None && List.mem v adjs
                  then F.return "#ff0000"
                  else F.return "#ffffff"))));

This is the functional reactive core of the program. For each square on the board we compute essentially the highlighted function above, but in monadic form (the bindN function binds a list of behaviors at once), and attach the result to the background color of the input node. Because the set of adjacent cells does not depend on the value of the cells, we can hoist its computation out of the reactive part so it won't be recomputed every time a cell changes (and since dependency on a behavior is captured in the type of a function, the fact that this typechecks tells us it is safe to do!).

That's it. The rest of the program is almost the same as before. (Here's the full code.) The one important change has to do with check_enabled. In the reaction to cell changes, we consult check_enabled, returning the unhighlighted color when it's false. Since we do this before binding the cells, a change to a cell causes no recomputation when check_enabled is false. So we turn off check_enabled while loading a new game board, saving a lot of needless recomputation that otherwise makes it annoyingly slow.

It's interesting to compare functional reactive programming to the model-view-controller pattern. The point of MVC is to separate the changeable state (the model) from how it is displayed (the view). Although MVC is typically implemented with change events and state update, a view behaves as a pure function of the state (or can be made so by making the state of UI components explicit). So you could think of FRP as "automatic" MVC: you just write down dependencies (with bind) and the framework manages events and state update. For small examples this may not seem like a big win, but FRP takes care of some complexities that tend to swamp MVC apps: managing dynamic dependencies (registering and unregistering event handlers in response to events) and maintaining coherence (i.e. functional behavior) over different event orders.

I haven't yet written a serious application with froc, but so far I think it is awesome!

Monadic functional reactive AJAX in OCaml

Yesterday I released three related projects which I've been working on for a long time:

• ocamljs, a Javascript backend for ocamlc, along with some libraries for web programming
• orpc, a tool for generating RPC stubs from OCaml signatures, either ONC RPC for use with Ocamlnet's RPC implementation, or RPC over HTTP for use with ocamljs
• froc, a library for functional reactive programming that works with ocamljs

The idea of all this is to build a platform for client-side web programming like Google Web Toolkit (but better, of course :). There is still a lot of work to get there, but already we use ocamljs and orpc for production work at Skydeck. In my next few posts I'll work through some examples using ocamljs, orpc, and froc:

• part 1: DOM programming
• part 2: RPC over HTTP
• part 3: functional reactive programming