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

Xiaodi Wu xiaodi.wu at gmail.com
Sat Jul 23 15:57:46 CDT 2016 

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
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160723/a17b1790/attachment.html>

More information about the swift-evolution mailing list