[swift-evolution] [pitch] Comparison Reform

[Dave Abrahams]

on Sun Apr 23 2017, Xiaodi Wu <xiaodi.wu-AT-gmail.com> wrote:

> On Sun, Apr 23, 2017 at 4:32 PM, Dave Abrahams <dabrahams at apple.com> wrote:
>
>>
>> on Sun Apr 23 2017, Xiaodi Wu <xiaodi.wu-AT-gmail.com> wrote:
>>
>> > On Sun, Apr 23, 2017 at 7:54 AM, Dave Abrahams <dabrahams at apple.com>
>> wrote:
>> >
>> >>
>> >> on Sun Apr 23 2017, Xiaodi Wu <xiaodi.wu-AT-gmail.com> wrote:
>> >>
>> >> > On Sat, Apr 22, 2017 at 11:00 PM, Dave Abrahams <dabrahams at apple.com>
>> >> wrote:
>> >> >
>> >> >>
>> >> >> >> > That is to say, I would expect the standard library to supply an
>> >> >> >> > alternative implementation of equality for Array<T where T :
>> >> >> >> > FloatingPoint>.
>> >> >> >>
>> >> >> >> And also for Dictionary?  What do you expect to happen when
>> Double is
>> >> >> >> used as a dictionary key and it happens to be NaN?
>> >> >> >
>> >> >> > The proposal is very clear that `Dictionary` and `sort` will always
>> >> use
>> >> >> > level 2 comparison.
>> >> >>
>> >> >> Yes, but I'm not asking about my own proposal :-).  My question is,
>> what
>> >> >> are *your* expectations for dictionaries or sets, specifically for
>> the
>> >> >> insertion of NaN keys and for comparison of whole collections?
>> >> >
>> >> > My expectations for comparison of collections clearly differ from
>> >> > yours.
>> >>
>> >> Maybe, in that you *have* strong expectations when it comes to FP.  I'm
>> >> still trying to figure out what mine should be.
>> >>
>> >> > For me, I think it is a reasonable expectation that, for all `x` and
>> >> > `y` where `x == y`, `[x] == `[y]`, `[[x]] == [[y]]`, `[x, x, x] == [y,
>> >> > y, y]`, etc.
>> >>
>> >> It seems pretty obvious when you put it that way.  Here's an interesting
>> >> question: how much of that is because of the way array literals let you
>> >> “see through” the value being compared to its elements?
>> >>
>> >
>> > I don't think it's the visual representation. More to do with
>> expectations
>> > as to what an array is.
>> >
>> > If `a == b`, then `thingWrappingA == thingWrappingB`, for values of
>> "thing"
>> > that are "wrapper-like" (I will blithely leave the term undefined) rather
>> > than, say, stateful class instances.
>>
>> wrapper-like probably means "Monad"
>>
>> >> Also, does the same go for != ? That's telling w.r.t. NaN.
>> >
>> > Yes, I think so. I'd have to think harder to be more sure of that.
>>
>> Well, that's the hard one, so please do.  We can easily shift the
>> proposal so -0.0 == +0.0, but NaNs are harder to account for.
>>
>>
> Right, more thought is necessary. It was obviated when I was writing my
> proposed design, because NaN != NaN simply traps, and [NaN] != [NaN] would
> too.

More thought was obviated?  That's a neat trick! ;-)

>> > Hmm, not an expert, but I don't see that definition. MathWorld <
>> > http://mathworld.wolfram.com/ComparableElements.html> confirms that the
>> > Wikipedia formulation is correct:
>> >
>> > x is incomparable to y if neither x ***>=*** y nor x ***<=*** y.
>>
>> Ah, right.  But this is where it gets tricky to interpret, because IIUC
>> in orderings in general, there is no concept of equality; there's just
>> "x precedes y or it doesn't."  So when these articles use <= or <, it is
>> a stand-in for "the ordering predicate".  In ancient times, I wrote an
>> article exploring some of this
>> (http://web.archive.org/web/20120422220137/http://cpp-
>> next.com/archive/2010/02/order-i-say/).
>> I always go back to that when I need to ground myself, though using your
>> own article for that has its perils.  Please check that out and let me
>> know if you think I'm off-base, because the notion of incomparability in
>> that article is central to my understanding (and is, I believe,
>> consistent with https://en.wikipedia.org/wiki/Weak_ordering, FWIW).
>
> IIUC, you're talking about a _strict_ partial order, which is
> _irreflexive_. 

That may be another name for the same thing.  The terminology in this
area is... problematic.  But look for “incomparable” at
https://en.wikipedia.org/wiki/Weak_ordering and you'll see that I'm
consistent with that.

> Such a relation is totally silent, however, as to whether x and y are
> equivalent if `x !<> y`. 

Correct; that's what I meant by “in orderings in general, there's no
concept of equality.”  However, if `x !<> y` in a strict weak ordering,
`x` and `y` are part of an equivalence class, each element of which has
the same relationships with all the other elements of the set.

> As a standalone predicate, it isn't sufficient to order a set which
> contains a pair of incomparable values in the way that you and Ben
> propose. For instance, suppose I'm trying to sort an array with 42 and
> NaN using a generic algorithm that can't just test `isNaN`. 
> So, to the algorithm, these values are an opaque `a` and `b`.  Since
> !(a < b) and !(b < a), there's no information I can get from the
> predicate to tell me which one is the "problem value" (is it a, or is
> it b: which one is NaN?).

I'm sorry, I don't follow.  Your statement that our ordering of incomparable
values is insufficient seems to lack context, so I can't evaluate it.
I'll note that in a strict weak ordering, incomparable values are not
problematic, but Floating Point doesn't have a strict weak ordering.

> In the context of set theory, I'm reading that comparability is defined in
> terms of _weak_ partial orders (which are reflexive). 

Where are you reading that?

As my article notes, trying to analyze the space can be really
confusing, because *strict weak* partial orders are *not* reflexive.

> I guess I've just assumed we're using this definition of comparability
> because IEEE floating point appears to adopt it. 

What makes you say that?

> With a _weak_ partial order as a predicate, you *can* order a set
> which contains a pair of incomparable values:
>
> * Given: 42 ("a") and NaN ("b").
> * First, we note that !(a <= b) && !(b <= a). So, we have a pair of
> incomparable values.
> * Then, we ask which value is not a member of the partially ordered set on
> which the <= relation is defined.
> * We find that (a <= a) == true but (b <= b) == false.
> * We conclude that b is the "problem value" (NaN) which is not a member of
> the partially ordered set.
> * We decide to send it to the back of the line.

Yes, I understand that.  But I don't think I get the point yet.

>> > I am not suggesting this particular name, but
>> > `array1.elementsIndistinguishable(from: array2)` expresses something of
>> the
>> > idea.
>>
>> I'm very skeptical of introducing a notion of indistinguishability
>> that's distinct from equality.
>
> I think this goes back to the above about what we want equality to be. If
> equality is to be distinguished from incomparability (as it is in floating
> point), then we must have some notion of what happens when two values
> cannot be compared. 

That two elements are incomparable doesn't mean you can't compare them.
It means that when you do compare them, you'll find they have no
relative ordering, like siblings in a DAG.  See
https://en.wikipedia.org/wiki/Comparability

More later, if I can find time...

-- 
-Dave