Notes by Brad Lucier about eqv?
My goal is to incorporate others' comments in this document as appropriate to reflect accurately the discussion on this subject.
My background: I'm an educated, enthusiastic amateur when it comes to IEEE arithmetic, somewhat less so when it comes to Scheme and programming languages in general.
If something is stated in the passive voice, I guess I'm claiming that I got that information from somewhere else, and I tried to preface my own opinions with "I".
Part 4 contains my proposed revisions.
1. General statements about IEEE numbers and NaNs:
1.1 In general, the view has been that IEEE arithmetic will be implemented and used/expoited through the cooperation of hardware, libraries, and programming languages. Hardware should provide what it can (and many things that were left to libraries and interrupts early on, such as implementation of subnormal numbers in early IBM Power machines, have moved to hardware), libraries take up the slack, and some accomodation needs to be made in programming languages.
1.2 It was assumed that NaNs would be returned when certain "error" conditions occured, and would provide in their mantissa certain diagnostic information about what each error condition might be. Such results depended on the libraries provided by each OS, so one machine/OS combination might have many NaNs, one might have few. The sign of a NaN has no meaning, and indeed the "default" NaN returned for 0/0, say, has different signs on x86 and PPC processors.
1.3 Because programming languages generally rely on the OS's builtin mathematical libraries to return results for, e.g., sin or acos, the results returned by expressions in that language will be affected, or determined, by the library results. If the libraries deal with NaNs as input, or generate NaNs as output, then those values will be used in programs written in the language.
1.4 So, if a programming language had an eqv?-type predicate that could distinguish NaNs based on their mantissas, one could set up a table at at the beginning of the program by calling various library routines with erroneuous arguments, and associate with each returned NaN value a string associated with the types of errors that caused that NaN to be generated. In a system with few NaNs, each NaN may be associated with many (or all) error strings, while a system might generate several unique NaNs to indicate several types of errors. In the latter case, each NaN may be associated only with one descriptive error string. One can do this without knowing anything about the values returned by the libraries, except that they can be tested as NaNs (which (= x x) can do) and they can be distinguished by eqv?
1.5 NaNs are generally propagated through computations, except possibly when the result of a computation can be inferred no matter the numerical result substitued for the NaN, e.g., (max +inf.0 +nan.0) => +inf.0. Propagation of NaNs allows one to have, at the end of the computation with a NaN result, information about the first NaN generated in one of the arms of the DAG that generates the final result.
1.6 Various IEEE-type arithmetics differ based on the underlying radix, precision, and maximum exponent. I don't consider a value like 1.0000000000000000000 (where all the zeros are significant) equivalent to 1.000000 (with fewer significant zeros); I don't think that numbers with different precisions, even with the same numerical value, should be equivalent. In a language with generic numerical primitives, where (sin 1.0f0) might return a single-precision result that differs numerically from a 64-bit result of (sin 1.0d0), I don't consider 1.0f0 and 1.0d0 to be equivalent. (This seems to be the R6RS view, too.)
2. General Statement about Scheme and eqv?
2.1 About equivalence predicates: Generally, I see eq? as meaning (as much as possible) "identical", as in the same object, and "eqv?" as meaning (as much as possible) substitutionally equivalent (which seems to motivate the R6RS definition of eqv? on inexacts).
2.2 The definition of eqv? in R6RS (from the HTML R6RS standard)
2.2.1 The eqv? procedure returns #t if one of the following holds:
Obj1 and obj2 are both inexact number objects, are numerically equal (see =, section 11.7), and yield the same results (in the sense of eqv?) when passed as arguments to any other procedure that can be defined as a finite composition of Scheme’s standard arithmetic procedures.
2.2.2 The eqv? procedure returns #f if one of the following holds:
Obj1 and obj2 yield different results (in the sense of eqv?) when passed as arguments to any other procedure that can be defined as a finite composition of Scheme’s standard arithmetic procedures.
2.3 The definition of eqv? in R5RS.
2.3.1 The eqv? procedure returns #t if:
obj1 and obj2 are both numbers, are numerically equal (see =, section 6.2), and are either both exact or both inexact.
2.3.2 The eqv? procedure returns #f if:
obj1 and obj2 are numbers for which the = procedure
returns #f.
3. Eqv? in the November 10 Draft
"Section such-and-such" refers to the section in the draft.
3.1 Section 1.3.5:
For example, list->vector takes a list and returns a vector whose elements are the same (in the sense of eqv?) as those of the list.
3.2 Section 2.4:
The lexical syntax #⟨n⟩# serves as a reference to some object labelled by #⟨n⟩=; the result is the same object as the #⟨n⟩= as compared with eqv? (see section 6.1).
3.3 Section 3.4:
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 6.1) to the object last stored in the location before the fetch.
3.3.1 I believe that this reference and the reference in 3.1 (numbering of these notes) are related.
3.4 Section 4.2.1:
Semantics: A case expression is evaluated as follows. ⟨Key⟩ is evaluated and its result is compared against each ⟨datum⟩. If the result of evaluating ⟨key⟩ is equivalent (in the sense of eqv?; see section 6.1) to a ⟨datum⟩, then the expressions in the corresponding ⟨clause⟩ are evaluated in order and the results of the last expression in the ⟨clause⟩ are returned as the results of the case expression.
3.5 Section 4.2.5: Example
(eqv? (delay 1) 1) =⇒ unspecified
3.6 Section 6.1, definition of equivalence predicates.
I will not repeat the entire section here, but only parts I find relevant. If other parts come up in the discussion, I will add them here for reference.
3.6.1 eqv? of inexact numbers:
The eqv? procedure returns #t if:
• obj1 and obj2 are both inexact real numbers conforming to the IEEE 754-2008 standard, and have the same radix, precision, maximum exponent, sign, exponent and significand as described in that standard, but are not both representations of NaNs.
3.6.2 Section 6.2:
Section 6.2 is all about numbers. I make a few notes.
3.6.2.1 The section uses the word "equivalent" twice without saying what "equivalent" means:
3.6.2.1.1 In Section 6.2.2:
If two implementations produce exact results for a com- putation that did not involve inexact intermediate results, the two ultimate results will be mathematically equivalent.
3.6.2.1.2 In Section 6.2.4:
IEEE 754 specifies multiple NaN values. Scheme generally does not care if there is a single value (bit pattern) for NaN, or if there are multiple values: if there are multiple NaN values, or just one, they are all equivalent in terms of Scheme computation.
3.6.2.2 Also in 6.2.4, there is the statement
A Scheme implementation is not required to distinguish negative zero. If it does, however, the behavior of the transcendental functions is sensitive to the distinction in accordance with IEEE 754. Specifically, in a Scheme implementing complex numbers and negative zero, (imag-part (log -1.0-0.0i)) is −π rather than π.
3.6.2.2.1
My comment: IEEE 754 does not deal with complex numbers.
3.6.2.3 The text says:
The numbers positive infinity, negative infinity and NaN are written +inf.0, -inf.0 and +nan.0 respectively. NaN may also be written -nan.0.
3.6.2.3 In Section 6.2.7, it is stated that
The procedure number->string takes a number and a radix and returns as a string an external representation of the given number in the given radix such that
(let ((number number)
(radix radix))
(eqv? number (string->number (number->string number
radix)
radix)))
is true. It is an error if no possible result makes this expression true.
4 My proposed revisions
4.1 My proposed revision to Section 6.1.
Given my general description above about the purpose and implementation of IEEE arithmetic, I believe that the exception for NaNs leads to unnecessary difficulties, in that it does not interact well with the underlying hardware and system libraries. I would propose that this clause read:
The eqv? procedure returns #t if:
• obj1 and obj2 are both inexact real numbers conforming to the IEEE 754-2008 standard, and have the same radix, precision, maximum exponent, sign, exponent and significand as described in that standard.
4.2 My proposed revision to Section 6.2.4: I would remove the statement
IEEE 754 specifies multiple NaN values. Scheme generally does not care if there is a single value (bit pattern) for NaN, or if there are multiple values: if there are multiple NaN values, or just one, they are all equivalent in terms of Scheme computation.
4.3 My proposed revision to Section 6.2.7: I would rather start with an external representation, and write:
The procedure number->string takes a number and a radix and returns as a string an external representation of the given number in the given radix such that if string is the representation of any number,
(let* ((string string)
(radix radix)
(number (string->number string)))
(eqv? number
(string->number (number->string number
radix)
radix)))
is true. It is an error if no possible result makes this expression true.
4.3.1 Rationale: No matter what we do, R7RS will have at most two external representations for NaNs ("+nan.0" and "-nan.0"); the above rewrite implies that the NaN returned by one instance of (string->number "+nan.0") will be eqv? to any other instance of the result of (string->number "+nan.0"). We need this because number->string "collapses" all NaNs to a single external representation.
4.4 I am open to suggestions about what to do about non-IEEE inexact number systems. I will make a few comments:
4.4.1 "Extended" floating-point systems based, e.g., on GMP and MPFR are going to have numbers of the same general form as IEEE floating point numbers, with radixes, signs, precisions, maximum exponents, etc. It would be good if R7RS distinguished such numbers based on these properties.
4.4.2 Comparing my proposed definition of eqv? with the R6RS definition of eqv? reminds me of a quote from Tony Hoare's Turing Award lecture:
There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies.
4.4.2.1 While I believe that the R6RS definition does the right thing, I can't think how to absolutely convince myself of that. It bothers me that adding a new function in the next standard could take two numbers that are now "eqv?" and turn them into non-"eqv?", that is, "eqv?"-ness is not an intrisic property of the numbers.
4.4.3 Perhaps a more general, slightly more complicated phrasing that would work for IEEE 754-2008 as well as GMP/MPFR-type inexact implementations:
The eqv? procedure returns #t if:
• obj1 and obj2 are both inexact real numbers in a system where inexact numbers are specified by radix, precision, maximum exponent, sign, exponent, and significand (as in IEEE 754-2008), and obj1 and obj2 have the same radix, precision, maximum exponent, sign, exponent and significand.