What React, Excel, and build systems have in common

A spreadsheet, a build, and a user interface all contain results derived from inputs. When those inputs change, the results need updating. Reactivity connects input changes to updates of dependent results. Incremental computation reuses previous work to obtain updated results.¹

These are separate concerns. A view can react to every change by recomputing everything. Conversely, a build launched on demand can reuse previous work without automatically starting whenever a file changes. The common problem is maintaining derived results; propagation determines how changes reach them, and incrementality determines how much computation can be saved.

Propagate changes through dependencies

Consider a spreadsheet with a unit price in A1, a quantity in A2, a subtotal $\mathrm{B1} = \mathrm{A1} \times \mathrm{A2}$, and a total including tax $\mathrm{C1} = \mathrm{B1} \times 1.1$. Changing the quantity can affect the subtotal and therefore the total. It has no effect on a separate calculation that reads neither those cells nor anything derived from them.

The references establish a dependency graph. An edge from an input to a result records that the result depends on that input. Following these edges from a changed cell identifies results that may be stale. Marking them as needing validation or recomputation is invalidation. Excel marks dependent cells dirty and recalculates them in dependency order. The subtotal must be current before the total is recomputed from it. Knowing what depends on what enables the system to propagate a change through the calculations without the user updating each result by hand.

Dependencies also change. Editing a formula changes its references; taking a different branch can change what a computation reads. Maintaining the graph is part of maintaining the results.

React carries state changes through to the view: a state update triggers rendering, and React commits the necessary DOM changes. This is reactivity even when deriving the updated view requires rerunning component functions.

Reuse the work that remains valid

Once the system knows which results a change may affect, it can reuse the others. For deterministic computations over a given set of inputs, the correctness target is the result a fresh computation would produce. The optimization is in how much work must be repeated to obtain it. Smaller units and finer tracking also add storage and bookkeeping; incrementality is not automatically cheaper than a fresh run.

The graph must account for every input whose change could alter a reused result. A missing dependency can leave a stale answer; an unnecessary dependency causes extra work. If a computation reads a file, the clock, or changing global state, those inputs need to participate in validity checking too, or reuse must be restricted. Pure computations make this contract explicit: their results depend on their input values alone.

An affected computation can still produce the same result. Bazel's documentation illustrates this with a comment edit in a C++ source file:

The compiler had work to do, but if its output is unchanged, the linker's input is unchanged too. Bazel calls this change pruning: recomputing an affected result can establish that downstream work remains valid.

Reuse can also happen within an affected result. Instead of rerunning its computation from scratch, a specialized algorithm can update it from a delta—a change to its inputs.

A B-tree index is a familiar example. Inserting a row adds an index entry without rebuilding the index from the entire table. PostgreSQL maintains indexes automatically when their tables change. The table is the input; the index is a derived structure maintained along with it.

The systems differ, but the questions remain the same: what depends on the changed input, and what previous work is still valid? Tracking those relationships lets a spreadsheet, a user interface, or a build stay current while preserving work that needn’t be repeated.

Footnotes

1. For a research approach to automating this reuse, see Umut Acar’s overview of self-adjusting computation. ↩