User:MatthewHammer/Incremental computing

Incremental computing, also known as incremental computation (IC) consists of software techniques that exploit the dependency structure of a computer program as its input changes over time. The goal of IC is to update the salient output of a program quickly and avoid redundant re-computation. When IC is successful, it can be significantly faster than computing new outputs naively.

For example, spreadsheet software packages commonly use incremental computation to selectively update cells whose formula depend on other cells that change, while avoiding the re-computation of cells that are not affected by changes.

Programming Models

Various programming models have been proposed for creating incremental computations. They vary in their generality, and in what they require from the programmer.

Explicit versus Implicit

Different IC approaches vary in what they require from the programmer. Explicit approaches require the programmer to specify how data-structures are permitted to change over time, and provide special abstractions to work with such data. By contrast, Implicit approaches permit the programmer to eschew these details, and program in a more conventional manner.

Implementation Techniques

The efficient implementation of incremental computations often leverage either a form of dependency graphs, or a form of memoization, or some combination of both techniques.

Related concepts

Incremental computation is related to other software concepts, such as reactive systems and partial evaluation.

Reactive systems

Reactive systems often use incremental computing techniques to increase their responsiveness. Spreadsheet software gives an everyday example.

See also:

• Dataflow programming
• Functional reactive programming

Partial Evaluation

Partial evaluation stages computations whose inputs can be divided into two classes: those that are fixed for all time and known a priori ("static") and those that may change over time, from one run to the next ("dynamic"). Incremental computing is more general than partial evaluation. In particular, IC techniques do not assume the presence of "static" inputs that are known a priori.