[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 10:32 PM, Dave Abrahams via swift-evolution <
> swift-evolution at swift.org> wrote:
>
>>
>> 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.
>
> Hmm, I will admit I have not tried it because I have always assumed that
> the assertion above is meaningless, and that it ought to be.

Why ought it be meaningless?

> `XCTAssertTrue(resultOfComputation.isNaN)` is the way I've been
> testing my NaN's.
>
>> 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.”
>
> By FP awareness, I mean that in comparing two FP values a function uses
> `FloatingPoint.==` as opposed to `Comparable.==`. 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.

I don't see how you're going to avoid that anyway.  A generic function
constrained to FloatingPoint or written for a concrete FP type like
Double is never going to accept your Rational number.  The only context
in which it can accept a Rational number without intervention on your
part is where the is treating that number as Equatable... and thus
depending on == being an equivalence relation.  In those cases, of
course == needs to have equivalence relation semantics.

>> >> > 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.
>
> Not critical to the argument. Just that it will impact all users of Swift.
> It's not as though some particularly studious user of Swift 3 will be
> rewarded with a head start because he or she has devoted time to careful
> study of the language.

I still don't follow, but maybe we should let it go since you say it's
not critical.

>> >
>> >> > 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.
>>
>
> I've evolved my thinking based on the discussion. Let's see:
>
> ```
> public enum ComparisonResult : Equatable {
>   case orderedAscending, equivalent, orderedDescending, unordered
>   // I have renamed one case, in the hopes of emphasizing that two values
>   // that compare `equivalent` are not merely ordered the same, but should
>   // satisfy the three conditions of an equivalence relation.
> }
> // I will have to leave the question of how to bridge from Obj-C
> // NSComparisonResult up to more capable hands.
>
> public protocol Comparable : Equatable {
>   func compared(to other: Self) -> ComparisonResult
> }
> // This will have to be modified as necessarily to support compiler magic
> // necessary for source-compatibility with Swift 3
>
> extension Comparable {
>   public static func == (lhs: Self, rhs: Self) -> Bool {
>     let comparison = lhs.compared(to: rhs)
>     precondition(comparison != .unordered)
>     return comparison == .equivalent
>   }
>
>   public static func < (lhs: Self, rhs: Self) -> Bool {
>     let comparison = lhs.compared(to: rhs)
>     precondition(comparison != .unordered)
>     return comparison == .orderedAscending
>   }
>   // etc.
>
>   // Something I thought I'd never want to see, but on reflection not
> terrible:
>   public static func &== (lhs: Self, rhs: Self) -> Bool {
>     return lhs.compared(to: rhs) == .equivalent
>   }
>
>   public static func &< (lhs: Self, rhs: Self) -> Bool {
>     return lhs.compared(to: rhs) == .orderedAscending
>   }
>   // etc.
> }
>
> extension FloatingPoint : Comparable {
>   public func compared(to other: Self) -> ComparisonResult {
>     if isNaN || other.isNaN { return .unordered }
>     if isLess(than: other) { return .orderedAscending }
>     if other.isLess(than: self) { return .orderedDescending }
>
>     // On reconsideration, probably actually least surprising if +0.0 ==
> -0.0
>     // no matter what. It does not matter that division can give different
>     // results for two equivalent values, only that the three rules of an
>     // equivalence relation will hold, and it does.
>     //
>     // If a user is really savvy to the sign of zero, there is
> FloatingPoint.sign,
>     // which is necessary in any case for working with FP operations that
>     // distinguish between +0 and -0. I can't think of a generic algorithm
> over
>     // all Comparable types that could make use of the distinction between
> +0
>     // and -0.
>     return .equivalent
>   }
> }
> ```
>
> In this design, `==`, `<`, etc. correspond to IEEE "signaling" operators,
> while `&==`, `&<`, etc. correspond to C-style operators, which IEEE calls
> "quiet" and actually notates using "?==", "?<", etc.

It's interesting, but what's missing here is a description of the user
model.  How do users program with this design?  What should my
expectations be w.r.t. generic algorithms like sort() and floating point
numbers, particularly NaN?  If, as I suspect, sorting a collection
containing NaN is going to trap (unless the collection has only one
element?), why is that the right behavior?

-- 
-Dave