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

Nevin Brackett-Rozinsky nevin.brackettrozinsky at gmail.com
Sat Jul 23 16:19:58 CDT 2016 

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/913da8dd/attachment.html>

More information about the swift-evolution mailing list