[swift-evolution] [Draft][Proposal] Formalized Ordering

Xiaodi Wu xiaodi.wu at gmail.com
Sat Jul 23 16:24:53 CDT 2016 

IMO what's causing the headaches now isn't NaN; it's actually +0 and -0.


On Sat, Jul 23, 2016 at 4:19 PM, Nevin Brackett-Rozinsky <
nevin.brackettrozinsky at gmail.com> wrote:

> Another option would be to leave the IEEE 754 NaN hijinks in Float and
> Double (as numerics people expect), and create a new type (with a nice
> approachable name) that “acts like” Double but does not model NaN. Then any
> operation which would ordinarily produce a NaN, instead traps for the new
> type. That way its comparison operators only have to worry about non-NaN
> values, which makes everything much cleaner.
>
> Sorting Doubles would retain its present functionality, warts and all,
> which numerics people should be expected to handle. Whereas the new type
> (“Number” sounds good, especially if we can make it subsume NSNumber) would
> never have a NaN in the first place.
>
> Nevin
>
>
>
> On Sat, Jul 23, 2016 at 4:57 PM, Xiaodi Wu via swift-evolution <
> swift-evolution at swift.org> wrote:
>
>> Sorry to overwhelm with more emails. I'd like to show some work and
>> further analysis for your consideration that refines the sketch I just
>> wrote:
>>
>> Two FP values a and b can be, with respect to each other:
>>
>> * ordered or unordered (per IEEE, NaN compares unordered to everything,
>> including itself)
>> * identical or not identical (for these purposes, we adopt Steve's
>> proposed test for identity: substitutable for all operations; thus +0 is
>> not identical to -0, but different binary representations of the same value
>> are identical)
>> * equal or not equal (i.e. the behavior of the == operator today)
>>
>> So, if a and b are, with respect to each other:
>>
>> * ordered, identical, equal -- this is what happens ordinarily with two
>> equal, non-NaN values
>> * ordered, identical, not equal -- this can never happen
>> * ordered, not identical, equal -- only +0 and -0
>> * ordered, not identical, not equal -- this is what happens ordinarily
>> with two unequal, non-NaN values
>>
>> * unordered, identical, equal -- this can never happen, but if NaNs are
>> to be well-behaved (for a true equivalence relation), then we will need an
>> equivalence relation in which NaN == NaN
>> * unordered, identical, not equal -- this is what always happens, but if
>> NaNs are to be well-behaved, then such behavior will need to change
>> * unordered, not identical, equal -- this can never happen
>> * unordered, not identical, not equal -- this is what ordinarily happens
>> with one NaN and one non-NaN value
>>
>> Equatable can have === and my proposed ==? as part of its protocol; a
>> generic ==, as originally proposed, would be defined outside the protocol.
>> A default implementation of ==? will forward to ===, and the generic ==
>> will be defined as `{ return (lhs ==? rhs) ?? (lhs === rhs) }`.
>> For floating point, ==? will be specialized and cease to forward to ===
>> so that +0 and -0 compare true and NaN and anything compare nil, and
>> floating point == will be defined notionally as `{ return (lhs ==? rhs) ??
>> false }`.
>>
>>
>> On Sat, Jul 23, 2016 at 3:09 PM, Xiaodi Wu <xiaodi.wu at gmail.com> wrote:
>>
>>> Throwing out some more radical ideas here. Suppose we had instead
>>> (taking inspiration from IEEE notation):
>>>
>>> [Pardon any errors; I'm writing freehand in Gmail]
>>>
>>> infix operator ==? { /* figure out precedence later */ }
>>>
>>> protocol Equatable {
>>>   static func ==? (lhs: Self, rhs: Self) -> Bool?
>>>   /* semantics:
>>>      this function returns nil if lhs and rhs are unordered with respect
>>> to each other
>>>      otherwise, evaluate by means of a legal equivalence relation */
>>> }
>>>
>>> func == <T: Equatable>(lhs: T, rhs: T) -> Bool {
>>>   return (lhs ==? rhs) ?? false
>>> }
>>>
>>> protocol Comparable : Equatable {
>>>   static func <=> (lhs: Self, rhs: Self) -> Ordering
>>>   /* semantics:
>>>      this is a total ordering; thus:
>>>      if `(a ==? b) == true`, then `(a <=> b) == .same`
>>>      if `(a ==? b) == false`, then `(a <=> b) != .same`
>>>      but, if `(a ==? b) == nil`, then `a <=> b` may yield any result
>>>   */
>>> }
>>>
>>>
>>> On Sat, Jul 23, 2016 at 2:35 PM, Pyry Jahkola <pyry.jahkola at iki.fi>
>>> wrote:
>>>
>>>> Given all this, I propose a simpler model that makes `a <=> b` follow
>>>> the expected behaviour of < and ==, with the tradeoff that `a <=> .nan` and
>>>> `.nan <=> b` will abort with a precondition failure:
>>>>
>>>> 1) We keep the current Interface of Equatable  unchanged, with !=
>>>> defined in terms of ==.
>>>>
>>>> 2) Comparable would still refine Equatable, and include all the
>>>> comparison operators, adding the new <=>:
>>>>
>>>>     protocol Comparable : Equatable {
>>>>       static func <=>(lhs: Self, rhs: Self) -> Ordering
>>>>       static func <(lhs: Self, rhs: Self) -> Bool
>>>>       static func >(lhs: Self, rhs: Self) -> Bool
>>>>       static func <=(lhs: Self, rhs: Self) -> Bool
>>>>       static func >=(lhs: Self, rhs: Self) -> Bool
>>>>     }
>>>>
>>>> The comparison operators are kept in the interface so that partially
>>>> ordered types such as Double can be supported in generic code. However, the
>>>> documentation should recommend against defining `<` manually.
>>>>
>>>> 3) Default implementations for <Self : Comparable> are provided for the
>>>> following operators: ==, <, >, <=, and >=.
>>>>
>>>> 4) User-defined types will need to define just <=> to conform to
>>>> Comparable. (Even == can be omitted!)
>>>>
>>>> 5) FloatingPoint types implement custom versions of ==, <, >, <=, and
>>>> >= using the standard IEEE 754 definition (i.e. comparisons involving NaN
>>>> return false). Zero is zero; `0.0 == -0.0 && !(-0.0 < 0.0)` holds.
>>>>
>>>> 6) FloatingPoint types implement <=> as:
>>>>
>>>>     func <=> <T : FloatingPoint>(lhs: T, rhs: T) -> Ordering {
>>>>       if lhs < rhs { return .ascending }
>>>>       if rhs < lhs { return .descending }
>>>>       precondition(lhs == rhs)
>>>>       return .same
>>>>     }
>>>>
>>>> 7) Algorithms using <=> directly should mention so in their
>>>> documentation as a precondition that they require total order between
>>>> elements. Many generic algorithms can be defined in terms of == or <, and
>>>> should.
>>>>
>>>> If we took the oroginally planned route that distinguished between
>>>> identities such as -0.0 vs. +0.0, or between the 2⁴⁹ - 2 ≈ 5.6 × 10¹⁴
>>>> possible NaN values that Double has, we'd also need to consider other
>>>> oddballs like the difference and ordering between the Strings "ä" and
>>>> "a\u{308}", which are considered equal but produce a different Unicode
>>>> representation. I think it's best to hide those identities behind another
>>>> interface than Equatable and Comparable, and let the protocols serve more
>>>> mundane application logic.
>>>>
>>>> — Pyry
>>>>
>>>> > Dave Abrahams wrote:
>>>> >
>>>> >
>>>> >> on Sat Jul 23 2016, Xiaodi Wu <xiaodi.wu-AT-gmail.com> wrote:
>>>> >>
>>>> >> On Fri, Jul 22, 2016 at 11:34 PM, Stephen Canon <scanon at apple.com>
>>>> wrote:
>>>> >>
>>>> >>>> The point of this design is that `===` means identity and that
>>>> `.same `
>>>> >>>> also means identity.
>>>> >>>>
>>>> >>>> Since this is new territory I suppose we get to decide what
>>>> identity
>>>> >>>> means for floating point.  Should +0 and -0 have the same identity
>>>> or
>>>> >>>> not?  I’ll leave the answer to folks more knowledgable about
>>>> numerics
>>>> >>>> than I.
>>>> >>>
>>>> >>> Boy, I take my wife out for a movie and come back to 50 new
>>>> messages on SE.
>>>> >>>
>>>> >>> I need to read the entire thread more carefully, but off the top of
>>>> my
>>>> >>> head, I think that `-0 === +0` is False.  If we’re going to have an
>>>> >>> `isSame` / `isIdentical` / whatever it's called, I would expect it
>>>> to imply
>>>> >>> substitutability.  Although -0 == +0, they are not equivalent when
>>>> >>> substituted:
>>>> >>>
>>>> >>> - 1/(-0) != 1/0
>>>> >>> - Float(-0).sign != Float(+0).sign
>>>> >>> - etc
>>>> >>>
>>>> >>> This probably then implies that `<=>` is not `.same` either.  I’ll
>>>> read
>>>> >>> the rest of this and respond more completely tomorrow.
>>>> >>
>>>> >> Eagerly await your evaluation of the discussion. In the meantime:
>>>> >>
>>>> >> I think Dave's view that `===` defines identity in terms of
>>>> "essential"
>>>> >> qualities implies that two identical values can be
>>>> >> different/non-substitutable in "inessential" qualities. For generic
>>>> >> purposes, the sign of zero could be one such inessential quality.
>>>> >
>>>> > Yes, and I think our view of how people work with numbers in swift
>>>> (and
>>>> > their protocol conformances) reflect this approach.
>>>> >
>>>> > http://article.gmane.org/gmane.comp.lang.swift.evolution/16321
>>>> >
>>>> > My sense is that we want to choose the default notions of identity and
>>>> > ordering so as to support the way people think about these numeric
>>>> > types, inexact though it may be.  Therefore, finding 0.0 in a sequence
>>>> > of floats should succeed when the sequence contains -0.0, and a stable
>>>> > sort on floating point keys should preserve the relative order of all
>>>> > elements having +0.0 and -0.0 keys.
>>>> >
>>>> > People that want to work with inessential qualities such as the sign
>>>> of
>>>> > zero can always pass Float.totalOrdering (or whatever) to their
>>>> > closure-accepting algorithms.
>>>> >
>>>> > [In order to support the user model, we still need to fix the
>>>> semantics
>>>> > of the default identity and ordering operations so that things like
>>>> > sorting and searching work, which is why == and < won't cut it for
>>>> these
>>>> > purposes]
>>>> >
>>>> >> On the other hand, the stdlib stride algorithm is going to be borked
>>>> if -0
>>>> >> < +0. Of course, as we already started to do there, we could
>>>> specialize for
>>>> >> floating point and then adjust accordingly. However, it seems to me
>>>> that
>>>> >> every generic algorithm that performs comparisons and can take
>>>> floating
>>>> >> point arguments would have to be specialized to account for floating
>>>> point
>>>> >> -0 != +0 (`index(of:)` being the previous example). This appears to
>>>> defeat
>>>> >> the aim of trying to accommodate FP at all in this revised design for
>>>> >> Comparables.
>>>> >
>>>> > Yes, that would be a disaster, generically speaking.
>>>> >
>>>> >> The argument for `-0 === +0` is that -0 and +0 should be equivalent
>>>> when
>>>> >> substituted for every comparison operation. For FP operations, you'd
>>>> >> continue to test (as you have to test now) `a == b && a.sign ==
>>>> b.sign` if
>>>> >> you cared about the sign of zero. For non-FP arithmetic operations,
>>>> hmm,
>>>> >> not sure how to square that circle.
>>>> >
>>>> > I followed all of this... except, what are you getting at with that
>>>> last
>>>> > sentence?
>>>> >
>>>> > --
>>>> > Dave
>>>> > _______________________________________________
>>>> > swift-evolution mailing list
>>>> > swift-evolution at swift.org
>>>> > https://lists.swift.org/mailman/listinfo/swift-evolution
>>>>
>>>
>>>
>>
>> _______________________________________________
>> swift-evolution mailing list
>> swift-evolution at swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160723/3940fb42/attachment.html>

More information about the swift-evolution mailing list