Many researchers have proposed programming languages that support incremental computation (IC), which allows programs to be efficiently re-executed after a small change to the input. However, existing implementations of such languages have two important drawbacks. First, recomputation is oblivious to specific demands on the program output; that is, if a program input changes, all dependencies will be recomputed, even if an observer no longer requires certain outputs. Second, programs are made incremental as a unit, with little or no support for reusing results outside of their original context, e.g., when reordered.

To address these problems, we present λ^CDD_IC, a core calculus that applies a demand-driven semantics to incremental computation, tracking changes in a hierarchical fashion in a novel demanded computation graph. λ^CDD_IC also formalizes an explicit separation between inner, incremental computations and outer observers. This combination ensures λ^CDD_IC programs only recompute computations as demanded by observers, and allows inner computations to be reused more liberally. We present Adapton, an OCaml library implementing λ^CDD_IC. We evaluated Adapton on a range of benchmarks, and found that it provides reliable speedups, and in many cases dramatically outperforms state-of-the-art IC approaches.

[ .pdf ]

@inproceedings{hammer13adapton,
  author = {Matthew Hammer and Yit Phang Khoo and Michael Hicks and Jeffrey S. Foster},
  booktitle = {Proceedings of the {ACM} Conference on Programming Language Design and Implementation (PLDI)},
  title = {Adapton: Composable, Demand-Driven Incremental Computation},
  month = jun,
  year = 2014
}

This file was generated by bibtex2html 1.99.