Title | ||
---|---|---|
A theory of changes for higher-order languages: incrementalizing λ-calculi by static differentiation |
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. |
Year | DOI | Venue |
---|---|---|
2014 | 10.1145/2594291.2594304 | Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation |
Keywords | DocType | Volume |
whole computation,program transformation,derivative maps change,original program,chosen primitive,nontrivial program,higher-order language,static differentiation,case study,expensive computation,base type,old result,first class functions,performance | Conference | abs/1312.0658 |
Citations | PageRank | References |
15 | 0.58 | 14 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Yufei Cai | 1 | 21 | 1.43 |
Paolo G. Giarrusso | 2 | 271 | 9.97 |
Tillmann Rendel | 3 | 392 | 16.15 |
Klaus Ostermann | 4 | 457 | 23.97 |