MASSACHVSETTS INSTITVTE OF TECHNOLOGY
Department of Electrical Engineering and Computer Science
6.001---Structure and Interpretation of Computer Programs
Spring Semester, 1999
Recitation -- Wednesday, April 28
We can also add and to our explicit-control evaluator. We first add a clause to the evaluator dispatch
eval-dispatch ... (test (op and?) (reg exp)) (branch (label ev-and)) ...
EV-AND presumes that the EXP register holds the expression to be evaluated, the ENV register holds the current environment pointer, and the CONT register holds the place to jump to.
The key is to write register machine code to implement AND starting at the label EV-AND. Fill in the missing spots. Assume we've got the primitives first-conjunct and second-conjunct.
1. ev-and 2. (assign unev HighlitedAnswer (op second-conjunct) (reg exp) EndOfAnswer) 3. (assign exp HighlitedAnswer (op first-conjunct) (reg exp) EndOfAnswer) 4. (save continue) 5. (save env) 6. (save unev) 7. (assign continue eval-after-first) 8. (goto HighlitedAnswer (label eval-dispatch) EndOfAnswer) 9. eval-after-first 10. (restore HighlitedAnswer unev EndOfAnswer) 11. (restore HighlitedAnswer env EndOfAnswer) 12. (test (op true?) (reg val)) 13. (branch (label eval-second-arg)) 14. (assign val #f) 15. (restore HighlitedAnswer continue EndOfAnswer) 16. (goto (reg continue)) 17. eval-second-arg 18. (assign exp HighlitedAnswer (reg unev) EndOfAnswer) 19. (assign continue after-second) 20. (goto HighlitedAnswer (label eval-dispatch) EndOfAnswer) 21. after-second 22. HighlitedAnswer (restore continue) EndOfAnswer 23. (goto (reg continue))
Does this ev-and routine handle tail recursion? For example, consider the scheme code below. What result (if any) do we get when we evaluate (list? x) in our regular scheme? How about a scheme built on top of the above explicit-control evaluator?
(define (list? x) (or (null? x) (and (pair? x) (list? (cdr x)))))
(define z (list 1)) (set-cdr! z z)
(list? z)
To see how this is working, let's evaluate the expression (and #t (and #f #t)).
to 3in to 6.5in
How could we change the code above so that it handles tail-recursion? Hint: remove lines 19 through 23 and add two lines in their place.
19. HighlitedAnswer (restore continue) EndOfAnswer 20. HighlitedAnswer (goto (label eval-dispatch)) EndOfAnswer
Can we get rid of the new line 19 by moving another line somewhere?
HighlitedAnswer Move line 15 after line 11 EndOfAnswer
Could we remove line 14 without changing the value returned by the code? Why or why not?
HighlitedAnswer Yes, if true? is defined as anything that is not #f EndOfAnswer
How can we get rid of line 18 by changing another line?
HighlitedAnswer Change line 10 to (restore exp) EndOfAnswer