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

[Dave Abrahams]

on Sat Jul 23 2016, 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:

This effectively makes it a precondition violation to default-sort
a sequence of floats that contains a NaN or even to ask whether
someSequence.contains(.nan).  IMO that's not really acceptable.

> 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, 

I agree that our default ordering and equivalence tests should not
consider these differences to be essential/salient.

> 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