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

Matthew Johnson matthew at anandabits.com
Fri Jul 22 22:04:42 CDT 2016 

> On Jul 22, 2016, at 9:57 PM, Dave Abrahams <dabrahams at apple.com> wrote:
> 
> 
> on Fri Jul 22 2016, Xiaodi Wu <xiaodi.wu-AT-gmail.com <http://xiaodi.wu-at-gmail.com/>> wrote:
> 
>> On Fri, 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.
>>> 
>> 
>> I was (that was the "=== if but not iff <=>" business above), then I
>> thought Matthew was saying something different and agreed with him.
>> 
>> What I thought that Matthew thought was actually very insightful. He didn't
>> actually think this, apparently, but: IEEE totalOrder does exactly what it
>> says on the tin. But, it is not useful for any generic comparisons or (as
>> far as I'm aware) any generic sorting algorithms. I cannot conceive of a
>> numeric algorithm or a generic algorithm that relies on two equal floating
>> point values being ordered based on their binary representation. We should
>> have some way of exposing totalOrder to a user of a BinaryFloatingPoint
>> type, but I don't know that it should be the basis for floating point
>> *identity* with respect to protocol conformance. It's explicitly *not* what
>> IEEE recommends for comparison anyway.
> 
> That makes sense.  Perhaps IEEE hasn't actually made a principled
> decision about which aspects of floating point numbers are essential,
> and we have to do it for them.

Xiaodi is swaying me on this point as well.  I am no numerics expert so I don’t know of cases where the difference between -0 and +0 matter and whether the reasons they matter in these cases are applicable to generic code or not. But maybe it is the case that they actually don’t.  (Or maybe they are just an artifact of the implementation in which case the difference really shouldn’t matter at all)

> 
> -- 
> Dave

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160722/ff81f14b/attachment.html>

More information about the swift-evolution mailing list