|START Conference Manager|
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)