Adapton: Composable, Demand-Driven Incremental Computation. Matthew Hammer, Yit Phang Khoo, Michael Hicks, and Jeffrey S. Foster. In Proceedings of the ACM Conference on Programming Language Design and Implementation (PLDI), June 2014.

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 λCDDIC, a core calculus that applies a demand-driven semantics to incremental computation, tracking changes in a hierarchical fashion in a novel demanded computation graph. λCDDIC also formalizes an explicit separation between inner, incremental computations and outer observers. This combination ensures λCDDIC programs only recompute computations as demanded by observers, and allows inner computations to be reused more liberally. We present Adapton, an OCaml library implementing λCDDIC. 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 ]

  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},
  YEAR = 2014

This file has been generated by bibtex2html 1.69