[swift-evolution] [pitch] Comparison Reform

[Jonathan Hull]

> On Apr 25, 2017, at 9:34 PM, Jaden Geller <jaden.geller at gmail.com> wrote:
> 
>> 
>> On Apr 25, 2017, at 8:28 PM, Jonathan Hull via swift-evolution <swift-evolution at swift.org <mailto:swift-evolution at swift.org>> wrote:
>> 
>> 
>>> On Apr 25, 2017, at 7:17 PM, Xiaodi Wu <xiaodi.wu at gmail.com <mailto:xiaodi.wu at gmail.com>> wrote:
>>> 
>>> I'll refer you to Steve Canon's answer on StackOverflow: http://stackoverflow.com/questions/1565164/what-is-the-rationale-for-all-comparisons-returning-false-for-ieee754-nan-values/1573715#1573715 <http://stackoverflow.com/questions/1565164/what-is-the-rationale-for-all-comparisons-returning-false-for-ieee754-nan-values/1573715#1573715>
>> I get what he is saying about not being able to suddenly change C’s definition to the opposite boolean value (even if they would have designed it differently for modern systems).  We aren’t C though.  And nil is a different name than NaN.  This gives us a way to make a change without breaking conformance.
> 
> I really like this idea, but it’s not true to say this doesn’t break IEEE-compliance if what we expose as NaN no longer compares not equal to itself.

I would argue that we aren’t actually exposing NaN, so much as we are exposing something which is different, but stays in sync with it.  NaN is still there in the format under the surface, but you wouldn’t be able to access it directly (only indirectly).

It is a bit of a magic trick.  Whenever the value is NaN, we only let you access ‘.none’ instead of the value.  So, if you were able to directly compare NaN with NaN, it would be false (or unordered), but you can’t get ahold of them to do that comparison.

The important thing to me is binary compatibility.  Algorithms need to be rewritten a bit anyway when moving them into swift, so that isn’t a big deal to write it for nil instead of NaN… especially when the compiler helps you due to the optional.  But data, which might contain NaN, needs to be read/written in an interchangeable format.  That is why I suggest having Optional do the lifting to match NaN. Anytime it crosses a boundary which strips the wrapper, it will just work (as long as we import as Double?).

>>> Bottom line is, whatever it's designed for, it's here to stay. I'm *not* on any IEEE committee; I'm not qualified to design an alternative universe of floating point types; and the Swift evolution mailing list (or even Swift itself) is not the place to design one. I and others rely on Swift floating point types to be IEEE-complaint, so that's where we start the discussion here about Comparable.
>> 
>> It *is* IEEE compliant (or at least the same amount we currently are), what is different is the way we interface with that in code.  You can think of Swift Double as a simple (runtime-cost-free) wrapper around the compiler’s double that limits how you can touch it (in order to provide additional safety guarantees).  Sounds very swifty to me… we do similar things with other C constructs using various wrappers.  We aren’t getting rid of NaN behind the scenes, just packaging it’s use in a way which aligns with Swift as a whole…  What changes is the programer’s mental model. The bits are exactly the same.
>> 
>> If the naming is what bothers you, we could even just create a “new” Swift type that is this wrapper, and then discourage the use of Double outside of places where NaN is needed.  I feel like NaN is actually needed in relatively few places though…
>> 
>>>  
>>> The programmer (mental) model would be that Swift Double just doesn’t have NaN, and anywhere where you would normally return NaN, you return nil instead.
>>> 
>>> Look, you can already use Double? today. There is no barrier to trying it out for yourself. However, `Double?.none` doesn't mean the same thing as `Double.nan`. The former indicates that _there is no value_; the latter indicates that there _is_ a value, it's just _not a number_. Suppose I parse a list of numbers into an array. If I ask for [Double].last and get nil, it's telling me that _there are no elements in the array_. If I get .nan, it's telling me that there *is* a value, it just wasn't a number. In the former case, I'd do nothing. In the latter case, I might prompt the user: this isn't a number!
>>>  
>>> However, the property of using NaN’s bits to represent nil let’s us inter-op seamlessly with C and ObjC (or any other language’s) code.  They just treat it as a double with NaN as normal (including NaN != NaN) and we interface with it as ‘Double?'
>>> 
>>> I'm going to sound like a broken record, now. Whether floating point types in Swift conform to IEEE standards is _not_ up for discussion, afaict; that's simply a given. Now, around that constraint, we're trying to design a revised Comparable protocol. Code written today for floating point work expects NaN != NaN. That is just something that is and will forever be. We break source compatibility if we change that.
>> 
>> As I said above, they *do* conform to those standards… they just don’t expose the full capabilities directly to the end programmer.  The capabilities are still there, you just have to be more explicit about their use.  
>> 
>> I could be wrong, but I believe that in the current version of Swift, the result of doing comparisons with NaN is actually undefined at the moment… so it isn’t breaking source compatibility with the defined language.  Just with code which is using implementation artifacts…
> 
> I think you’re incorrect. It says in the docs for NaN that it always compares false with itself.

That’s too bad. I was looking in the language guide.  I guess it would be a breaking change to change Float/Double.  We could still use the idea though, we would just have to add the wrapper as a new type with a different name.  

I would be in favor of renaming Float/Double to something like CFloat/CDouble, and then reusing the names for the wrappers. Not sure if I could convince the powers that be of that though…

I am not sure how much code actually uses NaN in this way in the real world.  


>> C code might require some simple changes to work in Swift, but as you argued passionately before, that is already to be expected.  We shouldn’t have the expectation of copy/pasting C code without thinking through the differences in &+, etc...
>> 
>>> 
>>>> This did not always work correctly, if I recall, but it does now and it's an intentional part of the design. However, NaN must compare not equal to every NaN. These could not be more different properties. It seems quite absurd on its face that we might want NaN to compare equal to a value of type `Optional<UIViewController>`.
>>> 
>>> Is there an algorithm that requires NaN != NaN that couldn’t be reasonably rewritten to handle nil/optionals instead? 
>>> 
>>> I don't need an algorithm to show you the problem. See this expression: `0 * Double.infinity == .infinity * 0` correctly evaluates to false. Zero times infinity is simply not equal to infinity times zero. You're suggesting a design where the result would be true, and that simply won't fly, because it's just not true.
>> 
>> IEEE 754 says that the result of any comparison with NaN should be *undefined*.  C’s implementation is the one who brings us this idea that NaN != NaN.  The *correct* evaluation according to 754 would be ‘undefined’.  We aren’t breaking 754, just breaking away from a C convention… in a way which is very much in line with how Swift breaks away from other C conventions.
> 
> I don’t think this is true. I got excited for a minute and looked it up. Where do you see that comparison behavior is undefined?

Oh, sorry, I didn’t mean that the behavior is undefined…  I used the wrong word (freudian slip).  I meant to say that the correct evaluation is *unordered*.  Four possibilities are defined in the spec: GreaterThan, LessThan, Equal, and Unordered.  NaN is always unordered when compared with anything.

From the spec:
> For every supported arithmetic format, it shall be possible to compare one floating-point datum to another in that format (see 5.6.1). Additionally, floating-point data represented in different formats shall be comparable as long as the operands’ formats have the same radix.
> Four mutually exclusive relations are possible: less than, equal, greater than, and unordered. The last case arises when at least one operand is NaN. Every NaN shall compare unordered with everything, including itself. Comparisons shall ignore the sign of zero (so +0 = −0). Infinite operands of the same sign shall compare equal.
> 


And as I read further, It does appear I was wrong about NaN != NaN (when doing a partial order).  I had somehow missed it in my first read-through  In the 2008 version of the spec, it goes on to say:
> Languages define how the result of a comparison shall be delivered, in one of two ways: either as a relation identifying one of the four relations listed above, or as a true-false response to a predicate that names the specific comparison desired.
> 
Which means that we should have 4 functions: ==, <, >, and isUnordered… where isUnordered is the only one which returns true for NaN

One loophole is that it gives alternate names for those functions which we could use for the official behavior (and still use < and == for our strict total order):
• compareQuietEqual
• compareQuietGreater
• compareQuietLess
• compareQuietUnordered

Also, we should all read section 5.10, as it seems to give a canonical answer of how to do a total order for 754:
> totalOrder(x, y) imposes a total ordering on canonical members of the format of x and y:
> 
> a)  If x < y, totalOrder(x, y) is true.
> 
> b)  If x > y, totalOrder(x, y) is false.
> 
> c)  Ifx=y:
> 
> 1)  totalOrder(−0, +0) is true.
> 
> 2)  totalOrder(+0, −0) is false.
> 
> 3)  If x and y represent the same floating-point datum:
> 
> i) If x and y have negative sign,
> totalOrder(x, y) is true if and only if the exponent of x ≥ the exponent of y
> 
> ii) otherwise
> totalOrder(x, y) is true if and only if the exponent of x ≤ the exponent of y.
> 
> d) If x and y are unordered numerically because x or y is NaN:
> 
> 1)  totalOrder(−NaN, y) is true where −NaN represents a NaN with negative sign bit and y is a
> 
> floating-point number.
> 
> 2)  totalOrder(x, +NaN) is true where +NaN represents a NaN with positive sign bit and x is a floating-point number.
> 
> 3)  If x and y are both NaNs, then totalOrder reflects a total ordering based on:
> 
> i)  negative sign orders below positive sign
> 
> ii)  signaling orders below quiet for +NaN, reverse for −NaN
> 
> iii) lesser payload, when regarded as an integer, orders below greater payload for +NaN, reverse for −NaN.
> 
> Neither signaling NaNs nor quiet NaNs signal an exception. For canonical x and y, totalOrder(x, y) and totalOrder( y, x) are both true if x and y are bitwise identical. 
> 

Here we see NaN == NaN when doing a total order (as long as the payloads are the same).

Thanks,
Jon







-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20170425/c9116c18/attachment.html>