Abstract

Incremental computation aims to compute more efficiently on changed input by reusing previously computed results. We give a high-level overview of works on incremental computation, and highlight the essence underlying all of them, which we call incrementalization—the discrete counterpart of differentiation in calculus. We present the gist of a systematic method for incrementalization, and a systematic method centered around it—called Iterate-Incrementalize-Implement—for program design and optimization, as well as algorithm design and optimization. We illustrate the methods with example applications in arithmetic computations, recursive functions, graph analysis, and distributed algorithms. At a meta-level, with historical contexts and for future directions, we stress the power of high-level data, control, and module abstractions in developing new and better algorithms and programs as well as their precise complexities.

Incremental Computation: What Is the Essence?

As the real world changes continually, computer programs that handle input from the real world must handle continually changing input. Furthermore, because any algorithm that solves a nontrivial problem must proceed in an iterative or recursive fashion, computations must be performed on a repeatedly changed state. The general area of incremental computation studies how to efficiently handle continually changing input by storing and reusing previously computed results. The problem is fundamental and ubiquitous, from graph algorithms to database queries, and from program analysis to neural network training, including everything nontrivial.

In this monograph, a high-level overview of works on incremental computation are presented, and the essence underlying all of them is highlighted. This is called incrementalization — the discrete counterpart of differentiation in calculus. Presented is the gist of a systematic method for incrementalization, and a systematic method centered around it — called Iterate-Incrementalize Implement — for program design and optimization, as well as algorithm design and optimization. Also illustrated are methods with example applications in arithmetic computations, recursive functions, graph analysis, and distributed algorithms. At a meta-level, with historical contexts and for future directions, the power of high-level data, control, and module abstractions in developing new and better algorithms and programs as well as their precise complexities are stressed.