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

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