5.23 Exercise 5.23

Back in chapter 4, we defined a few types of expressions as transformations of other, more "basic" expressions that we already supported. For example, cond expressions can be transformed into ifs, lets can be defined in terms of immediately-invoked lambdas, and so on. Since the book does not detail exactly what forms we’ll support, I’ll implement cond as well as all three types of let constructs supported by Scheme, but not the "extra" constructs like while.

Since we’re implementing them while assuming that transformation functions such as cond->if are available as operations, our methodology can be very straightforward: We call the operation to transform the value contained in the exp register, save it back into exp, and then re-evaluate the expression by branching to eval-dispatch again. This is very similar to how we called eval recursively on the transformed expressions earlier.

The most straightforward way to do this is to duplicate the re-evaluation code for each of these cases. It would be possible to implement a single sub-procedure which receives an operation as an argument and jump to it from different locations. However elegant this idea may seem, I think it would require significantly more code in addition to being more complex, so I’m not going to do this.

Assuming we’ve brought over the required operations and their dependencies (which will not be repeated here), the changes to the interpreter are very easy. First, we expand eval-dispatch to check for our new expression types before trying to perform function application:

eval-dispatch

(test (op self-evaluating?) (reg exp))

(branch (label ev-self-eval))

(test (op variable?) (reg exp))

(branch (label ev-variable))

(test (op quoted?) (reg exp))

(branch (label ev-quoted))

(test (op assignment?) (reg exp))

(branch (label ev-assignment))

(test (op definition?) (reg exp))

(branch (label ev-definition))

(test (op if?) (reg exp))

(branch (label ev-if))

(test (op lambda?) (reg exp))

(branch (label ev-lambda))

(test (op begin?) (reg exp))

(branch (label ev-begin))

(test (op cond?) (reg exp))

(branch (label ev-cond))

(test (op let?) (reg exp))

(branch (label ev-let))

(test (op let*?) (reg exp))

(branch (label ev-let*))

(test (op application?) (reg exp))

(branch (label ev-application))

(goto (label unknown-expression-type))

Next, we add the new evaluation methods. They are all almost exactly the same:

ev-cond

(assign exp (op cond->if) (reg exp))

(goto (label eval-dispatch))

ev-let

(assign exp (op let->combination) (reg exp))

(goto (label eval-dispatch))

ev-let*

(assign exp (op let*->nested-lets) (reg exp))

(goto (label eval-dispatch))

And that’s all. There isn’t much to verify, but we can give it a spot check: