Call-by-name and call-by-need both defer an argument until it is used, so what does call-by-need add?

## Two ways to defer Both **call-by-name** and **call-by-need** are non-strict: the argument expression is not evaluated at the call site, and if the body never uses the parameter, the expression never runs at all. They part company at the *second* use. - **Call-by-name** behaves as if the argument expression were substituted for the parameter wherever the parameter appears. Every occurrence of the parameter is an occurrence of the expression, so the expression is evaluated once **per use** — three uses, three evaluations. - **Call-by-need** evaluates the expression at the **first** demand and stores the result. Every later use reads that stored result — three uses, one evaluation. So call-by-need is call-by-name plus memoisation of exactly one result, for one deferred argument, within one call. ## The counter that tells them apart ``` counter = 0 function next() counter = counter + 1 return counter function pair(x) return [x, x] pair(next()) ``` - **Call-by-value**: `next()` runs once, at the call, producing `1`. Result `[1, 1]`, counter `1`. - **Call-by-name**: the body contains two uses of `x`, so `next()` runs twice. Result `[1, 2]`, counter `2`. - **Call-by-need**: the first use forces `next()` to `1` and stores it; the second use reads the stored value. Result `[1, 1]`, counter `1`. Notice that call-by-value and call-by-need agree here for different reasons — one evaluated eagerly once, the other lazily once. That agreement is the point of call-by-need: it preserves the ordinary evaluate-once cost model that programmers reason with, while keeping the non-strict guarantee that an unused argument costs nothing. ## Counting evaluations | Uses of the parameter in the body | Call-by-value | Call-by-name | Call-by-need | |---|---|---|---| | Zero | 1 | 0 | 0 | | One | 1 | 1 | 1 | | Three | 1 | 3 | 1 | For a **pure** argument — one that returns the same result every time and changes nothing observable — the two non-strict columns produce identical values and differ only in work performed. The difference becomes visible in *results*, not merely in cost, exactly when the expression is impure or when repeating it is expensive enough to matter. That is why the practical question at a whiteboard is rarely "which is lazier" and usually "is this argument pure, and how many times does the body use it". ## What the caching costs Memoising a deferred argument is not free. The call must carry somewhere to put the result and a marker saying whether it has been computed yet, and every use tests that marker before reading. Call-by-name stores nothing and pays repetition instead. So: 1. For a parameter used **zero** times, the two are identical and both beat strict evaluation. 2. For a parameter used **once**, caching is pure overhead — real, but usually small. 3. For a parameter used **many** times, caching converts n evaluations into one, which is the case that justifies it. There is also a behavioural price for the cache: once the result is stored it is fixed. An argument expression that reads mutable state is sampled at the moment of first demand, and every later use sees that sample, not a fresh read. Under call-by-name each use is a fresh read. Neither is "more correct" — but a caller who assumed one and got the other has a bug that is hard to see. ## Reading these claims in the right direction Every statement in this area is still grammatical when reversed, so check yours against these: - The cached value is fixed at **first demand**, not at the call site. - Memoisation makes **later** demands cheap; the first demand costs what the expression costs, plus the bookkeeping. - Re-evaluation at every use is **call-by-name**; a single evaluation on demand is **call-by-need**. - Neither strategy evaluates an argument the body never uses. ## What interviewers listen for A strong answer names caching as the difference in one sentence, then proves it with a case where the two visibly disagree — an argument with an effect, or one used repeatedly — and states what is unchanged between them (an unused argument is evaluated by neither). A weak answer treats "lazy" as a single idea with one behaviour, which leaves it unable to explain why one deferred argument can run twice.