Inconsistent box-and-pointer diagrams in SICP

Question

Structure and Interpretation of Computer Programs (SICP)'s box-and-pointer diagrams in Figures 3.16 and 3.17 don't appear equivalent (purely with respect to value, not memory) even though it says they are. ("When thought of as a list, z1 and z2 both represent "the same" list, ((a b) a b))", pg. 258)

(define x (list 'a 'b))
(define z1 (cons x x))
(define z2 (cons (list 'a 'b) (list 'a 'b)))

SICP diagrams the pair z1 like this:

and z2 like this:

The arrows in the pair, z1, don't both seem to be pointing to the entire pair, x. They don't even point to the same thing, despite both having received the same (memory and value) pair. I would evaluate the first diagram as (a b), and the second as ((a b) a b)

I could guess that each arrow is actually pointing to the entire pair, x, but in figure 2.3 on page 98:

it very clearly points to an entire box by either pointing to the side or in between two items.

Am I understanding box-and-pointer diagrams incorrectly or something else entirely?

Answer 1

You're reading too much into it. :-) If it points into the box anywhere, assume it's a pointer to that cons cell. You cannot specifically point to the car or cdr portion of it.

Answer 2

Your last assumption is correct. The dot indicates where the pointer value is, the whole double box the arrow is pointing at is the target. It doesn't matter if it's pointing on the side, top middle, top left or top right. It's the whole pair that is the "address" of the object.

You can't point to a part of an object without accessing its part with car and cdr. The second you do that you have whatever it was pointed to and not a indirect pointer. (car '(a b)) ; ==> a and a doesn't have any essence of the list that still is pointing to it until it is garbage collected.

We could illustrate it like this instead:

[=#1|#3|#2]
[=#2|#3|()] 
[=#3|a |#4]
[=#4|b |()]

The first value with =# is the location of the box itself, while the next two are car and cdr. Above, x points to the address #3 and z1 to #1. Let's make z2

[=#5|#6|#8]
[=#6|a |#7] 
[=#7|b |()] 
[=#8|#9|()]
[=#9|a |#10]
[=#10|b |()]

As you can see, z2 uses two more cons than z1 since it doesn't reuse the same object as both elements of its list, but uses individual similar-looking lists.

In the drawings, both car and cdr of z1 point to the same list x. z2 points to two different lists, but the elements in those lists are the same.

The reason for this is that symbols are singletons. Thus, you only have one symbol object for a and evaluating 'a in two different places will both point to the same a. Other singletons are #f, #t and ()

cons always creates a fresh pair and list is just a procedure that cons together the arguments. Thus the same code (list 'a 'b) two places in the expression makes two different objects that just look the same.

(eq? (car z1) (cdr z1))    ; ==> #t same object
(eq? (car z2) (cdr z2))    ; ==> #f not same object
(equal? (car z2) (cdr z2)) ; ==> #t they look the same, but they are not the same. (created at different places)

Quoted data can be seen as created all at once before the program starts. Thus this is undefined.

(eq? '(a b) '(a b))         ; ==> #t or #f (undefined)
(eq? '(b c) (cdr '(a b c))) ; ==> #t or #f (undefined)

The reason is that Scheme is allowed, but not obligated, to reuse data the same way as with the structure z1.