按年被提到
20132018 · 1 次2026
编程语言与编译器›类型系统与函数式语言·arXiv:1312.0658 · cs.PL

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

高阶语言的变化理论:通过静态微分对 λ 演算做增量化
Yufei Cai, Paolo G. Giarrusso, Tillmann Rendel, Klaus Ostermann · 2013

用静态程序变换求出程序的导数,让结果随输入变化而增量更新

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 3 人首次 2018-11-12 · 最近 2020-08-07
3不同的人
3活跃月份
3讨论串
5被引(OpenAlex)

论文用「导数」把程序增量化:导数把输入的变化直接映射为输出的变化,无需重新执行原程序。作者提出一种完全静态、自动的程序变换,支持一等函数,产生的导数还可以套用标准优化;该变换在 Agda 中对一族简单类型 λ 演算证明了正确性,并在 Scala 中实现,在一个非平凡程序上把性能提升了数量级。

HN 为什么提它

评论者在讨论增量计算、增量解析和编译时,把它当作与增量 λ 演算相关的参考文献,用来指出类似思路已有理论基础。

方法难度 5 / 5约 120 分钟经得起时间
读之前最好知道
1λ 演算(lambda calculus)
2简单类型系统(simply-typed lambda calculus)
3程序变换与函数式编程
4Agda 等证明助手基础
5增量计算(incremental computation)

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
引用cgrand-net · 2018-11

“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.”

引述摘要:把程序变换为其导数的静态自动程序变换
Derivatives of Regular Expressions (2007)原评论 ↗
引用markharper · 2019-05

“That sounds similar to the incremental lambda calculus described in this paper: A Theory of Changes for Higher-Order Languages - Incrementalizing λ-Calculi by Static Differentiation”

说这与论文中的 incremental lambda calculus 类似
Virtual DOM is pure overhead (2018)原评论 ↗
引用benrbray · 2020-08

“I've seen quite a few papers relating to incremental parsing, compilation, etc. (e.g. [1,2])”

把它列入与增量解析、编译相关的论文之中
What Is the Minimal Set of Optimizations Needed for Zero-Cost Abstraction?原评论 ↗