Evaluation strategies

When a function is applied to an argument, when does the argument get evaluated? Different choices give you different languages. The three classic strategies are call-by-value (CBV), call-by-name (CBN), and call-by-need (lazy evaluation). They agree on terminating, pure programs but disagree on cost, semantics under effects, and what "diverges" means.

The three strategies

Call-by-name and call-by-need are both non-strict; call-by-need is the "smart" version that avoids recomputing the same thunk.

Why the choice matters

Consider f x = 42 (a function that ignores its argument) applied to (loop ()), a divergent term.

• CBV reduces (loop ()) first → never terminates.
• CBN / call-by-need never touches the argument → returns 42.

Non-strict languages can therefore give meaning to programs that strict languages can't — at the cost of harder reasoning about when effects happen. That's why Haskell pushes effects into IO: with lazy evaluation, you need a separate handle on order.

Clojure is strict — but you can opt into laziness

Clojure evaluates arguments before the call (CBV), but you can simulate call-by-need with delay (memoized thunk) and force:

Lazy seqs ((map f xs), (filter p xs), (iterate f x0)) are call-by-need at the element level: each element is computed at first realization and cached in the seq.

Normal-order vs applicative-order, briefly

In the untyped λ-calculus, applicative order reduces arguments before substituting (= CBV at the term level), while normal order reduces the leftmost-outermost redex first (= CBN). Normal order has the standardization theorem going for it: if a term has a normal form, normal-order reduction finds it. Applicative order can fail to terminate on terms that do have a normal form (the diverging-argument example).

The cost model

Lazy evaluation isn't free. Each delay/thunk is a small allocation; chains of thunks can leak memory until forced (the classic "space leak"). Strictness analysis in compilers like GHC tries to recover CBV cost where it's safe. Idiomatic Haskell uses bangs (!) and seq to opt out of laziness in hot spots.

Real-world: where each strategy lives

The general lesson: strict-by-default + opt-in laziness is the practical sweet spot. Pure call-by-need is elegant but hard to reason about for performance, which is why Haskell shops invest heavily in strictness analysis and bang patterns.

Check yourself

Exercise

Write a lazy-seq in Clojure that generates Fibonacci numbers. Then take 10 elements twice from the same seq and confirm (via time or a println inside the generator) that the elements aren't recomputed — that's call-by-need sharing in action.