This is part 2 of a series on implementing a simple CAML language. Previous parts:
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”