Incremental Computation: What Is the Essence? (Invited Contribution)
summary
Argues that the core idea is incrementalization = discrete differentiation: transform programs to reuse previous results and treat input changes explicitly, yielding provable complexity gains (e.g., Fibonacci becomes constant time per increment). Presents a systematic recipe Iterate-Incrementalize-Implement and concrete techniques—caching + change propagation, program transformations, rule/set abstractions—and reports implemented systems and semantic methods that produce new algorithms with improved complexities and practical distributed and constraint-solving applications.
AI-written summary · about
chapters (8)
- 0:00Introduction
- 1:24Incremental computation overview
- 3:31Three categories
- 9:20Essence of incrementalization
- 14:34Systematic method
- 17:54Optimization via incrementalization
- 20:19Power of higher-level instructions
- 21:46Q&A
related talks
15mIncremental Certified Programming
15mIncremental Data Architecture
43mHow to Innovate in a Legacy
01h 28mA Galilean revolution for computing
14mIncr: Faster Re-Execution via Bolt-On Incrementalization
01h 25mCreating an Incremental Architecture for your System
16mTermination Analysis for Evolving Programs: An Incremental Approach by Reusing Certified Modules
47mRefactor Without Breaking Everything: Anatomy of Incremental Modernization Patterns