miniAdapton
A Minimal Implementation of Incremental Computation in Scheme
Dakota Fisher

Matthew A. Hammer

arXiv:1609.05337v1 [] 17 Sep 2016

University of Colorado Boulder
first.last@colorado.edu

William Byrd

Matthew Might

University of Utah
Will.Byrd@utah.edu
might@cs.utah.edu

Abstract
We describe a complete Scheme implementation of miniAdapton, which implements the core functionality of the
Adapton system for incremental computation (also known
as self-adjusting computation). Like Adapton, miniAdapton
allows programmers to safely combine mutation and memoization. miniAdapton is built on top of an even simpler system, microAdapton. Both miniAdapton and microAdapton
are designed to be easy to understand, extend, and port to
host languages other than Scheme. We also present adapton
variables, a new interface in Adapton for variables intended
to represent expressions.

(define-memo (max-tree-path t)
(cond
((pair? t)
(if (> (max-tree (car t))
(max-tree (cdr t)))
(cons ’left (max-tree-path (car t)))
(cons ’right (max-tree-path (cdr t)))))
(else ’())))

Categories and Subject Descriptors D.1.1 [Programming
Techniques]: Applicative (Functional) Programming

(define some-tree ’((1 . 2) . (3 . 4)))

Keywords incremental computation, self-adjusting computation, Adapton, memoization, Scheme

1.

Observe that following the path returned by max-tree-path
should yield the value returned by max-tree.
Suppose that we also have a tree, some-tree:

For clarity, here is some-tree explicitly represented as a
tree:

Introduction

Memoization (Michie 1968) is a simple yet powerful optimization technique, avoiding redundancy in computation
to save considerable amounts of time. When used properly, memoization can achieve asymptotic speedup of many
algorithms. Amazingly, in some cases memoization can
even transform an exponential-time program into a lineartime program (Cormen et al. 2006). Unfortunately, although
memoization is an extremely powerful technique, it suffers
from a serious limitation: memoization does not work in the
presence of mutation.
Consider max-tree and max-tree-path, two memoized functions (see Appendix E for a complete definition of define-memo). Function max-tree finds the maximum number in a tree made of pairs and numbers and
max-tree-path finds the path from the root of the tree
to the maximum number.
(define-memo (max-tree t)
(cond
((pair? t)
(max (max-tree (car t))
(max-tree (cdr t))))
(else t)))

1

2 3

4

Now let’s consider a user session. First we ask for the
maximum value of any leaf node in some-tree:
> (max-tree some-tree)
4
This is what we expect, since the maximum number in the
tree is clearly 4.
Next we modify some-tree, replacing its entire righthand branch with the number 5.
> (set-cdr! some-tree 5)
> some-tree
((1 . 2) . 5)
And here is the updated explicit tree representation of
some-tree:

5
1

2

Once more we ask for the maximum number in the tree.

allows us to provide a simple and portable core and layer
user functionality on top of it. Inspired by microKanren,
microAdapton contains zero macros and fits in under 50
lines of source code. It avoids building Adapton’s Demanded Computation Graph, relegating it to be done by
miniAdapton, or manually if used directly, making for a
more flexible yet less immediately useful system.

> (max-tree some-tree)
4
This answer is no longer correct, since now the maximum
number in the tree is 5, not 4. In fact, 4 isn’t even in the tree
anymore! As soon as the user performs a single mutation in
the tree, our statements about the supposed behavior of the
program are promptly violated. Memoization cannot handle
mutation.
We can use max-tree-path, which determines the path
to the maximum value, to figure out what went wrong.

• miniAdapton (section 4): a complete implementation of

adapton, intended to provide a full Adapton system to the
user, including:
an interface to adaptons which automatically maintains Adapton’s Demanded Computation Graph (section 4.1);

> (max-tree-path some-tree)
(right)
> (max-tree (cdr some-tree))
5
Following max-tree-path to the cdr of the tree yields a
subtree containing a larger number than the entire tree!
In our implementation of memoization, shown in Appendix E, the problem is even worse, since the user has mutated the lookup key. Now every instance of ((1 . 2) . 5)
irreparably has the maximum number 4 somewhere in the
tree according to the function, which is apparently in the
path (right), where a 5 resides.
In order to make memoization work in the presence of
mutation, we must keep additional information about the
computation while also keeping track of the mutations which
have occured. Adapton (Hammer et al. 2014) is a system that
provides these capabilities, combining the flexibility of mutation with the potentially asymptotic speedup of memoization. Adapton is a form of incremental computation (sometimes called self-adjusting computation), an umbrella term
for techniques which take changing inputs and save time by
reusing previous results to compute new results for mutated
inputs (Acar et al. 2006).
Although Adapton reconciles memoization and mutation,
the complete code for an implementation of Adapton has
not appeared in the literature. In addition, Adapton implementations have focused on performance rather than on understandability, portability, or hackability. Inspired by microKanren (Hemann and Friedman 2013), which presented
a tiny, easily understandable implementation of the core of
the miniKanren programming language (Byrd and Friedman
2006), we have created microAdapton, a tiny, easily understandable implementation of the core of Adapton. Also in the
spirit of microKanren and miniKanren, we build a higherlevel interface, miniAdapton, on top of the microAdapton
core.
Our paper provides the first complete implementation of
a version of Adapton in the literature. More specifically, our
paper presents two small implementations of Adapton:
• microAdapton (section 3): a minimal substrate on which

to build the miniAdapton system, providing only the
barest interfaces to aid portability and readability. Separating miniAdapton into microAdapton and miniAdapton

functions and macros for function memoization (section 4.3);
a convenience macro for constructing elements of
adapton thunks representing expressions similar to
delay (section 4.2);
adapton variables: a new interface in Adapton for variables intended to represent expressions (section 4.4).
The code for these implementations is publicly available
here: https://github.com/fisherdj/miniAdapton

2.

Overview

Adapton, like memoization, stores the results of computation
so that it can avoid redundant computation. Memoization,
however, stores only the results, which means that even after
mutation, the computation cannot be restarted, and even
if it could, it might not be possible to figure out when it
needs to be restarted. Instead of storing just the results
of computations, Adapton stores their results, how it got
those results and a graph of the dependencies between those
computations. Then, whenever a value is mutated through
the Adapton interface, the computations depending on that
value are marked dirty to indicate that their computation
must be restarted. This lets Adapton keep many of the
benefits of memoization while still permitting mutation.
2.1

What is Adapton?

Adapton refers to a system for self-adjusting computation
by keeping track of computation at runtime. An adapton
thunk (or athunk) keeps track of any subcomputations it
needs to determine its value and any supercomputations that
need its value. The athunks maintain the property of Fromscratch Consistency, meaning that after modifying referenced mutable elements through Adapton, the result of forcing these thunks is the same as if one had computed them
from scratch. However, because athunks keep track of computation. they can avoid redundant re-computation, yielding
the potential speedup of memoization while retaining the capability of mutation (see (Hammer et al. 2014) for performance discussion).

Here athunks are mutable promises: they store a computation which may reference mutable objects in memory
(adapton-refs) and cache the result of the computation but
when forced will always return the same value as if computed from scratch. Other behaviors may be possible, but
this is the primary use case.

2.2

Supercomputation and Subcomputation

If a is some computation (an athunk), then a’s supercomputations are computations that depend on a, and a’s subcomputations are computations that a depends on. If b is a’s
subcomputation, then a is b’s supercomputation.

3.

microAdapton Implementation

The implementation of microAdapton operates primarily on
the adapton data structure, the datatype is defined as:
(define-record-type
(adapton adapton-cons adapton?)
(fields
thunk
(mutable result)
(mutable sub)
(mutable super)
(mutable clean?)))
The fields are:
thunk the computation to cache
result cached result of the computation

2.3

Demanded Computation Graph

sub set of subcomputations

The demanded computation graph or DCG is a graph representing the dependencies between computations and their
supercomputation/subcomputation relation. Each node of
the graph is a computation and each edge is a supercomputation/subcomputation relation. This implementation provided
uses inefficient implementations of sets and memoization,
which may hinder its performance (see Sections D and E for
discussion on speeding it up).
The figure below is a representation of the DCG for the
computation (max-tree some-tree) when some-tree is
modified from ((1 . 2) . (3 . 4)) to ((1 . 2) . 5).
Nodes represent athunks and edges represent supercomputation/subcomputation relationships: An edge exists from
node n to node m when n depends on m (i.e., this edge
represents that n is the supercomputation and m is one of its
subcomputations). Black nodes and edges represent portions
of the original graph, red nodes and edges represent portions
of the original graph which are dirtied or which propagate
dirtiness, and gray nodes and edges will be created when the
adapton is forced again later. Modifying some-tree dirties
the root node; when forced again it will create new thunks
for (max-tree ’((1 . 2) . 5)) and (max-tree 5)
to complete the computation. Although the root node still
points to (max-tree ’((1 . 2) . (3 . 4))), the edge
between the two is removed before the thunk is recomputed,
which regenerates the edge anew.
(max-tree some-tree)

some-tree

(max-tree '((1 . 2) . (3 . 4)))

(max-tree '(1 . 2))

(max-tree 1)

(max-tree 2)

(max-tree '((1 . 2) . 5))

(max-tree '(3 . 4))

(max-tree 3)

(max-tree 5)

(max-tree 4)

super set of supercomputations
clean? whether or not the cached result is valid
Function make-athunk constructs an athunk representing a thunk yet to be computed.
(define (make-athunk thunk)
(adapton-cons thunk
’empty
empty-set
empty-set
#f))
The first parameter of the constructor is the only parameter
of the make-athunk function. The result is arbitrarily set to
the symbol empty. The sub and super sets are both empty,
since this athunk is not yet placed in the DCG. Finally, the
athunk is not clean until after the thunk is computed, so
cleanliness is false.
Function adapton-add-dcg-edge! adds edges of the
DCG, and adapton-del-dcg-edge! removes edges of the
DCG, from their parameters a-super and a-sub.
(define (adapton-add-dcg-edge! a-super a-sub)
(adapton-sub-set!
a-super
(set-cons a-sub (adapton-sub a-super)))
(adapton-super-set!
a-sub
(set-cons a-super (adapton-super a-sub))))
(define (adapton-del-dcg-edge! a-super a-sub)
(adapton-sub-set!
a-super
(set-rem a-sub (adapton-sub a-super)))
(adapton-super-set!
a-sub
(set-rem a-super (adapton-super a-sub))))

Adding the DCG edge means connecting the athunks together by adding to their respective sub and super sets, while
removing the DCG edge means disconnecting the athunks
by removing their sub and super sets.
Function adapton-compute computes an athunk and
performs maintenance, returning the athunk’s value, and
keeping from-scratch consistency if the DCG is correctly
maintained:
(define (adapton-compute a)
(if (adapton-clean? a)
(adapton-result a)
(begin
(set-for-each
(lambda (x)
(adapton-del-dcg-edge! a x))
(adapton-sub a))
(adapton-clean?-set! a #t)
(adapton-result-set! a
((adapton-thunk a)))
(adapton-compute a))))
If the result is already available and valid, signified by the
athunk being clean, then that value is returned. Otherwise,
either because the result is not available or because the current result is invalid, additional maintanence must be performed. First, since computation is starting or restarting, all
subcomputation relations are invalid and the subcomputation
set must be removed. Second, the athunk must be marked
as clean. Third, the result of the computation must be computed and stored in the athunk. After this maintanence, we
restart computing the athunk, which may lead to restarting
the computation if the athunk has been marked dirty during
the computation. This maintains from-scratch consistency
in certain edge cases where mutation occurs within computation. The order of maintanence operations is important:
computing the result must be done after removing edges
to subcomputations and after marking the athunk as dirty.
Function adapton-compute is very sensitive to errors in the
DCG. If an edge is added to a dirty athunk as a subcomputation, changes will not propagate until that athunk is clean.
This is a direct consequence of Adapton’s lazy change propagation strategy: changes are indicated in the DCG, but the
changes themselves are not computed until forcing the corresponding athunks. Avoiding marking changes more than
once prevents redundant repeated traversal of large DCGs.
Function adapton-dirty! implements this change propagation strategy. It marks an athunk dirty along with all
supercomputations, under the assumption that the DCG is
correctly maintained so that any dirty subcomputations are
not subcomputations of clean nodes.
(define (adapton-dirty! a)
(when (adapton-clean? a)
(adapton-clean?-set! a #f)
(set-for-each adapton-dirty!

(adapton-super a))))
Calling adapton-dirty! on the immediate supercomputations of an athunk is sufficient for change propagation. Since
adapton-dirty! only recurses for an athunk marked clean,
calling adapton-dirty! twice or more on any one athunk
without computing it (and thus, cleaning it) between calls
traverses the graph only once.
Finally, we need to be able to create mutable cells. Function adapton-ref takes a value creates a new ref cell with
that value without needing to define an additional structure.
(define (adapton-ref val)
(letrec ((a (adapton-cons
(lambda () (adapton-result a))
val
empty-set
empty-set
#t)))
a))
Because it references itself, the ref can be set just by modifying the value in its cell. Since this invalidates supercomputations, one must also call adapton-dirty! to guarantee
from-scratch consistency. Function adapton-ref-set!
sets the value of the ref cell in its first parameter to the second parameter.
(define (adapton-ref-set! a val)
(adapton-result-set! a val)
(adapton-dirty! a))
Function adapton-ref-set! is the sole method of mutation provided.
The microAdapton interface exposes these functions:
adapton-compute, adapton-ref, adapton-ref-set!,
adapton?, make-athunk, adapton-add-dcg-edge!, and
adapton-del-dcg-edge!. All uses and users of microAdapton, including the higher-level miniAdapton interface,
must use this interface; modifying the DCG directly, without using the interface functions, may result in unspecified
or erroneous behavior.
(define r1 (adapton-ref 8))
(define r2 (adapton-ref 10))
(define a
(make-athunk
(lambda ()
(adapton-add-dcg-edge! a r1)
(adapton-add-dcg-edge! a r2)
(- (adapton-compute r1)
(adapton-compute r2)))))
> (adapton-compute a)
-2
> (adapton-ref-set! r1 2)
> (adapton-compute a)
-8

4.

miniAdapton: A Higher-level Interface

A user of microAdapton has all the tools they need to get the
benefits of from-scratch consistency and memoization. The
user must, however, build the DCG manually within computations. microAdapton provides only the low-level operations adding and removing edges for correct construction
and use of DCGs. This process is tedious, mechanical, potentially error-prone and should be avoided where possible.
Truly memoizing functions using athunks requires significant additional work: one has to use letrec to grab the
thunk to add it, and must reference the thunk inside the other
function. Thankfully, some extra interfaces can be made
readily available to the user which avoids these difficulties.
4.1

Essential Interface

The essential interface to miniAdapton is adapton-force,
a function that marks athunks as subcomputations if their
computation occurs during the computation of a different
athunk. Although using adapton-compute directly cannot
provide this, we can instead define adapton-force and use
it exclusively in place of adapton-compute, as shown in
this user session:
(define r (adapton-ref 5))
(define a
(make-athunk
(lambda ()
(+ (adapton-force r) 3))))
> (adapton-force a)
8
> (adapton-ref-set! r 2)
> (adapton-force a)
5
Here is the definition of adapton-force:
(define adapton-force
(let ((currently-adapting #f))
(lambda (a)
(let ((prev-adapting
currently-adapting))
(set! currently-adapting a)
(let ((result (adapton-compute a)))
(set! currently-adapting
prev-adapting)
(when currently-adapting
(adapton-add-dcg-edge!
currently-adapting
a))
result)))))
Function adapton-force keeps track of any Adapton computation that we are immediately in and, when called with a
single athunk argument, computes the result of its argument
and places the athunk in the DCG.

4.2

The adapt Form

A useful macro styled after delay takes expressions and turns
them into athunks. Translating our example for adaptonforce to use adapt:
(define r (adapton-ref 5))
(define a (adapt (+ (adapton-force r) 3))))
The adapt macro is straightforward, it takes an expression, wraps it in a thunk and then packages it with
make-athunk:
(define-syntax adapt
(syntax-rules ()
((_ expr)
(make-athunk (lambda () expr)))))
4.3

Memoization

Function adapton-force, paired with a memoization implementation (Appendix E), allows us to define two memoization procedures for Adapton. Here are max-tree (find
maximum number in tree) and max-tree-path from the introduction (find path to maximum number in tree) translated
into a variant utilizing Adapton:
(define-amemo (max-tree t)
(cond
((adapton? t)
(max-tree (adapton-force t)))
((pair? t)
(max (max-tree (car t))
(max-tree (cdr t))))
(else t)))
(define-amemo (max-tree-path t)
(cond
((adapton? t)
(max-tree-path (adapton-force t)))
((pair? t)
(if (> (max-tree (car t))
(max-tree (cdr t)))
(cons ’left
(max-tree-path (car t)))
(cons ’right
(max-tree-path (cdr t)))))
(else ’())))
The following functions are convienences for defining
memoized functions:
(define (adapton-memoize-l f)
(memoize (lambda x (adapt (apply f x)))))
(define (adapton-memoize f)
(let ((f* (adapton-memoize-l f)))
(lambda x (adapton-force (apply f* x)))))

The first function produces memoized functions returning athunks, where the “l” suffix means “lazy.” The second produces functions which are both memoized and
from-scratch consistent within the adapton system. Function adapton-memoize-l operates by memoizing a version of its function argument returning athunks. A standard implementation of memoization in conjunction with
the adapt form is sufficient to perform this task. Function adapton-memoize operates by taking the result of
adapton-memoize-l and making a new function equivalent except that it returns the result of forcing the athunk
instead of the athunk itself.
A small battery of convenience macros for memoization
are also useful to have. We have two macros for constructing
procedures with the syntax of lambda:
(define-syntax lambda-amemo-l
(syntax-rules ()
((_ (args ...) body ...)
(let ((f* (adapton-memoize-l
(lambda (args ...)
body ...))))
(lambda (args ...) (f* args ...))))))
(define-syntax lambda-amemo
(syntax-rules ()
((_ (args ...) body ...)
(let ((f* (adapton-memoize
(lambda (args ...)
body ...))))
(lambda (args ...) (f* args ...))))))
and two for defining procedures with the syntax of define:
(define-syntax define-amemo-l
(syntax-rules ()
((_ (f args ...) body ...)
(define f (lambda-amemo-l (args ...)
body ...)))))
(define-syntax define-amemo
(syntax-rules ()
((_ (f args ...) body ...)
(define f (lambda-amemo (args ...)
body ...)))))
4.4

(adapton-force r2))))
Notice that we force r1 to get the value of r2. Upfront, we
expect that r1 has 2 stored in it and r2 has 6 stored in it.
Now consider this user session:
> (adapton-force a)
8
> (adapton-ref-set! r1 10)
> (adapton-force a))
16
The first answer is not surprising, it corresponds to adding 2,
2 and 4 (8). After we set and force a, one might desire to get
the result of adding 10, 10 and 4 (24), but instead we get the
result of adding 10, 2 and 4 (16). This happens because r2
is a ref and retains its value instead of updating to match the
value of its expression. The final useful interfaces provided
are the “avar” macros and functions, short for “adapton variable.” Adapton variables provide the behavior of acting as
expressions rather than values:
(define-syntax define-avar
(syntax-rules ()
((_ name expr)
(define name
(adapton-ref (adapt expr))))))
(define (avar-get v)
(adapton-force (adapton-force v)))
(define-syntax avar-set!
(syntax-rules ()
((_ v expr)
(adapton-ref-set! v (adapt expr)))))
An avar is a variable representing an expression which can
be changed and will remain from-scratch consistent with
other changes. It is made of an adapton-ref that itself contains an athunk for the desired expression. Macro define-avar
defines an avar and assigns it an expression. Function avar-get
gets the value resulting from evaluating the avar’s expression, forcing the adapton ref to get the thunk and then
forcing that to actually obtain the value from the thunk.
Macro avar-set! sets the expression of an avar.
Here is our example again, translated to use avars:

Adapton Variables

Function adapton-ref-set! can be a somewhat unwieldy
interface, one can only set references equal to values, when
we might want to set those references to expressions instead.
Consider these definitions:
(define r1 (adapton-ref 2))
(define r2
(adapton-ref (+ (adapton-force r1) 4)))
(define a
(adapt (+ (adapton-force r1)

(define-avar v1 2)
(define-avar v2 (+ (avar-get v1) 4))
(define-avar b
(+ (avar-get v1) (avar-get v2)))
> (avar-get b)
8
> (avar-set! v1 10)
> (avar-get b))
24

This code is much easier to reason about, since we can get
the correct value by only looking at the expressions.
4.5

Putting it All Together: Extended Example

Now that we have all of miniAdapton available to us, we can
translate and extend the example of our introduction. Before
we do so, let’s define a new function to help us inspect trees
containing our new data structures:
(define (remove-adapton v)
(cond
((pair? v)
(cons (remove-adapton (car v))
(remove-adapton (cdr v))))
((adapton? v)
(remove-adapton (adapton-force v)))
(else v)))
This recursively takes any athunks in our structures and
replaces them with their values. Here are some avar definitions in addition to our original some-tree:
(define-avar lucky 7)
(define-avar t1 (cons 1 2))
(define-avar t2 (cons 3 4))
(define-avar some-tree
(cons (avar-get t1) (avar-get t2)))
Now our user session from the start:
> (avar-get some-tree)
((1 . 2) 3 . 4)
> (max-tree some-tree)
4
> (max-tree-path some-tree)
(right right)
So far, so good, but this is where the original broke last time.
We do the same thing, setting the cdr of some-tree to 5:
> (avar-set! t2 5)
> (avar-get some-tree)
((1 . 2) . 5)
> (max-tree some-tree)
5
> (max-tree-path some-tree)
(right)
> (max-tree (cdr (avar-get some-tree)))
5
> (max-tree-path (cdr (avar-get some-tree)))
()
The memoized functions are now reporting the correct results in spite of the mutation. In fact, we have even more
flexibility than our introduction example might suggest. We
can set our subtrees to expressions instead of values:
> (avar-set! t2
(cons 20 (* 3 (avar-get lucky))))
> (avar-get some-tree)

((1 . 2) 20 . 21)
> (max-tree some-tree)
21
> (max-tree-path some-tree)
(right right)
This is all as usual, t2 has the value (20 . 21).
> (avar-set! lucky 3)
> (avar-get some-tree)
((1 . 2) 20 . 9)
> (max-tree some-tree)
20
> (max-tree-path some-tree)
(right left)
Even in the presence of more complicated dependencies
of computation, from-scratch consistency is maintained. In
addition, the code is made easier to reason about, all the
properties that were lacking in our introductory example are
once again present.

5.

Related Work

Researchers have provided many language-based approaches
to incremental computation (Acar et al. 2006; Hammer
and Acar 2008; Acar and Ley-Wild 2009; Hammer et al.
2015). In particular, researchers have shown that for certain algorithms, inputs, and classes of input changes, IC
delivers large, even asymptotic speed-ups over full reevaluation (Acar et al. 2007, 2008). IC has been developed in
many different language settings (Shankar and Bodik 2007;
Hammer et al. 2007, 2009; Chen et al. 2014b), and has addressed open problems in computational geometry (Acar
et al. 2010).
Some PL approaches to IC are static, transforming programs to derive a second program that can process input
changes. Static approaches perform these transformations
a priori, before any dynamic changes. As such, static approaches are often lack the ability to transform general recursion or to fully cache and exploit dynamic dependencies (Liu
and Teitelbaum 1995; Liu et al. 1998; Cai et al. 2014).
In contrast to static approaches, dynamic approaches
attempt to trade space for time savings. A variety of dynamic approaches to IC have been proposed. Most early
approaches fall into one of two camps: they either perform function caching of pure programs (Bellman 1957;
McCarthy 1963; Michie 1968; Pugh 1988), or they support input mutation and employ some form of dynamic dependency graphs, along with a mechanism for performing
change propagation (Acar et al. 2004, 2006; Hammer and
Acar 2008; Acar and Ley-Wild 2009; Hammer et al. 2015).
Earlier work restricted programs to those expressible as attribute grammars (Demers et al. 1981; Reps 1982a,b; Vogt
et al. 1991). Various threads of research propose general
schemes for practical memoization, either making it applicable in more settings, or more efficient. Researchers have ex-

tended memoization to parallel C and C++ programs (Bhatotia et al. 2015) and to distributed, cloud-based settings
(Bhatotia et al. 2011), and have reduced the (often large)
space overhead (Chen et al. 2014a).

Umut A. Acar, Guy E. Blelloch, Kanat Tangwongsan, and Duru
Türkoğlu. Robust kinetic convex hulls in 3D. In Proceedings of
the 16th Annual European Symposium on Algorithms, September 2008.

6.

Umut A. Acar, Andrew Cotter, Benoı̂t Hudson, and Duru Türkoğlu.
Dynamic well-spaced point sets. In Symposium on Computational Geometry, 2010.

Conclusion

We have presented the complete implementation of microAdapton, a minimal system for incremental computation,
and the higher-level miniAdapton interface built on top of
it. Like full Adapton, microAdapton and miniAdapton allow
programmers to safely combine memoization and mutation.
Our approach of dividing our implementation into a
“mini”-level built on top a core “micro”-level is inspired
by microKanren and miniKanren. As with microKanren,
we take care to separate the hygienic macros in miniAdapton from the “micro” core. This separation, and the careful exposition of the microKanren code in Hemann and
Friedman (2013), has resulted in readers of that paper porting microKanren to several dozen languages in addition to
Scheme (Byrd). We hope that microAdapton and miniAdapton will make the ideas and implementation of incremental computation similarly accessible, and will also result in
readers porting the system to other languages and extending the system. One such extension would be to add cycle
detection for the DCG.

Acknowledgements
This material is partially based on research sponsored by
DARPA under agreement number AFRL FA8750-15-2-0092
and by NSF under CAREER grant 1350344. The views
expressed are those of the authors and do not reflect the
official policy or position of the Department of Defense or
the U.S. Government. The U.S. Government is authorized to
reproduce and distribute reprints for Governmental purposes
notwithstanding any copyright notation thereon.
We would also like to thank Jason Hemann and Dan
Friedman for their work on the original microKanren system, which was a significant inspiration for this paper.
We also thank the Scheme workshop reviewers for their
helpful comments.

References
Umut A. Acar and Ruy Ley-Wild. Self-adjusting computation with
Delta ML. In Proceedings of the 6th International Conference
on Advanced Functional Programming, AFP’08. 2009.
Umut A. Acar, Guy E. Blelloch, and Robert Harper. Adaptive memoization. Technical Report CMU-CS-03-208, Carnegie Mellon
University, November 2004.
Umut A. Acar, Guy E. Blelloch, Matthias Blume, Robert Harper,
and Kanat Tangwongsan. A library for self-adjusting computation. Electr. Notes Theor. Comput. Sci., 148(2):127–154, 2006.
Umut A. Acar, Alexander Ihler, Ramgopal Mettu, and Özgür
Sümer. Adaptive Bayesian inference. In Neural Information
Processing Systems (NIPS), 2007.

Richard Bellman. Dynamic Programming. Princeton Univ. Press,
1957.
Pramod Bhatotia, Alexander Wieder, Rodrigo Rodrigues, Umut A.
Acar, and Rafael Pasquin. Incoop: MapReduce for incremental
computations. In SOCC, 2011.
Pramod Bhatotia, Pedro Fonseca, Umut A. Acar, Björn B. Brandenburg, and Rodrigo Rodrigues. iThreads: A threading library
for parallel incremental computation. In ASPLOS, 2015.
William E. Byrd. minikanren.org (official miniKanren website).
http://minikanren.org/. Accessed: 2016-06-25.
William E. Byrd and Daniel P. Friedman. From variadic functions
to variadic relations: A miniKanren perspective. In Robby Findler, editor, Proceedings of the 2006 Scheme and Functional Programming Workshop, University of Chicago Technical Report
TR-2006-06, pages 105–117, 2006.
Yufei Cai, Paolo G. Giarrusso, Tillmann Rendel, and Klaus Ostermann. A theory of changes for higher-order languages: Incrementalizing λ-calculi by static differentiation. In PLDI, 2014.
Yan Chen, Umut A. Acar, and Kanat Tangwongsan. Functional
programming for dynamic and large data with self-adjusting
computation. In ICFP, 2014a.
Yan Chen, Joshua Dunfield, Matthew A. Hammer, and Umut A.
Acar. Implicit self-adjusting computation for purely functional
programs. J. Functional Programming, 24(1):56–112, 2014b.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and
Clifford Stein. Introduction to Algorithms. MIT Press, 2006.
Alan Demers, Thomas Reps, and Tim Teitelbaum. Incremental
evaluation of attribute grammars with application to syntaxdirected editors. In POPL, 1981.
Matthew Hammer and Umut A. Acar. Memory management for
self-adjusting computation. In ISMM, 2008.
Matthew Hammer, Umut A. Acar, Mohan Rajagopalan, and Anwar
Ghuloum. A proposal for parallel self-adjusting computation. In
Declarative Aspects of Multicore Programming, 2007.
Matthew A. Hammer, Umut A. Acar, and Yan Chen. CEAL:
a C-based language for self-adjusting computation. In ACM
SIGPLAN Conference on Programming Language Design and
Implementation, 2009.
Matthew A. Hammer, Khoo Yit Phang, Michael Hicks, and Jeffrey S. Foster. Adapton: Composable, demand-driven incremental computation. In PLDI, 2014.
Matthew A. Hammer, Joshua Dunfield, Kyle Headley, Nicholas
Labich, Jeffrey S. Foster, Michael Hicks, and David Van Horn.
Incremental computation with names. In OOPSLA, 2015.
Jason Hemann and Dan Friedman.
µkanren: A minimal functional core for relational programming, November 2013. URL http://www.schemeworkshop.org/2013/
papers/HemannMuKanren2013.pdf.

Yanhong A. Liu and Tim Teitelbaum. Systematic derivation of
incremental programs. Science of Computer Programming, 24
(1):1–39, 1995.
Yanhong A. Liu, Scott Stoller, and Tim Teitelbaum. Static caching
for incremental computation. ACM Transactions on Programming Languages and Systems, 20(3):546–585, 1998.
John McCarthy. A basis for a mathematical theory of computation.
In Computer Programming and Formal Systems, 1963.
Donald Michie. ”Memo” Functions and Machine Learning. Nature, 218(5136):19–22, April 1968.
William Pugh. Incremental Computation via Function Caching.
PhD thesis, Cornell University, 1988.
Thomas Reps. Generating Language-Based Environments. PhD
thesis, Cornell University, August 1982a.
Thomas Reps. Optimal-time incremental semantic analysis for
syntax-directed editors. In POPL, 1982b.
Ajeet Shankar and Rastislav Bodik. DITTO: Automatic incrementalization of data structure invariant checks (in Java). In Programming Language Design and Implementation, 2007.
Harald Vogt, Doaitse Swierstra, and Matthijs Kuiper. Efficient
incremental evaluation of higher order attribute grammars. In
PLILP, 1991.

A.

Complete microAdapton Implementation

This appendix presents the full code for microAdapton.
microAdapton requires an appropriate implementation of
sets—see Appendix D for a compatible set implementation
using lists, and a brief performance discussion.
(define-record-type
(adapton adapton-cons adapton?)
(fields
thunk
(mutable result)
(mutable sub)
(mutable super)
(mutable clean?)))
(define (make-athunk thunk)
(adapton-cons thunk
’empty
empty-set
empty-set
#f))
(define (adapton-add-dcg-edge! a-super a-sub)
(adapton-sub-set! a-super
(set-cons a-sub (adapton-sub a-super)))
(adapton-super-set! a-sub
(set-cons a-super (adapton-super a-sub))))
(define (adapton-del-dcg-edge! a-super a-sub)
(adapton-sub-set! a-super
(set-rem a-sub (adapton-sub a-super)))

(adapton-super-set! a-sub
(set-rem a-super (adapton-super a-sub))))
(define (adapton-compute a)
(if (adapton-clean? a)
(adapton-result a)
(begin
(set-for-each
(lambda (x)
(adapton-del-dcg-edge! a x))
(adapton-sub a))
(adapton-clean?-set! a #t)
(adapton-result-set! a
((adapton-thunk a)))
(adapton-compute a))))
(define (adapton-dirty! a)
(when (adapton-clean? a)
(adapton-clean?-set! a #f)
(set-for-each adapton-dirty!
(adapton-super a))))
(define (adapton-ref val)
(letrec ((a (adapton-cons
(lambda () (adapton-result a))
val
empty-set
empty-set
#t)))
a))
(define (adapton-ref-set! a val)
(adapton-result-set! a val)
(adapton-dirty! a))

B.

Complete miniAdapton Implementation

This appendix presents the full code for miniAdapton. miniAdapton requires a memoization implementation—see Appendix E for a compatible memoization implementation using association lists, and a brief performance discussion.
(define adapton-force
(let ((currently-adapting #f))
(lambda (a)
(let ((prev-adapting
currently-adapting))
(set! currently-adapting a)
(let ((result (adapton-compute a)))
(set! currently-adapting
prev-adapting)
(when currently-adapting
(adapton-add-dcg-edge!
currently-adapting
a))
result)))))

(define-syntax adapt
(syntax-rules ()
((_ expr)
(make-athunk (lambda () expr)))))
(define (adapton-memoize-l f)
(memoize (lambda x (adapt (apply f x)))))
(define (adapton-memoize f)
(let ((f* (adapton-memoize-l f)))
(lambda x (adapton-force (apply f* x)))))
(define-syntax lambda-amemo-l
(syntax-rules ()
((_ (args ...) body ...)
(let ((f* (adapton-memoize-l
(lambda (args ...)
body ...))))
(lambda (args ...) (f* args ...))))))
(define-syntax lambda-amemo
(syntax-rules ()
((_ (args ...) body ...)
(let ((f* (adapton-memoize
(lambda (args ...)
body ...))))
(lambda (args ...) (f* args ...))))))
(define-syntax define-amemo-l
(syntax-rules ()
((_ (f args ...) body ...)
(define f (lambda-amemo-l (args ...)
body ...)))))
(define-syntax define-amemo
(syntax-rules ()
((_ (f args ...) body ...)
(define f (lambda-amemo (args ...)
body ...)))))
(define-syntax define-avar
(syntax-rules ()
((_ name expr)
(define name
(adapton-ref (adapt expr))))))
(define (avar-get v)
(adapton-force (adapton-force v)))
(define-syntax avar-set!
(syntax-rules ()
((_ v expr)
(adapton-ref-set! v (adapt expr)))))

C.

Spreadsheet Example Redux

The motivating example for the original Adapton work
(Hammer et al. 2014) consists of a incremental “spreadsheet” evaluator, given as a simple interpreter, made incremental via use of the Adapton primitives. In this section, we
show that miniAdapton can also express this example.
In the original example, given in a variant of ML, the programmer specifies a data structure to represent expressions
that change over time, and a recursive function that evaluates
these expressions to their valuation. In this version, we do
not employ an explicit data structure representation for expressions; rather, we use the host Scheme evaluator in place
of this programmer-defined interpreter. This approach employs avars to hold (Scheme) expressions that can change
over time; in particular, avars hold suspended computations
that represent the formulae of the spreadsheet cells. In this
way, each avar is like a cell in a (very) simple spreadsheet.
Under this representation, we can encode the example from
the prior work as follows:
(define-avar
(define-avar
(define-avar
(define-avar
(define-avar

n1
n2
n3
p1
p2

1)
2)
3)
(+ (avar-get n1) (avar-get n2)))
(+ (avar-get p1) (avar-get n3)))

This code creates five cells in the spreadsheet, which hold
three constants (1, 2 and 3) and two sums over these (p1 and
p2).
With these bindings in place, we can encode the example
session as follows:
> (avar-get p1)
3
> (avar-get p2)
6
Because Adapton (and miniAdapton) are demand-driven,
the evaluation of p1 and p2 are suspended until they are
forced to execute, by the uses of avar-get above; these
operations compute their valuations, 3 and 6, respectively.
> (avar-set! n1 5)
> (avar-get p1)
7
Next, the user mutates an avar using avar-set!, and reobserves the valuation of avar-get. Meanwhile, the valuation of n2 is unaffected, and need not be recomputed. In
this case, n2 is merely a constant value, but if it were more
complex, this entire computation would still be reusable.
This demonstrates how miniAdapton allows memoization
and mutation to safely coexist.
As with Adapton, if the user decides to mutate the input by swapping expression trees, miniAdapton responds by
swapping their corresponding memoized sub-computations
behind the scenes:

> (avar-set! p2 (+ (avar-get n3) (avar-get p1)))
> (avar-get p2)
10
Finally, the following user interactions demonstrate how
miniAdapton permits memoization to benefit from switching, where the user updates avar p1, but then changes their
mind and reverts its expression:
> (avar-set! p1 4)
> (avar-get p2)
7
> (avar-set! p1 (+ (avar-get n1) (avar-get n2)))
> (avar-get p2)
10
In this case, the original computation (with p1 holding
(+ (avar-get n1) (avar-get n2))) is recovered from
the memoized cache.
By using Scheme’s evaluator, rather than a special language that we define (as in the original Adapton work),
our spreadsheet language can use primitives from Scheme,
rather than having to encode them. In effect, we acquire the
spreadsheet formulae language from Scheme, merely by using avars. As a simple example, we can immediately use
other primitives (like multiplication) without having to redefine their meaning for this spreadsheet language:
> (avar-set! p1 (* (avar-get n1) (avar-get n2)))
10
> (avar-get p2)
13
Doing the equivalent in the original paper would have required modifying the interpreter, but here, Scheme’s standard multiplication function suffices.

D.

Set Implementation

The microAdapton implementation in Appendix A requires
an implementation of sets. This appendix presents a minimal
but sufficient list-based set implementation which yields the
desired semantics. Most operations take linear time on average, which can cause microAdapton to run slowly when
adding or deleting edges in an athunk that has large numbers of ingoing or outgoing nodes. More efficient set representations include self-balancing trees and hashtables. Mutable set implementations are also compatible with the microAdapton implementation in Appendix A, provided the
microAdapton code is modified for the mutable interface.
(define empty-set ’())
(define (set-mem e s)
(memv e s))
(define (set-cons e s)
(if (set-mem e s) s (cons e s)))
(define (set-rem e s)
(filter (lambda (x) (not (eqv? e x))) s))

(define (set-union s1 s2)
(fold-left set-cons s2 s1))
(define (set-intersect s1 s2)
(fold-left set-rem s2 s1))
(define set-for-each for-each)
(define set->list (lambda (x) x))

E.

Memoization

This appendix presents an implementation of memoization,
compatible with the miniAdapton implementation in Appendix B.
(define (memoize f)
(let ((s (make-kv-store)))
(lambda x ; variadic memoization
(let ((k/v (lookup-kv-store s x)))
(if k/v
(cdr k/v)
(let ((result (apply f x)))
(add-kv-store! s x result)
result))))))
(define simple-memoization-test
(memoize (lambda x (read))))
(define-syntax lambda-memo
(syntax-rules ()
((_ (args ...) body ...)
(let ((f* (memoize
(lambda (args ...)
body ...))))
(lambda (args ...) (f* args ...))))))
(define-syntax define-memo
(syntax-rules ()
((_ (f args ...) body ...)
(define f (lambda-memo (args ...)
body ...)))))
The memoization code requires a key-value store implementation, such as this one, which uses association lists:
(define (make-kv-store) (list ’()))
(define (add-kv-store! s k v)
(set-car! s ‘((,k . ,v) . ,(car s))))
(define (lookup-kv-store s k)
(assoc k (car s)))
This key-value store implementation is inefficient, taking
linear time looking up any item not currently in the store. For
reasonable performance a more efficient key-value store implementation should be used. Most memoization implementations use hash tables, which typically take constant time
for most operations. In addition, our implementation uses
equal? (through assoc) where the more efficient pointer
equality tests eq? or eqv? might be preferred.

