Introduction

In the previous chapter we have seen different approaches on how to work with data structures:

  • Ephemeral data structures can be modified any time. Operations on data structures may or may not destroy their input.
  • Persistent data structures can not be modified. Each operations creats a copy of the input with the operation applied to the output.

In this post, we build on persistent data structures and add mutation to them in a well-formed manner. Instead of blindly destroying memory cells, we keep track of computations and their dependencies in order to finally adapt dependent computation according to the modifications occured to the input. This approach is often called incremental computation in the CS literature.

A bit of History / Related Work

Incremental computation as characterized by [Ramalingam and Reps 1993] can be defined as such:

  • Given some input data x and the computation result f(x), find the necessary changes of f(x) given some changes in x. Crucially here, computing the changes in the result should have incremental performance, i.e. should run in O(delta), where delta is the size of the change applied to x.

One of the first areas where incremental computation was thoroughly examined were language-based editors that need to continuously analyze the edited source-code, without disrupting the programmers work flow by performing the analysis from scratch even after only small changes [Reps et al. 1983].

Based on the idea of computing results incrementally (i.e. in running time proportional to the change), various dynamic algorithms have been developed in the algorithmics community. The field basically worked in two directions. Firstly, algorithms people took standard algorithms, derived incremental ones and showed them to be efficient. Secondly, researchers tried to develop algorithms to propagate changes in arbitrary computation graphs. By the way, this (second one) is kind of the approach we took in our first dependency paper [Worister et al. 2013]. On main problem with the general approach was how to represent changes of the dependency graph itself. Can the algorithm be used to incrementally evaluate the incremental evaluation algorithm? An extensive survey on this topic can be found in [Ramalingam and Reps 1993].

In the early 2000s, the language community started to investigate the problem of incremental computation again. In their seminal paper, [Acar et al. 2003] introduced adaptive functional programming, a technique to automatically propagate changes in purely functional programs. Later, in his thesis [Acar 2005] Acar refined adaptive funtional programming (from then called self-adjusting-computation) and showed the approach to be (provable) efficient for most programs (you can find precise definitions of most programs in his thesis).

Syntax and Semantics of our incremental language (Mod system as we call it)

An interactive Tour

This tutorial is written in literate FSharp, so in order to make it work, let us set up some infrastructure.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
#r @"..\Packages\Aardvark.Base\lib\net45\Aardvark.Base.dll"
#r @"..\Packages\Aardvark.Base.FSharp\lib\net45\Aardvark.Base.TypeProviders.dll"
#r @"..\Packages\Aardvark.Base.FSharp\lib\net45\Aardvark.Base.FSharp.dll"
#r @"..\Packages\Aardvark.Base.Essentials\lib\net45\Aardvark.Base.Essentials.dll"
#r @"..\Packages\Aardvark.Base.Incremental\lib\net45\Aardvark.Base.Incremental.dll"
#r @"..\Packages\Aardvark.Base.Incremental\lib\net45\Aardvark.Base.Incremental.dll"
#r @"..\Packages\FAKE\tools\FakeLib.dll"

open System
open Aardvark.Base
open Aardvark.Base.Incremental

The Mod Module

Aardvark.Base.Incremental provides two essential types: IMod and ModRef<'a>

The associated operations live in the Mod module which somewhat looks like:

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
module Mod' =

    (* mod constructors *)

    // creates a mod cell which can be changed afterwards (data source)
    let init       (v : 'a) : ModRef<'a> = ``...some implementation...``()
    // creates a mod cell which cannot be changed by the user
    let constant   (v : 'a) : IMod<'a>   = ``...some implementation...``()

    (* mod combinators *)

    // maps over a mod and creates a new one (tracks dependency)
    let map (f : 'a -> 'b) (m : IMod<'a>) : IMod<'b> = ``...some implementation...``()
    // value dependent map over mod cell (tracks dependency, dependency graph is dynamic)
    let bind (f : 'a -> IMod<'b>) (m : IMod<'a>) : IMod<'b> = ``...some implementation...``()
    // maps over two mods and runs f on the consistent inputs.
    let map2 (f : 'a -> 'b -> 'c) (m : IMod<'a>) (m' : IMod<'b>) : IMod<'c> = ``...some implementation...``()

    (* meta operations *)
    
    // changes the content of a ModRef. Only valid within transact function (see below)
    let change (r : ModRef<'a>) (newValue : 'a) : unit = ``...some implementation...``()

    // scope for supplying changes to the system. in f there might be calls to change (defined above).
    // after transact, all dependencies know that they are inconsistent and need to be recomputed on demand
    let transact (f : unit -> 'a) : 'a = ``...some implementation...``()

    // makes the content of a modifiable observable to the user
    let force (m : IMod<'a>) : 'a = ``...some implementation...``()

Let us now define the semantics for each of the operations step-by-step:

1: 
let constantMod = Mod.constant 10

Mod.constant creats a new modifiable cell which is not modifiable (funny hmm?). The purpose of this operator is to create values, which can be fed to the system (so that it typechecks), although the thing is not really modifiable. Nevertheless, the operation creates a new cell with initially no outputs.

alt text

1: 
let modRef1 = Mod.init 10

Mod.init creats a new modifiable cell which can be changed afterwards:

alt text

1: 
let mappedref = Mod.map (fun s -> s + 1) modRef1

Mod.map creats a fresh modifiable cell, adds the dependency to its single source and taggs conceptually tags the introduced edge with the function supplied as first argument.

alt text

Whenever its source is changed, f needs to be reexecuted in order to make the result consistent again.

1: 
Mod.force mappedref |> printfn "mappedRef=%d"

prints 11, since modRef1 has value 10 and map increments its value

1: 
2: 
3: 
transact (fun () ->
    Mod.change modRef1 0
)

performs a modification on the input cell, which due to the semantics of transact results in marking mappedRef to be invalid. *

1: 
Mod.force mappedref |> printfn "mappedRef=%d"

prints 1, since the input value modref1 was changed to have value 0, and due to transact mappedref was marked to be inconsisted. Mod.force is guaranteed to always return the consistent value of the supplied mod. Thus, Mod.force carries all operations, required to make mappedref consistent again, reads out the constitent value which is finally handled over to printfn.

So far, our dependency graphs are entirely static, i.e. each operation adds an edge to exactly one source node. In order to formulate arbitrary functional programs it is necessary to express dynamic dependencies. More precisely, depending on the actual avalue of an IMod<'a> we would like to proceed in different sub dependency graphs. To be honest, this is the core of our system and buzzled us for a long time.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
let dynamicDependency // implements value level dependency
     (m : IMod<'a>)   // source mod which we depend on per value
     (cont : 'a -> #IMod<'b>) // A continuation function. Whenever ``m``'s value changes,
                              // we call ``cont`` which in turn returns us a complete 
                              // dependency graph. (ignore the # for the moment)
     : IMod<'b> = ``...some implementation...``()

let g1 = Mod.init 10 
let g2 = Mod.init 20
let s = Mod.init true
let g3 = dynamicDependency s (fun s -> if s then g1 else g2)

Wow, the code type-checks. So of course we must have found the right primitve... right? Incident?? Not really. ... Let us recall LINQ which essentially provides a module (removing C# clutter and wrong return type placement):

1: 
2: 
3: 
module IEnumerable =
    let select (xs : seq<'a>) (f : 'a -> 'b) : seq<'b> = ``...some implementation...``()
    let selectMany (xs : seq<'a>) (f : 'a -> seq<'b>) : seq<'b> = ``...some implementation...``()

Ok... what we got here in select is just map (trivial by seq ~ IMod). Let us now look at selectMany. selectMany applies a seqence creation function per element of an input sequence and flattens the result. In mod world, in dynamicDependency we apply a continuation function to the actual value of the mod and return a inner mod which is returned to the outer level. Again, by substituting seq ~ IMod we can convert between the prented functions. Turns out that this goes back to the mathematican [Moggi 1991] and [Wadler 1995] who firstly used monads in the context of programming. Later this monad stuff was used in LINQ [Meijer et al. 2006],[Syme 2006] and many many many others. In order to respekt zollen we from now on call dynamicDependency bind. Let us now get back to dependencies and how to use bind in practise.

So far we can create input boxes and boxes depending on another single box. This is rather useless, right?. Let us now implement a more complex dependency graph.

1: 
2: 
3: 
4: 
5: 
let mode = Mod.init true
let inputA = Mod.init 5
let inputB = Mod.init 10
let multiplyInputs = Mod.map2 (fun a b -> a * b) inputA inputB
let addInputs = Mod.map2 (fun a b -> a + b) inputA inputB
1: 
2: 
3: 
// here comes the shit. Bind extracts the value of a mod thingy and dependent on
// its value it returns different mods, i.e. different dependency grpahs.
let output = Mod.bind (fun m -> if m then multiplyInputs else addInputs) mode

Since mode is true, we return the multiplyInputs graph. As you can see the complete addInputs graph is not even existent:

alt text

1: 
2: 
3: 
4: 
5: 
6: 
// change the mode
transact (fun () -> Mod.change mode false)

// compute the result of output

output |> Mod.force |> printfn "output is: %d"

Since mode is now true, we return the addInputs graph. As you can see the complete multipleInputs graph is not even existent:

alt text

Of course working with those boring combinators can be painful when working with complex graphs. Luckily, in F# we can do better by creating a computation expression builder which internally, calls our primitives, i.e. creates a dependency graph under the hood. Given the inputs introduced earlier we can use this syntactic sugar in order to retrieve much nicer code:

1: 
2: 
3: 
4: 
5: 
6: 
7: 
8: 
let output2 = 
    adaptive {
        let! m = mode
        if m then
            return! multiplyInputs
        else 
            return! addInputs
    }

output2 semantically behaves exactly like output, which can be seen by inspecting the dependency graph

alt text

Semantically, let! behaves like let, but introduces a dependency edge.

Correct usage of the operators introduced so far

Our implementation is very kind to the user (at first). Almost everything compiles, but there are some things which need to be taken care of when writing adaptive code (i.e. we check some static properties at runtime instead of compile time for pragmantic reasons... ammmm or something we check nothing and you get garbagge!!).

  • Mod.change can only be used in transact. We enforce this at runtime.
  • transact and change shall never occur in an adaptive lambda function like the one handed over to map. Repeat after me. No transact in stuff which is reexecuted by the mod system.
  • Although it might be useful to use Mod.force in adaptive functions it at least smells bad. Mod.force extracts the value of an IMod without adding an edge to the dependency graph.
1: 
2: 
3: 
4: 
5: 
6: 
7: 
let a =
    adaptive {
        let! m = Mod.init 10
        let! c = Mod.init 20
        let! d = Mod.init 30
        return m + c + d
    } 

Academic background of our implementation

Our approach is inspired by [Acar et al. 2003] and [Acar 2005]. The computation expression builder (aka monad) is (a tiny bit if you want) similar to the one presented by [Carlsson 2002]. However the semantics is unpublished, yet somewhat inspired by [Hudson et al. 1991]: eager marking, lazy evaluation. Notably, in parallel to our efforts, [Hammer et al. 2014] published our change propagation sheme.

namespace System
val x : 'a
val s : string
Multiple items
val string : value:'T -> string

Full name: Microsoft.FSharp.Core.Operators.string

--------------------
type string = String

Full name: Microsoft.FSharp.Core.string
val ( ...some implementation... ) : unit -> 'a

Full name: Adaptive-functional-programming.( ...some implementation... )
val failwith : message:string -> 'T

Full name: Microsoft.FSharp.Core.Operators.failwith
namespace System.IO
val gen' : path:string -> name:string -> m:'a -> unit

Full name: Adaptive-functional-programming.Visualization.gen'
val path : string
val name : string
val m : 'a
val dotFile : string
type Path =
  static val DirectorySeparatorChar : char
  static val AltDirectorySeparatorChar : char
  static val VolumeSeparatorChar : char
  static val InvalidPathChars : char[]
  static val PathSeparator : char
  static member ChangeExtension : path:string * extension:string -> string
  static member Combine : [<ParamArray>] paths:string[] -> string + 3 overloads
  static member GetDirectoryName : path:string -> string
  static member GetExtension : path:string -> string
  static member GetFileName : path:string -> string
  ...

Full name: System.IO.Path
Path.Combine([<ParamArray>] paths: string []) : string
Path.Combine(path1: string, path2: string) : string
Path.Combine(path1: string, path2: string, path3: string) : string
Path.Combine(path1: string, path2: string, path3: string, path4: string) : string
val sprintf : format:Printf.StringFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.sprintf
val target : string
val dotFile : obj
type Int32 =
  struct
    member CompareTo : value:obj -> int + 1 overload
    member Equals : obj:obj -> bool + 1 overload
    member GetHashCode : unit -> int
    member GetTypeCode : unit -> TypeCode
    member ToString : unit -> string + 3 overloads
    static val MaxValue : int
    static val MinValue : int
    static member Parse : s:string -> int + 3 overloads
    static member TryParse : s:string * result:int -> bool + 1 overload
  end

Full name: System.Int32
field int.MaxValue = 2147483647
val printfn : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn
val gen : n:string -> m:'a -> unit

Full name: Adaptive-functional-programming.Visualization.gen
val n : string
val ignore : value:'T -> unit

Full name: Microsoft.FSharp.Core.Operators.ignore
val init : v:'a -> 'a0

Full name: Adaptive-functional-programming.Mod'.init
val v : 'a
val constant : v:'a -> 'a0

Full name: Adaptive-functional-programming.Mod'.constant
val map : f:('a -> 'b) -> m:'a0 -> 'b1

Full name: Adaptive-functional-programming.Mod'.map
val f : ('a -> 'b)
val bind : f:('a -> 'a0) -> m:'b -> 'c

Full name: Adaptive-functional-programming.Mod'.bind
val f : ('a -> 'a0)
val m : 'b
val map2 : f:('a -> 'b -> 'c) -> m:'a0 -> m':'b1 -> 'c2

Full name: Adaptive-functional-programming.Mod'.map2
val f : ('a -> 'b -> 'c)
val m' : 'b
val change : r:'a -> newValue:'a0 -> unit

Full name: Adaptive-functional-programming.Mod'.change
val r : 'a
val newValue : 'a
type unit = Unit

Full name: Microsoft.FSharp.Core.unit
val transact : f:(unit -> 'a) -> 'a

Full name: Adaptive-functional-programming.Mod'.transact
val f : (unit -> 'a)
val force : m:'a -> 'a0

Full name: Adaptive-functional-programming.Mod'.force
val constantMod : obj

Full name: Adaptive-functional-programming.constantMod
val modRef1 : obj

Full name: Adaptive-functional-programming.modRef1
val mappedref : obj

Full name: Adaptive-functional-programming.mappedref
val dynamicDependency : m:'a -> cont:('a0 -> 'b) -> 'c

Full name: Adaptive-functional-programming.dynamicDependency
val cont : ('a -> 'b)
val g1 : obj

Full name: Adaptive-functional-programming.g1
val g2 : obj

Full name: Adaptive-functional-programming.g2
val s : obj

Full name: Adaptive-functional-programming.s
val g3 : obj

Full name: Adaptive-functional-programming.g3
val s : bool
val select : xs:seq<'a> -> f:('a -> 'b) -> seq<'b>

Full name: Adaptive-functional-programming.IEnumerable.select
val xs : seq<'a>
Multiple items
val seq : sequence:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Core.Operators.seq

--------------------
type seq<'T> = Collections.Generic.IEnumerable<'T>

Full name: Microsoft.FSharp.Collections.seq<_>
val selectMany : xs:seq<'a> -> f:('a -> seq<'b>) -> seq<'b>

Full name: Adaptive-functional-programming.IEnumerable.selectMany
val f : ('a -> seq<'b>)
val mode : obj

Full name: Adaptive-functional-programming.mode
val inputA : obj

Full name: Adaptive-functional-programming.inputA
val inputB : obj

Full name: Adaptive-functional-programming.inputB
val multiplyInputs : obj

Full name: Adaptive-functional-programming.multiplyInputs
val addInputs : obj

Full name: Adaptive-functional-programming.addInputs
val output : obj

Full name: Adaptive-functional-programming.output
module Visualization

from Adaptive-functional-programming
val output2 : obj

Full name: Adaptive-functional-programming.output2
val a : obj

Full name: Adaptive-functional-programming.a