Two pure cell formulas in a recalculation pass — when may the engine evaluate them in either order?
answer
- order is a scheduling choice
- look for a dependency edge
- inputs of one, output of the other
- purity closes the hidden channel
- reads never constrain reads
basics
~20 sEither order is safe exactly when neither formula reads the cell the other writes. Purity closes every other channel — no shared counters, no clock, no files — so only declared data dependencies constrain the schedule.
solid answer
~40 sThe engine may swap them when there is no **data dependency**: neither formula's inputs contain the other's output cell. Purity is what makes that single check sufficient. A pure formula's result depends only on the cells it names and it changes nothing observable, so there is no second, invisible channel — a running total, an audit line, a clock reading — through which evaluating one first could change what the other sees. If the formulas were impure the engine would have to assume any pair might communicate through that channel and fix one global order. Two formulas that read the *same* input cell are still independent: reads impose no order on each other, and that is the case a parallel pass lives on.
code
pseudocode · 6 linesB = width * 2 # independent
C = height * 3 # independent
D = B + 10 # consumes B
# legal orders: any in which B precedes D
# C may run before, between, or alongside themgo deeper
Be able to say that order is fixed only by one formula consuming another's output, and that two formulas reading the same cell remain free to run in either sequence.
Explain how the dependency graph is built from declared references, and why purity is what makes the collected input set complete rather than merely likely to be complete.
Show where a real pass loses this: a hidden counter or a clock read turns an unprovable interaction into a forced serial order for everything that might reach it.
The trade you own is how much of a system stays freely schedulable. That freedom is bought by routing every effect through a narrow boundary, and teams have to agree to keep it narrow.
## What the engine is actually deciding A recalculation pass over a sheet of thousands of formulas is a **scheduling** problem, not an arithmetic one. Each formula names the cells it reads and the single cell it writes, and the engine must choose an order to evaluate them in. The point most candidates miss is that there is rarely one correct order — there is a whole *set* of orders that all produce the same final sheet. The engine wants to prove that set as large as it can, because every extra degree of freedom is an optimisation it may take: skipping work that cannot have changed, evaluating one expression once instead of twenty times, handing ranges of rows to several workers, or starting a likely-needed value early. So *when may these two be swapped?* is the atomic version of the question the whole pass turns on. ## The one edge that constrains order A **data dependency** exists between two formulas when one consumes what the other produces. Concretely: - **Write-then-read is a real constraint.** If `D = B + 10`, whatever computes `B` must finish first. In a pure sheet this is the only kind of edge there is. - **Read-read is not a constraint.** Two formulas that both read the width cell impose no order on each other, because neither can tell that the other ran. - **Position is not a constraint.** Where a formula sits in the sheet, or the order the formulas were typed in, tells the engine nothing about evaluation order. - **Cost is not a constraint.** A slow formula and a fast one are still unordered if neither consumes the other's output. The procedure that follows is mechanical: 1. Read each formula's references to collect its input set and its output cell. 2. Draw a directed edge from each producer to every consumer of its output. 3. Evaluate in any order consistent with that graph — any topological order will do. 4. Treat any two nodes with no path between them as unordered: either sequence, or both at once. ## Why purity is the enabling condition Step 1 is the step that quietly depends on purity. The engine collects a formula's inputs by reading what the formula *names*. That collection is only **complete** if a formula cannot reach a value it did not name. A pure formula cannot: its result is a function of its declared inputs alone, and it changes nothing observable, so there is no second route by which one evaluation could influence another. | Channel | Visible to the engine? | Effect on ordering | |---|---|---| | A referenced input cell | Yes, it is written in the formula | Adds an edge the engine can honour | | A running total updated as formulas evaluate | No | Makes every pair potentially ordered | | A clock or a random source | No | Makes the result depend on when it ran | | A line appended to an audit log | No | Makes the number and order of evaluations observable | With any of the bottom three present, a sound engine falls back to a fixed order for everything that might touch them, because it cannot prove the absence of a link it cannot see. Purity converts *I cannot prove these do not interact* into *these demonstrably cannot*. ## A worked pair Take three formulas: `B = width * 2`, `C = height * 3`, `D = B + 10`. The graph has exactly one edge, from `B` to `D`. That single edge rules out the orders in which `D` runs first, and it leaves `C` entirely free — before, between, or alongside. Now suppose `C` also increments a hidden counter that `B` happens to read. Nothing in the text of either formula changed, but the sheet now carries a second edge no reader of the formulas can see, and orders that were legal a moment ago produce a different sheet. That is the whole argument for purity in one example. ## What purity does not relax Purity buys freedom *within* the dependency graph, never freedom *from* it: - A consumer still waits for its producer; no amount of purity lets `D` precede `B`. - A cycle is still a cycle. Two formulas that read each other have no valid order at all, and the engine must reject the sheet rather than pick one. - Ordering freedom is not a promise about cost. Two legal orders can differ substantially in how many intermediate values are held alive at once. ## How this is asked The interviewer is usually checking two things. First, whether you reach for the dependency graph rather than for the text order — describing evaluation as top-to-bottom shows you have not separated a program's text from its schedule. Second, whether you can say *why* the graph can be trusted: the honest answer names purity as the reason the declared inputs are the only inputs, and names a shared counter or a clock as the thing that would make the graph a lie.
- Two formulas read the same input cell but neither reads the other's output. Are they dependent?No. Two reads of a value nothing writes create no ordering constraint at all; a dependency means one formula consumes what the other produces. Read-read pairs are exactly what a parallel pass exploits, because neither evaluation can observe the other's timing.
- How does the engine learn the dependency edges in the first place?It reads the cells each formula references and builds a directed graph from producers to consumers. Purity is what makes that graph complete: a pure formula cannot reach an input it did not name, so an edge the engine cannot see cannot exist. Evaluation is then any topological order of the graph.
Two cooks working from separate recipes can start in either order. The moment one recipe calls for the sauce the other is making, the order is fixed — and nothing about how fast either cooks changes that.
saying these in an interview costs you the question
- Says any two pure formulas may always be swapped, data dependencies included.
- Thinks a formula's position in the sheet determines when it is evaluated.
- Treats two formulas reading the same input cell as dependent on each other.
- Believes reading shared mutable state is harmless because nothing is written.