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


>> > 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.”
>
> Yet both these scenarios really do happen with stdlib types.
>
> I'm of the strong belief that it's only potentially head-exploding for some
> users because the language tries to paper over scenarios where it might
> happen and doesn't provide a way even to express this idea in code ("Binary
> operator '===' cannot be applied to two 'Int' operands").

I don't think this has anything to do with the language.  IMO this is
about what “equal” means.  People have an innate sense of equality that
doesn't admit x != x, at least not without some thread atomically
changing x's value behind our backs.  

> If, as I suggest, we put front and center the idea that _some comparisons
> might fail or return nil_, the resulting design is not in itself guaranteed
> to explode heads--I think.

I don't know that it's possible to put together a coherent understanding
of what a == b means in such a world.

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

>> 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.
>
> Well, x is said to be comparable to x if either x <= x or x >= x.
> Otherwise, x and x are incomparable.
>
> I propose we model this by returning a result of type `Comparison?`, such
> that this scenario produces a nil value rather than a `Comparison` case. In
> that sense, one might say that there is no comparison result.
>
>> > 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.
>
> For behaviors such as "always sort NaN greater than everything else" or
> "always sort NaN less than everything else," the way to answer the question
> would be to inspect whether `x` is comparable to `x` and/or `y` is
> comparable to `y`.

That's fine if you know what the behavior should be.  I'm not yet
convinced it's easy to answer the question of what the behavior should
be.

>> >> > 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).
>
> Indeed, `elementsEqual` requires special consideration. I had the same
> thought while writing the Gist and commented; "One consequence of this
> design is that `[Double.nan].contains(.nan)` returns true, as ordinarily
> expected. Consideration may be given to improving the naming of
> `elementsEqual` so as not to suggest that all elements of the receiver and
> argument literally compare `.some(.equal)`."
>
> 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 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.
>
> Sure. However, consider that `sort`, `contains`, `elementsEqual` all have
> corresponding `sort(by:)`, `contains(where:)`, `elementsEqual(_:by:)`. When
> I write `sort()`, I'm also saying, "Let the stdlib provide me with a
> default sort." I don't think that anyone who writes `sort()` is ignorant of
> the fact that they must accept a default predicate since they are
> _choosing_ not to specify one themselves.

I don't think this is consistent with your claim that algorithm authors
“either explicitly accommodate the presence of unordered values or
assert their absence.”  In your model I can call sort without making any
kind of explicit accomodation or assertion.

>>> 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())
>>
>
> Aha. A harebrained idea strikes: `elementsEqual` could ignore NaN.
>
> [.nan, .nan, 42, 42].elementsEqual([42, .nan, 42, .nan]) // true
>
> Just thinking out loud; not seriously proposing it. 

It's interesting... but I'm not sure why it's right, any more than you
would want

  [.nan, .nan, 42, 42] == [42, .nan, 42, .nan] // true

> I do not have a problem with observing the invariant you state by
> sorting all NaN values always greater than or less than non-NaN
> values.

This suggests to me that you haven't thought about the strictest
possible requirements we could place on comparison that would still work
for FP.  I think that's a necessary part of doing this design.

>> > 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?
>>
>
> This is what permits a generic `Comparable.max` and `Comparable.min` to
> both avoid spitting out NaN.

I am not convinced that's necessary.

> It also enables potentially more advanced algorithms: a partially ordered
> set S can have more than one maximal element; a mathematically rigorous
> algorithm could be provided (in a third-party library, say) to return all
> of them. Any such work in this domain requires the baseline Comparable
> protocol to recognize this concept of incomparability. It cannot be
> retroactively bolted on by a third party.
>
>>> 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*.
>>
>
> Sure. Is your principal worry that people will run into this behavior while
> writing simple code in the context of using concrete Doubles? 

Yes.

> It is an inescapable possibility with trapping `==`. It is also
> clearly different from precedent in a lot of languages to name the
> default FP comparison operator `&==`. That said, conceptually it seems
> similar to making `+` trap on overflow. 

The difference is that with `+` the trap happens as close as possible to
the source of the problem, not after nonsense has propagated all over
the program, been saved to disk, etc.

> Were the designers of that feature simply not worried about people
> adding lots of Int8 values?
>
> Anyway, I look forward to Steve's expanded thoughts on this particular
> point.
>
>> 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.
>>
>
> How convenient that (quoting from Wikipedia) it is recorded for all the
> world that "[f]loating-point operations **other than ordered comparisons**
> normally propagate a quiet NaN" [emphasis mine]. It is true that the IEEE
> default is "non-stop" exception handling; the consequence of a design such
> as mine would be that such IEEE floating-point defaults would need their
> own distinct notation.
>
> Simply, all of the following cannot be true:
>
> (a) `==` gives the same answer in all contexts (i.e., if `a == b` in
> generic contexts, then `a == b` in non-generic contexts)
> (b) `==` behaves according to IEEE default "non-stop" exception handling
> rules for FP values and gives the IEEE-prescribed result
> (c) `==` is useful for a generic algorithm that works with both FP and
> non-FP values and avoids unspecified behavior with FP values
>
> Currently, (a) and (b) are both true. I propose (a) and (c), providing (b)
> with a different spelling. You propose (b) and (c).

Well, I'm withdrawing my proposal and claiming agnosticism at this
point.  We're back into the design phase on this one.  But I understand
what you mean.

>> 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.
>>
>
> Hmm, I have always assumed that the most pressing motivation is to permit
> you to compute `sin(cos(tan(atan(acos(asin(x))))))` and deal with NaN at
> the end instead of checking after every function call, which would make
> writing out a mathematical formula like this quite untenable.

I think there are at least two uses for NaN.  That is one of them.
Another is, e.g., in linear algebra, where you may be able to solve for
some of the variables in a system and the appearance of NaN in one place
should not necessarily invalidate the entire calculation.  IIUC there
are more esoteric uses too, but I don't know much about them.

> It is true that by allowing propagation, you can serialize NaN into some
> long-term storage format for arbitrary periods of time before dealing with
> it, but my understanding is that it's actually recommended for placeholders
> in deserialized data to be __signaling NaNs__. The standard is pretty terse
> on the topic (unless I'm missing some text), but writes: "Signaling NaNs
> afford representations for uninitialized variables and arithmetic-like
> enhancements (such as complex-affine infinities or extremely wide range)
> that are not in the scope of this standard."

You don't need to go through serialization to put off comparison
arbitrarily long.

>> > 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.
>
> I think that this concern would have to be addressed with either empirical
> data or expertise more than I can offer. It seems that you're arguing that
> no function should ever halt execution when it encounters NaN.

I'm not making an argument; I'm saying “I don't know, and I have a
concern.”

>>> 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.
>
> In my limited experience, generally what goes wrong is that feeding NaN
> into algorithms often leads to nonsensical results. Other than simply
> displaying the result, if you want to actually use it to do interesting
> work, you end up taking decisions you do not really intend on the basis of
> those results.

...which would suggest that NaN shouldn't propagate at all. I see your
point that if nearly all the bad effects come from decisions, and decisions
are rooted in comparison, trapping comparison could be enough to prevent
it.

Anyway, I think I want to propose something much simpler based on what
Chris L. has been pressing me to think about.  

Sketch: suppose we take it as a given that == and < for all FP types
have to have IEEE level 1 semantics in all contexts?  Then the only
problematic value is NaN.  We can say it lies outside the domain of FP
Equatable/Comparable conformance.  Then we can ask how we want important
generic components (sort, min, Dictionary, etc.) to behave in the
presence of NaN and consider what they need to do in order to provide
that behavior.  These components can document their behavior w.r.t. NaN,
and if/when it emerges that there's a coherent generalization of this
NaN handling, we can standardize it in a protocol or protocol
requirements.  Until then it can remain an implementation detail of the
standard library.

I realize this doesn't force anyone to think about NaN, but that might
be a feature rather than a bug.  Note also that this direction doesn't
presume we need a ternary comparison.

I don't have time to go into this in any more detail right now (need to
focus on String work), but I wanted to sketch it here in case anyone is
inspired to carry this direction forward and see where it leads.  That
could be a huge contribution.

Cheers,

-- 
-Dave