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

[Matthew Johnson]

> On Jul 22, 2016, at 9:46 PM, Dave Abrahams <dabrahams at apple.com> wrote:
> 
> 
> on Fri Jul 22 2016, Xiaodi Wu <xiaodi.wu-AT-gmail.com> wrote:
> 
>> On Fri, Jul 22, 2016 at 9:23 PM, Matthew Johnson <matthew at anandabits.com>
>> wrote:
>> 
>>> 
>>> On Jul 22, 2016, at 9:17 PM, Xiaodi Wu <xiaodi.wu at gmail.com> wrote:
>>> 
>>> On Fri, Jul 22, 2016 at 9:15 PM, Matthew Johnson via swift-evolution <
>>> swift-evolution at swift.org> wrote:
>>> 
>>>> 
>>>> On Jul 22, 2016, at 9:04 PM, Dave Abrahams via swift-evolution <
>>>> swift-evolution at swift.org> wrote:
>>>> 
>>>> 
>>>> on Fri Jul 22 2016, Matthew Johnson <swift-evolution at swift.org> wrote:
>>>> 
>>>> On Jul 22, 2016, at 8:37 PM, Xiaodi Wu via swift-evolution
>>>> <swift-evolution at swift.org> wrote:
>>>> 
>>>> On Fri, Jul 22, 2016 at 8:20 PM, Dave Abrahams via swift-evolution
>>>> <swift-evolution at swift.org
>>>> 
>>>> 
>>>> <mailto:swift-evolution at swift.org <swift-evolution at swift.org>>>
>>>> wrote:
>>>> 
>>>> on Fri Jul 22 2016, Daniel Duan <daniel-AT-duan.org
>>>> <http://daniel-at-duan.org/>> wrote:
>>>> 
>>>> On Jul 22, 2016, at 3:00 PM, Dave Abrahams via swift-evolution
>>>> <swift-evolution at swift.org
>>>> <mailto:swift-evolution at swift.org <swift-evolution at swift.org>>>
>>>> wrote:
>>>> 
>>>> 
>>>> on Fri Jul 22 2016, Daniel Duan
>>>> <swift-evolution at swift.org
>>>> <mailto:swift-evolution at swift.org <swift-evolution at swift.org>>
>>>> <mailto:swift-evolution at swift.org <swift-evolution at swift.org>
>>>> <mailto:swift-evolution at swift.org <swift-evolution at swift.org>>>>
>>>> wrote:
>>>> 
>>>> 
>>>> On Jul 22, 2016, at 11:05 AM, Dave Abrahams via swift-evolution
>>>> <swift-evolution at swift.org
>>>> <mailto:swift-evolution at swift.org <swift-evolution at swift.org>>
>>>> <mailto:swift-evolution at swift.org <swift-evolution at swift.org>
>>>> <mailto:swift-evolution at swift.org <swift-evolution at swift.org>>>>
>>>> wrote:
>>>> 
>>>> 
>>>> on Thu Jul 21 2016, Duan
>>>> 
>>>> 
>>>> <swift-evolution at swift.org
>>>> <mailto:swift-evolution at swift.org <swift-evolution at swift.org>>
>>>> <mailto:swift-evolution at swift.org <swift-evolution at swift.org>
>>>> <mailto:swift-evolution at swift.org <swift-evolution at swift.org>>>
>>>> <mailto:swift-evolution at swift.org <swift-evolution at swift.org>
>>>> <mailto:swift-evolution at swift.org <swift-evolution at swift.org>>
>>>> <mailto:swift-evolution at swift.org <swift-evolution at swift.org>
>>>> <mailto:swift-evolution at swift.org <swift-evolution at swift.org>>>>>
>>>> wrote:
>>>> 
>>>> Great proposal. I want to second that areSame may mislead user to
>>>> think this is about identity.
>>>> 
>>>> I like areEquivalent() but there may be better names.
>>>> 
>>>> 
>>>> It really *is* about identity as I posted in a previous message.  But
>>>> that doesn't change the fact that areEquivalent might be a better name.
>>>> It's one of the things we considered; it just seemed long for no real
>>>> benefit.
>>>> 
>>>> 
>>>> If the addresses of the arguments aren’t being used, then we don’t
>>>> consider
>>>> them part of their *identity*. I can follow this logic. My fear is most
>>>> users
>>>> won’t make this leap on their own and get the same initial impression as
>>>> I did.
>>>> It's entirely possible this fear is unfounded. Some educated bikesheding
>>>> wouldn't hurt here IMO :)
>>>> 
>>>> 
>>>> Well, it's still a very real question whether we ought to have the
>>>> additional API surface implied by areSame, or wether we should collapse
>>>> it with ===.
>>>> 
>>>> 
>>>> To spell this out (because I had to think about it for a second): ===
>>>> will be derived from
>>>> <=>,
>>>> but also becomes default implementation for ==, which remains open for
>>>> customization.
>>>> 
>>>> 
>>>> I was imagining roughly this (untested):
>>>> 
>>>> /// Two references are identical if they refer to the same
>>>> /// instance.
>>>> ///
>>>> /// - Note: Classes with a more-refined notion of “identical”
>>>> ///   should conform to `Identifiable` and implement `===`.
>>>> func ===(lhs: AnyObject, rhs: AnyObject) -> Bool {
>>>>   ObjectIdentifier(lhs) == ObjectIdentifier(rhs)
>>>> }
>>>> 
>>>> /// Supports testing that two values of `Self` are identical
>>>> ///
>>>> /// If `a` and `b` are of type `Self`, `a === b` means that
>>>> /// `a` and `b` are interchangeable in most code.  A conforming
>>>> /// type can document that specific observable characteristics
>>>> /// (such as the `capacity` of an `Array`) are inessential and
>>>> /// thus not to be considered as part of the interchangeability
>>>> /// guarantee.
>>>> ///
>>>> /// - Requires: `===` induces an equivalence relation over
>>>> ///   instances.
>>>> /// - Note: conforming types will gain an `==` operator that
>>>> ///   forwards to `===`.
>>>> /// - Note: Types that require domain-specific `==`
>>>> ///   implementations with different semantics (e.g. floating
>>>> ///   point) should define a more-specific overload of `==`,
>>>> ///   which will be used in contexts where the static type is
>>>> ///   known to the compiler.
>>>> /// - Note: Generic code should usually use `==` to compare
>>>> ///   conforming instances; that will always dispatch to `===`
>>>> ///   and will be unaffected by more specific overloads of
>>>> ///   `==`.
>>>> protocol Identifiable { // née Equatable name is negotiable
>>>>   func ===(_: Self, _: aSelf) -> Bool
>>>> }
>>>> 
>>>> /// Default definition of `==` for Identifiable types.
>>>> func ==<T: Identifiable>(lhs: T, rhs: T) -> Bool {
>>>>   return lhs === rhs
>>>> }
>>>> 
>>>> /// Conforming types have a default total ordering.
>>>> ///
>>>> /// If `a` and `b` are of type `Self`, `a <=> b` means that
>>>> /// `a` and `b` are interchangeable in most code.  A conforming
>>>> /// type can document that specific observable characteristics
>>>> /// (such as the `capacity` of an `Array`) are inessential and
>>>> /// thus not to be considered as part of the interchangeability
>>>> /// guarantee.
>>>> ///
>>>> /// - Requires: `<=>` induces a total ordering over
>>>> ///   instances.
>>>> /// - Requires: the semantics of `<=>` are  consistent with
>>>> ///   those of `===`.  That is, `(a <=> b) == .equivalent`
>>>> ///   iff `a === b`.
>>>> 
>>>> For floating point, I'd hope that `a === b` if `(a <=> b) == .same` *but
>>>> not iff*. This is to satisfy IEEE 754: "Comparisons shall ignore the sign
>>>> of zero (so +0 = −0)”.
>>>> 
>>>> 
>>>> 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.
>>>> 
>>>> 
>>>> It's settled law
>>>> https://en.wikipedia.org/wiki/IEEE_floating_point#Total-ordering_predicate
>>>> :-)
>>>> 
>>>> 
>>>> Yes, assuming we want to define identity in terms of the IEEE definition
>>>> of total ordering.
>>>> 
>>> 
>>> I see what you're saying here. That could work. Comparable `===` and
>>> Equatable `<=>` could do its own thing, and FloatingPoint
>>> `isTotallyOrdered(below:)` can preserve the IEEE definition of total
>>> ordering
>>> 
>>> 
>>> Actually, I was hinting at your argument that `===` true iff `<=>` same
>>> shouldn’t be a semantic requirement of the protocols.
>>> 
>>> This is another option, but I don’t think it’s going to fly.  It seems
>>> reasonable to assume that `<=>` will have IEEE semantics.  We will trip a
>>> lot of people up if it doesn’t.  That’s a big reason we can’t consider
>>> changing floating point `==` to define an equivalence relation.
>>> 
>> 
>> Actually, here I doubt it. The total ordering isn't exposed as part of any
>> comparison operator defined in the IEEE spec. In fact, the total ordering
>> wasn't introduced until a (fairly) recent IEEE revision, IIUC. Breaking
>> `==` would definitely cause people to jump, but `<=>` needn't be the IEEE
>> totalOrder predicate IMO.
> 
> Wait, I thought we were saying that `<=>` could be IEEE totalOrder, and
> `===` could be like `==` but with well-behaved NaNs, so it's still an
> equivalence relation, thus declaring the signedness of 0 to be
> inessential.

He’s considering two or three different approaches.  That’s one of them and abandoning IEEE total order for `<=>` is another.

> 
> -- 
> Dave