R6RS main report section 5.10:

> Variables and objects such as pairs, vectors, bytevectors, strings, hashtables, and records implicitly refer to locations or sequences of locations. […] An object fetched from a location, by a variable reference or by a procedure such as car, vector-ref, or string-ref, is equivalent in the sense of eqv? (section 11.5) to the object last stored in the location before the fetch.

(Comparable language is found in the R5RS and R7RS small reports.)

A catena of quotations from SRFI 101:

> A random-access pair (or just pair) is a compound structure with two fields called the car and the cdr fields (consistent with the historical naming of pair fields in Scheme). Pairs are created by the procedure cons. The car and cdr fields are accessed by the procedures car and cdr.

s.v. ‘cons’:
> Returns a newly allocated pair whose car is obj1 and whose cdr is obj2. The pair is guaranteed to be different (in the sense of eqv?) from every existing object.

‘Implementation requirements’:
> The behavior of eq? and eqv? on random-access pairs must be the same as that for pairs, vectors, or records. Namely, two random-access pair objects are eq? if and only if they are eqv?, and they are eqv? if and only if they refer to the same location in the store.
> […]
> Implementations are encouraged, but not required, to support random-access pairs and lists as their primary pair and list representation. In such an implementation, the external representation of random-access pairs and list should be as described in section 4.3.2 (Pairs and lists) of R6RS, the behavior of equivalence predicates on random-access pairs should be as described in section 11.5 (Equivalence predicates) of R6RS, and so on. In short, all pairs should be random-access pairs.

The obvious problem is that random-access lists are not mutable, so any Scheme code which uses the (rnrs mutable-pairs) library cannot take advantage of this recommendation.

There is a slightly less obvious problem, though. The ‘cdr’ procedure on random-access pairs does not fulfil the requirement of R6RS section 5.10 that objects fetched from locations are eqv? to the objects last stored in those location. Therefore, it is not possible with a ‘pure’ random-access pair implementation (like the sample implementation of SRFI 101) to fulfil the recommendation that ‘the behavior of equivalence predicates on random-access pairs should be as described in section 11.5 of the R6RS’, nor the requirement that ‘The behavior of eq? and eqv? on random-access pairs must be the same as that for pairs, vectors, or records.’

The reason is that Okasaki’s random-access lists are, effectively, chunked into vectors, and the ‘cdr’ operation will copy the first chunk (excluding the first element), leaving the pointer to additional chunks in place. (This is not exactly how they work, but it’s sufficiently accurate to understand the problem.) In this example, the ‘cdr’ operation may create a new value distinct from the original pair:

(define suits (cons 'clubs (cons 'spades (cons 'hearts (cons 'diamonds '())))))
(define joker (cons 'joker suits))
(eqv? suits (cdr joker)) ;=> could be #t or #f
;; the sample implementation happens to make that appear to work; if you’re not convinced, try adding another:
(define joker2 (cons 'joker joker))
(eqv? joker (cdr joker2)) ;=> could be #t or #f (#f in the sample implementation)

A future Scheme report which makes pairs immutable could allow implementations to use random-access lists by changing the behaviour of ‘eqv?’ on pairs to recursively look at their contents, instead of simply going by their location in the store, since immutable pairs whose contents are operationally equivalent to one another are themselves operationally equivalent. Such a change might be inadvisable for other reasons, though (it would partially break the common use of ‘cons’ or ‘list’ to create sentinel values only useful for their identity). It could also explicitly specify that the cdr field of a pair is not a location in the sense of (the equivalent of) section 5.10 of the R6RS.

Daphne

P.S. This of course is of no current practical importance since no implementation has adopted SRFI 101 in the way ‘encouraged’, though some provide it as a library completely distinct from regular Scheme pairs. However, after having to explain this problem for the nth time, I figured it was worth sending to the mailing list so it would be archived somewhere I and others could more easily point to in future.