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 to 10pt to 3in
) 3. (assign exp to 10pt to 3in
) 4. (save continue) 5. (save env) 6. (save unev) 7. (assign continue eval-after-first) 8. (goto to 10pt to 3in
) 9. eval-after-first 10. (restore to 10pt to 3in
) 11. (restore to 10pt to 3in
) 12. (test (op true?) (reg val)) 13. (branch (label eval-second-arg)) 14. (assign val #f) 15. (restore to 10pt to 3in
) 16. (goto (reg continue)) 17. eval-second-arg 18. (assign exp to 10pt to 3in
) 19. (assign continue after-second) 20. (goto to 10pt to 3in
) 21. after-second 22. to 10pt to 3in
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. to 10pt to 3in
20. to 10pt to 3in
Can we get rid of the new line 19 by moving another line somewhere?
to .25in to 33pc
Could we remove line 14 without changing the value returned by the code? Why or why not?
to .25in to 33pc
How can we get rid of line 18 by changing another line?
to .25in to 33pc