[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Scheme-reports] EQV? on numbers should be based on operational equivalence

Hello all,

We need a portable way to implement memoization, and that requires an
equality predicate based on operational equivalence.  As John Cowan
pointed out, the R3RS explicitly defined EQV? in terms of operational
equivalence:  <http://people.csail.mit.edu/jaffer/r3rs_8.html>

   The eqv? procedure implements an approximation to the relation of
   operational equivalence.  It returns #t if it can prove that obj1 and
   obj2 are operationally equivalent.  If it can't, it always errs on
   the conservative side and returns #f.

Here's the R3RS definition of operational equivalence:

   Two objects are operationally equivalent if and only if there is no
   way that they can be distinguished, using Scheme primitives other
   than eqv? or eq? or those like memq and assv whose meaning is defined
   explicitly in terms of eqv? or eq?.  It is guaranteed that objects
   maintain their operational identity despite being named by variables
   or fetched from or stored into data structures.

It then elaborates what this means for various types, including numbers:

   Two numbers are operationally equivalent if they are numerically
   equal (see =, section see section 6.5.4 Numerical operations) and are
   either both exact or both inexact (see section see section 6.5.2

It seems clear to me that this latter elaboration on numbers is
non-normative.  It was adequate on a system without signed zeroes or
NaNs, but it clearly conflicts with the normative definition of
operational equivalence on IEEE 754 systems.

Unfortunately, the R4RS removed the term "operational equivalence" and
retained only the R3RS elaborations.  Nonetheless, EQV? on numbers is
consistent with operational equivalence in _every_ existing Scheme
standard, if one only considers the numbers that are discussed in the
standard.  The R7RS would be the first to deviate from this.
*** Looking at it from another angle:

Is there _any_ job for which the right tool is a numerical equality
predicate that regards 0 and 0.0 as unequal, but 0.0 and -0.0 as equal?

The fact that EQV? distinguishes exact from inexact numbers already
makes it the wrong tool for normal numerical comparisons.  We should
preserve the properties of EQV? that make it the _only_ portable tool
for memoization.

Therefore, I propose that the R7RS should re-integrate the R3RS concept
of "operational equivalence", but with an updated non-normative
elaboration for numbers based on the R6RS.

In particular, on platforms with signed zeroes, the R7RS should mandate
that (eqv? 0.0 -0.0) => #false.

What about NaNs?  If we allow (eqv? +nan.0 +nan.0) => #false for NaNs
with the same bit patterns, then memoization tables would accumulate
redundant entries for NaN arguments.  I would argue that although we
cannot mandate a specific answer for (eqv? +nan.0 +nan.0), we should
mandate that the answer be consistent with operational equivalence.  On
IEEE 754 platforms, this implies that the result should be #true if both
NaNs have the same bit patterns, and #false for NaNs with different bit
patterns if they are distinguishable by standard numerical procedures.

What do you think?


Scheme-reports mailing list