[Draft][Proposal] Formalized Ordering


(Beta) #1

Hello Swift Community,

Harlan Haskins, Jaden Geller, and I have been working on a proposal to clean up the semantics of ordering relations in the standard library. We have a draft that you can get as a gist. <https://gist.github.com/CodaFi/f0347bd37f1c407bf7ea0c429ead380e> Any feedback you might have about this proposal helps - though please keeps your comments on Swift-Evolution and not on the gist.

Cheers,

~Robert Widmann


(Xiaodi Wu) #2

This is nice. Is `areSame()` being proposed because static `==` is the
status quo and you're trying to make the point that `==` in the future need
not guarantee the same semantics?

Nit: I think the more common term in stdlib would be `areEquivalent()`. Do
you think `same` in that context (independent of the word "ordering") might
erroneously suggest identity?

···

On Thu, Jul 21, 2016 at 8:11 PM, Robert Widmann via swift-evolution < swift-evolution@swift.org> wrote:

Hello Swift Community,

Harlan Haskins, Jaden Geller, and I have been working on a proposal to
clean up the semantics of ordering relations in the standard library. We
have a draft that you can get as a gist.
<https://gist.github.com/CodaFi/f0347bd37f1c407bf7ea0c429ead380e> Any
feedback you might have about this proposal helps - though please keeps
your comments on Swift-Evolution and not on the gist.

Cheers,

~Robert Widmann

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Dmitri Gribenko) #3

Hi,

···

On Thu, Jul 21, 2016 at 6:11 PM, Robert Widmann via swift-evolution <swift-evolution@swift.org> wrote:

Hello Swift Community,

Harlan Haskins, Jaden Geller, and I have been working on a proposal to clean
up the semantics of ordering relations in the standard library.

Great work!

As a part of your implementation, are you planning to add <=>
overloads for tuples, like we do now for comparison operators? (See
stdlib/public/core/Tuple.swift.gyb.)

Dmitri

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/


(Brent Royal-Gordon) #4

My thoughts on this are not yet fully formed, but I have a couple questions concerning `isSame(_:_:)` and `==`:

* Should calls like `index(of:)` and `split(separator:)` use `==` or `isSame(_:_:)`?

* Should `Hashable` use `==` or `isSame(_:_:)`?

* Do we know of any use cases where a type conforms to `Equatable` but not `Comparable` and needs separate `isSame(_:_:)` and `==` operators?

Essentially, I'm wondering if we can leave `Equatable`'s definition alone and only change `Comparable` to require `<=>`, with a generic operator to provide a default `==` which uses `<=>`.

···

On Jul 21, 2016, at 6:11 PM, Robert Widmann via swift-evolution <swift-evolution@swift.org> wrote:

Hello Swift Community,

Harlan Haskins, Jaden Geller, and I have been working on a proposal to clean up the semantics of ordering relations in the standard library. We have a draft that you can get as a gist. Any feedback you might have about this proposal helps - though please keeps your comments on Swift-Evolution and not on the gist.

--
Brent Royal-Gordon
Architechies


(Pyry Jahkola) #5

Bravo! It would be great to have Comparable defined in terms of a full comparison. I'd specifically call out String as a concrete example in the Motivation section, as this proposal is likely to give a performance boost on sorting String arrays, which is a pretty common thing to do.

···

On 22 Jul 2016, at 04:11, Robert Widmann via swift-evolution <swift-evolution@swift.org> wrote:

Harlan Haskins, Jaden Geller, and I have been working on a proposal to clean up the semantics of ordering relations in the standard library. We have a draft that you can get as a gist. Any feedback you might have about this proposal helps - though please keeps your comments on Swift-Evolution and not on the gist.

----

I think the Detailed design section should explicitly show as source code:

1. What is the updated Equatable protocol?

2. What are all the updated operators? (I.e. show the new default implementations of `==` and `!=` too.)

3. In code comments, what are the updated rules or laws that should hold for Equatable and Comparable (and FloatingPoint, if any)?

4. What are the new "by: (Self, Self) -> Ordering" functions that the proposal is about to introduce to the stdlib?

----

On the topic of partial orderings (e.g. floating-point types), starting with the more important questions first:

5. Will it be considered "ok" to define a type for which `T.areSame(a, b) == true` but `a != b`? An obvious example would be Double.nan, so I assume the answer is a resounding yes.

6. Similarly, will it be "ok" to define a type for which `T.areSame(a, b) == false` but `a == b`? One possible example could be the comparison of `-0.0 <=> +0.0`. Should those be `.same` or not?

7. What, in fact, is the proposed total order for the stdlib's floating-point types?

(For an example, here is one possible way of defining `<=>` for Double, using `Double.bitPattern`. It distinguishes between +0.0 and -0.0, and even the various patterns of NaN! But do we want this for our `<=>` or something else?

    func <=> (lhs: Double, rhs: Double) -> Ordering {
      func f(_ x: UInt64) -> UInt64 {
        return x < 0x80000000_00000000 ? x + 0x80000000_00000000 : ~x
      }
      return f(lhs.bitPattern) <=> f(rhs.bitPattern)
    }
    print( -0.0 <=> 0.0) // ascending
    print( 1.0 <=> 0.0) // descending
    print( Double.infinity <=> Double.nan) // ascending
    print(-Double.infinity <=> -Double.nan) // descending
    print( Double.nan <=> Double.nan) // same

See http://swiftlang.ng.bluemix.net/#/repl/5791db33719d5d045b4d430c for a running example.)

----

A general idea:

8. I wouldn't mind if the proposal also covered including generated definitions for `tuple1 <=> tuple2` of tuples from zero arity through to 6 or whatever the gyb's upper limit may be.

That would simplify the example implementation of Date down to:

    func <=> (lhs: Date, rhs: Date) -> Ordering {
      return (lhs.year, lhs.month, lhs.day)
         <=> (rhs.year, rhs.month, rhs.day)
    }

9. Some of us were not satisfied with the name of `.areSame(_:_:)`. Let me just point out that it would be nice if the name aligned with whatever `Ordering.same` will be called.

-- Pyry


(Haravikk) #6

Definitely a +1 from me, in fact I've implemented essentially this as an extension for my own convenience, but would definitely prefer it to be a proper component of the stdlib.

I have some queries to raise:

First is the naming, to me Ordering implies the enum itself is used for ordering collections but that's not really the case. In my own hacked implementation I'm using Order.before, Order.same, and Order.after. It's not much of a change, but it seems to clarify what the enum is, at least in my opinion.
One thing I was considering, but didn't do since my extension is just a bolt-on for convenience, is whether the before/ascending and after/descending cases should contain a value, allowing implementations to provide a hint of how far back/forward an element should be. This is a hint only of course, but could be useful; for example, when implementing a binary search you could instead use the hint value to provide a (hopefully) better guess at where to jump to next, for example if the value is very high you might jump to a position forward backward/forward rather than always selecting the middle every time. This is what Java's Comparable type does, since it uses a number where negative is before, 0 is same and positive is after.
Why is Equatable in this case implemented with a static .areSame() method, but Comparable isn't implemented by a static .compare() method? Seems like they should both be the same personally.
There should be a way to "flip" the operator. One thing that's great about the current sorting method is the ability to pass the < or > operators for ascending/descending respectively, we can do the first one by passing the <=> operator, but a flip function or something would be nice to, well, flip it (swap the ascending and descending cases before returning).

Just some thoughts, but I definitely want this.

···

On 22 Jul 2016, at 02:11, Robert Widmann via swift-evolution <swift-evolution@swift.org> wrote:

Hello Swift Community,

Harlan Haskins, Jaden Geller, and I have been working on a proposal to clean up the semantics of ordering relations in the standard library. We have a draft that you can get as a gist. <https://gist.github.com/CodaFi/f0347bd37f1c407bf7ea0c429ead380e> Any feedback you might have about this proposal helps - though please keeps your comments on Swift-Evolution and not on the gist.

Cheers,

~Robert Widmann

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Karl) #7

I fear that this will become confusing (especially since Equatable may now be implemented as a static function, too). We will have 3 different “equality” comparisons in Swift:

=== for reference-types
== for all types
areSame() which may be subtly different to ==

In order to have an opinion on whether or not this is justified, I need to know more about how areSame() may differ from == and how this will affect generic code. What is required that could not fit inside an override of Equatable? If this only applies to a few types, will it be its own protocol (e.g. EquivalenceCheckable)?

Karl

···

On 22 Jul 2016, at 03:11, Robert Widmann via swift-evolution <swift-evolution@swift.org> wrote:

Hello Swift Community,

Harlan Haskins, Jaden Geller, and I have been working on a proposal to clean up the semantics of ordering relations in the standard library. We have a draft that you can get as a gist. <https://gist.github.com/CodaFi/f0347bd37f1c407bf7ea0c429ead380e> Any feedback you might have about this proposal helps - though please keeps your comments on Swift-Evolution and not on the gist.

Cheers,

~Robert Widmann

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Tony Allevato) #8

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. 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.
But it's still reasonable to want a stable ordering with those included.

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 being said, don't get me wrong—there's still a lot about this proposal
that I like :slight_smile: 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!).
As it stands today, I think the proposal "leaks" ordering concepts into
Equatable when it shouldn't.
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).
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.
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. 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.

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

···

On Thu, Jul 21, 2016 at 6:11 PM Robert Widmann via swift-evolution < swift-evolution@swift.org> wrote:

Hello Swift Community,

Harlan Haskins, Jaden Geller, and I have been working on a proposal to
clean up the semantics of ordering relations in the standard library. We
have a draft that you can get as a gist.
<https://gist.github.com/CodaFi/f0347bd37f1c407bf7ea0c429ead380e> Any
feedback you might have about this proposal helps - though please keeps
your comments on Swift-Evolution and not on the gist.

Cheers,

~Robert Widmann

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Beta) #9

This is nice. Is `areSame()` being proposed because static `==` is the status quo and you're trying to make the point that `==` in the future need not guarantee the same semantics?

Yep! Equivalence and equality are strictly very different things.

Nit: I think the more common term in stdlib would be `areEquivalent()`. Do you think `same` in that context (independent of the word "ordering") might erroneously suggest identity?

There is room for improvement here. Keep ‘em coming.

···

On Jul 21, 2016, at 6:19 PM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

On Thu, Jul 21, 2016 at 8:11 PM, Robert Widmann via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
Hello Swift Community,

Harlan Haskins, Jaden Geller, and I have been working on a proposal to clean up the semantics of ordering relations in the standard library. We have a draft that you can get as a gist. <https://gist.github.com/CodaFi/f0347bd37f1c407bf7ea0c429ead380e> Any feedback you might have about this proposal helps - though please keeps your comments on Swift-Evolution and not on the gist.

Cheers,

~Robert Widmann

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution


(Daniel Duan) #10

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.

Daniel Duan

···

Sent from my iPhone

On Jul 21, 2016, at 6:32 PM, Robert Widmann via swift-evolution <swift-evolution@swift.org> wrote:

On Jul 21, 2016, at 6:19 PM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

This is nice. Is `areSame()` being proposed because static `==` is the status quo and you're trying to make the point that `==` in the future need not guarantee the same semantics?

Yep! Equivalence and equality are strictly very different things.

Nit: I think the more common term in stdlib would be `areEquivalent()`. Do you think `same` in that context (independent of the word "ordering") might erroneously suggest identity?

There is room for improvement here. Keep ‘em coming.

On Thu, Jul 21, 2016 at 8:11 PM, Robert Widmann via swift-evolution <swift-evolution@swift.org> wrote:
Hello Swift Community,

Harlan Haskins, Jaden Geller, and I have been working on a proposal to clean up the semantics of ordering relations in the standard library. We have a draft that you can get as a gist. Any feedback you might have about this proposal helps - though please keeps your comments on Swift-Evolution and not on the gist.

Cheers,

~Robert Widmann

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Chéyo Jiménez) #11

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.

what about areEqual() ?

···

On Jul 21, 2016, at 7:15 PM, Duan via swift-evolution <swift-evolution@swift.org> wrote:

Daniel Duan
Sent from my iPhone

On Jul 21, 2016, at 6:32 PM, Robert Widmann via swift-evolution <swift-evolution@swift.org> wrote:

On Jul 21, 2016, at 6:19 PM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

This is nice. Is `areSame()` being proposed because static `==` is the status quo and you're trying to make the point that `==` in the future need not guarantee the same semantics?

Yep! Equivalence and equality are strictly very different things.

Nit: I think the more common term in stdlib would be `areEquivalent()`. Do you think `same` in that context (independent of the word "ordering") might erroneously suggest identity?

There is room for improvement here. Keep ‘em coming.

On Thu, Jul 21, 2016 at 8:11 PM, Robert Widmann via swift-evolution <swift-evolution@swift.org> wrote:
Hello Swift Community,

Harlan Haskins, Jaden Geller, and I have been working on a proposal to clean up the semantics of ordering relations in the standard library. We have a draft that you can get as a gist. Any feedback you might have about this proposal helps - though please keeps your comments on Swift-Evolution and not on the gist.

Cheers,

~Robert Widmann

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Xiaodi Wu) #12

This is nice. Is `areSame()` being proposed because static `==` is the
status quo and you're trying to make the point that `==` in the future need
not guarantee the same semantics?

Yep! Equivalence and equality are strictly very different things.

Nit: I think the more common term in stdlib would be `areEquivalent()`. Do
you think `same` in that context (independent of the word "ordering") might
erroneously suggest identity?

There is room for improvement here. Keep ‘em coming.

Well, since you asked...
Wikipedia reminds me that a ~ b is an appropriate mathematical notation for
equivalence of a and b. We probably wouldn't want to confuse things with
bitwise not, but in the grand tradition of reduplicating to form operators
from their mathematical counterparts, what about infix operator `~~`? [In a
few minutes, I might find this to be a terrible idea.]

···

On Thu, Jul 21, 2016 at 8:32 PM, Robert Widmann <rwidmann@apple.com> wrote:

On Jul 21, 2016, at 6:19 PM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

On Thu, Jul 21, 2016 at 8:11 PM, Robert Widmann via swift-evolution < > swift-evolution@swift.org> wrote:

Hello Swift Community,

Harlan Haskins, Jaden Geller, and I have been working on a proposal to
clean up the semantics of ordering relations in the standard library. We
have a draft that you can get as a gist.
<https://gist.github.com/CodaFi/f0347bd37f1c407bf7ea0c429ead380e> Any
feedback you might have about this proposal helps - though please keeps
your comments on Swift-Evolution and not on the gist.

Cheers,

~Robert Widmann

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Dmitri Gribenko) #13

Hello Swift Community,

Harlan Haskins, Jaden Geller, and I have been working on a proposal to clean up the semantics of ordering relations in the standard library. We have a draft that you can get as a gist. Any feedback you might have about this proposal helps - though please keeps your comments on Swift-Evolution and not on the gist.

My thoughts on this are not yet fully formed, but I have a couple questions concerning `isSame(_:_:)` and `==`:

* Should calls like `index(of:)` and `split(separator:)` use `==` or `isSame(_:_:)`?

Use sites should always use `==`. They will pick up the semantics
appropriate for the generic constraints they see.

* Should `Hashable` use `==` or `isSame(_:_:)`?

Code generic over Hashable will not see a difference.

* Do we know of any use cases where a type conforms to `Equatable` but not `Comparable` and needs separate `isSame(_:_:)` and `==` operators?

No, but I can easily imagine that one exists.

Essentially, I'm wondering if we can leave `Equatable`'s definition alone and only change `Comparable` to require `<=>`, with a generic operator to provide a default `==` which uses `<=>`.

We can't do that, because two values equal according to `<=>` should
be equal according to Equatable. Otherwise protocols don't make any
sense.

Dmitri

···

On Thu, Jul 21, 2016 at 11:09 PM, Brent Royal-Gordon via swift-evolution <swift-evolution@swift.org> wrote:

On Jul 21, 2016, at 6:11 PM, Robert Widmann via swift-evolution <swift-evolution@swift.org> wrote:

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/


(Xiaodi Wu) #14

Robert, the gist is notably vague on this point, so I'm hoping you will
clarify. Are you proposing that FloatingPoint will break with IEEE754
semantics? What will be the result of `Float.nan == Float.nan`?

(My guess at the sanest outcome is that areSame/Equivalent() and <=> will
be totally ordered but FloatingPoint types will override == and the
standard comparison operators to maintain IEEE754 semantics, yes?)

···

On Thu, Jul 21, 2016 at 11:02 PM Dmitri Gribenko via swift-evolution < swift-evolution@swift.org> wrote:

Hi,

On Thu, Jul 21, 2016 at 6:11 PM, Robert Widmann via swift-evolution > <swift-evolution@swift.org> wrote:
> Hello Swift Community,
>
> Harlan Haskins, Jaden Geller, and I have been working on a proposal to
clean
> up the semantics of ordering relations in the standard library.

Great work!

As a part of your implementation, are you planning to add <=>
overloads for tuples, like we do now for comparison operators? (See
stdlib/public/core/Tuple.swift.gyb.)

Dmitri

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Dmitri Gribenko) #15

5. Will it be considered "ok" to define a type for which `T.areSame(a, b) == true` but `a != b`? An obvious example would be Double.nan, so I assume the answer is a resounding yes.

Yes, because `==` is not a protocol requirement of Equatable, so it
can have domain-specific semantics.

6. Similarly, will it be "ok" to define a type for which `T.areSame(a, b) == false` but `a == b`? One possible example could be the comparison of `-0.0 <=> +0.0`. Should those be `.same` or not?

7. What, in fact, is the proposed total order for the stdlib's floating-point types?

The IEEE 754 definition.

https://github.com/apple/swift/blob/f318fe853d7898246db24d501f1ddc03c9eb8651/stdlib/public/core/FloatingPoint.swift.gyb#L855

Dmitri

···

On Fri, Jul 22, 2016 at 2:13 AM, Pyry Jahkola via swift-evolution <swift-evolution@swift.org> wrote:

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/


(Dave Abrahams) #16

Definitely a +1 from me, in fact I've implemented essentially this as
an extension for my own convenience, but would definitely prefer it to
be a proper component of the stdlib.

I have some queries to raise:

First is the naming, to me Ordering implies the enum itself is used
for ordering collections but that's not really the case.

I don't understand why you think that's implied

In my own hacked implementation I'm using Order.before, Order.same,
and Order.after. It's not much of a change, but it seems to clarify
what the enum is, at least in my opinion.

I always thought the name “Order” would be perfect if it weren't so
short and likely to conflict with type names that user code will want.
We do have qualification to fall back on, so this is a judgement call.

I pretty strongly believe in the words “ascending” and “descending” for
the cases. The result reflects the order in which the arguments to the
function appear in a call. So if f reflects standard dictionary order,

    f("a", "b") => ascending
    f("b", "a") => descending

One thing I was considering, but didn't do since my extension is just
a bolt-on for convenience, is whether the before/ascending and
after/descending cases should contain a value, allowing
implementations to provide a hint of how far back/forward an element
should be. This is a hint only of course, but could be useful; for
example, when implementing a binary search you could instead use the
hint value to provide a (hopefully) better guess at where to jump to
next, for example if the value is very high you might jump to a
position forward backward/forward rather than always selecting the
middle every time. This is what Java's Comparable type does, since it
uses a number where negative is before, 0 is same and positive is
after.

I'm deeply skeptical. I don't believe you can use this hint to do
binary search without destroying its complexity guarantee. If you can
show me algorithms that take advantage of this hint, with demonstrations
of their correctness, I'd consider it.

Why is Equatable in this case implemented with a static .areSame()
method, but Comparable isn't implemented by a static .compare()
method? Seems like they should both be the same personally.

Because we wouldn't be able to .compare() tuples, which are not nominal
types that can be extended. That's almost the only reason, IIRC.

···

on Fri Jul 22 2016, Haravikk <swift-evolution@swift.org> wrote:

There should be a way to "flip" the operator. One thing that's great
about the current sorting method is the ability to pass the < or >
operators for ascending/descending respectively, we can do the first
one by passing the <=> operator, but a flip function or something
would be nice to, well, flip it (swap the ascending and descending
cases before returning).

Just some thoughts, but I definitely want this.

On 22 Jul 2016, at 02:11, Robert Widmann via swift-evolution >> <swift-evolution@swift.org> wrote:

Hello Swift Community,

Harlan Haskins, Jaden Geller, and I have been working on a proposal
to clean up the semantics of ordering relations in the standard
library. We have a draft that you can get as a
gist. <https://gist.github.com/CodaFi/f0347bd37f1c407bf7ea0c429ead380e>
Any feedback you might have about this proposal helps - though
please keeps your comments on Swift-Evolution and not on the gist.

Cheers,

~Robert Widmann

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

--
Dave


(Dave Abrahams) #17

Hello Swift Community,

Harlan Haskins, Jaden Geller, and I have been working on a proposal
to clean up the semantics of ordering relations in the standard
library. We have a draft that you can get as a
gist. <https://gist.github.com/CodaFi/f0347bd37f1c407bf7ea0c429ead380e>
Any feedback you might have about this proposal helps - though
please keeps your comments on Swift-Evolution and not on the gist.

Cheers,

~Robert Widmann

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

I fear that this will become confusing (especially since Equatable may
now be implemented as a static function, too). We will have 3
different “equality” comparisons in Swift:

=== for reference-types
== for all types
areSame() which may be subtly different to ==

In order to have an opinion on whether or not this is justified, I
need to know more about how areSame() may differ from == and how this
will affect generic code. What is required that could not fit inside
an override of Equatable?

Floating point types. You should be able to ask for
arrayOfFloats.firstIndex(of: x) even if there are NaNs in the array (or
x).

It will not affect generic code, since in generic code == will always
dispatch to areSame() (unless the argument is constrained to
FloatingPoint, in which case == will have floating point semantics).

It would not be wholly unreasonable to merge === and areSame; they mean
almost exactly the same thing.

If this only applies to a few types, will it be its own protocol
(e.g. EquivalenceCheckable)?

It applies to every type where an == operator is appropriate, as far as
I know. That's a lot.

Whether we should rename it something having to
do with “Equivalence” or “Identity,” etc., is a good (and separate) question.

···

on Fri Jul 22 2016, Karl <swift-evolution@swift.org> wrote:

On 22 Jul 2016, at 03:11, Robert Widmann via swift-evolution >> <swift-evolution@swift.org> wrote:

--
Dave


(Dave Abrahams) #18

This is nice. Is `areSame()` being proposed because static `==` is the
status quo and you're trying to make the point that `==` in the future need
not guarantee the same semantics?

Nit: I think the more common term in stdlib would be `areEquivalent()`. Do
you think `same` in that context (independent of the word "ordering") might
erroneously suggest identity?

It essentially *is* identity.

* Conformance to this protocol (the one we've been calling “Equatable”)
  means that when `areSame` returns `true` you can't distinguish one
  argument from the other (except maybe by looking at qualities that
  are explicitly documented as being inessential to the type, such as an
  array's capacity).

* When you make a class type conform, it therefore means that either you
  will implement areSame as address comparison or that you don't
  consider the address of the instance to be an essential quality. In
  other words, it's not part of the instance's logical identity.

···

on Thu Jul 21 2016, Xiaodi Wu <swift-evolution@swift.org> wrote:

On Thu, Jul 21, 2016 at 8:11 PM, Robert Widmann via swift-evolution < > swift-evolution@swift.org> wrote:

Hello Swift Community,

Harlan Haskins, Jaden Geller, and I have been working on a proposal to
clean up the semantics of ordering relations in the standard library. We
have a draft that you can get as a gist.
<https://gist.github.com/CodaFi/f0347bd37f1c407bf7ea0c429ead380e> Any
feedback you might have about this proposal helps - though please keeps
your comments on Swift-Evolution and not on the gist.

Cheers,

~Robert Widmann

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

--
Dave


(Dave Abrahams) #19

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.

···

on Thu Jul 21 2016, Duan <swift-evolution@swift.org> wrote:

Daniel Duan
Sent from my iPhone

On Jul 21, 2016, at 6:32 PM, Robert Widmann via swift-evolution >> <swift-evolution@swift.org> wrote:

On Jul 21, 2016, at 6:19 PM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

This is nice. Is `areSame()` being proposed because static `==` is
the status quo and you're trying to make the point that `==` in the
future need not guarantee the same semantics?

Yep! Equivalence and equality are strictly very different things.

Nit: I think the more common term in stdlib would be
`areEquivalent()`. Do you think `same` in that context (independent
of the word "ordering") might erroneously suggest identity?

There is room for improvement here. Keep ‘em coming.

On Thu, Jul 21, 2016 at 8:11 PM, Robert Widmann via >>>> swift-evolution >>>> <swift-evolution@swift.org> wrote:
Hello Swift Community,

Harlan Haskins, Jaden Geller, and I have been working on a
proposal to clean up the semantics of ordering relations in the
standard library. We have a draft that you can get as a gist.
Any feedback you might have about this proposal helps - though
please keeps your comments on Swift-Evolution and not on the gist.

Cheers,

~Robert Widmann

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

--
Dave


(Dave Abrahams) #20

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 :slight_smile: 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.

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.

···

on Fri Jul 22 2016, Tony Allevato <swift-evolution@swift.org> wrote:

--
Dave