Compiling Self-Adjusting Programs with Continuations

Ruy Ley-Wild, Matthew Fluet and Umut Acar

The 13th ACM SIGPLAN International Conference on Functional Programming (ICFP 2008)
Victoria, British Columbia, Canada, September 22-24, 2008

---

Abstract

Self-adjusting programs respond automatically and efficiently to input changes by tracking the dynamic data dependences of the computation and incrementally updating the output as needed. In order to identify data dependences, previously proposed approaches required the user to make use of a set of monadic primitives. However, rewriting an ordinary program into a self-adjusting program with these primitives can be difficult due to various monadic and proper-usage restrictions. It has therefore been suggested that self-adjusting computation would benefit from direct language and compiler support.

In this paper, we propose a language-based technique for writing and compiling self-adjusting programs from ordinary programs. To compile self-adjusting programs, we use a continuation-passing style (cps) transformation to automatically infer a conservative approximation of the dynamic data dependences. We ensure the efficient propagation of input changes by generating memoizing versions of cps functions that can reuse previous work even when they are invoked with different continuations. This approach offers a natural programming style that requires minimal changes to existing code, while statically enforcing the invariants required by self-adjusting computation.

We validate the feasibility of our proposal by extending Standard ML and by integrating the transformation into MLton, a whole-program optimizing compiler for Standard ML. Our experiments show that the compilation technique produces efficient self-adjusting programs that are consistent with the asymptotic bounds and experimental results obtained via manual rewriting.

---

START Conference Manager (V2.54.6)