MCS287 Lab Project 2: Reduction Orders (Spring 2000)
Due: March 16, 2000
Your project report should reflect your final product, rather than
focusing on each incremental step along the way. Your project report
should explain the examples in which you compare applicative and
leftmost reduction orders, and the functionality of your reduction
procedures that allow you to make these comparisons. Don't go into
the details in English: your audience can read Scheme. However, don't
assume the audience knows what you are trying to accomplish or how you
have gone about accomplishing it.
 Do exercises 4.2.24.2.4 on pages 106107.
 Do exercise 4.3.1 and/or 4.3.2 from pages 112113, as modified
below. It will be most convenient to have both of these, but you can
make do with either one of them for the crux of the lab (the
comparison of reduction orders), so if you are hung up on one but not
the other, you might want to go on. The modifications I would make to
these exercises are as follows:
 Do exercise 4.3.5 from page 115. Now rename
reducehistory
to reducehistoryappl
and
reduce*
to reduce*appl
and make
corresponding reducehistoryleftmost
and
reduce*leftmost
procedures. Rather than duplicating
code between the applicativeorder and leftmost versions, you should
use a generalized or higherorder procedure to capture the commonality.
 Now, for the crux of the lab, use your programs to show examples
where

The expression exp reaches the answer exp' after
exactly n applicativeorder reductions and reaches the
normal form exp' after exactly n leftmost
reductions, with n > 0. (As a note on mathematical
convention: the two occurrences of exp' mean that these
should be equal, and similarly for the occurrences of
n. However, moving from one bulleted goal to the next,
you are allowed to switch to a different exp,
exp', etc.)

The expression exp reaches the answer exp' after
exactly n applicativeorder reductions and reaches the
normal form exp' after exactly n' leftmost
reductions, with n' > n > 0.

The expression exp reaches the answer exp' after
exactly n applicativeorder reductions and reaches the
normal form exp' after exactly n' leftmost
reductions, with n > n' > 0.

The expression exp reaches the normal form exp' after
exactly n leftmost reductions but has not reached any
answer after 100+n applicativeorder
reductions, with n > 0.

The expression exp reaches the answer exp' after
some number of applicativeorder reductions and reaches the
normal form exp'' after some (possibly different) number of leftmost
reductions, with exp' different from exp''.
If you have trouble with one of these, you may want to do later ones
and come back.
Instructor: Max Hailperin