Incremental Computation Graphs

Abstract Overview of computation graphs Background I learned this as part of my work on Yabu. There I need to work recompile, regenerate code and type-check at interactive speeds. The implementation is based on Salsa Main Ideas You have two main things in the algorithm: Inputs, mutable, the only source of external change. The system sets these and then consumes from: Computations, pure functions of inputs or other computations, these are memoized and invalidated by the red-green walk. 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 …