Implementing Implicit Self-Adjusting Computation

Computational problems that involve dynamic data have been an important subject of study in programming languages. Recent advances in self-adjusting computation have developed techniques that enable programs to respond automatically and efficiently to dynamic changes in their inputs. But these techniques have re-quired an explicit programming style, where the programmer must use specific monadic types and primitives to identify, create and operate on data that can change over time. Our paper, “Implicit Self-Adjusting Com-putation for Purely Functional Programs ” (ICFP ’11), describes the theory underlying implicit self-adjusting computation, where the programmer need only annotate the (top-level) input types of the programs to be translated. A type-directed translation rewrites the (purely functional) source program into an explicitly self-adjusting target program. The subject of this talk is a prototype implementation (an extension of MLton) and experimental results that are competitive with explicitly self-adjusting handwritten code. 2 Implicit Self-Adjusting Computation In self-adjusting computation, programs respond efficiently to changes in their input. The parts of the computation that could be affected by such changes are changeable; the parts that cannot be affected are stable. (Not all of a program’s input need be changeable, but if we actually change the “stable ” part of the input, we must run the program from scratch.