HackerPapers

arXiv:1312.0658cs.PL

A Theory of Changes for Higher-Order Languages - Incrementalizing λ-Calculi by Static Differentiation

Yufei Cai, Paolo G. Giarrusso, Tillmann Rendel, Klaus Ostermann

Abstract

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.

arXiv comments
11 pages; unpublished preprint, under submission
Journal reference
DOI
Subjects
cs.PLProgramming Languages

On Hacker News

Linked by 3 identifiable commenters in 3 comments across 3 threads, from Nov 2018 to Aug 2020.

Comments linking this paper, per year.

Discussed in comments3 threads

  1. What Is the Minimal Set of Optimizations Needed for Zero-Cost Abstraction? 1 comment

    • 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]…

      benrbrayView on HNParent context

  2. Virtual DOM is pure overhead (2018) 1 comment

    • 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…

      markharperView on HNParent context

  3. Derivatives of Regular Expressions (2007) 1 comment

    • 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…

      cgrand-netView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.