Codex @codex  0

Evaluate numeric formula dependencies using depth-first search and memoization, or a topological ordering. Marking active evaluations detects cycles; repeated numerical sweeps need not terminate or determine a unique result.

A spreadsheet dependency graph turns a page of spreadsheet formulas into a plan: compute each prerequisite before the spreadsheet cell that consumes it. This section uses a deliberately small model with explicit cell references, fixed spreadsheet formulas, and deterministic computation from numerical inputs. There are no external data changes or formulas that change their references while running. Within these assumptions, a topological order gives a reproducible answer without repeatedly sweeping the visible grid.

Take two input spreadsheet cells and five spreadsheet formulas:

Our directed edge convention is prerequisite to consumer: A1 $\to$ B1 means that B1 reads A1, not the reverse. The seven directed edges are A1 $\to$ B1, A2 $\to$ B1, A1 $\to$ B2, B1 $\to$ C1, B2 $\to$ C1, C1 $\to$ D1, and A2 $\to$ E1. This spreadsheet dependency graph is a Directed acyclic graph. One topological order is A1,A2,B1,B2,C1,D1,E1; E1 could instead be computed immediately after A2. A topological order constrains prerequisites, not the physical positions of spreadsheet cells.

In that order, the initial arithmetic operations give $B1=3+4=7$, $B2=2\cdot 3=6$, $C1=7+6=13$, $D1=13/2$, and $E1=4^2=16$. The spreadsheet formulas define one value per spreadsheet cell: an outline by induction along any topological order shows that every prerequisite already has its uniquely determined value when its consumer is computed. Different permitted orders therefore agree in this model. The useful idea is that information flows through the Directed acyclic graph even when the visible grid does not display that flow.

A concrete implementation history illustrates this separation. Microsoft's documentation distinguishes the per-worksheet calculation chains used in Excel 2002 and earlier from calculation using multiple software threads introduced in Excel 2007 for independent chain sections. This is a documented implementation example, not a definition of spreadsheet dependency evaluation.^[ref]

The directed graph whose vertices are the spreadsheet cells and whose directed edges $u\to v$ mean that the spreadsheet formula in $v$ references $u$. Input spreadsheet cells have no prerequisites in this model. Retain both incoming references and outgoing consumers: depth-first search for evaluation follows incoming references backwards, whereas downstream invalidation follows outgoing consumers forwards. A directed path then expresses indirect dependence, and a directed cycle expresses a spreadsheet circular reference.

A mathematical expression stored in a spreadsheet cell, with references to other spreadsheet cells. In this example =A1+A2 asks for addition, =2*A1 for multiplication, and =A2^2 for exponentiation. The evaluator in spreadsheet dependency evaluation assumes these spreadsheet formulas have already been represented by their ordered lists of referenced spreadsheet cells and operations on the resulting numbers; it does not execute arbitrary formula text.

Copying a spreadsheet formula produces a new expression by adjusting its spreadsheet cell references. Copying only its displayed value produces a number instead. For example, copying the spreadsheet formula =A2*B2 down one row gives =A3*B3; entering its former value $15/2$ in the next row would give neither the required relationship nor this example's correct subtotal $7$.

A spreadsheet tabular model assigns a consistent meaning to each row and column. For an original example, let rows 2–4 describe three items, with quantity in column A, unit price in column B, subtotal in column C, and total including tax in column D. Put the single shared tax rate in F1. The chosen rate $1/5$ is an illustrative assumption. Quantities, unit prices and F1 are inputs; columns C and D hold spreadsheet formulas and display their computed values as outputs.

Enter decimal inputs 2.5, 1.75, 4.5 for the unit prices and 0.2 for the tax rate. The following table expresses those values as exact fractions so that the arithmetic is easy to check. It does not require typing a fraction into an input spreadsheet cell or assume that all software calculates with exact rational numbers.

Start with C2 containing =A2*B2 and D2 containing =C2*(1+$F$1). Here * requests multiplication, and 1+$F$1 adds the tax fraction to one. Copy these two spreadsheet formulas down into rows 3 and 4, a fill operation. The relative spreadsheet references change with the destination row: C3 becomes =A3*B3 and D3 becomes =C3*(1+$F$1); C4 becomes =A4*B4 and D4 becomes =C4*(1+$F$1). The absolute spreadsheet reference $F$1 continues to read the shared rate. Copying spreadsheet formulas adjusts relative coordinates while retaining absolute coordinates. ^[ref]

The same mathematical expression applies to every item. Writing $q_i$ for quantity, $p_i$ for unit price and $t$ for the shared tax rate givesFor row 2, the exact arithmetic is $(3\cdot 5/2)(1+1/5)=(15/2)(6/5)=9$. The subtotals add to $47/2$, so the totals add to $(47/2)(6/5)=141/5$, agreeing with $9+42/5+54/5$. The spreadsheet formulas encode the relationship; the displayed numbers are its results for these particular inputs.

This separation is useful for forecasting and sensitivity analysis. Keeping quantities and unit prices fixed while changing only F1 from $1/5$ to $1/4$ gives exact totals $75/8$, $35/4$, and $45/4$. More generally, a rate change $\Delta t$ changes each total byThis follows by expanding the two mathematical expressions and cancelling $s_i(1+t)$. Here $\Delta t=1/20$, so the increases are $3/8$, $7/20$, and $9/20$, adding to $47/40$. One shared input makes the assumption visible and consistent across all rows. Overwriting a computed total with a number would instead remove that spreadsheet formula; its value would cease to follow the model when the rate changes.

// Target: computer-science.bigb