增量计算

增量计算（英語：Incremental computing），又称增量计算法，是一种软件特性。当部分数据变化时，增量计算试图仅重新计算那些依赖于变化的数据的输出，以节省计算时间。^[1]^[2]^[3] 相比于简单地重新计算完整的输出内容，增量计算能够显著地节省计算时间。比如，电子表格的重计算功能可能会采用增量计算的方式，只有当单元格含有的公式直接或间接依赖于发生变化的其他单元格时，该单元格才会被更新。

当一个工具能够自动地为各种不同的代码实现增量计算时，该工具可被视为一种用于优化的程序分析工具。

静态实现和动态实现[编辑]

增量计算在技术实现上可以大致分为两种类型：

静态方法 试图从现有的程序P中派生出一个增量计算程序。例如可以采取进行程序的重新设计、程序重构的手段，或者使用工具自动生成增量计算程序。这种程序的转换需要发生在输入或是输入的变化量出现之前。

动态方法 记录运行中的程序P在接受某个特定输入（l1）时的信息。当这P接受另一个输入（l2）时，把这些信息用于计算并更新输出结果（从O1变化到O2）。图示中显示了：程序P；构成增量计算程序的核心的变化量计算函数ΔP；以及两组输入和输出（I1，O1和I2，O2）。

专用实现和通用实现[编辑]

某一些实现增量计算的方法是只适用于特定程序的专用实现方法，但也有一些可以普遍适用于任何程序的通用方法。专用实现方法需要程序员特别指定用于保存未修改子计算的算法和数据结构。通用实现方法则会使用编程语言特性、编译器功能或者一些算法来给非增量计算程序赋予增量计算的行为。

现有系统[编辑]

编译器与编程语言支持[编辑]

自动增量化（也称“自调节计算”和“适应性函数式计算”）^[4]
康奈尔合成器生成器^[5]
IceDust （页面存档备份，存于互联网档案馆） - 定制化的领域特定语言（DSL）

框架与程序库[编辑]

Adapton （页面存档备份，存于互联网档案馆）
Jane Street Incremental （页面存档备份，存于互联网档案馆）

应用[编辑]

数据库（视图维护）
软件构建系统
电子表格^[6]
软件开发环境
金融计算
属性文法分析
图计算和查询
GUI （例如 React 和 DOM diffing）
科学计算应用程序

另请参阅[编辑]

参考文献[编辑]

^ Carlsson, Magnus. Monads for incremental computing. Proceedings of the seventh ACM SIGPLAN international conference on Functional programming - ICFP '02 (Pittsburgh, PA, USA: ACM Press). 2002: 26–35. ISBN 9781581134872. doi:10.1145/581478.581482 （英语）.
^ Umut A. Acar (2005). Self-Adjusting Computation （页面存档备份，存于互联网档案馆） (PDF)(Ph.D. thesis).
^ Demetrescu, Camil; Finocchi, Irene; Ribichini, Andrea. Reactive imperative programming with dataflow constraints. Proceedings of the 2011 ACM international conference on Object oriented programming systems languages and applications - OOPSLA '11 (Portland, Oregon, USA: ACM Press). 2011: 407. ISBN 9781450309400. doi:10.1145/2048066.2048100 （英语）.
^ Hammer, Matthew A.; Acar, Umut A.; Chen, Yan. CEAL: a C-based language for self-adjusting computation. Proceedings of the 2009 ACM SIGPLAN conference on Programming language design and implementation - PLDI '09 (Dublin, Ireland: ACM Press). 2009: 25. ISBN 9781605583921. doi:10.1145/1542476.1542480 （英语）.
^ Reps, Thomas; Teitelbaum, Tim. The synthesizer generator. Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments - SDE 1 (Not Known: ACM Press). 1984: 42–48. ISBN 9780897911313. doi:10.1145/800020.808247 （英语）.
^ Hammer, Matthew; Phang, Khoo; Hicks, Michael; Foster, Jeffrey (2014). ADAPTON: Composable, Demand-Driven Incremental Computation （页面存档备份，存于互联网档案馆） (PDF). PLDI.

[1] Carlsson, Magnus. Monads for incremental computing. Proceedings of the seventh ACM SIGPLAN international conference on Functional programming - ICFP '02 (Pittsburgh, PA, USA: ACM Press). 2002: 26–35. ISBN 9781581134872. doi:10.1145/581478.581482 （英语）.

[2] Umut A. Acar (2005). Self-Adjusting Computation （页面存档备份，存于互联网档案馆） (PDF)(Ph.D. thesis).

[3] Demetrescu, Camil; Finocchi, Irene; Ribichini, Andrea. Reactive imperative programming with dataflow constraints. Proceedings of the 2011 ACM international conference on Object oriented programming systems languages and applications - OOPSLA '11 (Portland, Oregon, USA: ACM Press). 2011: 407. ISBN 9781450309400. doi:10.1145/2048066.2048100 （英语）.

[4] Hammer, Matthew A.; Acar, Umut A.; Chen, Yan. CEAL: a C-based language for self-adjusting computation. Proceedings of the 2009 ACM SIGPLAN conference on Programming language design and implementation - PLDI '09 (Dublin, Ireland: ACM Press). 2009: 25. ISBN 9781605583921. doi:10.1145/1542476.1542480 （英语）.

[5] Reps, Thomas; Teitelbaum, Tim. The synthesizer generator. Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments - SDE 1 (Not Known: ACM Press). 1984: 42–48. ISBN 9780897911313. doi:10.1145/800020.808247 （英语）.

[6] Hammer, Matthew; Phang, Khoo; Hicks, Michael; Foster, Jeffrey (2014). ADAPTON: Composable, Demand-Driven Incremental Computation （页面存档备份，存于互联网档案馆） (PDF). PLDI.

[1]

[2]

[3]

[4]

[5]

[6]