6.001 Structure and Interpretation of Computer Programs
Recitation #13
Friday, 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
 
(set-cdr! (car x) '(8))
2.
 
image3


(set-car! (cddr x) (caaar x))
3.
 
image5


(set-cdr! (first x) (second x))
4.
 
image7


(set! x (cdadr x)
5.
 
image9


(set-car! (cdr (second x)) 4)
6.
 
image11
 
(set-car! (cdr x) nil)
(set-cdr! (car x) nil)

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.
 
(let ((w (list 6 7 8)))
  (set-car! w w)
  (set! w (list w w))
  w))






(set-car! (car x) (cddr x))
8.
 
(let ((y '((a) (b))))
  (set-cdr! (first y) y)
  (set-car! (second y) (cdr y))
  (set! y (car y))
  y))






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

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.
 
((1 2) (1) (2))






(set-car! (caar x) 3)
10.
 
(c (b c) (a b c))






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