6.001 Structure and Interpretation of Computer Programs
Recitation #13
Wednesday, October 22, 2004

Lecture Topics

Exercise

For each of these box & pointer diagrams,
(a) Write a Scheme expression that makes the structure.
(b) Write what Scheme prints for the structure (if you can).
(c) Show how the mutation (given on the right) affects the box-and-pointer diagram and the printed representation, assuming the structure is named x.

1.
 
image1
(define x
  (let ((a '(9)))
    (let ((b (cons a a)))
      (cons b b)))

x => (((9) 9) (9) 9)

(set-cdr! (car x) '(8))

; after this mutation:
image2
x => (((9) 8) (9) 8)
2.
 
image3

(define x
  (let ((w '(a b c)))
    (cons (list w)
          (cons nil (cddr w)))))

x => (((a b c)) () c)
  or (((a b c)) #f c)


(set-car! (cddr x) (caaar x))

; after this mutation:

image4

x => (((a b a)) () a)
  or (((a b a)) #f a)
3.
 
image5
(define x
  (let ((k '(x)))
    (let ((m (list k k)))
      (cons m (cdr m)))))

x => (((x) (x)) (x))





 
(set-cdr! (first x) (second x))

; after this mutation:

image6

x => (((x) x) (x))
4.
 
image7


(define x
  (let ((y (list 1 2 3)))
    (set-car! y y)
    (set-car! (cdr y) y)
    (set-car! (cddr y) y)
    y))

x => ((((((((((((((((...  unprintable




 
(set! x (cdadr x)

; after this mutation:

image8

x => still unprintable
5.
 
image9


(define x
  (let ((z (list 3 2 1)))
    (list z (cdr z) (cddr z))))

x => ((3 2 1) (2 1) (1))




 
(set-car! (cdr (second x)) 4)

; after this mutation:

image10a

x => ((3 2 4) (2 4) (4))
6.
 
image11


(define x
  (let ((c (cons nil nil)))
    (let ((d (cons c c)))
      (set-car! c d)
      (set-cdr! c d)
      c)))

x => ((((((((((((((((...  unprintable




 
(set-car! (cdr x) nil)
(set-cdr! (car x) nil)

; after this mutation:

image12

x => ((()) ())
  or ((#f) #f)

For each of these Scheme expressions,
(a) Draw a box-and-pointer representation of the expression's value.
(b) Write what Scheme prints for the expression's value (if you can).
(c) Show how the mutation (given on the right) affects the box-and-pointer diagram and the printed representation, assuming
the value of the expression is named x.


7.
 
(define x
  (let ((w (list 6 7 8)))
    (set-car! w w)
    (set! w (list w w))
    w))

image13

x => ((((((((((((((((...  unprintable









(set-car! (car x) (cddr x))

; after this mutation:

image14

x => ((() 7 8) (() 7 8))
  or ((#f 7 8) (#f 7 8))
8.
 
(define x
  (let ((y '((a) (b))))
    (set-cdr! (first y) y)
    (set-car! (second y) (cdr y))
    (set! y (car y))
    y))

image15

x => (a (a (a (a ... unprintable




(set-cdr! x (third x))
(set-cdr! (cdr x) nil)

; after this mutation:

image16

x => still unprintable

For each of these printed lists,
(a) Draw a box-and-pointer representation corresponding to it, using as few cons cells as possible.
(b) Write an expression that produces this box-and-pointer structure.
(c) Show how the mutation (given on the right) affects the box-and-pointer structure and the printed representation,
assuming the structure is named x.


9.
 
x => ((1 2) (1) (2))

image17

(define x
  (let ((two '(2)))
    (list (cons 1 two) (list 1) two)))



(set-car! (caar x) 3)

==> error: (caar x) => 1
10.
 
x => (c (b c) (a b c))

image18

(define x
  (let ((bc '(b c)))
    (list 'c bc (cons 'a bc))))




(set-cdr! (cdr x) (third x))

; after this mutation:

image19

x => (c (b c) a b c)