[swift-evolution] [pitch] Comparison Reform

[Dave Abrahams]

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

> On Sat, Apr 22, 2017 at 4:14 PM, Dave Abrahams <dabrahams at apple.com> wrote:
>
>>
>> on Tue Apr 18 2017, Xiaodi Wu <xiaodi.wu-AT-gmail.com> wrote:
>>
>> > On Tue, Apr 18, 2017 at 10:40 AM, Ben Cohen via swift-evolution <
>> > swift-evolution at swift.org> wrote:
>> >
>> >>
>> >> On Apr 17, 2017, at 9:40 PM, Chris Lattner via swift-evolution <
>> >> swift-evolution at swift.org> wrote:
>> >>
>> >>
>> >> On Apr 17, 2017, at 9:07 AM, Joe Groff via swift-evolution <
>> >> swift-evolution at swift.org> wrote:
>> >>
>> >>
>> >> On Apr 15, 2017, at 9:49 PM, Xiaodi Wu via swift-evolution <
>> >> swift-evolution at swift.org> wrote:
>> >>
>> >> For example, I expect `XCTAssertEqual<T : FloatingPoint>(_:_:)` to be
>> >> vended as part of XCTest, in order to make sure that `XCTAssertEqual(
>> resultOfComputation,
>> >> Double.nan)` always fails.
>> >>
>> >>
>> >> Unit tests strike me as an example of where you really *don't* want
>> level
>> >> 1 comparison semantics. If I'm testing the output of an FP operation, I
>> >> want to be able to test that it produces nan when I expect it to, or
>> that
>> >> it produces the right zero.
>> >>
>> >>
>> >> I find it very concerning that == will have different results based on
>> >> concrete vs generic type parameters.  This can only lead to significant
>> >> confusion down the road.  I’m highly concerned about situations where
>> >> taking a concrete algorithm and generalizing it (with generics) will
>> change
>> >> its behavior.
>> >>
>> >>
>> >> It is already the case that you can start with a concrete algorithm,
>> >> generalize it, and get confusing results – just with a different
>> starting
>> >> point. If you start with a concrete algorithm on Int, then generalize
>> it to
>> >> all Equatable types, then your algorithm will have unexpected behavior
>> for
>> >> floats, because these standard library types fail to follow the rules
>> >> explicitly laid out for conforming to Equatable.
>> >>
>> >> This is bad. Developers need to be able to rely on those rules. The
>> >> standard library certainly does:
>> >>
>> >> let a: [Double] = [(0/0)]
>> >> var b = a
>> >>
>> >> // true, because fast path buffer pointer comparison:
>> >> a == b
>> >>
>> >> b.reserveCapacity(10) // force a reallocation
>> >>
>> >> // now false, because memberwise comparison and nan != nan,
>> >> // violating the reflexivity requirement of Equatable:
>> >> a == b
>> >>
>> >>
>> >> Maybe we could go through and special-case all the places in the
>> standard
>> >> library that rely on this, accounting for the floating point behavior
>> >> (possibly reducing performance as a result). But we shouldn't expect
>> users
>> >> to.
>> >>
>> >
>> > I was not thinking about the issue illustrated above, but this is
>> > definitely problematic to me.
>> >
>> > To be clear, this proposal promises that `[0 / 0 as Double]` will be made
>> > to compare unequal with itself, yes?
>>
>> Nope.
>>
>> As you know, equality of arrays is implemented generically and based on
>> the equatable conformance of their elements.  Therefore, two arrays of
>> equatable elements are equal iff the conforming implementation of
>> Equatable's == is true for all elements.
>>
>> > It is very clear that here we are working with a concrete FP type and
>> > not in a generic context, and thus all IEEE FP behavior should apply.
>>
>> I suppose that's one interpretation, but it's not the right one.
>>
>> If this were C++, it would be different, because of the way template
>> instantiation works: in a generic context like the == of Array, the
>> compiler would look up the syntactically-available == for the elements
>> and use that.  But Swift is not like that; static lookup is done at the
>> point where Array's == is compiled, and it only finds the == that's
>> supplied by the Element's Equatable conformance.
>>
>> This may sound like an argument based on implementation details of the
>> language, and to some extent it is.  But that is also the fundamental
>> nature of the Swift language (and one for which we get many benefits),
>> and it is hopeless to paper over it.  For example, I can claim that all
>> doubles are equal to one another:
>>
>>   9> func == (lhs: Double, rhs: Double) -> Bool { return true }
>>  10> 4.0 == 1.0
>> $R2: Bool = true
>>  11> [4.0] == [1.0]  // so the arrays should be equal too!
>> $R3: Bool = false
>>
>> Another way to look at this is that Array is not a numeric vector, and
>> won't be one no matter what you do ([1.0] + [2.0] => [1.0, 2.0]).  So it
>> would be wrong for you to expect it to reflect the numeric properties of
>> its elements.
>>
>
> I understand that's how the generic Array<T> would work, but the proposal
> as written promises FP-aware versions of these functions. 

Where do you see that promise?  If we said or even implied that, I
didn't review the text carefully enough.

> 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?

>> >> 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?

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

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

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

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

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

>> 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?

-- 
-Dave