[swift-evolution] [pitch] Comparison Reform

[Dave Abrahams]

on Sat Apr 15 2017, Xiaodi Wu <swift-evolution at swift.org> wrote:

> On Sat, Apr 15, 2017 at 3:12 PM, Dave Abrahams via swift-evolution <
> swift-evolution at swift.org> wrote:
>
>>
>> on Thu Apr 13 2017, Xiaodi Wu <swift-evolution at swift.org> wrote:
>>
>> > Getting this sorted out is definitely a worthwhile effort. I do have
>> > thoughts about this proposal:
>> >
>> > I continue to have reservations about an identical spelling (e.g. `==`)
>> > giving two different answers with the same values of the same type,
>> > depending on the generic context. It is a very *clever* design, but it is
>> > also a very *subtle* behavior that I can see leading to much confusion
>> and
>> > befuddlement for any user who is not well versed *both* in the
>> intricacies
>> > of IEEE floating point *and* in the intricacies of Swift.
>>
>> I can't help but think that the concern over confusion here is not
>> informed by any realistic situations.  Please describe
>>
>
> To be clear, I'm not claiming that my concerns about the proposal outweigh
> my enthusiasm for it.
>
> But here, the confusion I'm concerned about stems from the essential
> conclusion by the proposal authors that types (including, but not
> necessarily only limited to FP types) which are ordinarily compared in a
> way that treats certain "special values" differently must also present an
> alternative notion of comparison that accounts for all possible
> values. 

That may be a conclusion, but it's not an assumption.  For example, it's
totally reasonable that there is a value of Int (i.e. 0) for which the
requirements of division don't hold.  We say that 0 is outside the
domain of / when used as a divisor, and we tried to get away with saying
that NaN was outside the domain of ==.  However, it's also reasonable to
trap on integer division by zero.

What we have is a situation where values that “misbehave” when given
IEEE semantics occur in normal code and are expected to interoperate
with other floating point values under normal circumstances (such as
when sorting), and not only interoperate but give reasonable results.

Now, having thought about this a bit more myself, here is a real case
where confusion might occur:

  if values.contains(.NaN) {
    print(values.filter { $0 != .NaN }) // Surprise, NaN is printed!
  }

I find this result truly loathsome, but it seems to me that the only
reasonable cure is giving == equivalence relation semantics under all
circumstances.

> The special casing of certain values already makes comparison
> operations difficult to understand; I guess I'm simply stating what is
> unavoidably true, that having a "non-special-cased" comparison *in
> addition* to that adds additional difficulty.

Yup.

> One example where this comes to mind is this: `XCTAssertEqual(+0.0, -0.0)`
> will pass or fail depending on whether XCTAssertEqual provides a
> FP-specific specialization. This is something that cannot be determined by
> reading the testing code itself: that is, it requires not merely knowledge
> about whether or not the call site "knows" that it's operating on a FP
> type, but also knowledge about whether XCTest itself is FP-aware.

Yep.

> The issue increases in difficulty when it comes to non-stdlib types.
> Suppose I were to write a Rational type. (I am writing a Rational type, but
> we can talk about that later.) This Rational type is capable of
> representing NaN (`(0 / 0 as Rational<Int>).isNaN == true`) and, for
> consistency with FP types, `Rational<Int>.nan != Rational<Int>.nan`. 

Hey, it's your funeral! ;-)

> If this proposal is implemented, *I* would be responsible for making
> XCTest Rational-aware, vending `XCTAssertEqual<Rational<T>>(_:_:)`. 

Now you're mixing apples and oranges with NaN and +/-0, the latter of
which doesn't apply to rationals.  The way you make XCTest aware of NaN
is to do the same thing that floating point did: vend the static version
of == separately from the dynamic version, using @_implements (and get
us to drop the underscore).

XCTestAssertEqual is a perfect example of a generic function: it is (or
should be!) concerned with verifying that results match expectations,
not that “==” behaves according to the specific quirks of a type.
Anything else would make

   XCTestAssertEqual(resultOfComputation, NaN)

meaningless.

> In fact, to ensure that users of Rational get the expected behavior
> everywhere, I would have to vend special Rational-aware versions of
> every stdlib, core library, and _third-party_ function that is
> FP-aware, which it is not possible to do.

I'm sorry, I don't follow.  Give me an example, please, and also clearly
define “FP-awareness.”

>> Actually, the fact that this behavior cannot even be achieved without
>> > currently non-existent compiler features means that it is not possible
>> > to understand what's truly going on without reading *this document*,
>>
>> This doesn't seem like a reasonable argument.  New compiler features get
>> documented outside of the proposals they come from.  Nobody's going to
>> have to go read a proposal to understand what @implements means.
>
> I do not mean that I seriously believe @_implements will never be
> documented. (Although, as an underscored attribute, it does not need to be
> documented outside of the apple/swift repo, in the same way that
> @_transparent and its ilk are not documented outside the repo.) 

Either way, we either end up documenting @_implements or special magic
behavior for floating point types.  Somebody already needs to document
the latter for floating point types (.NaN != .NaN), frankly, even though IEEE is a
commonly implemented standard.

> I am simply saying that fully understanding how `Comparable` and
> `FloatingPoint` interact with each other will require learning one
> additional advanced feature of the language than is required now, 

Agreed, it will require learning something new.

> and that this feature does not even currently exist.

I don't understand the relevance of that last point though.

>
>
>> > after mastering *both* IEEE floating point *and* Swift
>> > generics/protocols/extensions/static vs. dynamic dispatch. All to use
>> > `==` correctly.
>>
>> I don't understand this argument.  The *whole* point of this proposal is
>> that you use `==` correctly *without* the need for any special knowledge.
>>
>> > Which is to say, most people will simply not even know if they happen
>> > to be using the `==` they did not intend to use.
>>
>> Most people aren't aware that IEEE comparison is quirky and don't know
>> what they intend with respect to those semantics, but anyone who *is*
>> aware of his intention has an easy way to understand what's happening.
>> Does this code know it's operating on floating point numbers?  If so,
>> it's IEEE.  If not, it's an equivalence relation.
>>
>> > I think consideration should be given to a design that achieves a
>> > user-facing but not onerous differentiation between level 1 and level 2
>> > equality. However, the only one I can think of is essentially a different
>> > shade of the `PartiallyComparable` alternative already outlined in the
>> > document.
>>
>> I am *deeply* opposed to such a protocol.  It is purely syntactic in
>> nature and thus useless for correctly constraining generic algorithms.
>
> But there do exist types for which some pairs of values cannot be compared
> to each other. A generic algorithm that blows up if a value cannot be
> compared to another value should not operate on such types, no?

I don't know what you mean by “blows up.” If you mean, “traps,” I think
that's fine.  If you mean, “misbehaves,” I think that's really hard to
justify unless it's easy for users to keep these values from ever
entering their program.  The algorithm itself doesn't know all the types
on which it can operate, so its documentation isn't in a position to
warn users about this precondition.  Therefore, the caller, who got the
values from somewhere and may be generic itself, is in no position to
check for the problem.  The only cure is to bottleneck production of
values of that type and ensure that those values never get beyond some
boundary in the code.  I don't think that's practical in the case of
floating point, not least because ordinary operations on legit values
can produce the problematic values.

>> People will use it anyway, resulting in algorithms that statically
>> accept, but are incorrect for, floating point.  In my opinion there's
>> only one feasible answer that doesn't use the static/dynamic distinction
>> we've proposed: throw IEEE semantics under the bus, making it available
>> only under a different syntax.
>>
>> This would be a drastic move whose primary downside is that floating
>> point code ported from C would need to be carefully audited and may
>> become less easy to read.  But at least it would be viable.
>>
>
> Yes I agree that it would be a much more drastic move that would make
> Swift difficult to use for numerics, and I, at least, would not want
> to go down that road.

I'd rather not, myself.  The choices are not good:

1. Complexity and occasional surprises that can be documented and 
   explained.
2. Silent misbehavior.
3. Separate syntax for distinct semantics.

#2 is the only one I find completely unacceptable.

>> > Yet I cannot help but think that the rejected alternative may be
>> > advantageous in one key aspect. `FloatingPoint` comparison is in a
>> > sense "less refined" (not exactly precise language, I know) than the
>> > level 2 ordering proposed here, at least in the sense that the latter
>> > offers more semantic guarantees about the relationships between
>> > comparison operators.
>>
>> No, they are effectively refinement siblings.  If it was a hierarchical
>> relationship, we could just make the floating point types conform to
>> Equatable.  But floating point types are *required* by IEEE to have
>> comparison semantics that conflict with Equatable.
>>
>> > It's weird that the less refined `FloatingPoint` refines the more
>> > refined `Comparable`,
>>
>> Do you want to be able to sort floating point numbers without providing
>> a comparison predicate (one that has to be spelled less obviously than
>> "<")?  If so, floating point numbers must be Comparable.  If not, we
>> could talk about breaking this refinement relationship.
>>
>> > and I think the acrobatics with compiler support illustrate how the
>> > design is actively working against Swift's overarching direction.
>>
>> It's not more acrobatic than things we already do in the standard
>> library to ensure that people transparently see the right behavior (see
>> .lazy), and we could probably even find ways to do it without language
>> features.  It would be less principled, harder to understand, and more
>> fragile than designing a language feature that addresses the need
>> directly.
>
> I have an incipient idea. It begins with:
>
> enum ComparisonResult {
>   case orderedAscending, orderedSame, orderedDescending, unordered
> }
>
> I am sure there is something I am missing which makes this design a
> horrible idea, but I'm interested in hearing them.

It's not a horrible idea, but to be fair it's not really a design yet,
either.  You haven't said anything about what it's supposed to mean, how
it is supposed to be used, how people write, use, and compose generic
algorithms with it, how it deals with floating point, etc.

-- 
-Dave