[swift-evolution] [pitch] Comparison Reform

[Xiaodi Wu]

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.
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. To put it more strongly, I think that anything short of that is rather
inexplicable.

With respect to dictionaries keys or sets, it's a subtly different
question, I think. When it comes to questions like "does this dictionary
have this key" or "does this set already have this element," I think what
the user is really asking about is a closer approximation to identity than
to equality. I get that this gets complicated if we're talking about sets
of class instances, so let me move away from the word identity and
re-phrase. If a user asks if a set (or even an array) contains something,
it's not exactly identical to asking if a set contains an element _equal
to_ something. See:

* "Does the set of cars in your parking lot contain my car?" =>
`parkingLot.contains(myCar)`
* "Does the set of cars in your parking lot contain a car that is equal to
my car?" => `parkingLot.contains { $0 == myCar }`

Put another way, one can simultaneously hold the thought that (1) a thing
is itself, obviously; but (2) a thing is not necessarily _equal to_ itself.


> >> >> >> This is a bump in the rug – push it down in one place, it pops up
> >> >> >> in another. I feel like this proposal at least moves the bump to
> >> >> >> where
> >> >> fewer
> >> >> >> people will trip over it. I think it highly likely that the
> >> >> intersection of
> >> >> >> developers who understand enough about floating point to write
> truly
> >> >> >> correct concrete code, but won’t know about or discover the
> >> documented
> >> >> >> difference in generic code, is far smaller than the set of people
> who
> >> >> hit
> >> >> >> problems with the existing behavior.
> >> >> >>
> >> >> >
> >> >> > So, to extend this analogy, I'd rather say that the bump is not in
> the
> >> >> rug
> >> >> > [Comparable] but rather in a section of the floor [FP NaN]. The rug
> >> might
> >> >> > overlie the bump, but the bump will always be there and people will
> >> find
> >> >> it
> >> >> > as they walk even if they don't immediately see it.
> >> >>
> >> >> Correct.
> >> >>
> >> >> > If we don't want people to trip over the bump while walking on the
> >> >> > rug, one very good alternative, IMHO, is to shape the rug so that
> it
> >> >> > doesn't cover the bump.
> >> >>
> >> >> At what cost?
> >> >>
> >> >> More specifically: why is it the right behavior, for our audience, to
> >> >> trap when Equatable comparison happens to encounter NaN?  Will this
> not
> >> >> simply "crash" programs in the field that otherwise would have "just
> >> >> worked?"
> >> >
> >> > No, as I propose it, programs in the field would be automatically
> >> migrated
> >> > to an alternative set of comparison operators `&==`, `&<`, etc. that
> >> would
> >> > work exactly as `==`, `<`, etc. do today.
> >>
> >> Meaning, for floating point NaN &== NaN is false, and if you want to
> >> write numeric code that accounts for NaN, you use &==.
> >>
> >> OK, so... Is &== a protocol requirement, or a protocol extension, or
> >> neither?  If so, to which protocol is it attached?
> >
> > Please allow me to refer you to a Gist:
> > https://gist.github.com/xwu/e864ffdf343160a8a26839388f677768
> >
> > In brief, it would be a protocol requirement on Comparable with a default
> > implementation. The rationale for its being on Comparable is given in the
> > text.
>
> I'm sorry, I've seen your gist; I still can't find this rationale.
>

"These operators will be defined on Comparable and not on FloatingPoint. A
key rationale for this design is to permit types other than FloatingPoint,
including third-party types, to distinguish between signaling and quiet
comparison of values when some values may be unordered with respect to
others. (Another rationale for this design is that &< corresponds to what
is currently spelled as <, which can be used as a predicate for
Sequence.sorted.)"

> I am not married to its being a requirement vs. an extension, but my
> > initial thought here is that there might be reason to provide an
> > alternative implementation in a conforming type, say for performance
> > reasons on Float.
> >
> >> > I would quibble with the notion that all such generic algorithms
> >> > currently "just work,"
> >>
> >> I never claimed they do!  They don't, because Equatable.== for floating
> >> point is not an equivalence relation.  That's part of what we aim to
> >> fix.
> >>
> >> You are proposing to fix that same problem a different way, one that
> leaves
> >> NaNs a bit out-in-the-cold (not necessarily bad), but also explicitly
> >> modifies generic algorithms so they continue to silently produce
> >> unspecified results (bad!)
> >
> > To clarify, no, I would not have the stdlib's generic algorithms continue
> > to produce unspecified results. I propose changes to them which align
> their
> > behavior with what you and Ben have proposed.
>
> OK, I guess I must've misunderstood your earlier statements.
>
> So this, IMO, is not tenable, at least in its current form:
>
> ,----
> | The default implementation for contains, elementsEqual, split, and
> | starts(with:) on Sequence where Iterator.Element : Equatable, and for
> | index(of:) on Collection where Iterator.Element : Equatable, will
> | (notionally) use the following predicate:
> |
> | {
> |   ($0 &== $1) || (
> |     ($0 <=> $1) == .none &&
> |     ($0 <=> $0) == .none &&
> |     ($1 <=> $1) == .none)
> | }
> `----
>
> The first problem here is that I can't figure out what this means and I
> doubt any normal user could either.


I think it is a little ill-served by the notation. However the concept is
simple. Sometimes, a thing cannot be compared even to itself. The prime
example we speak of is NaN != NaN. This is the only major concept that the
design I propose here would require a user to understand.

In this notation, if `x` cannot be compared to itself, `x <=> x` is nil.
For `contains` and other methods that are asking "do you have a thing" more
than they are asking "do you have a thing that is equivalent to a thing,"
we'll regard all values that can't be compared even to themselves as "the
same"; therefore, if `x <=> x` is nil and `y <=> y` is nil, then a
collection with an element `x` will be regarded as "containing" `y`.

How would this change in semantics
> be reflected in the documentation for these algorithms?  How would you
> describe their requirements and results?  All these algorithms currently
> have simple, understandable descriptions.
>

The description would be augmented by an explanation along the lines of
this: "Some types can represent values that do not compare equal to
themselves; one example is floating point NaN ("not a number"). For the
purposes of { contains | split | etc. }, every value not equal to itself is
considered indistinguishable from every other value not equal to itself."

Secondarily, I can't expect any generic algorithm author to understand
> what he's getting with this.
>

Obviously, we'd have to have real-world data to back it up, but the beauty
of `Comparison?` being an optional enum is that all an author has to do is
handle all the cases. The compiler can even help with that. In other words,
all your generic algorithm author has to do is to decide *something* for
the question, "What should I do when x <=> y returns nil?"

> Any automatically migrated third-party generic code would indeed continue
> > to exhibit the same behavior as in Swift 3--but not only do I not
> consider
> > that to be a problem, I consider it to be a requirement of source
> > compatibility which is absolutely essential.
>
> Well, we have not promised to preserve unspecified behaviors, so
> technically we can handle this either way.  And we all seem to be agreed
> that any code that uses, e.g., the default sort(), *will* change its
> behavior with respect to NaN.  So this is really a matter of degree.
>
> > It would not, however, be _invisible_ to the reader of the generic
> > algorithm. The use of my proposed `&==` in a generic context should stand
> > out and prompt re-evaluation. That is to say, by using a different
> > spelling, we would have a visible hint in the code that a generic
> algorithm
> > may produce unspecified results with NaN.
>
> That's a very nice feature.
>
> >>> but the result is that they would behave exactly as they do today and
> >>> therefore would at least be no more broken.
> >>
> >> If that's all we acheive, we should do nothing.
> >
> > I should hope that it's not all we achieve. But, consider the following
> two
> > alternatives: migrated code exhibits identical behavior to Swift 3, or
> > migrated code silently exhibits different behavior that is "fixed."
>
> I think we're both agreed that the latter *will* happen with
>
>   sort(floatsContainingNaN)
>
> or
>
>    floatsContainingNaN.contains(.NaN)


Well, I do not agree that `[+0.0].contains(-0.0)` should return `false`,
but we can discuss that on the side.

Otherwise, the key difference here is that code that's _correctly written_
for FP *would never use* a statement like
`floatsContainingNaN.contains(.nan)` because with its current behavior it'd
be equivalent to `false` (or at least, it's not reliably `true`). The same
cannot be said for `Array<Double>.==`, which can be profitably used when
the user knows that `[.nan] != [.nan]`.

> I am very disturbed by the possibility of the latter. It is the only
> > part of this proposal that keeps me up at night.
>
> I agree it's concerning, but I don't think fixing just part of this
> problem is going to help either ;-).
>
> > As it turns out, some people really do understand how floating point
> > comparison works, and they might have even carefully written code that
> > behaves correctly, relying on the current behavior when things are
> > compared. Please don't "fix" that code. If an array of type [Float]
> starts
> > to distinguish between +0.0 and -0.0 as you propose, I'm quite sure that
> > there is at least some code of my own that will be quite broken.
>
> yep, sadly.  But IIUC that's inevitable.
>
> >> > Standard library changes to `sort` and other functions will make them
> >> > "just work" with no distinguishable difference to the end user as
> >> > compared to this proposal here.
> >>
> >> I'm sorry, I don't know what "this proposal here" means.  Is that yours
> >> or the one Ben and I offered?  It's certainly different from the results
> >> of our proposal.
> >>
> >> The big problem with our proposal, AFAICT, is that
> >>
> >>     floatsIncludingNaNs.sort()
> >>
> >> works but
> >>
> >>     floatsIncludingNaNs.sort(>)
> >>
> >> does not.  That is a real problem, but it *is* a difference from the
> >> current behavior, where neither one works.
> >>
> >
> > Hmm, I get the sense that some of my replies to you have been lost. I
> have
> > explicitly proposed a design where `floatsIncludingNaNs.sort()` produces
> > the same behavior as what is proposed by you and Ben. I'd like to refer
> you
> > again to the fleshed out Gist:
> >
> > https://gist.github.com/xwu/e864ffdf343160a8a26839388f677768
>
> Sorry I misread your earlier remarks.  I don't think I missed them.
>
> >> > It would be an improvement over how the algorithms work today with
> >> > NaN.
> >> >
> >> > The major difference to the end user between what I propose and
> >> > this proposal here will surface when _new_ code is written that
> >> > uses `==` in the generic context, when working with types whose
> >> > values may compare unordered. Since I propose `<=>` to return a
> >> > value of type `Comparison?`, using the revised operator `==` is an
> >> > assertion that the result of comparison is not unordered. A user is
> >> > welcome to use `&==` or a custom predicate if that is not their
> >> > intention.
> >>
> >> The problem with this is that there's still no simple way to get an
>                                                   ^^^^^^
> >> equivalence relation or a total order over all Doubles, including NaNs.
> >
> > There is. Given two values x and y, `x &< y || (y <=> y) == nil` is
> > identical to the `<` that you propose.
>
> Err, I rest my case?
>

It'd be easier with some more syntactic sugar, I guess. But my point above
is that it is not difficult to describe what is happening in prose. Here,
simply, if a value is not equal to itself, then it's ordered after all
values that are equal to themselves.

>> Now, I'm totally willing to have the discussion about how NaNs have no
> >> business being used as dictionary keys, or sort keys, or searched for,
> >> or any of the other things we do with day-to-day values.  That's not
> >> something I really have an opinion on, yet.
> >
> > I would not assert that NaN has no business being used here; again, my
> > alternative design accommodates all of these use cases.
> >
> > Where we differ is that, in the case of a generic algorithm, my
> > alternative design would result in the author of that algorithm either
> > explicitly accommodating the presence of unordered values or asserting
> > their absence.
>
> That is a nice property, except that IIUC you're talking about granting
> an exception for the most common forms of algorithms.
>

Not that I'm aware of? All algorithms will need to be modified to deal with
what happens if `(x <=> y) == nil`. I've just listed the ways in which
stdlib functions will do so.


> Aside: I object to characterizing these things as unordered.


Sorry, just using the terminology I read about. For instance, IEEE says
that NaN compares _unordered_ to itself.


> For the
> purposes of the algorithms that are written to accomodate them, they
> must be very much ordered, if not with respect to each other, at *least*
> with respect to other values in the space.  In other words, there needs
> to be an underlying strict-weak order or the algorithms won't work.
>

Not a fixed one, though, unless I'm misunderstanding? It would be trivial
in my design for `sort` to order NaN values to the _end of the array_, as
opposed to ordering them greater than all other values, with the result
that NaN comes last whether you sort ascending or descending. Not that I'm
proposing this behavior, but I don't *think* that it breaks anything.

Put another way, as far as I can tell, values like NaN only need to have a
specified sequence with respect to other values _for the purposes of any
particular operation at hand_. Therefore, I've proposed a design where it's
the generic algorithm and not the type that makes the decision for how
these values are placed in sequence.

> It is not an avoidable problem--this is the bump in the rug that
> > cannot be smoothed out.
> >
> > I would posit that it is not possible to write an arbitrary generic
> > algorithm that (a) compares floating point values; (b) doesn't account
> for
> > NaN; and (c) behaves correctly, where correctly here means that it
> returns
> > what an average user would expect who is not thinking of floating point
> > comparison foibles.
>
> Existence proof: any algorithm that, internally, uses binary search over
> a sorted collection of Comparabble values, or stores Comparable values
> in a tree-based dictionary, but does not care exactly how two distinct
> values sort, will work just fine
>
> ...provided average users expect the existence of a distinct -0.0
> ;-)
>

Ha, that's not what I was trying to get at. I fully expect that there will
be _some_ algorithms that will work out in this way. But, it is not
possible to say that any particular design of Comparable will smooth over
wrinkles with NaN such that generic algorithms in general can ignore the
possibility of NaN and yet handle them "correctly."

> For instance, generic `max` produces what to the average user is
> > nonsense if NaN compares greater than everything.
> >
> >> I am, however, concerned that ordinary valid computations can lead to
> >> NaN and that allowing the appearance of a NaN to turn into a trap
> >> much later in the program, where it is finally compared with
> >> something, is not a behavior that would work for ordinary users.
>
> That is my central worry with anything that turns operations on NaN into
> a trap.  I'd very much appreciate hearing your thoughts.
>

There are a limited number of ordinary operations that actually generate
NaN.

If using arithmetic operators, there's 0/0 (which, as everyone already
knows, traps if you're doing integer math--you'll notice I lobbied to
remove `/` from protocols refined by both Integer and FloatingPoint, so now
it's not even possible to accidentally do this in generic code unless you
unwisely make your own `Divisible` protocol).

Other than that, you'd have to be already working with infinite values and
the arithmetic operators, or you'd have to invoke some of the trigonometric
and transcendental functions--but those are specific to floating point and
not accounting for NaN would be pretty silly there.

In general, I really think there's something valuable to trapping when you
try to propagate NaN through code that doesn't expect it. After all,
_something_ has gone wrong if you're copying "NaN GB" of data, or you're at
"NaN%" progress on a task. And those are innocuous examples because it's
probable that the value is being used for user interface display and not
much else. With other uses, certainly nothing good can come of an
unaccounted-for NaN. Is it really the correct thing to supply some
"default" answer, however explainable, when a user unintentionally asks,
"Is my number x less than not-a-number?" As a healthcare provider, would it
be OK for me to prescribe NaN doses of medication? An EMR written in Swift
might tell me it's not less than the minimum dose!

>>
> >> >> My purpose in exploring an alternative design is to see if it would
> be
> >> >> > feasible for non-FP-aware comparison operators to refuse to compare
> >> NaN,
> >> >> > rather than giving different answers depending on context.
> >> >>
> >> >> So... to be clear, this is still different behavior based on context.
> >> >> Is this not just as confusing a result?
> >> >>
> >> >>   let nan = 0.0 / 0.0
> >> >>   print(nan == nan)     // false
> >> >>   print([nan] == [nan]) // trap
> >> >>
> >> >> > I now strongly believe that this may make for a design
> simultaneously
> >> >> > _less_ complex *and* _more_ comprehensive (as measured by the
> >> >> > flatness-of-rug metric).
> >> >>
> >> >> I'm certainly willing to discuss it, but so far it doesn't seem like
> >> >> you've been willing to answer the central questions above.
> >> >>
> >> >
> >> > Clearly, I'm not understanding the central questions. Which ones have
> I
> >> > left unanswered?
> >>
> >> Again:
> >>
> >>   Why is it the right behavior, for our audience, to trap when Equatable
> >>   comparison happens to encounter NaN?
> >>
> >
> > There are three possibilities (that I know of) when an equatable
> comparison
> > `==` encounters NaN:
> >
> > * unspecified behavior (the current situation)
> > * a default behavior (as proposed by you and Ben, that would be ordering
> > NaN after all other values)
> > * trapping (as proposed by me)
> >
> > I take it as given that you do not need to be convinced why unspecified
> > behavior is inferior to the alternatives. As to why trapping is superior
> to
> > a default behavior, I return to what I talk about above:
> >
> > Rhetorical question--do you think that there is any design for Comparable
> > that would allow someone to compare floating point values *without*
> knowing
> > about the existence of NaN in such a way that an arbitrary generic
> > algorithm would behave as expected for a user who isn't thinking about
> > floating point comparison?
>
> Yep, see above.
>
> > As I point out above, ordering NaN after all other values works for
> `sort`
> > but doesn't work so well for `max`. You can say that you'll provide a
> > special floating point `max`, but I can do you one better with a design
> > where the _generic algorithm_ and not the _comparable type_ sorts out
> what
> > happens with unordered values. In such a design, both generic `sort` and
> > generic `max` can offer fully specified, sensible behavior *without*
> > special versions for floating point.
>
> Yeah... I'll believe it when I see it.  The sensible specification, that
> is ;-).  So far what I've seen looks much too complicated for simple
> notions like equality and ordering.
>
> > So, having said all of that, I return to address the question directly.
> > Let's consider where a user might encounter `==` unexpectedly trapping on
> > NaN:
> >
> > * The user is writing FP code, intending to use FP comparisons, and
> hasn't
> > heard about the change in spelling. He or she is given immediate feedback
> > and uses the corresponding operators `&==`, etc. This is a one-time
> > learning experience.
>
> Yeah, that happens as long as the appearance of NaN in his or her
> computation is a case caught by tests.  But I'm not confident it will
> be.
>
> > * The user is authoring a generic algorithm and using `==`. Trapping is
> > optimal because either they will test their algorithm with floating point
> > NaN and then consider how to handle that special case, or they will not
> > test their algorithm and `==` is effectively a precondition that the
> > algorithm will not encounter NaN, which would be an untested scenario.
> If,
> > on the other hand, a default behavior is instead what occurs, it may not
> be
> > unspecified behavior to _you_ the author of this proposal for Comparable,
> > but it certainly would be behavior that has never been reasoned through
> by
> > the author of the generic algorithm.
> >
> > * The user is calling a generic algorithm not designed for handling NaN
> > using a FP argument that is NaN. I believe that trapping is still the
> > correct behavior because silently proceeding with a result that the
> author
> > of the generic algorithm has never tested or thought about is potentially
> > more harmful than the user of the algorithm getting immediate feedback
> that
> > the algorithm has not been tested with NaN. For instance, how can I tell
> if
> > stdlib `max` is "NaN-ready"? Well, if `max` is not NaN-ready, in my
> > proposed design `max(.nan)` will trap right away; in yours, one must
> > inspect the result and consider whether the behavior is what is intended
> > and appropriate, which should principally be the job of the author of the
> > generic algorithm.
>
> Again, I'm concerned that NaNs will arise as the result of computations
> involving external inputs, and that programs that would otherwise
> harmlessly propagate NaN values (just as non-signaling NaN was
> designed!) will trap in the field, very far from the original source of
> the problem, which means bugs will be very hard to correct.
>

Is it that common to get NaN as a result of external inputs? JSON, for
example, doesn't even permit NaN. I agree that it is possible to propagate
NaN in a useful way, and indeed I would propose to expand the option to
propagate values that are unordered with respect to themselves by having
operators defined on Comparable. However, my disagreement with you here is
that we should not assume that _unintentional_ propagation is _harmless_
propagation.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20170423/763fa15a/attachment.html>