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

Dave Abrahams dave at boostpro.com
Sun Jul 24 12:20:07 CDT 2016 

on Sat Jul 23 2016, Xiaodi Wu <xiaodi.wu-AT-gmail.com> wrote:

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

Yes, and specifically division by zero, which *seriously doesn't concern
me*.  I view the reason for floating point's (1/0 == Inf) to be very
similar to its reason for having NaN, which I understand to be this:
practitioners want to do very large multivariate calculations where if
*some* of the results can't be computed, it doesn't scuttle all of them.
They also want to preserve as much information as possible about the
likely nature of results when precision limits come into play

When I read what mathematicians say about division by zero (e.g.
https://www.quora.com/Is-1-0-infinity/answer/Dan-Piponi and
https://www.quora.com/Is-1-0-infinity/answer/Michael-Lamar), it seems to
me that there is no well-defined answer, and we could view +Inf and -Inf
as the way floating point responds to a precondition violation.

I would *much* rather do a little handwaving in the area of division by
zero than in the areas of equivalence and ordering.

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

More information about the swift-evolution mailing list