Reduction Strategies

mini CAML part 2
November 2026

This is part 2 of a series on implementing a simple CAML language. Previous parts:

  1. Stack Machines

Code for this post is available on my GitHub.

This post assumes basic familiarity with \(\lambda\)-calculus

In the next post, we will try to extend our stack machines to compute with \(\lambda\)-calculus instead of arithmetic. But first, we'll need to understand what a reduction strategy is.

Lambda Calculus Reduction Strategies

In a lambda calculus, a term is in normal form if it can't be \(\beta\)-reduced. A term that is not normal can sometimes be turned into one which is normal through reductions. When this is possible, we say the term has a normal form.

But even when a term has a normal form, not every possible ordering of reduction is guaranteed to reach it (we'll see a concrete example later). A strategy for picking what order to reduce terms is called a reduction strategy. This is analogous to an order of operations for the lambda calculus.

There is a special reduction strategy called normal order reduction which does guarantee this. But in real languages, there are some practical reasons why normal order reduction is not desirable. And there are some very useful terms which don't have a normal form.

Two common strategies are call-by-name (CBN) and call-by-value (CBV). These are both so-called “weak” strategies, which means they never reduce inside of an abstraction (and thus neither will always reduce to full \(\beta\)-normal form). Instead, CBV reduces to something called weak normal form and CBN reduces to weak head normal form.

The practical difference between these strategies is this: CBV reduces arguments before applying to a function, while CBN does not.

There is a real tradeoff here. Imagine the following function in your favorite programming language: foo(x, y) = x + y + y. And suppose we call it with foo(1, veryExpensiveCalculation). With a CBN strategy, every occurrence of y means a re-evaluation of veryExpensiveCalculation. So clearly CBV is better, right?

But now consider foo(x, y) = x + x and the call foo(1, crashesIfEvaluated). With a CBV strategy, even though the parameter y is completely unused, this will always crash, since we always evaluate arguments first!

Both of these scenarios can and do occur, but in most programs, the latter case is rare while the former is common, so most languages use a CBV-like strategy.

In lambda calculus, crashesIfEvaluated is something like the “\(\Omega\)” term (λx.x x) (λx.x x), so (λx.λy.x) (λz.z) Ω will reduce to normal form with CBN but not CBV.

You can play around with the demo below to see how the same term is reduced in both strategies.

(λx.λy.x) ((λa.a) (λb.b))

CBN and CBV reduce to different terms

λx.x

In normal form

λx.(λy.y) x

Not normal, but weak normal form

(λx. x x) ((λa.a) (λb.b))

CBN computes the right side twice

(λx.x x) (λx.x x)

The \(\Omega\) term (will show error)

(λx.λy.x) (λz.z) ((λw.w w) (λw.w w))

CBV fails trying to evaluate \(\Omega\)

(λx.λy.y (x x y)) (λx.λy.y (x x y))

\(\Theta\), a “fixed point combinator”


        

Footnotes


  1. I give a brief overview here, but there are many good resources on the topic. In \(\lambda\) calculus, we have “terms”. A term can be a variable, an abstraction, or an application. A variable is just a lower-case letter, while an application is just two terms next to each other. An abstraction looks like λx. M where x is a variable (a binding) and M is another term.

    The most important rule is \(\beta\)-reduction. Given an application with an abstraction on the left, that is, a term like (λx.M) N where M and N are arbitrary terms, you can rewrite this term to M where every occurrence of x has been replaced with N. This is usually called substitution.

    In more day-to-day programming terminology, abstractions are function definitions, and applications are function applications. So \(\beta\)-reduction corresponds to actually carrying out the computation of applying a function.

    There is some extra bookkeeping required to precisely define \(\beta\)-reduction. For instance (λx.λx.x) x is a perfectly legal term, but it's not obvious how substitution should work, or how to distinguish the various xs anymore. We'll see in the next post that this won't really be an issue by taking advantage of de Bruijn indices again.

  2. Usually by normal form we mean “\(\beta\)-normal” form. But there is also “\(\beta\eta\)-normal”. This has to do with which terms are considered equivalent.
  3. The most common useful terms without normal forms are “fixed-point” combinators. These allow you to implement recursion despite the language having no explicit recursive constructions. You may have heard of the Y-combinator or its cousins. The examples include the \(\Theta\) combinator first described by Alan Turing.
  4. One notable exception are languages like Haskell which implement a “lazy”, or call-by-need strategy, which is like a memoized call-by-name. In other words, arguments are not evaluated until necessary, and the result of the evaluation is stored and used. This avoids duplicate work, but also avoids unnecessary evaluations. This seems to solve everything, but can only really work in a language without side-effects, or at least makes no guarantees about the order and how often side effects occur.