CS 61A Summer 2011 Lab 6
1. Load the Scheme-1 interpreter from the file
To start the interpreter, type (scheme-1). Familiarize yourself with it by evaluating some expressions. Remember: you have all the Scheme primitives for arithmetic and list manipulation; you have lambda but not higher-order functions; you don’t have define. To stop the scheme-1 interpreter and return to STk, just evaluate an illegal expression, such as ().
a) Trace in detail how a simple procedure call such as
((lambda (x) (+ x 3)) 5)
is handled in scheme-1.
b) Since all the Scheme primitives are automatically available in scheme-1, you might think you could use STk’s primitive map function. Try these examples:
Scheme-1: (map first ’(the rain in spain))
Scheme-1: (map (lambda (x) (first x)) ’(the rain in spain))
Explain the results.
c) Modify the interpreter to add the special form and. Test your work. Be sure that as soon as a false value is computed, your and returns #f without evaluating any further arguments.
For the rest of the lab, start by reading SICP section 2.3.3 (pages 151–161).
2. SICP ex. 2.62.
3. The file ~cs61a/lib/bst.scm contains the binary search tree procedures from pages 156–157 of SICP. Using adjoin-set, construct the trees shown on page 156.