Yufei Cai, Paolo G. Giarrusso, Tillmann Rendel, Klaus Ostermann
2013 · arXiv
If the result of an expensive computation is invalidated by a small change to the input, the old result should be updated incrementally instead of reexecuting the whole computation. We incrementalize programs through their derivative. A derivative maps changes in the program's input directly to changes in the program's output, without reexecuting the original program. We present a program transformation taking programs to their derivatives, which is fully static and automatic, supports first-class functions, and produces derivatives amenable to standard optimization. We prove the program transformation correct in Agda for a family of simply-typed λ-calculi, parameterized by base types and primitives. A precise interface specifies what is required to incrementalize the chosen primitives. We investigate performance by a case study: We implement in Scala the program transformation, a plugin and improve performance of a nontrivial program by orders of magnitude.
Metadata: arXiv. Abstracts retain their original authors’ rights.
Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels
3 selected excerpts · 3 total mentions
I think this is an area where practice has lagged quite far behind theory (for entirely reasonable practical reasons). I've seen quite a few papers relating to incremental parsing, compilation, etc. (e.g. [1,2]) but afaik very few build systems actually take advantage. [1] https://arxiv.org/abs/1312.0658 [2] https://blog.functorial.com/posts/2018-04-08-Incrementally-I...
That sounds similar to the incremental lambda calculus described in this paper: https://arxiv.org/abs/1312.0658 There's an implementation for DOM updates in Purescript (https://blog.functorial.com/posts/2018-04-08-Incrementally-I...), but I haven't come across a similar approach in Javascript yet.
A Theory of Changes for Higher-Order Languages - Incrementalizing λ-Calculi by Static Differentiation > [...] We present a program transformation taking programs to their derivatives, which is fully static and automatic, supports first-class functions, and produces derivatives amenable to standard optimization. https://arxiv.org/abs/1312.0658
More from the same topics.
Haoran Xu, Fredrik Kjolstad
Fast compilation is important when compilation occurs at runtime, such as query compilers in modern database systems and WebAssembly virtual machines in modern browsers.
David Manheim, Scott Garrabrant
There are several distinct failure modes for overoptimization of systems on the basis of metrics.
Donald E. Knuth
The author presents two tricks to accelerate depth-first search algorithms for a class of combinatorial puzzle problems, such as tiling a tray by a fixed set of polyominoes.
Jon Kleinberg, Sendhil Mullainathan, Manish Raghavan
Recent discussion in the public sphere about algorithmic classification has involved tension between competing notions of what it means for a probabilistic classification to be fair to different groups.