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

Fri Jul 22 17:41:03 CDT 2016

On Fri, Jul 22, 2016 at 5:34 PM, Matthew Johnson <matthew at anandabits.com>
wrote:

>
> On Jul 22, 2016, at 5:29 PM, Xiaodi Wu <xiaodi.wu at gmail.com> wrote:
>
> On Fri, Jul 22, 2016 at 5:17 PM, Matthew Johnson via swift-evolution <
> swift-evolution at swift.org> wrote:
>
>>
>> On Jul 22, 2016, at 4:47 PM, Dave Abrahams via swift-evolution <
>> swift-evolution at swift.org> wrote:
>>
>>
>> on Fri Jul 22 2016, Tony Allevato <swift-evolution at swift.org> wrote:
>>
>> I like a lot of this, but the changes to Equatable are where I get stuck.
>> What are the scenarios where areSame is useful *outside* the context of
>> the
>> proposed new Comparable interface?
>>
>> I ask because changing the requirement for Equatable to areSame instead of
>> == seems like a backwards change to me. There are plenty of unorderable
>> types where == is the obvious thing you want to implement, and this makes
>> it less obvious. It also adds a named method to a protocol to serve the
>> purpose of an operator, which I've been fighting hard against in SE-0091
>> (even though you keep the global one and delegate to it).
>>
>> There are two concepts at play here: comparability and orderability.
>> 99.99%
>> of the time, they are identical.
>>
>>
>> The concepts are “domain-specific semantics” vs “semantics that is
>> useful in generic contexts.”  Yes, they are usually identical.
>>
>> Your proposal mentions one place where they're not: IEEE floating
>> point numbers, because there exists an element in that space, NaN,
>> that doesn't satisfy an equivalence relation at all.
>>
>>
>> It's not limited to NaN.  The +0/-0 distinction can be tricky as well.
>>
>> But it's still reasonable to want a stable ordering with those
>> included.
>>
>>
>> It's also reasonable to want to search for those in a collection or use
>> them as hash keys.  I'm pointing this out because it goes to the
>> definition of equality, which sorting in general does not.
>>
>> In the proposal as it's written right now, the individual inequality
>> operators are implemented in terms of <=>. That won't work for
>> FloatingPoint, because (NaN < x) and (NaN >= x) should both be false but
>> the default implementations provided would make the latter true. So
>> FloatingPoint would still have to provide its own implementations of *all
>> of the (in)equality operators*, not just ==, in order to have the correct
>> definition w.r.t. to IEEE 754. I didn't see that called out anywhere in
>> the
>> write-up.
>>
>>
>> That's my error, actually. I wasn't thinking straight when I proposed a
>> change to the proposal that I claimed dropped the need for the other
>> operators.
>>
>> That being said, don't get me wrong—there's still a lot about this
>> proposal
>> that I like :)  Here's what I'm thinking (which is mostly what you have
>> written, with some tweaks):
>>
>> 1) Don't change Equatable. I don't see a need to distinguish between
>> equivalence and equality on its own (if there is one, please let me
>> know!).
>>
>>
>> There is, because for algorithms that require Equatable to have any kind
>> of meaningful semantics the equivalence relation requirement must be
>> fulfilled, and prominent types exist whose `==` operator is not an
>> equivalence relation.
>>
>>
>> Have you considered moving away from `==` for these domain specific
>> operations?  Does the IEEE standard specify the exact syntax of `==` or is
>> that just a convention?
>>
>> It feels really strange to me to have an `==` operation that is not an
>> equivalence relation (even if it is common and is the usual way to compare
>> floating point).  Despite common practice I think it lends itself to an
>> intuition of equivalence.
>>
>
> I think that would just be too disruptive. I expect to be able to compare
> any numeric type to the integer literal 0 using `==`.
>
>
> Sorry if it wasn’t clear.  I’m not suggesting taking that away.  I’m
> asking whether we have considered defining `==` on floating point types to
> be the equivalence relation that is proposed for `areSame` and giving the
> domain specific operation a different name.
>

Sorry, bad example. Doing so would take away NaN != NaN. I think many
users, not considering implementation of their own type, would be sorely
confused why this already difficult concept about floating point types
which they've just wrapped their heads around stops working yet again.

> Maybe this would break with convention too much, but it would feel much
> more intuitive (to me at least - although I am admittedly not a numerics
> expert).
>

IEEE does indeed suggest what standard comparison operators should do, if I
recall correctly.

> As it stands today, I think the proposal "leaks" ordering concepts into
>> Equatable when it shouldn't.
>>
>>
>> I don't see any evidence for that, and I don't even believe you've said
>> anything here to support that point of view.
>>
>> 2) Comparable defines <=>, as proposed, but *also* defines <, >, <=, >=. A
>> protocol extension provides defaults for <, >, <=, >=, ==, and !=
>> implemented in terms of <=>. This lets most implementors of Comparable
>> implement <=> and get everything else for free, but it also lets types
>> replace individual operators with customized implementations (see #4
>> below)
>> easily *within* the type (SE-0091).
>>
>>
>> Check
>>
>> 3) Comparable should be documented to imply that the default behavior is
>> to
>> link the behavior of <=> to the individual comparisons, but that it can be
>> changed, meaning that only <=> must define a total ordering and the
>> individual comparison operators need not.
>>
>>
>> Yes, the doc comments are missing from the proposal.
>>
>> 4) The very few types, like FloatingPoint, that need to provide
>> domain-specific behavior to do the obvious/intended thing for users can
>> and
>> should override <, >, <=, >=, ==, and !=. This should be called out
>> explicitly, and it would *not* affect ordering.
>>
>>
>> Depends what you mean by “affect ordering.”  Clearly if you sort Floats
>> using < explicitly, it will have an effect.
>>
>> I think it's entirely reasonable to have (NaN == NaN) return false and
>> (NaN != NaN) return true but (NaN <=> NaN) return .same without
>> introducing another areSame concept, because the former is demanded by
>> IEEE 754.  5) Algorithms that rely on a total order, like sorts, must
>> be implemented in terms of <=>, not in terms of the individual
>> operators, because of the possibility that the definitions can be
>> severed above.
>>
>>
>> But you're forgetting algorithms that require an equivalence relation,
>> which is basically everything that's constrained to Equatable.
>>
>> As mentioned below, the one thing that a three-way comparison loses is the
>> easy ability to pass > instead of < to reverse the ordering, but it's
>> trivial to write a function that does this and I think it should be
>> included as part of the proposal. Something like this (may be typos, I'm
>> writing it in Gmail):
>>
>> public func reverse<C: Comparable>(ordering: (C, C) -> Ordering) -> (C, C)
>> -> Ordering {
>>  return { lhs, rhs in
>>    switch ordering(lhs, rhs) {
>>    case .ascending: return .descending
>>    case .descending: return .ascending
>>    case .same: return .same
>>  }
>> }
>>
>> (Comedy alternative: Add a second operator, >=<. But that might be pushing
>> it.)
>>
>>
>> Agreed, we should do something about this use case.
>>
>> --
>> 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/20160722/e14053ea/attachment.html>