my attempt to do the exercises in sicp.

Monday, September 7, 2009

sicp exercise 3.16


; 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.



sicp exercise 3.15


; Exercise 3.15.  Draw box-and-pointer diagrams to explain the effect of set-to-wow! on the structures z1 and z2 above.



sicp exercise 3.14


; 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 ?

(define (mystery x)
  (define (loop x y)
    (if (null? x)
        y
        (let ((temp (cdr x)))
          (set-cdr! x y)
          (loop temp x))))
  (loop x '()))

(define v (list 'a 'b 'c 'd))
(display v) (newline)
(define w (mystery v))
(display v) (newline)
(display w) (newline)

; It reverses the list

Sunday, September 6, 2009

sicp exercise 3.13



; 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)?

(define (last-pair x)
  (if (null? (cdr x))
      x
      (last-pair (cdr x))))

(define (make-cycle x)
  (set-cdr! (last-pair x) x)
  x)

(define z (make-cycle (list 'a 'b 'c)))

(display z) (newline)

(display (last-pair z)) (newline)
;infinite loop

sicp exercise 3.12


; 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 consing 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 <response>s? Draw box-and-pointer diagrams to explain your answer.

(define (append! x y)
  (set-cdr! (last-pair x) y)
  x)

(define (last-pair x)
  (if (null? (cdr x))
      x
      (last-pair (cdr x))))

(define x (list 'a 'b))
(define y (list 'c 'd))
(define z (append x y))

;(display x)(newline)
;(display y)(newline)
;(display z)(newline)


(display (cdr x)) (newline)

(define w (append! x y))
(display w) (newline)

(display (cdr x)) (newline)


sicp exercise 3.9



; Exercise 3.9.  In section 1.2.1 we used the substitution model to analyze two procedures for computing factorials, a recursive version
;
; (define (factorial n)
;   (if (= n 1)
;       1
;       (* n (factorial (- n 1)))))
;
; and an iterative version
;
; (define (factorial n)
;   (fact-iter 1 1 n))
; (define (fact-iter product counter max-count)
;   (if (> counter max-count)
;       product
;       (fact-iter (* counter product)
;                  (+ counter 1)
;                  max-count)))
;
; Show the environment structures created by evaluating (factorial 6) using each version of the factorial procedure.