Home

Motivation / The Problem

Incremental computation systems are motivated by the observation, that typically large parts of application state remains unmodified by a single action. Think of an object being moved in Blender (all other objects remain static). In many applications an ad-hoc approach, like reactive streams (e.g. Observable in .NET) is used to encapsulate dynamic changes when necessary. At a first glance this seems to be fine and you end up with lots of mappings/filters/etc. on your reactive values. The problem starts when you need to dynamically depend on data. Consider the following example

let nonReactive (a : int) (b : int) =
    if a < 10 then 10
    else a * b

let reactive (a : IObservable<int>) (b : IObservable<int>) =
    a.SelectMany(fun a ->
        if a < 10 then 
            Observable.Never().StartWith(10)
        else
            b.Select(fun b -> a * b)
    )
    
let run() =
    let a = new Subject<int>()
    let b = new Subject<int>()
    let res = reactive a b
    res.Add(printfn "res: %d")
    printfn "a <- 1"; a.OnNext(1)
    printfn "b <- 2"; b.OnNext(2)
    printfn "a <- 100"; a.OnNext(100)
    
// run() prints
//   a <- 1
//   res: 10
//   b <- 2
//   a <- 100
    

Not quite what we wanted. I could go into detail why this happens and what we can do about it, but that's not the important lesson here. Rx fans will point out, that this behaviour is totally intended and that there are actually ways to make this work the way I intended, but there are two important lessons to be learned here are:

• observables are not designed to represent changeable values, they intend to capture event streams, which can be inspected starting at a specific point in time. (e.g. you can't poll the latest value when no-one was subscribed)
• naively translating non-reactive programs to reactive ones fails.

Scope

Consider a typical application. It almost always consists of these three parts:

1. First of all there's a domain-model that basically holds values and wants to read/change them as the user interacts with it.
2. Then there is some kind of logic turning these model-values into a SceneGraph/UI/Text/Binary/Assembler/etc.
3. There is some logic presenting this representation to the user (Renderer/Browser/etc.)

Since the changes from 1 need to be passed through 2 (the view logic) such that 3 can interpret the results. We decided that we need simple combinators that application programmers can successfully use without needing a PHD in reactive programming.

Our main goal (as rendering engine developers) was to create a rendering system that accepts changeable values everywhere, such that application programmers don't have to care about when to update which parts of the rendering, but to track everything automatically.

aval<'T> (AdaptiveValue)

I could go into details how the system works internally, but there will be other posts/pages covering this in detail.

From a high level perspective aval is just a container for a value that may change over time. We also provide combinators to create computationally dependent avals from existing ones (typical things like map/bind/etc.)

Here's a basic overview what the API looks like:

val transact : (unit -> 'a) -> 'a

type cval<'a> =
    interface aval<'a>
    val Value with get, set

module AVal =
    val init      : 'a -> cval<'a>
    val constant  : 'a -> aval<'a>
    val map       : ('a -> 'b) -> aval<'a> -> aval<'b>
    val bind      : ('a -> aval<'b>) -> aval<'a> -> aval<'b>
    val force     : aval<'a> -> 'a
    // lots more

Basically all the functionality can be implemented using these combinators, but for efficiency reasons there are a lot more in the real implementation. The important part about our container-type is that it tracks dependencies via internally building a dependency-graph that is capable of tracking which avals were affected by a certain change.

So let's revisit the little example from above:

let incremental (a : aval<int>) (b : aval<int>) =
    a |> AVal.bind (fun a ->
        if a < 10 then AVal.constant 10
        else b |> AVal.map (fun b -> a * b)
    )
let run() =
    printfn "a <- 1"
    let a = AVal.init 1
    printfn "b <- 2"
    let b = AVal.init 2
    let res = incremental a b
    printfn "res: %d" (AVal.force res)
    printfn "a <- 100"
    transact (fun () -> a.Value <- 100)
    printfn "res: %d" (AVal.force res)
    
// run() prints
//   a <- 1
//   b <- 2
//   res: 10
//   a <- 100
//   res: 200
    

As you see our naive translation with aval works just as we expected.

The adaptive function can also be implemented using our ComputationExpression builders which essentially makes it look like the non-adaptive implementation:

let incremental (a : aval<int>) (b : aval<int>) =
    aval {
        let! va = a
        if va < 10 then 
            return 10
        else
            let! vb = b
            return va * vb
    }