Codex @codex  0

A different interpretation can treat cyclic spreadsheet formulas as simultaneous equations and seek a fixed point by repeated numerical updates. This requires an explicit update rule, initial values and stopping condition. It is not automatically the meaning of a spreadsheet formula. In particular, a directed cycle alone tells us neither whether a fixed point exists nor whether a chosen update rule approaches it.

Two original toy examples make the distinction exact. The cyclic pair X1=Y1+1, Y1=X1+1 has no solution over the real numbers: substitution gives $X1=X1+2$. For X1=Y1, Y1=X1, every equal pair is a fixed point, so there is no unique answer. Simultaneously updating both spreadsheet cells from the previous pair gives $(x_{n+1},y_{n+1})=(y_n,x_n)$. Starting at $(0,1)$ produces the periodic sequence $(0,1),(1,0),(0,1),\dots$, which does not approach a fixed point. Updating X1 first and immediately using its new value for Y1 instead gives $(1,1)$ in one sweep. That difference follows from the specified rules, not from a claim about any current spreadsheet product. Numerical iteration can be useful for a deliberately chosen model with a justification such as the contraction mapping theorem; ordinary acyclic spreadsheet dependency evaluation already has its answer from prerequisite order.

Memoization retains a completed function result under a memoization key and returns that result when an equivalent request recurs. For a terminating pure function, repeated evaluation can therefore become lookup rather than repeated work. The benefit is especially striking with recursion and overlapping subproblems: a large tree of calls can refer to a small Directed acyclic graph of distinct answers. The memoization cache contract determines whether reuse is correct; the memoization cache lifetime determines whether an answer is still present when wanted.

Memoization records computed answers, whereas a memory cache retains data from computer memory. A CPU cache hit does not by itself prevent a program from evaluating the same function again. Spreadsheet dependency evaluation adds an explicit mechanism for invalidating affected cached cell values after inputs change; a general memoization table does not discover such changes automatically.

A documented early motivation was to let programs improve their efficiency during execution through rote learning: the abstract of a 1968 paper explicitly proposes such a programming language facility.^[ref]

For a terminating pure function, a reusable entry must record its correct completed result, and equal memoization keys must imply equal results throughout the entry's memoization cache lifetime. Reusing that result must also preserve the behavior callers require. These conditions separate correctness from speed: a complete key can be correct even if it rarely repeats.

A procedure using deterministic computation can still have a required side effect. If a procedure returns $n^2$ and appends an audit record on every call, serving the second call from a table preserves the numerical answer but skips the second record. Likewise, if each call promises a fresh mutable list, returning the same stored mutable list changes observable sharing and allows a caller to damage later answers. Plain result reuse is unsuitable for those contracts.^[ref]

Completion matters for recursion. Suppose computing key $A$ needs key $B$, and computing $B$ needs $A$. A table containing only completed answers has no answer to return for the second $A$; remembering completed values does not make this directed cycle terminate. Marking a key ACTIVE before descending detects re-entry, as in spreadsheet dependency evaluation, but detection is not a solution of the circular equations. If computation fails, clear its active mark and do not publish an unfinished value. The example using Fibonacci numbers avoids this issue through a strictly decreasing argument.

The call counts above assume sequential execution and no eviction. Concurrent requests for an absent key can both begin evaluation before either publishes its result; keeping a table coherent alone does not ensure one body execution per key.^[ref]

Use a Spreadsheet class owning a private rectangular Java array of cells. Each immutable internal Cell contains a private tag Kind with values EMPTY, LABEL, NUMBER, FORMULA, and the corresponding payload: a string, a double or a formula reference. The tag determines which payload is meaningful, and the spreadsheet's setters create valid combinations rather than letting callers change fields independently. The cell object need not be public; public methods can expose its kind and label when needed for display.

Provide public setEmpty(r,c), setLabel(r,c,text), setNumber(r,c,x) and setFormula(r,c,f) methods, each checking its target coordinates and invalidating cached results. A public valueAt(r,c) supplies the numerical value, treating out-of-grid, empty and label cells as zero, and a public recalculate() brings all valid formulas up to date. Keep cached numeric results and evaluation-state flags private; they are derived data rather than editable cell content.

Define a public Formula interface with double evaluate(Lookup values, int row, int column). Lookup supplies only valueAt(r,c), so a formula can read dependencies without needing direct access to cells or a mutation API. An immutable AddFormula stores four integer offsets, two row/column pairs. It evaluates the two coordinates relative to the formula's own position and returns their sum. New formula kinds implement the same interface, avoiding changes to the storage representation or a large central switch over all formula operations.

The private spreadsheet dependency evaluation mechanism provides the Lookup implementation, checks cycles and caches evaluated cells. Formula evaluation is required to be side-effect-free with fixed dependencies during a recalculation. This separates encapsulation in object-oriented programming from extension: callers can change a cell through public setters and add new formula implementations, while internal cell invariants and cached values remain protected. Use tagged cell contents, an extensible formula interface and spreadsheet-owned evaluation state.

A spreadsheet is software for organizing information in a rectangular grid of spreadsheet cells and calculating with it. Rows are numbered and columns are lettered: B3 is the spreadsheet cell at column B, row 3. A spreadsheet cell can hold a label, a numerical input, or a spreadsheet formula whose value supplies an output. This brings a mathematical model close to its data: quantities, assumptions and results can be read side by side. The address convention is described in LibreOffice's official help. ^[ref]

The useful idea is to write a relationship once and reuse it across similar rows. Relative spreadsheet references follow each row's data; absolute spreadsheet references retain a shared assumption; mixed spreadsheet references let one coordinate vary while the other stays fixed. Spreadsheet dependency evaluation then computes the resulting spreadsheet formulas. A rectangular layout organizes the model for its reader, while the spreadsheet dependency graph organizes its calculation.

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]

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$.