skip to content

Reduction order cannot change a pure expression's result — what does that guarantee leave unconstrained?

level: seniorimportance: nice to knowfreq 26%

answer

  1. the guarantee is about the value
  2. same answer, not same cost
  3. steps taken, memory held
  4. speculation can be wasted work
  5. one order may not finish

basics

~10 s

Everything except the value: how much work is done, how much memory is held, how long it takes, and whether a chosen order finishes at all. Confluence promises one answer, never one cost.

solid answer

~40 s

Confluence — the Church-Rosser property — says that if two reduction orders both reach a final form, it is the same final form. That is a claim about the *value* and about nothing else. Order still decides how many steps are taken: an order that evaluates a branch whose result is later discarded does real work for nothing, which is the standing bill for speculative evaluation. It decides peak memory, because one order may hold many intermediate values alive while another consumes them as it goes. And it decides termination: an order that evaluates something the answer never needs can run for an hour, or forever, where another returns at once. Purity makes a schedule safe to choose; it does not make every schedule a good one.

go deeper

for a junior

Hold on to the split: purity fixes what a computation produces, not how much it costs to produce it. Two correct orders can differ a lot in time and memory.

for a middle

Name the axes left open — steps taken, memory held, latency, termination — and be able to give an example where one order finishes and another does not.

for a senior

Use it when judging a rewrite. Answer-preserving is necessary but not sufficient, and a rearranged pipeline can hold far more alive than the one it replaced.

for a principal

Decide the policy for speculative work. Idle capacity makes the bet attractive, but unbounded or rarely needed speculation is a cost centre nobody is watching.

## What the result actually claims The reason a scheduler may rearrange pure work at all is a confluence property, stated for reduction systems by the Church-Rosser theorem: if an expression can be reduced along two different routes, those routes can always be brought back together, and where a final form exists it is unique. Informally — you cannot get a different answer by choosing differently. That is an unusually strong guarantee, and it is also an unusually narrow one. It quantifies over *values*. Every other property an engineer cares about is left open. ## Four axes it says nothing about 1. **Work done.** Two orders can reach the same answer with wildly different step counts. An order that evaluates an argument whose value is never consumed has done all of that work for nothing, and if the discarded branch was the expensive one, most of the pass was waste. 2. **Memory held.** An order that computes many intermediate results before consuming any of them holds all of them alive at once; an order that consumes as it produces holds one. Same answer, different peak. 3. **Time to first result.** Latency depends on which parts are computed early, which is entirely a scheduling choice. Two orders with identical total work can differ greatly in when anything useful becomes available. 4. **Whether it finishes.** This is the sharpest limit. Confluence is conditional — *if both orders reach a final form*. An order that insists on reducing something the answer does not need may never reach one, while another order returns immediately. Purity does not make every expression finite; it makes every finite outcome agree. | Property | Fixed by purity? | |---|---| | The value produced, if the order finishes | Yes | | Number of reduction steps taken | No | | Peak memory held during reduction | No | | Whether the chosen order terminates | No | ## Speculation: the bet purity makes safe Speculative evaluation is the clearest place where the distinction bites. A scheduler starts evaluating something before knowing whether the result will be wanted. Purity is what makes this legal at all: a discarded pure evaluation leaves nothing behind, so the worst case is wasted effort rather than a wrong sheet. But *wasted effort* is a real cost, and it is unbounded in principle. - The bet is good when workers would otherwise be idle, the work is bounded, and the result is likely to be needed. - The bet is bad when the speculated work is expensive, rarely needed, or of unknown duration — an unbounded computation speculated on idle capacity does not stay cheap. - The bet is never a correctness risk, which is exactly why schedulers are willing to make it and why the same move on impure work is simply forbidden. ## Why this distinction matters in practice Engineers who have just learned that purity licenses reordering tend to over-claim, and the over-claim is always on the cost axis: *it does not matter what order we evaluate in.* It does not matter to the **answer**. It can matter enormously to the bill. Concretely: - A rewrite that is provably answer-preserving can still be a serious performance regression, so an optimiser has to model cost as well as legality. - A pipeline that is rearranged for elegance may hold far more data in memory than the one it replaced, with no change in what it computes. - Where evaluation is deferred, the guarantee cuts in the useful direction: work not demanded is not done. That is a separate topic in its own right, but it is the same axis — the value is fixed, the cost is not. ## How this is asked Rarely on a first screen; this is the follow-up that separates *I have heard purity allows reordering* from *I know what it allows*. The interviewer usually offers an over-strong statement and waits to see whether it is accepted: purity means order is irrelevant, or a pure expression costs the same however it is evaluated. The answer to give names the value as the thing that is fixed, and then names the axes that are not — steps, memory, latency, termination — with speculative evaluation as the concrete case where the difference is the entire point.

  • If speculative evaluation can be wasted, why do schedulers do it at all?
    Because idle capacity is wasted too. Starting a pure computation before knowing it is needed can never corrupt the answer, so the only exposure is the work itself — a fair bet when workers are idle and the result is probably wanted. The bet turns bad when the work is expensive, unbounded, or rarely needed.
  • Does the guarantee still hold when the arithmetic is inexact?
    Not automatically, because re-associating operations is a different move from reordering independent work. Regrouping additions of inexact numbers can change the result, so rewriting `(a + b) + c` into `a + (b + c)` is a claim about the operation rather than about the schedule. Evaluating independent formulas in either order is unaffected.

saying these in an interview costs you the question

  • Says a pure expression costs the same under any evaluation order.
  • Believes confluence guarantees that every reduction order terminates.
  • Treats speculative evaluation as free because the answer cannot change.
  • Assumes a legal reordering can only ever make a program faster.