package prbnmcn-cgrph

Cgraph: a simple library for incremental computation

Introduction

The API exposed by Cgraph allows to construct a DAG where nodes hold functions. Users describe computations using this API; the library ensures that upon change of input, only the minimal amount of computation has to be performed to update the output. See the work by Umut Acar et al, and others for more details.

Example

We illustrate the library by considering the toy problem of evaluating an arithmetic expression. We consider a very simple data type, with just addition and negation. Variables are represented by strings and we'll use a string map to represent the environment in which the expression is evaluated.

module String_map = Map.Make (String)

type expr = Var of string | Add of expr * expr | Neg of expr

In the rest, we'll consider the following expression, corresponding to (a + b) - (c + d).

let expr = Add (Add (Var "a", Var "b"), Neg (Add (Var "c", Var "d")))

In order to trace the evaluation of the naive vs incrementalized evaluators, we instrument addition and negation with printfs.

let ( + ) x y =
  Format.printf "%d + %d@." x y ;
  x + y

let ( - ) x =
  Format.printf "- %d@." x ;
  -x

The Non_incremental module defines a straightforward evaluator for our small language and evaluates it, changing the value of the variable "a" the second time.

let env l = String_map.of_seq (List.to_seq l)

module Non_incremental = struct
  let () = Format.printf "Non incremental computation@."

  let rec eval (env : int String_map.t) expr =
    match expr with
    | Var s -> String_map.find s env
    | Add (l, r) -> eval env l + eval env r
    | Neg e -> -eval env e

  let () = Format.printf "First evaluation@."

  let () =
    assert (eval (env [("a", 1); ("b", 2); ("c", 3); ("d", 4)]) expr = -4)

  let () = Format.printf "Second evaluation@."

  let () =
    assert (eval (env [("a", 3); ("b", 2); ("c", 3); ("d", 4)]) expr = -2)
end

Evaluating this piece of code prints the following:

    Non incremental computation
    First evaluation
    3 + 4
    1 + 2
    3 + -7
    Second evaluation
    3 + 4
    3 + 2
    5 + -7

Let's reiterate the experiment, using the library.

module Incremental = struct
  let () = Format.printf "Incremental computation@."

  open Cgraph

  let rec eval (env : int t String_map.t) expr =
    match expr with
    | Var s -> String_map.find s env
    | Add (l, r) -> map2 (eval env l) (eval env r) ( + )
    | Neg e -> map (eval env e) ( ~- )

  let (a, b, c, d) = (Var.create 1, Var.create 2, Var.create 3, Var.create 4)

  let graph =
    eval (env [("a", var a); ("b", var b); ("c", var c); ("d", var d)]) expr

  let () = Format.printf "First evaluation@."

  let () = assert (get graph = -4)

  let () = Var.set a 3

  let () = Format.printf "Second evaluation@."

  let () = assert (get graph = -2)
end

Here, instead of evaluating the expession, Incremental.eval builds a graph with inputs the variables a,b,c,d and output the node graph. We force the evaluation of a node by calling Cgraph.get on that node. This triggers the recursive evaluation of all and only the nodes which are not up to date.

Evaluating this piece of code prints the following:

    Incremental computation
    First evaluation
    1 + 2
    3 + 4
    3 + -7
    Second evaluation
    3 + 2
    5 + -7

Notice how the node that didn't need to be recomputed wasn't!

API documentation