CS 61A         Summer 2011                 Lab 5

0. Experiment with the calc program including experimenting with display, print, and read.

Available here:

http://inst.eecs.berkeley.edu/~cs61a/sp11/library/calc.scm

1. Warm-up: SICP ex. 2.25 and 2.53

 Exercise 2.25.  Give combinations of cars and cdrs that will pick 7 from each of the following lists:(1 3 (5 7) 9)((7))(1 (2 (3 (4 (5 (6 7))))))

 Exercise 2.53.  What would the interpreter print in response to evaluating each of the following expressions?(list 'a 'b 'c)(list (list 'george))(cdr '((x1 x2) (y1 y2)))(cadr '((x1 x2) (y1 y2)))(pair? (car '(a short list)))(memq 'red '((red shoes) (blue socks)))(memq 'red '(red shoes blue socks))

2. SICP ex. 2.27. This is the central exciting adventure of today’s lab! Think hard about it. There are HINTS for getting started at the end of the lab....

 Exercise 2.27.  Modify your reverse procedure of exercise 2.18 to produce a deep-reverse procedure that takes a list as argument and returns as its value the list with its elements reversed and with all sublists deep-reversed as well. For example,(define x (list (list 1 2) (list 3 4)))x((1 2) (3 4))(reverse x)((3 4) (1 2))(deep-reverse x)((4 3) (2 1))

3. The single quote we’ve been using is really just syntactic sugar for the special form quote. Design a test to show that quote is a special form. Below are some examples of the syntactic sugar (and non-syntactic sugar) versions of quote:

STk> 'hi

hi

STk> (quote hi)

hi

STk> '(+ 1 2 3)

(+ 1 2 3)

STk> (quote (+ 1 2 3))

(+ 1 2 3)

 Exercise 2.55.  Eva Lu Ator types to the interpreter the expression(car ''abracadabra)To her surprise, the interpreter prints back quote. Explain.

5. Each person individually make up a procedure named mystery that, given two lists as arguments, returns the result of applying exactly two of cons, append, or list to mystery’s arguments, using no quoted values or other procedure calls. Here are some examples of what is and is not fair game:

okay                                                                              not okay

(define (mystery L1 L2)                     (define (mystery L1 L2)

(cons L1 (append L2 L1)))                     (cons L1 (cons L2 (cons L1 L2))))

(define (mystery L1 L2)                       (define (mystery L1 L2)

(list L1 (list L1 L1)))                    (cons L1 L2))

(define (mystery L1 L2)                            (define (mystery L1 L2)

(append (cons L2 L2) L1))                     (append L1 (cons L1 ’(A B C))))

Type your mystery definition into a file, and have one of your partners load it into Scheme and try to guess what it is by trying it out with various arguments.

After everyone has tried someone else’s procedure, decide with your partners which procedure was hardest to guess and why, and what test cases were most and least helpful in revealing the definitions.

HINTS FOR SICP ex. 2.27

• What are the base cases?
• What are possible arguments to deep-reverse?
• Will you ever pass it a non-list?
• How does each recursive call get you closer to one of the base cases?
• Try example calls with small input to consider when to use list, cons, and append.