MCS-287 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.2-4.2.4 on pages 106-107.
- Do exercise 4.3.1 and/or 4.3.2 from pages 112-113, 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
reduce-history
to reduce-history-appl
and
reduce*
to reduce*-appl
and make
corresponding reduce-history-leftmost
and
reduce*-leftmost
procedures. Rather than duplicating
code between the applicative-order and leftmost versions, you should
use a generalized or higher-order 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 applicative-order 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 applicative-order 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 applicative-order 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 applicative-order
reductions, with n > 0.
-
The expression exp reaches the answer exp' after
some number of applicative-order 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