[swift-evolution] [pitch] Comparison Reform

[Xiaodi Wu]

As discussed a long time ago, and as I raised here in an earlier reply in
this thread, a total order over floating point values is almost never what
you want. It distinguishes between +0.0 and -0.0, between +NaN and -NaN,
between signaling NaN and quiet NaN, between different NaN payloads, and
for IEEE Decimal (not yet implemented in Swift), between different
representations of the same floating point value based on their exponent.
Swift already exposes this function as `isTotallyOrdered` and it is, well,
very niche.


On Wed, Apr 26, 2017 at 2:08 AM, Jaden Geller <jaden.geller at gmail.com>
wrote:

>
> On Apr 25, 2017, at 11:50 PM, Jonathan Hull <jhull at gbis.com> wrote:
>
>
> 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> wrote:
>
>
> On Apr 25, 2017, at 7:17 PM, Xiaodi Wu <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
>
>
> 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).
>
>
> The problem is that the IEEE spec requires that certain operations return
> NaN. Either nil is NaN in this model, and we’re breaking the spec for
> equality, or nil is different from NaN in this model, and we’re breaking
> the spec for when NaN should be produced.
>
> 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.
>
>
> I don’t find this argument compelling. Again, if it doesn’t act like NaN,
> it isn’t following spec. It doesn’t matter that it has the same bit
> representation.
>
> 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?).
>
>
> I think this would be a cool idea were it not that so many people are
> against breaking the spec. This trick did work well for UnsafePointer, but
> the circumstances were different.
>
> Anyway, I would be partially in favor of this idea, but I don’t think
> there’s any way the community as a whole is going to be on-board.
>
> 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’d be a lot more in favor of this as compared to the Optional suggestion
> above, but I’m worried about the API surface impact. It also does not solve
> our `Equatable` and `Comparable` issues…
>
> I guess we could just say `PotentiallyUnknown<Double>` doesn’t conform to
> either, and you need to unwrap if you’d like to compare. We could also add
> optional-returning comparison functions without creating a formal protocol.
> I think this would all be pretty reasonable.
>
> 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…
>
>
> We could also write `typealias CDouble = PartiallyUnknown<Double>` so it’s
> less painful to work with. I’d be very happy if `Double` trapped.
>
> 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
>
>
> That sounds a lot more like what I expected, cool.
>
> 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
>
>
> Are you suggesting that `<` and friends trap? Is this still in the
> type-system aware NaN world, or is this an entirely different option you’re
> exploring?
>
> 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:
>
>    1.
>
>    a)  If x < y, totalOrder(x, y) is true.
>    2.
>
>    b)  If x > y, totalOrder(x, y) is false.
>    3.
>
>    c)  Ifx=y:
>    1.
>
>       1)  totalOrder(−0, +0) is true.
>       2.
>
>       2)  totalOrder(+0, −0) is false.
>       3.
>
>       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.
>
>    1)  totalOrder(−NaN, y) is true where −NaN represents a NaN with
>    negative sign bit and y is a
>
>    floating-point number.
>    2.
>
>    2)  totalOrder(x, +NaN) is true where +NaN represents a NaN with
>    positive sign bit and x is a floating-point number.
>    3.
>
>    3)  If x and y are both NaNs, then totalOrder reflects a total
>    ordering based on:
>    1.
>
>       i)  negative sign orders below positive sign
>
> Oh god, I didn’t realize that NaN could be signed…
>
>
>    1.
>       1.
>       2.
>
>       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
>
>
> Cheers,
> Jaden Geller
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20170426/c8a2f60b/attachment.html>