Incremental Computation Graphs

How to compute and invalidate computation graphs

2026-04-23

rev. 2026-04-23(8 hours ago)

draft ◑likely ★5/10 848w ~4m #computation #learning

contents

referenced from

❦Yabu - 藪

Abstract

Overview of computation graphs

I learned this as part of my work on Yabu. There I need to work recompile, regenerate code and type-check at interactive speeds.

You have two main things in the algorithm:

For example, in the case of Yabu an input would be the function definition. Let’s say you already have an image and you redefine a function.

(defun some-func ((a int) (b int)) int (+ a b))

The source string of this function would become an input and then from there you have defined several pure computations.

For example we can have a parse function, it depends on the source input and returns the AST of the source. Because this is a pure function, if the input hasn’t changed we can just return the memoized AST without having to re-parse it.

(define-computation parse (source) (yabu:parse source))

Now this gets interesting once you start composing computations, this looks very similar to regular functions calls except these internally keep track of which computations you are calling. Creating a runtime-graph of dependent computations. We’ll use this graph later to invalidate computations once inputs change.

(define-computation compile (source) (let* ((typecheck-result (typecheck source))) (if (errorp typecheck-result) typecheck-result (yabu:compile ast))))

NOTE: This is not a correct compile function for Yabu, because you are only checking if this function typechecks against the rest of the functions not if the rest of the functions typecheck against this function. We are also skipping around some complications around the staging system.

You can check the real algorithm at Yabu Incremental Typesystem

Here parse, typecheck and compile are all computations. These create a runtime graph where we see that compile <source> depends on typecheck, which will in turn probably depend on parse and it will probably depend on another computation type-signature for all of the functions the AST calls.

compile(source) ----. | v parse(source) <------ typecheck(ast) | .------------------------+------------------------. v v v type-signature(f_1) type-signature(f_2) ... type-signature(f_N)

Now if f_1 changes type signature, automatically the typecheck of this function will get invalidated! This invalidation is key to make the Yabu typechecker very fast for interactive use even in large programs.

Each memoization entry stores several things:

For each dependency we track also what was the changed-at revision of the dependency when we depended on it.

So let’s see an example, we just redefined some-func as above and we call (compile "<source>"), this is a new source so there is no memoization for this, we execute the computation function. We call typecheck, since this is a new source this doesn’t exist either, that depends on parse which also doesn’t exist, that creates one memoization entry:

(:key '(parse source) :return <ast> :verified-at :R7 :changed-at :R7 :dependency-list '((:input source)))

We then check type-signature for + with is (-> (int int) int) with a :verified-at and :changed-at of R1 (this is stdlib, so it was populated at the start of the session). Since R1 is less than R7, it may be outdated and we need to check the dependencies of (type-signature +). That depends on the source of + which also has a revision of R1. Since the revision of the memoization and the revision of its dependency are equal we consider it fresh and we update the :verified-at for (type-signature +) to the current revision of R7.

The typecheck passes so we memoize that as well and create an entry like

(:key '(typecheck source) :return <pass|fail> :verified-at :R7 :changed-at :R7 :dependency-list '((parse source) (type-signature +))')

It’s important here to note when we consider something fresh:

You always need to walk the dependency chain until you bottom out at the inputs or you have already validated the subtree this revision.

During the walk as you come up the recursion you update all :verified-at to current-revision so any other computation in this revision short-circuits.

Next time, if we reevaluate typecheck over the same source we’ll recurse through the graph, arrive at the same input, check that it hasn’t changed, go upwards the computation tree, updated :validated-at and skip typechecking and compiling altogether.