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

[Xiaodi Wu]

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/56cc1dee/attachment.html>