I’ve been thinking recently about how to structure dynamic web applications, and in particular about the role that incremental computation should play.

In this post, I’d like to outline an approach we’ve been experimenting with internally which uses Incremental, a general purpose library for building so-called self adjusting computations. Self adjusting computations are essentially graph-structured computations that can be updated efficiently when their inputs change.

I’ll describe this all in terms of OCaml, which is the language we’re doing these experiments in (courtesy of the excellent js_of_ocaml), but the ideas should be applicable to other languages.

Elm in OCaml

Let’s start by outlining a simple, non-incremental approach, inspired by the Elm Architecture. In that architecture, there are three primary elements from which an application is composed: the model, the view and a set of actions.

The model represents the logical state of the application. This includes things like the data being displayed on the page, the current page being displayed, and the part of the page that’s in focus. But it omits most presentation details, and doesn’t specify the concrete choice of dom elements used.

Actions are the things that can happen to the model. The arrival of new data to be displayed, or the click of a mouse, are translated into actions which are in turn interpreted to update the state. These are important, but don’t affect the incrementality story much, so we won’t discuss them in detail.

The view is a function that takes the current model and produces a vdom (virtual dom) tree, an immutable datastructure that represents the intended state of the dom. It is the view function that makes the concrete presentation choices that are left unsaid by the model. The view determines some of the dynamic behavior of the application as well, since within the vdom you can register callbacks on keypresses or mouse clicks that enqueue actions to later be applied to the state.

We can wrap this up into a module signature, as follows.

module type App_intf = sig
  module Model : sig
    type t
  end

  module Action : sig
    type t
    val apply : t -> Model.t -> Model.t
  end

  val view : Model.t -> (Action.t -> unit) -> Vdom.t
end

Note that the second argument to view is a function that can be used for scheduling actions to occur. This function is used to build callbacks which are attached to the vdom.

We can combine this with a simple interface for starting up an application:

val start_app
  : (module App_intf with type Model.t = 'model)
  -> init:'model
  -> unit

which is responsible for running the display loop.

This isn’t quite enough; in particular, I’ve omitted the necessary hooks for kicking off asynchronous processes for doing things like grabbing data from a server. But the model above is a pretty good start, and gives you a sense of the structure of an Elm-style application.

This approach isn’t too bad from a performance perspective. In particular, the on_startup function minimizes the amount of churn to the dom by, on every action, diffing the newly generated vdom against the previous instantiation, to produce a minimal patch to apply to the dom proper. And modifications to the dom itself are quite expensive.

But this approach doesn’t scale to big, complex UIs. That’s because, even though most actions change the model in only small ways, the full vdom tree has to be created every time. If the vdom is large and complicated, this is a serious problem.

Incremental Basics

Let’s see how we can use Incremental to optimize generation of the vdom.

Imagine we want to display information about the state of a set of machines in our datacenter. For each machine, assume we have two pieces of data: the temperature, and whether that particular server is currently selected. Now, given incremental values representing the data for just one machine, how can we use Incremental to produce the vdom?

Incremental provides operators for building computations on top of incremental values. For example, the function Incr.map2 has this signature.

val Incr.map2 : 'a Incr.t -> 'b Incr.t -> f:('a -> 'b -> 'c) -> 'c Incr.t

This lets us build a computation that takes two incremental inputs, and combines them to make a single new incremental. We can use this for generating an incremental vdom to display our machine.

let view temperature selected = 
    Incr.map2 temperature selected
      ~f:(fun temperature selected ->
          Vdom.text
            (if selected then [Vdom.class_ "selected"] else [])
            (sprintf "%F degrees" temperature))

We can write this a bit more naturally using the ppx_let syntax extension. Essentially, ppx_let allows us to encode maps using ordinary let binding syntax.

let view temperature selected =
  let%map temperature = temperature and selected = selected in
  Vdom.text 
    (if selected then [Vdom.class_ "selected"] else [])
    (sprintf "%F degrees" temperature)

The key issue here is that the code regenerating the text node will only be rerun when necessary, i.e., when the value of either selected or temperature have changes. In a complex view with lots of incremental inputs and lots of vdom nodes built on top of them, judicious use of map allow you to recompute only the vdom that are in need of an update.

Using bind

It turns out that map isn’t enough. One limitation of map is that the dependencies introduced by map are static. e.g. Incr.map2 a b ~f will produce a node that reruns f every time a or b change.

But sometimes, you want dynamic rather than static dependencies. For a trivial example, imagine that our machine view has different inputs that might be used in different situations, say, there’s a mode that determines whether uptime or temperature are displayed. We could implement such a view on top of map as follows.

let view temperature uptime selected mode =
  let%map temperature = temperature
  and     uptime      = uptime
  and     selected    = selected
  and     mode        = mode
  in
  Vdom.text
    (if selected then [Vdom.class_ "selected"] else [])
    (match mode with
     | Temperature -> sprintf "%F degrees" temperature
     | Uptime -> Time.Span.to_string uptime)

Here, the appearance of the dom node is dynamic, but the dependencies are not. Even if you’re in Temperature node, you’ll still recompute the Vdom when the uptime changes.

On this small scale, the extra cost is trivial. But as you consider larger more complicated views, the ability to control dependencies precisely can have real value.

In this case, we can control the dependencies using bind. Here’s the signature of bind:

val bind : 'a Incr.t -> ('a -> 'b Incr.t) -> 'b Incr.t

The signature is deceptively simple, but it lets you do something powerful. In particular, Incr.bind i f returns an incremental whose dependencies, and even whose interior nodes, are chosen dynamically by f.

Here’s a simple rewrite of the code above that takes advantage of bind.

let view temperature uptime selected mode =
    let text =
      Incr.bind mode (function
          | Temperature -> 
            let%map x = temperature in sprintf "%F degrees" x
          | Uptime -> 
            let%map x = uptime in Time.Span.to_string x
        )
    in
    let%map text = text and selected = selected in
    Vdom.text
      (if selected then [Vdom.class_ "selected"] else [])
      text

Here, bind lets us create a text incremental that depends either on the temperature or on the humidity, depending on the mode. We can write this with our syntax extension, using its specialized match syntax.

let view temperature uptime selected mode =
    let text =
      match%bind mode with
      | Temperature -> 
        let%map x = temperature in sprintf "%F degrees" x
      | Uptime -> 
        let%map x = uptime in Time.Span.to_string x
    in
    let%map text = text and selected = selected in
    Vdom.text
      (if selected then [Vdom.class_ "selected"] else [])
      text

One thing that’s nice about ppx_let is that it makes it easier to separate thinking about what your code does from how it’s incrementalized. If you ignore the %map and %bind annotations, what you’re left with is enough to understand the meaning of the computation that’s being incrementalized. The annotations are only important for understanding the performance characteristics of the incremental recomputation.

Decomposing incrementals

Here’s an updated version of our App_intf which includes Incremental.

module type App_intf = sig
  module Model : sig
    type t
  end

  module Action : sig
    type t
    val apply : t -> Model.t -> Model.t
  end

  val view : Model.t Incr.t -> (Action.t -> unit) -> Vdom.t Incr.t
end

The only change is the view function, which instead of taking a Model.t and returning Vdom.t now takes a Model.t Incr.t and returns a Vdom.t Incr.t. And instead of calling this function on every update, we simply call it once at the beginning. The start_app function would be responsible for repeatedly updating the Model.t Incr.t as the model changes, and can then read off the new vdom node from the Vdom.t Incr.t.

This all sounds good on the surface, but there’s a fly in this ointment, which is that my earlier examples were built on the assumption that the different inputs to the computation were already broken down into separate incremental values. But here, we have one big incremental value containing the entire model. How do we apply Incremental effectively in this case?

Let’s revist our server-display example from before. Now, instead of assuming we have a different incremental for each property of a server, imagine we have one incremental representing the full state of one server. We can use the following as our model type:

module Model = struct
      type display_mode = Temperature | Uptime
      type t = { temperature: float;
                 uptime: Time.Span.t;
                 selected: bool;
                 mode: display_mode;
               }
      [@@deriving fields]
    end

The deriving annotation above provides us with accessor functions for each field, which will be useful shortly.

It’s easy enough to write a view function that returns an incremental that recomputes in its entirety every time the model changes, as shown below.

let view model =
  let%map model = model in
  let text =
    match model.mode with
    | Temperature -> 
      sprintf "%F degrees" model.temperature
    | Uptime -> 
      Time.Span.to_string model.uptime
  in
  Vdom.text
    (if model.selected then [Vdom.class_ "selected"] else [])
    text

And for this tiny example, that’s likely the correct thing to do. But we’ll want to incrementalize more precisely for real world examples, so let’s see how we could do that in this case.

What we effectively need to do to incrementalize this is to convert our one big incremental model into a number of smaller incrementals. We can do that by projecting out individual components of the model using map.

For example, if we write:

Incr.map model ~f:(fun m -> m.mode)

or, equivalently

Incr.map model ~f:Model.mode

We’ll get an incremental that contains only the mode. Critically, incrementals that are depend on this one will only update when the mode actually changes, not, say, the temperature is updated. That’s because Incremental cuts off computations when the new output is physically equal to the old one, so that even if the model changes, each projected incremental will only propagate the computation if its data has changed.

We can use this approach to first project out the fields of the model record into different incrementals, and then build out computation on top of that. That looks like this:

let view model =
      let mode        = Incr.map model ~f:Model.mode        in
      let temperature = Incr.map model ~f:Model.temperature in
      let selected    = Incr.map model ~f:Model.selected    in
      let uptime      = Incr.map model ~f:Model.uptime      in
      let text =
        match%bind mode with
        | Temperature -> 
          let%map x = temperature in sprintf "%F degrees" x
        | Uptime -> 
          let%map x = uptime in Time.Span.to_string x
      in
      let%map text = text and selected = selected in
      Vdom.text
        (if selected then [Vdom.class_ "selected"] else [])
        text

And this has basically the right incremental structure.

This is a good start, but we still don’t really have the full story. In particular, the above approach to incrementalization makes sense when our overall data is organized as simple static structures like records. But it’s not clear what to do when we have more complex data structures. For example, what if we had a collection of machines stored in a map or a set? We don’t yet have a way of efficiently handling this kind of complex abstract data type using Incremental.

More on that in my next post.