Testing whether two pairs (cons cells) are the same

Question

The following function from pg 150 of the Seasoned Schemer establishes whether two lists have the same identity (i.e. occupy the same memory) by mutating each list's cdr and then checking whether the change has affected both:

(define same?
 (lambda (c1 c2)
   (let ((t1 (cdr c1))
         (t2 (cdr c2)))
     (set-cdr! c1 1)
     (set-cdr! c2 2)
     (let ((v (= (cdr c1) (cdr c2))))
       (set-cdr! c1 t1)
       (set-cdr! c2 t2)
       v))))

Now if I define a_list as follows:

(define a_list (list 'a 'b 'c 'd))

and evaluate

(same? a_list (cdr a_list))

the function returns #f, and the debugger (Dr. Racket) confirms that these two lists -- which ought to share most of their members since the second argument is a proper subset of the first -- do in fact have different copies of the same members. How is this possible?!

For a slight twist on this idea:

(set-cdr! (cddr a_list) a_list)

Now a_list is cyclical. If I test this function with same? it only registers #t when the two arguments are in phase, i.e. (same? a_list a_list) and (same? a_list (cdddr a_list)).

[EDIT The answer is at the bottom of the accepted post's comment chain]

soegaard · Accepted Answer · 2012-06-09T13:32:09.557

4

The same? function does not check whether two lists share elements. It checks whether two pairs (i.e. two cons cells) are the same.

In (define a_list (list 'a 'b 'c 'd)) you have 4 pairs. In (same? a_list (cdr a_list)) you check whether the first and second pair is the same pair, and since they aren't, same? returns #f.

With respect to:

.. and the debugger (Dr. Racket) confirms that these two lists -- which ought to share most of their members since the second argument is a proper subset of the first -- do in fact have different copies of the same members. How is this possible?!

Can you be more precise about how you check this in DrRacket?

The two lists a-list and (cdr a-list) do share members.

EDIT:

Suppose c1 and c2 are names for two different cons cells:

c1: (foo . bar)      c2:  (baz . qux)

Now we evaluate (set-cdr! c1 1) and get:

c1: (foo . 1)      c2:  (baz . qux)

Now we evaluate (set-cdr! c2 2) and get:

c1: (foo . 1)      c2:  (baz . 2)

Then we compare the cdrs with (= (cdr c1) (cdr c2)). Since the cdrs are different, we get #f.

Conclusion: When the cons cells are different, same? returns #f.

Now suppose c1 and c2 are names for the same cons cell:

c1 = c2: (foo . bar)

Now we evaluate (set-cdr! c1 1) and get:

c1 = c2: (foo . 1)

Now we evaluate (set-cdr! c2 2) and get:

c1 = c2: (foo . 2)

Then we compare the cdrs with (= (cdr c1) (cdr c2)). Since the cdrs are the same, we get #t.

Conclusion: When the cons cells are the same, same? returns #f.

EDIT 2

To check whether the cons cell c is one of the cons cells of l use this:

(define (loop c l)
  (cond
    [(null? l) #f]
    [(same? c l) #t]
    [else (loop c (cdr l))]))

edited Jun 09 '12 at 13:32

answered Jun 08 '12 at 18:45

soegaard

30,661
4
57
106

**It checks whether two pairs (i.e. two cons cells) are the same.** `same?` purports to show that two pairs occupy the same memory, but it isn't clear to me how the algorithm distinguishes pairs that are identical from those that share a member. **Can you be more precise about how you check this in DrRacket?** I'm stepping through the code using the debugger in R5RS – planarian Jun 08 '12 at 23:22
1

@Planarian `(A . (B C D)) != (B . (C D))` this is the *only* thing that `same?` checks. It does *not* concern itself with looking for sharing of structure *inside* those *cdr* lists. – Will Ness Jun 09 '12 at 06:38
Btw - normally one would use `eq?` to check whether two cons cells are the same. – soegaard Jun 09 '12 at 09:04
@WillNess My post doesn't question whether `same?` works (it clearly does), but _why_. How is it that `(set-cdr! (A . (B C D)) 1)` doesn't have any affect on `(B . (C D))`? – planarian Jun 09 '12 at 13:13
@soegaard Thanks for expanding your answer, but I'm afraid it doesn't address the case that I'm concerned about, namely when the second pair is the cdr of the first (see my response to Will) – planarian Jun 09 '12 at 13:17
@Planarian When the second pair is the cdr of the first, the two pairs are different. That is, we are in the first case where c1 and c2 are names for different cons cells. Therefore same? returns #f. – soegaard Jun 09 '12 at 13:26
@soegaard But doesn't that mean that every time Scheme takes the cdr of a list, it has to duplicate that segment? That seems terribly inefficient. – planarian Jun 09 '12 at 14:09
@planarian No. Suppose c2=(cdr 2 . ()) and c1=(cdr 1 . c2). Then (cdr c1) simply returns c1 without copying it. Take a look at http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-22.html#%_sec_3.3.1 – soegaard Jun 09 '12 at 14:46
1

@Planarian because `(B C D)` is held there *through a pointer*, not as an inlined value. In Lisp there is an additional level of indirection to everything. `cons` cells hold two pointers to values, not two values. That's why if resetting a pointer held in `c2.cdr` resets also a pointer held in `c1.cdr` it means `c1` and `c2` were the same. – Will Ness Jun 09 '12 at 17:57
@WillNess Yes, the SICP diagrams just made it clear to me. Thank you both! – planarian Jun 09 '12 at 18:18

Testing whether two pairs (cons cells) are the same

1 Answers1