# 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.

 1:  let modRef1 = Mod.init 10 

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

 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.

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:

 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:

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

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

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

val n : string
val ignore : value:'T -> unit

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

val v : 'a
val constant : v:'a -> 'a0

val map : f:('a -> 'b) -> m:'a0 -> 'b1

val f : ('a -> 'b)
val bind : f:('a -> 'a0) -> m:'b -> 'c

val f : ('a -> 'a0)
val m : 'b
val map2 : f:('a -> 'b -> 'c) -> m:'a0 -> m':'b1 -> 'c2

val f : ('a -> 'b -> 'c)
val m' : 'b
val change : r:'a -> newValue:'a0 -> unit

val r : 'a
val newValue : 'a
type unit = Unit

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

val f : (unit -> 'a)
val force : m:'a -> 'a0

val constantMod : obj

val modRef1 : obj

val mappedref : obj

val dynamicDependency : m:'a -> cont:('a0 -> 'b) -> 'c

val cont : ('a -> 'b)
val g1 : obj

val g2 : obj

val s : obj

val g3 : obj

val s : bool
val select : xs:seq<'a> -> f:('a -> 'b) -> seq<'b>

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>

val f : ('a -> seq<'b>)
val mode : obj

val inputA : obj

val inputB : obj

val multiplyInputs : obj