Is the cdr of a list always eqv?

Question

I am writing an interpreter for R7RS Scheme to gain a more complete understanding of the Scheme programming language.

From my understanding, eqv? must return #t if both list arguments denote the same location in memory. However, I am not sure if the cdr of a list must always be eqv:

(define l '(a b c))
(eqv? (cdr l) (cdr l))  ; #t of #f?

The missing part of my knowledge is whether or not the cdr of a particular list must always point to a particular location. For a particular list, must cdr always return an identical sublist every time it is called on the list, or can it return a completely new sublist?

(I understand that I can test this empirically using existing Scheme interpreters, but I am mainly interested in what the standard mandates).

Answer 1

• eq? is pointer equality (symbol, boolean, empty list)
• eqv? is #t for everything that is eq? and the same primitive value (number, char)
• equal? is #t for everything that is eqv? and values that look the same

cdr is an accessor. (cdr l) will return the same pointer and thus (eq? (cdr l) (cdr l)) ; ==> #t and so will eqv? and equal? since they are guaranteed #t when a lower level equality predicate is.

Note that is is not the other way around. eg. (equal? "test" "test"); ==> #t but (eqv? "test" "test") can be either #f or #t. The cause of the different behavior is if you reuse constant data when you read the code rather then create new.

It's common to store primitive values in the pointer. Eg. on a 64 bit machine the last 3 bits is always 0 since we access the words aligned. Scheme implementation usually then code 0-7 to indicate type and often when it's 0 the rest of the bits isn't a location at all rather than a number embedded in the pointer. This way you can have a list (1 2 3) that uses 6 words. 3 pairs of 2 words each but no memory used for the numbers when they fit the 61bit size. This is why numbers and char are often eq? while not guaranteed in the report.