Leftmost-outermost reduction repeatedly locates the leftmost occurrence of a redex
and applies the β-rule to it.
Here is a leftmost-outermost reduction step:
(lam x. (a x))((lam y. y) z) => (a ((lam y. y) z)
The above expression holds two redexes, namely,
(lam y. y) z and also (lam x. (a x))((lam y. y) z) ---
the first one is embedded in the second. But the second one is "outermost"
or "to the left of" the first one.
Sometimes leftmost-outermost reduction is called call-by-name evaluation. Apply leftmost-outermost reduction to these examples to rewrite them to their normal forms:
Question A2.
Say that a redex is visible if it is not embedded within
an abstraction expression, that is, the redex is not resting in the
E part of some (lam x. E).
Innermost reduction repeatedly locates a redex that is visible and does not
contain any other visible redexes and applies the β-rule to it.
Here is an innermost reduction step, the only one that can be done:
(lam x. (lam a. a) x)((lam y. y) z) => (lam x. (lam a. a) x) z
There are three redexes, and two are visible, but only the redex,
(lam y. y) z, is visible and contains no other visible redexes.
Sometimes innermost reduction is called call-by-value evaluation. Apply innermost reduction to the expressions (i) and (ii) above to compute the normal forms, if they exist.