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:
- The book's definition of what an answer is needs to be changed somewhat: we will say that any expression that reduce-once-appl fails to reduce is an answer. In most cases this is the same as the book's definition, but they differ on some irreducible applications such as (x x).
- Don't use the version of reduce-once-appl that is in the book. Instead, use my version, which is linked onto the web copy of this lab handout. Note that my version makes no use of the procedure called answer?. Nor should you: don't type it in or any variant of it. Anywhere you might think it is useful, you can instead use reduce-once-appl with appropriate success and failure continuations.
- For 4.3.1, n should be allowed to be 0, not just positive, and the list you produce should start with the given expression, rather than the first reduced version. The list should then continue with at most n reduced versions, but perhaps fewer (possibly even 0) if you reach a point where no further reduction is possible. Here are the book's examples with this modification:
```
> (reduce-history '((lambda (x) (x ((lambda (x) y) z))) w) 5)
(((lambda (x) (x ((lambda (x) y) z))) w)
 (w ((lambda (x) y) z))
 (w y))
> (reduce-history '((lambda (x) (x x)) (lambda (x) (x x))) 3)
(((lambda (x) (x x)) (lambda (x) (x x)))
 ((lambda (x) (x x)) (lambda (x) (x x)))
 ((lambda (x) (x x)) (lambda (x) (x x)))
 ((lambda (x) (x x)) (lambda (x) (x x))))
```
- For 4.3.2, you may want to loosen the restriction that n be positive.
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