In a recalculation sheet where every cell is defined by the cells it reads, what decides evaluation order?
answer
- order is data, not text
- an edge per cell read
- topological order over dependents
- mark stale, then evaluate once
- a cycle admits no order
basics
~20 sThe dependency graph decides, not the order the definitions were written. Each cell is a node with an edge from every cell it reads, and the engine evaluates in topological order, recomputing what an edit made stale.
solid answer
~40 sEach definition is a standing claim — `total` **is** the sum of the cells it reads — not an instruction that runs once. So the text order carries no meaning; the edges are the program. On an edit, the engine first marks every cell reachable from the edited one as stale, then evaluates that marked set in dependency order: a cell runs only once every cell it reads holds a current value. Two consequences fall straight out. Cells with no path between them may be evaluated in either order, or at the same time. And if the edges contain a cycle there is no order at all, so the engine must reject it, iterate with a cap on passes, or offer an operator that reads the previous pass's value.
code
pseudocode · 11 linescell a = 2
cell b = a + 1
cell c = a + b
edit a -> 5
mark stale: b, c # everything reachable from a
evaluate b = 5 + 1 = 6 # b first: c reads b
evaluate c = 5 + 6 = 11
# evaluating c before b would publish 5 + 3 = 8,
# a value no settled state of the sheet ever hasgo deeper
Recall that a cell states what it always equals rather than a step that runs once, and that the engine works out the order from which cells read which.
Explain both halves of a pass: mark everything reachable from the edit as stale, then evaluate that set in dependency order so no cell reads a value that is about to change.
Show the failure modes you have actually met: glitches from partial passes, hidden inputs that mark nothing stale, and cycles an engine must reject or bound rather than iterate blindly.
The call you own is where the recalculation boundary sits. A larger graph buys automatic consistency but makes an edit's blast radius, and the worst-case cost of a pass, much harder to bound.
## A definition, not an instruction In an imperative program, `total = a + b` is an **instruction**: it executes once, when control reaches it, and afterwards `total` is a value with no memory of where it came from. If `a` changes later, `total` is quietly wrong until someone runs the line again. In a dataflow model the same text is a **definition**: it asserts that `total` *is*, at all times, the sum of `a` and `b`. Keeping that true after every change is the engine's job, not the author's. That one change of reading is what the family turns on. Because each definition names the cells it reads, the set of definitions is a **graph**: one node per cell, and an edge from each cell to every cell whose definition reads it. The source text is only a serialisation of that graph, and the order the lines happen to appear in means nothing. ## Where the order comes from A cell may be evaluated as soon as every cell it reads holds a current value. Applying that rule across the whole graph is exactly a **topological order** — any order in which each node follows all of its inputs. Several such orders normally exist, and the engine may pick whichever it likes; two cells with no path between them may run in either order, or concurrently. A pass over an edited graph has two halves: 1. **Mark.** Walk forward along the edges from the edited cell, marking every reachable cell stale, and stop at cells already marked. The walk is linear in the nodes and edges it touches. 2. **Evaluate.** Run the marked set in topological order, each cell exactly once, publishing values as they are produced. Both halves matter, and dropping either produces a specific bug: - **Without the mark**, the engine must recompute the whole sheet to stay correct. That is wasteful rather than wrong: if three cells out of ten thousand depend on the edit, the other 9,997 already held current values. - **Without the order**, a cell can run before an input that is about to change, publishing a value no consistent state of the sheet ever had. This is the **glitch**: with `b` defined from `a`, and `c` defined from `a` and `b`, evaluating `c` immediately after `a` shows `c` a new `a` beside an old `b`. - **Without the once-per-pass rule**, a shared ancestor is recomputed on every path that reaches it. In a graph full of diamonds, re-entering along each edge multiplies work by the number of distinct paths, which grows far faster than the node count does. ## Push and pull Engines differ in *when* they run the evaluating half. Both use the same graph and the same order. | | eager (push) | lazy (pull) | |---|---|---| | when a pass runs | at the moment of the edit | at the next read of a cell | | what is computed | the whole stale set | only what the read reaches | | cost profile | paid at write time; reads are cheap | reads are uneven and can be expensive | | typical risk | work done for values nobody reads | a stale value observed through a side channel | The choice is a latency and cost decision, not a semantic one: both are obliged to produce the values the definitions claim. ## The cycle that admits no order If the edges contain a cycle — `a` reads `b` and `b` reads `a`, directly or through any chain — then no topological order exists, by definition. There is no "evaluate it twice and it settles": a cyclic system may converge, oscillate forever, or diverge, and nothing in the definitions says which. Engines take one of three defensible routes: - **Reject** — report the cycle and refuse the pass. - **Iterate with a bound** — repeat passes until values stop changing or a cap is reached, then report non-convergence. - **Break it explicitly** — provide an operator that reads the *previous* pass's value, turning the loop into a step in time rather than an edge inside one pass. ## What the model buys and what it costs - **Buys:** consistency by construction — nobody hand-writes invalidation, which is where imperative caching usually rots. Independent regions of the graph are visibly independent, so an engine may evaluate them concurrently without being told. And the definition sits beside the value it defines, so "why is this number what it is" is a local question answered by walking edges backwards. - **Costs:** every input must be **visible**. A definition that reads a clock, a device, or shared state the engine does not model has an edge nobody recorded: nothing marks its dependents stale when that input changes, and the value goes quietly wrong. Pass cost is also harder to predict than a loop's, because the blast radius of an edit is a property of the graph's shape rather than of the line you typed.
- What can a recalculation engine do when the definitions contain a cycle?One of three things: reject the pass and report the cycle, because no topological order exists; iterate passes until values stop changing, with a cap and a non-convergence report; or require an explicit operator that reads the previous pass's value, turning the cycle into a step in time rather than an edge inside one pass. What it must not do is evaluate twice and assume the values have settled.
- Why can a cell read a value that is about to change, even when the graph has no cycle?Because the pass was partial. If an engine recomputes depth-first along edges as it discovers them, a cell with two inputs can run after one input was refreshed and before the other, so it sees a mix of old and new values and publishes a result no consistent state had. Marking the full stale set first and then evaluating it in topological order is exactly what prevents that glitch.
- A cell's definition reads a value the engine does not model — what breaks?The edge is invisible, so when that value changes nothing marks the cell or its dependents stale. The cell keeps its old result until some unrelated edit happens to recompute it, which makes the wrongness intermittent and hard to attribute. Hidden inputs turn a declarative graph back into a manual invalidation problem, which is the problem the graph existed to remove.
A recipe lists steps in the order to perform them; a bill of materials says what each assembly is made of. Change one component and the bill tells you which assemblies must be rebuilt, and in what order.
saying these in an interview costs you the question
- Says cells run top to bottom in the order they were typed.
- Treats a cell definition as an assignment that executes once.
- Thinks a dependency cycle settles after a second pass.
- Believes reordering the definitions changes evaluation order.
- Cannot say what is recomputed after an edit, only that something is.