bug#75439: Behaviour of equal? on R6RS records is wrong by the spec, also the Wrong Thing in general

[Daphne Preston-Kendal]

Guile always compares record instances by their field structure when equal? is 
used, including for instances of record types defined by R6RS 
define-record-type, as demonstrated here:

$ guile --r6rs
scheme@(guile-user)> (import (rnrs records syntactic))
scheme@(guile-user)> (define-record-type foo (fields a b))
scheme@(guile-user)> (define x (make-foo 1 2))
scheme@(guile-user)> (define y (make-foo 1 2))
scheme@(guile-user)> (equal? x y)
$1 = #t

There are two parts to this bug report:
1. Objectively, this is not compatible with the R6RS, which clearly requires 
something else here
2. Subjectively, this is the Wrong Thing for all record types and should more 
widely be changed to match what the R6RS (and other record type SRFIs including 
SRFI 99) requires


According to the R6RS,
> The equal? predicate treats pairs and vectors as nodes with outgoing edges, 
> uses string=? to compare strings, uses bytevector=? to compare bytevectors 
> (see library chapter on “Bytevectors”), and uses eqv? to compare other nodes.

So records – at least those whose types were defined by R6RS define-record-type 
– should be compared by eqv?, which on records means by pointer identity.
(R7RS small – for some unknown reason – left equal? unspecified on records. 
SRFI 9 is completely silent about record identity. So technically Guile is 
conforming, for those specs. But e.g. SRFI 99 is in agreement with R6RS on this 
issue.)

The behaviour appears to be connected to a Guile-specific notion of record type 
‘opacity’ which has nothing to do with the R6RS sense of ‘opacity’. (Even 
record types which are not declared to be ‘opaque’ in their R6RS-style type 
definition should use eqv? for equal?.)

Also, in general, comparing records by their field structure in equal? is a bad 
idea.
When record types are used to implement data structures, those data structures 
might have different internal structure but externally represent collections 
which are equivalent in the sense programmers expect of ‘equal?’ – even if 
readtables or similar are used to give them lexical syntax and make them datums.

An example would be a functional set implemented as a binary tree. A binary 
tree which contains two elements might have two different structures, namely it 
could either be left-balanced or right-balanced, as follows:

  [2]
  / \
[1] [ ]

  [1]
  / \
[ ] [2]

(add red-black colouring or other additional fields used to maintain balance as 
you wish)

If it’s supposed to represent a set, and a high-level set API is the only 
exposed interface to the record type for nodes, these should be considered the 
same in the ‘intuitive’ sense of ‘equal?’, because as a set they have the same 
contents; but simply comparing the fields in the nodes will give a wrong answer 
of #f for this sense.

Making equal? be eqv? on records makes the domain of equal?’s graph traversal 
behaviour very well defined (namely, it applies to datum types only).
If you want to make equal? do something more useful on some record types, let 
record types define their own behaviour for it. See Chez Scheme’s ‘Record 
Equality and Hashing’ manual section for a well-designed example of such an 
extension to standard record types. 
<https://cisco.github.io/ChezScheme/csug10.0/objects.html#./objects:h16>
(Note that this design handles cyclical structures correctly.)

There is no semantics of equal? which is correct for all possible record types, 
but ‘eqv?’ is not *wrong* for any record type.


Daphne