More about evaluation
Reading: TAPL 5.3.
Page 72 gives evaluation rules for the call-by-value λ-calculus. If we want to use evaluation contexts, they are defined as:
E ::= [⋅] E1 t2 v1 E2
Then we can replace the congruence rules (E-App1 and E-App2) with the single rule:
t ⟶ t' ―――――――――――――― (E-Context) E[t] ⟶ E[t']
Earlier (p. 56), you read about several evaluation strategies. It may seem rather arbitrary to pick one evaluation order out of many, so here are some additional remarks on why it’s actually not so bad.
The original definition of λ-calculus allows β-reduction to occur anywhere (full β-reduction, p. 56). This means that the evaluation relation is nondeterministic, because there are terms that have more than one place where β-reduction can be done. So, what should we do if two different evaluation paths end in two different normal forms? (Cf. nondeterministic Turing machines, where we said that the machine accepts iff at least one path accepts).
The good news is that this cannot happen, because β-reduction is confluent: if
a ⟶* b and
a ⟶* c, then there exists some
d such that
b ⟶* d and
c ⟶* d (also known as the Church-Rosser theorem). In other words, whenever a path forks into two paths, there’s always a way to rejoin them. In particular, this means that every term has at most one normal form.
But it can happen that a term has some paths that lead to a normal form and some paths that do not. Such terms are called weakly normalizing but not strongly normalizing. For example, the term
(λx. λy. y) Ω is weakly normalizing but not strongly normalizing.
Fortunately, normal-order evaluation (“the leftmost, outermost redex is reduced first”) is deterministic and is guaranteed to find a normal form if there is one.
Call-by-name evaluation is similar to normal-order evaluation, except that we do not perform reductions inside lambdas. Because normal-order evaluation reduces outermost redexes first, it must be that a normal-order evaluation that results in a value always starts with a call-by-name evaluation :
t ⟶* v iff t ⟶* v' ⟶* v nrm cbn nrm
(The fact that
v' is an intermediate step in the normal-order evaluation from
v isn’t stated by Plotkin, but the proof is exactly the same as his Corollary 4.1.)
So call-by-name evaluation is just normal-order evaluation that stops as soon as it reaches a value.
To get to call-by-value, we back up to full β-reduction, then restrict to βᵥ-reduction , which, as mentioned briefly earlier, can only happen when the argument is a value. Another way of thinking about this restriction is in terms of what variables can be bound to: in the strategies above, variables can be bound to any terms, but under βᵥ-reduction and the strategies below, variables can only be bound to values.
βᵥ-reduction has some key properties in common with β-reduction:
Full βᵥ-reduction is confluent, and it is weakly but not strongly normalizing.
There is an evaluation strategy that always finds a βᵥ-normal form: “Find the leftmost, outermost subterm that contains a call-by-value redex; that redex is reduced first.” I don’t know if this strategy has a name; let’s call it βᵥ-normal-order evaluation.
t ⟶* v iff t ⟶* v' ⟶* v nrmv cbv nrmv
nrmvmeans βᵥ-normal-order evaluation.
|Arguments can be any terms||Arguments must be values|
|Reduce anywhere||Full β||“Full βᵥ”|
|Finds a normal form||normal-order||“βᵥ-normal-order”|
|Stops when term is a value||call-by-name||call-by-value|
 Matthias Felleisen and Matthew Flatt. 2006. Programming languages and lambda calculi. Retrieved from https://www.cs.utah.edu/~mflatt/past-courses/cs7520/public_html/s06/notes.pdf
 G. D. Plotkin. 1975. Call-by-name, call-by-value and the λ-calculus. Theoretical Computer Science 1, (1975), 125–159. DOI:https://doi.org/10.1016/0304-3975(75)90017-1