SICP

Exercise 3.17.   Devise a correct version of the  count-pairs  procedure of exercise  3.16  that returns the number of distinct pairs in any structure. (Hint: Traverse the structure, maintaining an auxiliary data structure that is used to keep track of which pairs have already been counted.) SOLUTION The code is here: Exercise 3.17 correct count-pairs The explanation and the box-and-pointer diagram is here: Diagram

Exercise 3.16.   Ben Bitdiddle decides to write a procedure to count the number of pairs in any list structure. ``It's easy,'' he reasons. ``The number of pairs in any structure is the number in the  car  plus the number in the  cdr  plus one more to count the current pair.'' So Ben writes the following procedure: (define (count-pairs x)   (if (not (pair? x))       0       (+ (count-pairs (car x))          (count-pairs (cdr x))          1))) Show that this procedure is not correct. In particular, draw box-and-pointer diagrams representing list structures made up of exactly three pairs for which Ben's procedure would return 3; return 4; return 7; never return at all. SOLUTION The code is here: Exercise 3.16 count-pairs The box-and-pointer diagrams are here: Page 1 Page 2

Exercise 3.15.   Draw box-and-pointer diagrams to explain the effect of  set-to-wow!  on the structures  z1  and  z2  above. The box-and-pointer diagrams are here: Page 1 Page 2

Exercise 3.14.   The following procedure is quite useful, although obscure: (define (mystery x)   (define (loop x y)     (if (null? x)         y         (let ((temp (cdr x)))           (set-cdr! x y)           (loop temp x))))   (loop x '())) Loop  uses the ``temporary'' variable  temp  to hold the old value of the  cdr  of  x , since the  set-cdr!  on the next line destroys the  cdr . Explain what  mystery  does in general. Suppose  v  is defined by  (define v (list 'a 'b 'c 'd)) . Draw the box-and-pointer diagram that represents the list to which  v  is bound. Suppose that we now evaluate  (define w (mystery v)) . Draw box-and-pointer diagrams that show the structures  v  and  w after evaluating this expression. What would be printed as the values of  v  and  w  ? SOLUTION The code is here: Exercise 3.14 mystery The box-and-pointer diagrams are here:

Exercise 3.13.    Consider the following  make-cycle  procedure, which uses the  last-pair  procedure defined in exercise  3.12 : (define (make-cycle x)   (set-cdr! (last-pair x) x)   x) Draw a box-and-pointer diagram that shows the structure  z  created by (define z (make-cycle (list 'a 'b 'c))) What happens if we try to compute  (last-pair z) ? SOLUTION The code is here: Exercise 3.13 make-cycle The box-and-pointer diagrams are here:

Exercise 3.12.    The following procedure for appending lists was introduced in section  2.2.1 : (define (append x y)   (if (null? x)       y       (cons (car x) (append (cdr x) y)))) Append  forms a new list by successively  cons ing the elements of  x  onto  y . The procedure  append!  is similar to  append , but it is a mutator rather than a constructor. It appends the lists by splicing them together, modifying the final pair of  x  so that its  cdr  is now  y . (It is an error to call  append!  with an empty  x .) (define (append! x y)   (set-cdr! (last-pair x) y)   x) Here  last-pair  is a procedure that returns the last pair in its argument: (define (last-pair x)   (if (null? (cdr x))       x       (last-pair (cdr x)))) Consider the interaction (define x (list 'a 'b)) (define y (list 'c 'd)) (define z (append x y)) z (a b c d) (cdr x) < response > (define w (append! x y)) w (a b c d) (cdr x) < response > What are the missing < respo

Exercise 3.11.    In section  3.2.3  we saw how the environment model described the behavior of procedures with local state. Now we have seen how internal definitions work. A typical message-passing procedure contains both of these aspects. Consider the bank account procedure of section  3.1.1 : (define (make-account balance)   (define (withdraw amount)     (if (>= balance amount)         (begin (set! balance (- balance amount))                balance)         "Insufficient funds"))   (define (deposit amount)     (set! balance (+ balance amount))     balance)   (define (dispatch m)     (cond ((eq? m 'withdraw) withdraw)           ((eq? m 'deposit) deposit)           (else (error "Unknown request -- MAKE-ACCOUNT"                        m))))   dispatch) Show the environment structure generated by the sequence of interactions (define acc (make-account 50)) ((acc 'deposit) 40) 90 ((acc 'withdraw) 60) 30 Where is the local state for  acc  kep

Exercise 3.10.   In the  make-withdraw  procedure, the local variable  balance  is created as a parameter of  make-withdraw . We could also create the local state variable explicitly, using  let , as follows: (define (make-withdraw initial-amount)   (let ((balance initial-amount))     (lambda (amount)       (if (>= balance amount)           (begin (set! balance (- balance amount))                  balance)           "Insufficient funds")))) Recall from section  1.3.2  that  let  is simply syntactic sugar for a procedure call: (let ((< var > < exp >)) < body >) is interpreted as an alternate syntax for ((lambda (< var >) < body >) < exp >) Use the environment model to analyze this alternate version of  make-withdraw , drawing figures like the ones above to illustrate the interactions (define W1 (make-withdraw 100)) (W1 50) (define W2 (make-withdraw 100)) Show that the two versions of  make-withdraw  create objects with t