We've discussed evaluation order before, primarily in connection with
the untyped lambda calculus. Whenever a term contains more than one
redex, we have to choose which one to reduce, and this choice can make
-a difference. For instance, in the term `((\x.I)(ωω)`, if we reduce
+a difference. For instance, in the term `((\x.I)(ωω))`, if we reduce
the leftmost redex first, the term reduces to the normal form `I` in
one step. But if we reduce the left most redex instead (namely,
`(ωω)`), we do not arrive at a normal form, and are in danger of
In order to fully reduce a term, we need to be able to reduce redexes
that are not at the top level of the term.
- (II)I ~~> IK ~~> K
+ (II)K ~~> IK ~~> K
That is, we want to be able to first evaluate the redex `II` that is
a proper subpart of the larger term, to produce a new intermediate term
itself a redex, we recursively call `reduce1`. The recursion will
continue until the result is no longer a redex.
- #trace reduce1;;
+ # #trace reduce1;;
reduce1 is now traced.
# reduce1 (FA (I, FA (I, K)));;
reduce1 <-- FA (I, FA (I, K))
*How can we can we specify the evaluation order of a computational
system in a way that is completely insensitive to the evaluation order
of the specification language?*
+
+
+[By the way, the evaluators given here are absurdly inefficient computationally.
+Some computer scientists have trouble even looking at code this inefficient, but
+the emphasis here is on getting the concepts across as simply as possible.]