<div dir="ltr">On Sat, Apr 22, 2017 at 6:37 PM, Dave Abrahams <span dir="ltr"><<a href="mailto:dabrahams@apple.com" target="_blank">dabrahams@apple.com</a>></span> wrote:<div><snip><br><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div class="gmail-HOEnZb"><div class="gmail-h5"><br>
>> > To be clear, this proposal promises that `[0 / 0 as Double]` will be made<br>
>> > to compare unequal with itself, yes?<br>
>><br>
>> Nope.<br>
>><br>
>> As you know, equality of arrays is implemented generically and based on<br>
>> the equatable conformance of their elements. Therefore, two arrays of<br>
>> equatable elements are equal iff the conforming implementation of<br>
>> Equatable's == is true for all elements.<br>
>><br>
>> > It is very clear that here we are working with a concrete FP type and<br>
>> > not in a generic context, and thus all IEEE FP behavior should apply.<br>
>><br>
>> I suppose that's one interpretation, but it's not the right one.<br>
>><br>
>> If this were C++, it would be different, because of the way template<br>
>> instantiation works: in a generic context like the == of Array, the<br>
>> compiler would look up the syntactically-available == for the elements<br>
>> and use that. But Swift is not like that; static lookup is done at the<br>
>> point where Array's == is compiled, and it only finds the == that's<br>
>> supplied by the Element's Equatable conformance.<br>
>><br>
>> This may sound like an argument based on implementation details of the<br>
>> language, and to some extent it is. But that is also the fundamental<br>
>> nature of the Swift language (and one for which we get many benefits),<br>
>> and it is hopeless to paper over it. For example, I can claim that all<br>
>> doubles are equal to one another:<br>
>><br>
>> 9> func == (lhs: Double, rhs: Double) -> Bool { return true }<br>
>> 10> 4.0 == 1.0<br>
>> $R2: Bool = true<br>
>> 11> [4.0] == [1.0] // so the arrays should be equal too!<br>
>> $R3: Bool = false<br>
>><br>
>> Another way to look at this is that Array is not a numeric vector, and<br>
>> won't be one no matter what you do ([1.0] + [2.0] => [1.0, 2.0]). So it<br>
>> would be wrong for you to expect it to reflect the numeric properties of<br>
>> its elements.<br>
>><br>
><br>
> I understand that's how the generic Array<T> would work, but the proposal<br>
> as written promises FP-aware versions of these functions.<br>
<br>
</div></div>Where do you see that promise? If we said or even implied that, I<br>
didn't review the text carefully enough.<br></blockquote><div><br></div><div><div>> This results in code that is explicitly designed to work with FloatingPoint types getting the expected IEEE behaviour, while code that is only designed to work with Comparable types (e.g. sort and Dictionary) gets more reasonable total ordering behaviour.</div><div><br></div><div>> To clarify: Dictionary and sort won’t somehow detect that they’re being used with FloatingPoint types and use level 1 comparisons. Instead they will unconditional[ly] use level 2 behaviour.</div><div><br></div><div>[...]</div><div><br></div><div><div>> Some free functions will have <T: FloatingPoint> overloads to better align with IEEE-754 semantics. This will be addressed in a follow-up proposal. (example: min and max)</div></div><div><br></div><div>The implication I took away is that a follow-on proposal will align a much greater swath of functions to IEEE-754 semantics. I did not realize you meant _some_ free functions also meant that _only_ free functions would be refined.</div></div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><span class="gmail-">
> That is to say, I would expect the standard library to supply an<br>
> alternative implementation of equality for Array<T where T :<br>
> FloatingPoint>.<br>
<br>
</span>And also for Dictionary? What do you expect to happen when Double is<br>
used as a dictionary key and it happens to be NaN?</blockquote><div><br></div><div>The proposal is very clear that `Dictionary` and `sort` will always use level 2 comparison. </div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div><div class="gmail-h5">
>> >> This is a bump in the rug – push it down in one place, it pops up<br>
>> >> in another. I feel like this proposal at least moves the bump to<br>
>> >> where<br>
>> fewer<br>
>> >> people will trip over it. I think it highly likely that the<br>
>> intersection of<br>
>> >> developers who understand enough about floating point to write truly<br>
>> >> correct concrete code, but won’t know about or discover the documented<br>
>> >> difference in generic code, is far smaller than the set of people who<br>
>> hit<br>
>> >> problems with the existing behavior.<br>
>> >><br>
>> ><br>
>> > So, to extend this analogy, I'd rather say that the bump is not in the<br>
>> rug<br>
>> > [Comparable] but rather in a section of the floor [FP NaN]. The rug might<br>
>> > overlie the bump, but the bump will always be there and people will find<br>
>> it<br>
>> > as they walk even if they don't immediately see it.<br>
>><br>
>> Correct.<br>
>><br>
>> > If we don't want people to trip over the bump while walking on the<br>
>> > rug, one very good alternative, IMHO, is to shape the rug so that it<br>
>> > doesn't cover the bump.<br>
>><br>
>> At what cost?<br>
>><br>
>> More specifically: why is it the right behavior, for our audience, to<br>
>> trap when Equatable comparison happens to encounter NaN? Will this not<br>
>> simply "crash" programs in the field that otherwise would have "just<br>
>> worked?"<br>
><br>
> No, as I propose it, programs in the field would be automatically migrated<br>
> to an alternative set of comparison operators `&==`, `&<`, etc. that would<br>
> work exactly as `==`, `<`, etc. do today.<br>
<br>
</div></div>Meaning, for floating point NaN &== NaN is false, and if you want to<br>
write numeric code that accounts for NaN, you use &==.<br>
<br>
OK, so... Is &== a protocol requirement, or a protocol extension, or<br>
neither? If so, to which protocol is it attached?</blockquote><div><br></div><div>Please allow me to refer you to a Gist:</div><div><a href="https://gist.github.com/xwu/e864ffdf343160a8a26839388f677768">https://gist.github.com/xwu/e864ffdf343160a8a26839388f677768</a><br></div><div><br></div><div>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 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.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><span class="gmail-"><br>
> I would quibble with the notion that all such generic algorithms<br>
> currently "just work,"<br>
<br>
</span>I never claimed they do! They don't, because Equatable.== for floating<br>
point is not an equivalence relation. That's part of what we aim to<br>
fix.<br>
<br>
You are proposing to fix that same problem a different way, one that leaves<br>
NaNs a bit out-in-the-cold (not necessarily bad), but also explicitly<br>
modifies generic algorithms so they continue to silently produce<br>
unspecified results (bad!)<br></blockquote><div><br></div><div>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.</div><div><br></div><div>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.</div><div><br></div><div>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.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><span class="gmail-">
> but the result is that they would behave exactly as they do today and<br>
> therefore would at least be no more broken.<br>
<br>
</span>If that's all we acheive, we should do nothing.<br></blockquote><div><br></div><div>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 am very disturbed by the possibility of the latter. It is the only part of this proposal that keeps me up at night.</div><div><br></div><div>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.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><span class="gmail-">
> Standard library changes to `sort` and other functions will make them<br>
> "just work" with no distinguishable difference to the end user as<br>
> compared to this proposal here.<br>
<br>
</span>I'm sorry, I don't know what "this proposal here" means. Is that yours<br>
or the one Ben and I offered? It's certainly different from the results<br>
of our proposal.<br>
<br>
The big problem with our proposal, AFAICT, is that<br>
<br>
floatsIncludingNaNs.sort()<br>
<br>
works but<br>
<br>
floatsIncludingNaNs.sort(>)<br>
<br>
does not. That is a real problem, but it *is* a difference from the<br>
current behavior, where neither one works.<br></blockquote><div><br></div><div>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:</div><div><br></div><div><a href="https://gist.github.com/xwu/e864ffdf343160a8a26839388f677768">https://gist.github.com/xwu/e864ffdf343160a8a26839388f677768</a><br></div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><span class="gmail-">
> It would be an improvement over how the algorithms work today with<br>
> NaN.<br>
><br>
> The major difference to the end user between what I propose and this<br>
> proposal here will surface when _new_ code is written that uses `==` in the<br>
> generic context, when working with types whose values may compare<br>
> unordered. Since I propose `<=>` to return a value of type `Comparison?`,<br>
> using the revised operator `==` is an assertion that the result of<br>
> comparison is not unordered. A user is welcome to use `&==` or a custom<br>
> predicate if that is not their intention.<br>
<br>
</span>The problem with this is that there's still no simple way to get an<br>
equivalence relation or a total order over all Doubles, including NaNs.<br></blockquote><div><br></div><div>There is. Given two values x and y, `x &< y || (y <=> y) == nil` is identical to the `<` that you propose.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
Now, I'm totally willing to have the discussion about how NaNs have no<br>
business being used as dictionary keys, or sort keys, or searched for,<br>
or any of the other things we do with day-to-day values. That's not<br>
something I really have an opinion on, yet.</blockquote><div><br></div><div>I would not assert that NaN has no business being used here; again, my alternative design accommodates all of these use cases.</div><div><br></div><div>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. It is not an avoidable problem--this is the bump in the rug that cannot be smoothed out.</div><div><br></div><div>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. For instance, generic `max` produces what to the average user is nonsense if NaN compares greater than everything.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">I am, however, concerned<br>
that ordinary valid computations can lead to NaN and that allowing the<br>
appearance of a NaN to turn into a trap much later in the program, where<br>
it is finally compared with something, is not a behavior that would work<br>
for ordinary users.<br>
<span class="gmail-"><br>
>> My purpose in exploring an alternative design is to see if it would be<br>
>> > feasible for non-FP-aware comparison operators to refuse to compare NaN,<br>
>> > rather than giving different answers depending on context.<br>
>><br>
>> So... to be clear, this is still different behavior based on context.<br>
>> Is this not just as confusing a result?<br>
>><br>
>> let nan = 0.0 / 0.0<br>
>> print(nan == nan) // false<br>
>> print([nan] == [nan]) // trap<br>
>><br>
>> > I now strongly believe that this may make for a design simultaneously<br>
>> > _less_ complex *and* _more_ comprehensive (as measured by the<br>
>> > flatness-of-rug metric).<br>
>><br>
>> I'm certainly willing to discuss it, but so far it doesn't seem like<br>
>> you've been willing to answer the central questions above.<br>
>><br>
><br>
> Clearly, I'm not understanding the central questions. Which ones have I<br>
> left unanswered?<br>
<br>
</span>Again:<br>
<br>
Why is it the right behavior, for our audience, to trap when Equatable<br>
<div class="gmail-HOEnZb"><div class="gmail-h5"> comparison happens to encounter NaN?<br></div></div></blockquote><div><br></div><div>There are three possibilities (that I know of) when an equatable comparison `==` encounters NaN:</div><div><br></div><div>* unspecified behavior (the current situation)</div><div>* a default behavior (as proposed by you and Ben, that would be ordering NaN after all other values)</div><div>* trapping (as proposed by me)</div><div><br></div><div>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:</div><div><br></div><div>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?</div><div><br></div><div>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.</div><div><br></div><div>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:</div><div><br></div><div>* 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.</div><div><br></div><div>* 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.</div><div><br></div><div>* 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.<br></div><div><br></div></div></div></div></div>