[swift-evolution] [pitch] Comparison Reform
Dave Abrahams
dabrahams at apple.com
Sun Apr 23 07:54:45 CDT 2017
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?
Also, does the same go for != ? That's telling w.r.t. NaN.
> To put it more strongly, I think that anything short of that is rather
> inexplicable.
That's somewhat mitigated if we have to accept x != x (i.e. for NaN).
> 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 }`
I don't think this example is a good illustration of it, but I am
familiar with the principle.
> 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.
x === y but x != y
?
IMO it may be possible, but not without head explosion. Sure, it's the
case for NaN, but that's just because of how IEEE defined it; there is
nothing in daily experience that acts that way. IMO it is much easier
to understand x == y but x !== y, that is, “these two forks are
identical, but they're not the same fork.”
>> >> >> >> 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.)"
Thanks.
>> > 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.
As noted above, I disagree that that is a simple concept. Is it even
mathematically well-founded? What you are expressing, at least on the
surface, *seems* to be different from the mathematical notion of
incomparability, which—despite its confusing name—is actually simple
<https://en.wikipedia.org/wiki/Comparability>: x is incomparable to y if
neither x > y nor x < y. The most common case is when x == y. In a
strict-weak ordering, every element is incomparable with itself. The
complexity of your predicate suggests that you mean something much more
complicated. Is there any reason not to require that when (x <=> y) ==
nil, (x <=> x) == nil? That would simplify things a lot.
Also, IMO it is confusing to say, “cannot be compared to itself,” when
in practice that means “you can compare it to itself, and you get nil.”
This is as much a result of comparison as any other.
> 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?"
Is that an easy question to answer? It doesn't look that way, to me.
>
>
>> > 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.
I'm not wedded to any particular answer there. The only reason I think
we proposed it is that it corresponds to an IEEE comparison level.
> 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]`.
Okay, take elementsEqual then. I don't see why array1 == array2 is any
different from array1.elementsEqual(array2).
>> > 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.
I don't think so. The problem, IMO, is that you're expressing something
hard to understand that falls outside anyone's experience (except maybe
their experience with NaN).
> 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.
An algorithm written in terms of any of the algorithms whose semantics
you're talking about adjusting (sort, contains, elementsEqual...) will
pick up that algorithm's decision without its author making any explicit
choice.
>> 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.
Well, that's just like saying you can sort with different predicates.
I'm not sure it's OK to break the invariant that, in the absence of
equal elements,
x.sorted(by: <).elementsEqual(x.sorted(by: >).reversed())
> 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.
Is that a known-useful property, or just a flexibility that is plausibly
useful, someday?
>> 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."
I guess if I agree that min and max should never return NaN unless
that's the only value in the sequence, I have to agree with that
statement.
>> > 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).
Thanks for that. But people *will* divide Doubles outside of a generic
context, and store the results. It happens a *lot*.
> 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.
Oh, I agree. The problem is that nobody is talking about stopping
propagation... unless you happen to compare the value somewhere along
the way.
> 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.
Now, wait just a darn-tootin' minute there, pardner. Well, if that were
strictly true, we'd just make them always trap, right? Non-signaling
NaNs exist because somebody thought it was “good” to be able to finish a
calculation and get *some* results out of it even if other parts of the
results come from unaccounted-for nonsense.
> 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!
Well, I'm afraid you haven't really addressed my concern, which is that
NaNs may propagate a long way before we find out they have appeared, if
we find out at all, and because of that propagation, trapping might be
worse than continuing.
>> 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?
I honestly don't know.
> JSON, for example, doesn't even permit NaN.
Yeah, but you only need to encode zero in your JSON to produce a NaN
from a simple division.
> 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.
I didn't say it was harmless. I'm just not sure whether it's as harmful
as trapping far from the source of the problem would be. I honestly
don't know the answers here. I've used very little FP in the
applicatiopn programming I've done, so I don't have a good read on what
goes wrong for people.
--
-Dave
More information about the swift-evolution
mailing list