[pitch] Comparison Reform

The thing that’s bad about it is that we silently pick different operators for different contexts. With Swift’s heavy use of abstraction layering, you often can’t really tell what the context is (if it even has meaning at all).

I’ve been thinking about Swift architectural patterns, and one pattern that I think of as being a good fit for the language is this idea of wrapping operations on protocol-types as generic structs (for example, the way we do FilterCollection, LazyMapCollection, and he various String views in the standard library), providing transformed “views” of the object with a common base protocol (which will hopefully get optimised away). I wonder if we couldn’t apply a similar idea here…

So basically, every FloatingPoint will expose another pseudo-FloatingPoint type which differs from its base object only in its interpretation of “Comparable” operators. The type-system would enforce that you are comparing them consistently.

protocol FloatingPoint: Comparable {

    /// A FloatingPoint with comparison quirks
    ///
    associatedtype StandardComparable: FloatingPoint
    var comparable: StandardComparable { get }

    /// A FloatingPoint which compares according to IEEE level <whatever>
    ///
    associatedtype IEEEComparable: FloatingPoint = Self
    var ieeeComparable: IEEEComparable { get }
}
extension FloatingPoint where IEEEComparable == Self {
    var ieeeComparable: Self { return self }
}

struct Float: FloatingPoint {
   /* IEEE comparison */
   static func compare(_: Float, to: Float) -> ComparisonResult { ... }

   /* Quirky Float where .Nan == .Nan, +0.0 == -0.0 etc... */
   struct StandardComparable: FloatingPoint {
     static func compare(_: StandardComparable, to: StandardComparable) -> ComparisonResult { ... }
   }
   var comparable: StandardComparable { return StandardComparable(self) }
}

The idea is that the invisible context-sensitive comparison quirks would become visible:

if values.contains(.NaN) { // uses IEEE rules, so is always false
    print(values.filter { $0 != .NaN })
}

if values.contains(where: { $0.comparable == .NaN }) { // opt-in to stdlib quirks
    print(values.filter { $0.comparable != .NaN }) // no NaNs
}

- Karl

···

On 16 Apr 2017, at 05:32, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:

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

On Sat, Apr 15, 2017 at 3:12 PM, Dave Abrahams via swift-evolution < >> swift-evolution@swift.org> wrote:

on Thu Apr 13 2017, Xiaodi Wu <swift-evolution@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.

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

···

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

On Sat, Apr 15, 2017 at 10:32 PM, Dave Abrahams via swift-evolution < > swift-evolution@swift.org> wrote:

on Sat Apr 15 2017, Xiaodi Wu <swift-evolution@swift.org> wrote:
> On Sat, Apr 15, 2017 at 3:12 PM, Dave Abrahams via swift-evolution < >> > swift-evolution@swift.org> wrote:
>> on Thu Apr 13 2017, Xiaodi Wu <swift-evolution@swift.org> wrote:

--
-Dave

Another option is to make a new type, not sure what to call it but I’ll use “Num” for now, that is essentially the same as Double except it does not represent NaN. After all, why should a numeric type ever be “not a number”,

Division by 0, incrementing past the largest representable value, probably a couple others that I'm not thinking of.

and what sort of name is “Double” anyway except as a hold-over from legacy standards?

FWIW, I suggested something like that ("Float"->"Float32", "Double"->"Float64", and typealias the largest CPU-native type to just "Float") a while back and the consensus was that we wanted to preserve the current notation.

- Dave Sweeris

···

On Apr 16, 2017, at 09:56, Nevin Brackett-Rozinsky via swift-evolution <swift-evolution@swift.org> wrote:

I agree with the rest of what you said, but I have to disagree on this point. What I think he is saying is that, in Swift, we really should be representing the NaN case as an optional instead of a magic value on the type itself (similar to how swift uses an optional instead of NSNotFound).

In fact, that might be an actual option here. For ‘Double?’ the compiler could use the bit pattern for NaN internally to represent .none (I believe it does similar tricks to save space with other optional types). Then disallow reference to NaN within swift code. Functions or operations which could produce NaN would either have to produce an optional or trap in case of NaN. (e.g. the trig functions would likely return an optional, and 0/0 would trap).

I think it would actually lead to much better code because the compiler would force you to have to explicitly deal with the case of optional/NaN when it is possible. Migration would be tricky though...

Thanks,
Jon

···

On Apr 16, 2017, at 10:42 AM, Xiaodi Wu via swift-evolution <swift-evolution@swift.org> wrote:

The point is that, when you manipulate two real numbers, sometimes there is no numeric result. You cannot simply wish this away with a new numeric type because it is not an artifact of _modeling_ real numbers but rather intrinsic to mathematics itself.

I've spent some time fleshing out this idea:

···

On Sun, Apr 16, 2017 at 1:13 AM, Dave Abrahams via swift-evolution < swift-evolution@swift.org> wrote:

<snip>

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

>
> Another option is to make a new type, not sure what to call it but I’ll
use “Num” for now, that is essentially the same as Double except it does
not represent NaN. After all, why should a numeric type ever be “not a
number”,

Division by 0, incrementing past the largest representable value, probably
a couple others that I'm not thinking of.

Those are reasons for integers to overflow.

Floating point values become NaN when you try to compute 0/0, when you try
to subtract infinity from itself, and when you try to multiply 0 and
infinity. There are also various trigonometric and hyperbolic functions
that are expected to emit NaN for various reasons, and for complex numbers
these reasons multiply (haha).

The point is that, when you manipulate two real numbers, sometimes there is
no numeric result. You cannot simply wish this away with a new numeric type
because it is not an artifact of _modeling_ real numbers but rather
intrinsic to mathematics itself.

···

On Sun, Apr 16, 2017 at 12:30 PM, David Sweeris via swift-evolution < swift-evolution@swift.org> wrote:

> On Apr 16, 2017, at 09:56, Nevin Brackett-Rozinsky via swift-evolution < > swift-evolution@swift.org> wrote:

and what sort of name is “Double” anyway except as a hold-over from
legacy standards?

FWIW, I suggested something like that ("Float"->"Float32",
"Double"->"Float64", and typealias the largest CPU-native type to just
"Float") a while back and the consensus was that we wanted to preserve the
current notation.

- Dave Sweeris
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

One benefit of the idea of using comparison metrics instead of changing comparable, is that you could just have two metrics on double. The default one which is closer to what we have now (or the new thing Xiaodi suggested with trapping NaN), and one which matches IEEE. You could in fact make a metric for each level if desired.

Right, but I'm arguing that having multiple comparison metrics is _undesirable_. I see the need for one design that can accommodate unordered comparisons. I do not see the need for a second comparison metric.

That is why there is a default metric. For most uses, what you suggest (i.e. trapping on NaN) makes sense, and that would be the default. Someone may have a need to compare in a way which differentiates NaN or matches a different IEEE level, and they can create a metric that provides that comparison, and still be able to use it with all of the algorithms in the standard library. (Note: I see those alternate metrics as living in a library as opposed to the standard library)

FloatingPoint already exposes IEEE total ordering as `isTotallyOrdered`. You can use it in `sort(by:)`. That's not what I'm talking about.

This proposal is about the design of `Comparable`. My concern is about `<` giving different answers depending on surrounding code. I don't see the point of it. Do you?

I agree that ‘<‘ should be consistent.

It is clear that we will need multiple comparison metrics for some types (e.g. Case/Diacritic insensitive compare), and I am suggesting we formalize that so we don’t end up with a bunch of random ‘compare(with: optionA: optionB:)’ functions which are incompatible across types.

Since the String overhaul is not done, and since localized comparison has been explicitly deferred from even the current scope of the String overhaul, I don't see how we can design around this with any sort of insight.

The point is to architect away the need to know specifics ahead of time. This should work regardless of how those end up being implemented.

In any case, again, I'm speaking specifically about the proposed design of `Comparable`. Do you think that there are meaningful generic algorithms to be written over localized string comparison and floating point comparison which are not possible today, which requires a redesign of `Comparable`?

  sort(.ascending, using: metric) //This is defined on collection, but works with case sensitive or insensitive, diacritics, IEEE ordering, etc… It basically works for all options

It would also be fairly easy to combine with the new key paths to create composable sort descriptors.

Note: If you look at my design again, you will notice it isn’t really a redesign of Comparable. Instead, it mainly adds a new protocol defining a comparison metric. Compare is left alone except for gaining a defaultMetric property (which has a default implementation that calls ‘<‘ & ‘==‘). It also gains a couple of convenience methods (and convenience operator '<=>’) which can be added post-hoc. All Swift 3 code would continue working unaltered. It simply gives the option of extra efficiency and flexibility when desired.

Thanks,
Jon

···

On Apr 16, 2017, at 11:52 AM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:
On Sun, Apr 16, 2017 at 12:58 PM, Jonathan Hull <jhull@gbis.com <mailto:jhull@gbis.com>> wrote:

On Apr 16, 2017, at 10:45 AM, Xiaodi Wu <xiaodi.wu@gmail.com <mailto:xiaodi.wu@gmail.com>> wrote:
On Sun, Apr 16, 2017 at 12:35 PM, Jonathan Hull via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

On Apr 13, 2017, at 8:30 PM, Jonathan Hull via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

One more thought. I am generally in favor of this proposal, but since it is in the pitch stage, I wanted to offer an alternative approach that I didn’t see mentioned. Food for thought/discussion.

What if, instead of repurposing comparable (and adding new functions for options like case insensitive compare), we define a comparison metric (with all of the options built in) and then use that to get our comparison result. Comparable things would have a default metric that uses ‘<‘ and ‘==‘ to provide a comparison result.

The metric would have a method which takes two things and returns a ComparisonResult. The two things would usually be the same type, but wouldn’t necessarily have to be.

As a convenience, any type could have a compared(to:, using:) method where you pass a comparison metric to the using parameter and receive a ComparisonResult. Comparable things could add a compared(with:) method and the spaceship operator <=>, which both use the default metric.

Pros:
• Would work without compiler alterations
• You can create metrics that compare items of different types
• Can setup the metric once for algorithms/comparisons with high setup cost
• Things like 'compare(to: other, using: .caseInsensitiveComparison)' fall out of the design without having to create/learn various different versions of compare on different types.
• Spaceship operator <=> for those who want it
• In some cases, it can provide a much more efficient implementation based on underlying structure. For example, you can get a metric from String/Unicode which is optimized for a particular view of that string (say ASCII). Depending on the case, when one of the objects doesn’t match the optimized type, it can either convert or fallback to a more general algorithm… but it should provide a pretty big win when most of the objects have a known structure.

Cons:
• More protocols defined by the design
• Requires an extra struct/class to implement in non-standard cases (e.g. case insensitive compare)
• Probably something else I am missing

Thanks,
Jon

On Apr 13, 2017, at 1:24 PM, Ben Cohen via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Online copy here:

https://github.com/airspeedswift/swift-evolution/blob/fa007138a54895e94d22e053122ca24ffa0b2eeb/proposals/NNNN-ComparisonReform.md

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

Another option is to make a new type, not sure what to call it but I’ll use
“Num” for now, that is essentially the same as Double except it does not
represent NaN. After all, why should a numeric type ever be “not a number”,
and what sort of name is “Double” anyway except as a hold-over from legacy
standards?

Then people who really need IEEE semantics can keep using Double with all
its quirks. But everyone else who just wants a floating-point value can use
Num, and if they need to represent NaN they can use an Optional<Num>.
Operations which would produce NaN on Double will simply trap when done on
Num.

Nevin

The point is that, when you manipulate two real numbers, sometimes there
is no numeric result. You cannot simply wish this away with a new numeric
type because it is not an artifact of _modeling_ real numbers but rather
intrinsic to mathematics itself.

I agree with the rest of what you said, but I have to disagree on this
point. What I think he is saying is that, in Swift, we really should be
representing the NaN case as an optional instead of a magic value on the
type itself (similar to how swift uses an optional instead of NSNotFound).

In fact, that might be an actual option here. For ‘Double?’ the compiler
could use the bit pattern for NaN internally to represent .none (I believe
it does similar tricks to save space with other optional types). Then
disallow reference to NaN within swift code. Functions or operations which
could produce NaN would either have to produce an optional or trap in case
of NaN. (e.g. the trig functions would likely return an optional, and 0/0
would trap).

I think it would actually lead to much better code because the compiler
would force you to have to explicitly deal with the case of optional/NaN
when it is possible. Migration would be tricky though...

This is essentially a cosmetic renaming from `Double` to `Double?`. There
are rules for propagating NaN which numeric algorithms expect. For example,
`cos(.nan)` returns a value. If your design is to work, every function that
takes a `Double` will need to take a `Double?`.

Just as Swift String conforms to Unicode standards, FloatingPoint conforms
to IEEE standards. You'd have to come up with enormous benefits to justify
breaking that. Doing so for Swift 4 is plainly a non-starter.

Thanks,

···

On Sun, Apr 16, 2017 at 1:14 PM, Jonathan Hull <jhull@gbis.com> wrote:

On Apr 16, 2017, at 10:42 AM, Xiaodi Wu via swift-evolution < > swift-evolution@swift.org> wrote:
Jon

One benefit of the idea of using comparison metrics instead of changing
comparable, is that you could just have two metrics on double. The default
one which is closer to what we have now (or the new thing Xiaodi suggested
with trapping NaN), and one which matches IEEE. You could in fact make a
metric for each level if desired.

Right, but I'm arguing that having multiple comparison metrics is
_undesirable_. I see the need for one design that can accommodate unordered
comparisons. I do not see the need for a second comparison metric.

That is why there is a default metric. For most uses, what you suggest
(i.e. trapping on NaN) makes sense, and that would be the default. Someone
may have a need to compare in a way which differentiates NaN or matches a
different IEEE level, and they can create a metric that provides that
comparison, and still be able to use it with all of the algorithms in the
standard library. (Note: I see those alternate metrics as living in a
library as opposed to the standard library)

FloatingPoint already exposes IEEE total ordering as `isTotallyOrdered`.
You can use it in `sort(by:)`. That's not what I'm talking about.

This proposal is about the design of `Comparable`. My concern is about `<`
giving different answers depending on surrounding code. I don't see the
point of it. Do you?

I agree that ‘<‘ should be consistent.

It is clear that we will need multiple comparison metrics for some types

(e.g. Case/Diacritic insensitive compare), and I am suggesting we formalize
that so we don’t end up with a bunch of random ‘compare(with: optionA:
optionB:)’ functions which are incompatible across types.

Since the String overhaul is not done, and since localized comparison has
been explicitly deferred from even the current scope of the String
overhaul, I don't see how we can design around this with any sort of
insight.

The point is to architect away the need to know specifics ahead of time.
This should work regardless of how those end up being implemented.

In any case, again, I'm speaking specifically about the proposed design of
`Comparable`. Do you think that there are meaningful generic algorithms to
be written over localized string comparison and floating point comparison
which are not possible today, which requires a redesign of `Comparable`?

sort(.ascending, using: metric) //This is defined on collection, but
works with case sensitive or insensitive, diacritics, IEEE ordering, etc…
It basically works for all options

We already have `sort(by:)`, and if it eventually takes a `(_:_:) ->
Comparison` as predicate, then it naturally should take a sort order as the
first argument. The only difference from what you write above is that the
label is `by` and not `using`. Not only do I not have a problem with such a
function, I think this falls into the "it goes without saying" category of
changes.

It would also be fairly easy to combine with the new key paths to create

composable sort descriptors.

Note: If you look at my design again, you will notice it isn’t really a
redesign of Comparable. Instead, it mainly adds a new protocol defining a
comparison metric. Compare is left alone except for gaining a
defaultMetric property (which has a default implementation that calls ‘<‘ &
‘==‘). It also gains a couple of convenience methods (and convenience
operator '<=>’) which can be added post-hoc. All Swift 3 code would
continue working unaltered. It simply gives the option of extra efficiency
and flexibility when desired.

Then I don't think we're talking about the same thing. The problem is that
the current Comparable protocol has conforming types which do not implement
`<` suitable for stable sorting or other generic functions over Comparable,
and the current Comparable does not require them to. The purpose of this
pitch, and the purpose of the alternatives I'm talking about, is precisely
to reform Comparable itself. By its nature it is incompatible with _all_
Swift 3 code working unaltered, and the question is how much and when
alternations should be necessary.

Thanks,

···

On Sun, Apr 16, 2017 at 2:45 PM, Jonathan Hull <jhull@gbis.com> wrote:

On Apr 16, 2017, at 11:52 AM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:
On Sun, Apr 16, 2017 at 12:58 PM, Jonathan Hull <jhull@gbis.com> wrote:

On Apr 16, 2017, at 10:45 AM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:
On Sun, Apr 16, 2017 at 12:35 PM, Jonathan Hull via swift-evolution < >> swift-evolution@swift.org> wrote:

Jon

On Apr 13, 2017, at 8:30 PM, Jonathan Hull via swift-evolution < >>> swift-evolution@swift.org> wrote:

One more thought. I am generally in favor of this proposal, but since
it is in the pitch stage, I wanted to offer an alternative approach that I
didn’t see mentioned. Food for thought/discussion.

What if, instead of repurposing comparable (and adding new functions for
options like case insensitive compare), we define a comparison metric (with
all of the options built in) and then use that to get our comparison
result. Comparable things would have a default metric that uses ‘<‘ and
‘==‘ to provide a comparison result.

The metric would have a method which takes two things and returns a
ComparisonResult. The two things would usually be the same type, but
wouldn’t necessarily have to be.

As a convenience, any type could have a compared(to:, using:) method
where you pass a comparison metric to the using parameter and receive a
ComparisonResult. Comparable things could add a compared(with:) method and
the spaceship operator <=>, which both use the default metric.

Pros:
• Would work without compiler alterations
• You can create metrics that compare items of different types
• Can setup the metric once for algorithms/comparisons with high setup
cost
• Things like 'compare(to: other, using: .caseInsensitiveComparison)'
fall out of the design without having to create/learn various different
versions of compare on different types.
• Spaceship operator <=> for those who want it
• In some cases, it can provide a much more efficient implementation
based on underlying structure. For example, you can get a metric from
String/Unicode which is optimized for a particular view of that string (say
ASCII). Depending on the case, when one of the objects doesn’t match the
optimized type, it can either convert or fallback to a more general
algorithm… but it should provide a pretty big win when most of the objects
have a known structure.

Cons:
• More protocols defined by the design
• Requires an extra struct/class to implement in non-standard cases
(e.g. case insensitive compare)
• Probably something else I am missing

Thanks,
Jon

On Apr 13, 2017, at 1:24 PM, Ben Cohen via swift-evolution < >>> swift-evolution@swift.org> wrote:

Online copy here:

GitHub - airspeedswift/swift-evolution at fa007138a54895e94d22e053122ca24ffa0b2eeb
38a54895e94d22e053122ca24ffa0b2eeb/proposals/NNNN-ComparisonReform.md

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Oh, and:

Float.StandardComparable.IEEEComparable = Float, and
Float.StandardComparable.StandardComparable = Self

...so they wouldn’t recurse. You could just flip between views with “.comparable” or “.ieeeComparable”.

- Karl

···

On 16 Apr 2017, at 18:35, Karl Wagner <karl.swift@springsup.com> wrote:

On 16 Apr 2017, at 05:32, Dave Abrahams via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

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

On Sat, Apr 15, 2017 at 3:12 PM, Dave Abrahams via swift-evolution < >>> swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

on Thu Apr 13 2017, Xiaodi Wu <swift-evolution@swift.org <mailto:swift-evolution@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 thing that’s bad about it is that we silently pick different operators for different contexts. With Swift’s heavy use of abstraction layering, you often can’t really tell what the context is (if it even has meaning at all).

I’ve been thinking about Swift architectural patterns, and one pattern that I think of as being a good fit for the language is this idea of wrapping operations on protocol-types as generic structs (for example, the way we do FilterCollection, LazyMapCollection, and he various String views in the standard library), providing transformed “views” of the object with a common base protocol (which will hopefully get optimised away). I wonder if we couldn’t apply a similar idea here…

So basically, every FloatingPoint will expose another pseudo-FloatingPoint type which differs from its base object only in its interpretation of “Comparable” operators. The type-system would enforce that you are comparing them consistently.

protocol FloatingPoint: Comparable {

    /// A FloatingPoint with comparison quirks
    ///
    associatedtype StandardComparable: FloatingPoint
    var comparable: StandardComparable { get }

    /// A FloatingPoint which compares according to IEEE level <whatever>
    ///
    associatedtype IEEEComparable: FloatingPoint = Self
    var ieeeComparable: IEEEComparable { get }
}
extension FloatingPoint where IEEEComparable == Self {
    var ieeeComparable: Self { return self }
}

struct Float: FloatingPoint {
   /* IEEE comparison */
   static func compare(_: Float, to: Float) -> ComparisonResult { ... }

   /* Quirky Float where .Nan == .Nan, +0.0 == -0.0 etc... */
   struct StandardComparable: FloatingPoint {
     static func compare(_: StandardComparable, to: StandardComparable) -> ComparisonResult { ... }
   }
   var comparable: StandardComparable { return StandardComparable(self) }
}

The idea is that the invisible context-sensitive comparison quirks would become visible:

if values.contains(.NaN) { // uses IEEE rules, so is always false
    print(values.filter { $0 != .NaN })
}

if values.contains(where: { $0.comparable == .NaN }) { // opt-in to stdlib quirks
    print(values.filter { $0.comparable != .NaN }) // no NaNs
}

- Karl

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.

-Joe

···

On Apr 15, 2017, at 9:49 PM, Xiaodi Wu via swift-evolution <swift-evolution@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.

+1

···

on Sun Apr 16 2017, Xiaodi Wu <swift-evolution@swift.org> wrote:

On Sun, Apr 16, 2017 at 1:14 PM, Jonathan Hull <jhull@gbis.com> wrote:

On Apr 16, 2017, at 10:42 AM, Xiaodi Wu via swift-evolution < >> swift-evolution@swift.org> wrote:

The point is that, when you manipulate two real numbers, sometimes there
is no numeric result. You cannot simply wish this away with a new numeric
type because it is not an artifact of _modeling_ real numbers but rather
intrinsic to mathematics itself.

I agree with the rest of what you said, but I have to disagree on this
point. What I think he is saying is that, in Swift, we really should be
representing the NaN case as an optional instead of a magic value on the
type itself (similar to how swift uses an optional instead of NSNotFound).

In fact, that might be an actual option here. For ‘Double?’ the compiler
could use the bit pattern for NaN internally to represent .none (I believe
it does similar tricks to save space with other optional types). Then
disallow reference to NaN within swift code. Functions or operations which
could produce NaN would either have to produce an optional or trap in case
of NaN. (e.g. the trig functions would likely return an optional, and 0/0
would trap).

I think it would actually lead to much better code because the compiler
would force you to have to explicitly deal with the case of optional/NaN
when it is possible. Migration would be tricky though...

This is essentially a cosmetic renaming from `Double` to `Double?`. There
are rules for propagating NaN which numeric algorithms expect. For example,
`cos(.nan)` returns a value. If your design is to work, every function that
takes a `Double` will need to take a `Double?`.

Just as Swift String conforms to Unicode standards, FloatingPoint conforms
to IEEE standards. You'd have to come up with enormous benefits to justify
breaking that. Doing so for Swift 4 is plainly a non-starter.

--
-Dave

I just wanted to ask for more detail on why this is a non-starter (it seems like most of my ideas are dismissed as “non-starters”, but I am rarely given a detailed reason why).

Migration would be a renaming from ‘Double' to ‘Double?’, but it wouldn’t be cosmetic. It would free us to use a non-optional Double, where we can guarantee the answer wouldn’t be NaN/nil. We would, as you say, have functions like ‘cos(Double?)->Double?’ which propagate the optional, but we could also add a ‘cos(Double)->Double’ overload which guarantees an actual result. For something like Tan, we would only have the optional version because the answer may actually be undefined, even when the input isn't.

In short, it would actually make people consider conditions which result in NaN because of Swift’s machinery which makes people consider nil.

It also allows non-optional Double to easily conform to Comparable, and removes the gotchas around Collections… Pretty big wins for a “cosmetic rename”. The only thing we lose is 'NaN != Nan' (because nil == nil), but then algorithms that had relied on that would be forced to consider the NaN/nil case explicitly because of the optionals.

It would also inter-op well with C/ObjC code by just having the compiler overlay Double? for Double…

Thanks,
Jon

···

On Apr 16, 2017, at 11:44 AM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

On Sun, Apr 16, 2017 at 1:14 PM, Jonathan Hull <jhull@gbis.com <mailto:jhull@gbis.com>> wrote:

On Apr 16, 2017, at 10:42 AM, Xiaodi Wu via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

The point is that, when you manipulate two real numbers, sometimes there is no numeric result. You cannot simply wish this away with a new numeric type because it is not an artifact of _modeling_ real numbers but rather intrinsic to mathematics itself.

I agree with the rest of what you said, but I have to disagree on this point. What I think he is saying is that, in Swift, we really should be representing the NaN case as an optional instead of a magic value on the type itself (similar to how swift uses an optional instead of NSNotFound).

In fact, that might be an actual option here. For ‘Double?’ the compiler could use the bit pattern for NaN internally to represent .none (I believe it does similar tricks to save space with other optional types). Then disallow reference to NaN within swift code. Functions or operations which could produce NaN would either have to produce an optional or trap in case of NaN. (e.g. the trig functions would likely return an optional, and 0/0 would trap).

I think it would actually lead to much better code because the compiler would force you to have to explicitly deal with the case of optional/NaN when it is possible. Migration would be tricky though...

This is essentially a cosmetic renaming from `Double` to `Double?`. There are rules for propagating NaN which numeric algorithms expect. For example, `cos(.nan)` returns a value. If your design is to work, every function that takes a `Double` will need to take a `Double?`.

Just as Swift String conforms to Unicode standards, FloatingPoint conforms to IEEE standards. You'd have to come up with enormous benefits to justify breaking that. Doing so for Swift 4 is plainly a non-starter.

Thanks,
Jon

Interesting… I think this is my favorite option so far.

I think we had an argument about this before, but if we could just make ‘<‘ throwing by marking it ‘throws!’ (that defaults to a trap unless ‘try’ or ’try?' is used), it would simplify the whole scheme to not require extra operators (though migration would be trickier).

···

On Apr 16, 2017, at 9:15 AM, Xiaodi Wu via swift-evolution <swift-evolution@swift.org> wrote:

I've spent some time fleshing out this idea:
An alternative design for Comparable · GitHub

See, your design still takes as given that floating point values require
more than one type of comparison, however these are spelled. I continue to
think that we do not need to go down this road, and that we can make things
work with each type being comparable in exactly one way.

The only wrinkle is that some floating point values are unordered with
respect to each other. While IEEE talks about different ways to think about
what a floating point value _represents_, it actually describes only one
type of comparison. And we have already nailed down what a floating point
value represents in Swift: it models a real value (level 1 representation).

···

On Sun, Apr 16, 2017 at 11:49 AM, Karl Wagner via swift-evolution < swift-evolution@swift.org> wrote:

On 16 Apr 2017, at 18:35, Karl Wagner <karl.swift@springsup.com> wrote:

On 16 Apr 2017, at 05:32, Dave Abrahams via swift-evolution < > swift-evolution@swift.org> wrote:

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

On Sat, Apr 15, 2017 at 3:12 PM, Dave Abrahams via swift-evolution < > swift-evolution@swift.org> wrote:

on Thu Apr 13 2017, Xiaodi Wu <swift-evolution@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 thing that’s bad about it is that we silently pick different operators
for different contexts. With Swift’s heavy use of abstraction layering, you
often can’t really tell what the context is (if it even has meaning at all).

I’ve been thinking about Swift architectural patterns, and one pattern
that I think of as being a good fit for the language is this idea of
wrapping operations on protocol-types as generic structs (for example, the
way we do FilterCollection, LazyMapCollection, and he various String views
in the standard library), providing transformed “views” of the object with
a common base protocol (which will hopefully get optimised away). I wonder
if we couldn’t apply a similar idea here…

So basically, every FloatingPoint will expose another pseudo-FloatingPoint
type which differs from its base object only in its interpretation of
“Comparable” operators. The type-system would enforce that you are
comparing them consistently.

protocol FloatingPoint: Comparable {

    /// A FloatingPoint with comparison quirks
    ///
    associatedtype StandardComparable: FloatingPoint
    var comparable: StandardComparable { get }

    /// A FloatingPoint which compares according to IEEE level <whatever>
    ///
    associatedtype IEEEComparable: FloatingPoint = Self
    var ieeeComparable: IEEEComparable { get }
}
extension FloatingPoint where IEEEComparable == Self {
    var ieeeComparable: Self { return self }
}

struct Float: FloatingPoint {
   /* IEEE comparison */
   static func compare(_: Float, to: Float) -> ComparisonResult { ... }

   /* Quirky Float where .Nan == .Nan, +0.0 == -0.0 etc... */
   struct StandardComparable: FloatingPoint {
     static func compare(_: StandardComparable, to: StandardComparable) ->
ComparisonResult { ... }
   }
   var comparable: StandardComparable { return StandardComparable(self) }
}

The idea is that the invisible context-sensitive comparison quirks would
become visible:

if values.contains(.NaN) { // uses IEEE rules, so is always false
    print(values.filter { $0 != .NaN })
}

if values.contains(where: { $0.comparable == .NaN }) { // opt-in to stdlib
quirks
    print(values.filter { $0.comparable != .NaN }) // no NaNs
}

- Karl

Oh, and:

Float.StandardComparable.IEEEComparable = Float, and
Float.StandardComparable.StandardComparable = Self

...so they wouldn’t recurse. You could just flip between views with
“.comparable” or “.ieeeComparable”.

- Karl

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

More interesting still, but you still failed to answer the final
question above.

···

on Sun Apr 16 2017, Xiaodi Wu <swift-evolution@swift.org> wrote:

On Sun, Apr 16, 2017 at 1:13 AM, Dave Abrahams via swift-evolution < > swift-evolution@swift.org> wrote:

<snip>

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

I've spent some time fleshing out this idea:
An alternative design for Comparable · GitHub

--
-Dave

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.

-Chris

···

On Apr 17, 2017, at 9:07 AM, Joe Groff via swift-evolution <swift-evolution@swift.org> wrote:

On Apr 15, 2017, at 9:49 PM, Xiaodi Wu via swift-evolution <swift-evolution@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 just wanted to ask for more detail on why this is a non-starter (it
seems like most of my ideas are dismissed as “non-starters”, but I am
rarely given a detailed reason why).

Migration would be a renaming from ‘Double' to ‘Double?’, but it wouldn’t
be cosmetic. It would free us to use a non-optional Double, where we can
guarantee the answer wouldn’t be NaN/nil. We would, as you say, have
functions like ‘cos(Double?)->Double?’ which propagate the optional, but we
could also add a ‘cos(Double)->Double’ overload which guarantees an actual
result. For something like Tan, we would only have the optional version
because the answer may actually be undefined, even when the input isn't.

Leave aside how one might implement such a system for a moment. The first
major issue is that your idea does not address the issues we're talking
about here:

We are debating, for instance, how to compare arrays with elements of type
`Double`. In your design, the question remains how we would compare arrays
with elements of type `Double?`. If the answer is that you cannot compare
arrays of type `[Double?]`, then we have a problem, because that's the type
that people will use when they ingest data that might contain NaN. Sure,
they can unwrap each element before using their data, but they can also
test each element with `isNaN` today. We are trying to *improve* on the
user experience of comparing arrays of floating point values *without*
checking if they contain NaN, not trying to take that feature away.

Your design also doesn't address the problem of how NaN should compare with
NaN. Only now, you've pushed the problem to `Optional`. By design, every
`Optional<T>.none` compares equal to every other `Optional<U>.none` (yes,
even of different types). This did not always work correctly, if I recall,
but it does now and it's an intentional part of the design. However, NaN
must compare not equal to every NaN. These could not be more different
properties. It seems quite absurd on its face that we might want NaN to
compare equal to a value of type `Optional<UIViewController>`.

In short, it would actually make people consider conditions which result in

···

On Tue, Apr 25, 2017 at 6:53 PM, Jonathan Hull <jhull@gbis.com> wrote:

NaN because of Swift’s machinery which makes people consider nil.

It also allows non-optional Double to easily conform to Comparable, and
removes the gotchas around Collections… Pretty big wins for a “cosmetic
rename”. The only thing we lose is 'NaN != Nan' (because nil == nil), but
then algorithms that had relied on that would be forced to consider the
NaN/nil case explicitly because of the optionals.

It would also inter-op well with C/ObjC code by just having the compiler
overlay Double? for Double…

Thanks,
Jon

On Apr 16, 2017, at 11:44 AM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

On Sun, Apr 16, 2017 at 1:14 PM, Jonathan Hull <jhull@gbis.com> wrote:

On Apr 16, 2017, at 10:42 AM, Xiaodi Wu via swift-evolution < >> swift-evolution@swift.org> wrote:

The point is that, when you manipulate two real numbers, sometimes there
is no numeric result. You cannot simply wish this away with a new numeric
type because it is not an artifact of _modeling_ real numbers but rather
intrinsic to mathematics itself.

I agree with the rest of what you said, but I have to disagree on this
point. What I think he is saying is that, in Swift, we really should be
representing the NaN case as an optional instead of a magic value on the
type itself (similar to how swift uses an optional instead of NSNotFound).

In fact, that might be an actual option here. For ‘Double?’ the compiler
could use the bit pattern for NaN internally to represent .none (I believe
it does similar tricks to save space with other optional types). Then
disallow reference to NaN within swift code. Functions or operations which
could produce NaN would either have to produce an optional or trap in case
of NaN. (e.g. the trig functions would likely return an optional, and 0/0
would trap).

I think it would actually lead to much better code because the compiler
would force you to have to explicitly deal with the case of optional/NaN
when it is possible. Migration would be tricky though...

This is essentially a cosmetic renaming from `Double` to `Double?`. There
are rules for propagating NaN which numeric algorithms expect. For example,
`cos(.nan)` returns a value. If your design is to work, every function that
takes a `Double` will need to take a `Double?`.

Just as Swift String conforms to Unicode standards, FloatingPoint conforms
to IEEE standards. You'd have to come up with enormous benefits to justify
breaking that. Doing so for Swift 4 is plainly a non-starter.

Thanks,

Jon

Sorting a collection will not use `<` as the default predicate.

In the Gist, I've outlined a design for `[Double].sorted()` which would
exhibit identical behavior to what is proposed in this thread, but the
design would be different under the hood. In brief, the "go-to" overload
for sorting a collection of comparable elements would be:

sorted(_ sortOrder: SortOrder = .ascending, by comparison:
(Iterator.Element, Iterator.Element) -> Comparison? = `<=>`) ->
[Iterator.Element]

which would notionally use the following for the predicate known today as
`areInIncreasingOrder`:

{
switch sortOrder {
case .ascending:
return comparison($0, $1) == .some(.less) || comparison($1, $1) == .none
case .descending:
return comparison($1, $0) == .some(.less) || comparison($0, $0) == .none
}
}

(We would add an enum `SortOrder` distinct from `Comparison` for reasons
spelled out in the Gist--not really germane to your question, though. And,
although the compiler may or may not do it today, there ought to be no
reason why it cannot optimize away checks for `comparison(a, b) == .none`
if values of the concrete type never compare unordered--i.e. if the
function passed as the second argument to `sorted` returns `Comparison`
instead of `Comparison?`.)

(The `Comparison` instead of `Comparison?` thing, incidentally, is for me
the crux of my alternative design. I'm quite proud of it. It allows us to
recover most (all?) the benefits of knowing at compile time which types are
"partially" comparable and which are not, but *without* having a distinct
protocol named PartiallyComparable. That is, the one protocol `Comparable`
would require a comparison method that returns an instance of type
`Comparison?`. Conforming types that never compare unordered can fulfill
that requirement with a method that returns `Comparison` (non-optional).
Both the compiler and readers can gain something meaningful from that.
Meanwhile, we avoid the disaster of generic algorithms having two different
protocols to choose from and potentially not supporting floating point.)

With this design, each generic function would decide how to handle
unordered comparisons. I believe this to be superior because ordering NaN
greater than all other values produces an acceptable result for `sort` but
a rather unintuitive one for `max`, and there is no reason why we should
have to tolerate that.

Using `sort(by: <)` explicitly with a collection of elements that may
compare unordered will give a compiler warning, as `<` would not satisfy
the semantic requirements for a sort predicate. Nothing will forbid the
user from passing an arbitrary function as a predicate, though, just as we
do not stop someone from writing `sort(by: ==)` today. The warning about
using `<` will be silenced by writing `sort { $0 < $1 }`.

For perfect migration of existing code, `sort(by: <)` can be migrated to
the proposed spelling `sort(by: &<)` and retain Swift 3 behavior in every
way, including the same wonky results with NaN. Otherwise,
`sort(.ascending)` and `sort(.descending)` would be the preferred way to
write the same thing, with more sensible results when sorting NaN.

···

On Mon, Apr 17, 2017 at 11:40 Dave Abrahams via swift-evolution < swift-evolution@swift.org> wrote:

on Sun Apr 16 2017, Xiaodi Wu <swift-evolution@swift.org> wrote:

> On Sun, Apr 16, 2017 at 1:13 AM, Dave Abrahams via swift-evolution < > > swift-evolution@swift.org> wrote:
>
>> <snip>
>>
>>> > 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?
>
> I've spent some time fleshing out this idea:
> An alternative design for Comparable · GitHub

More interesting still, but you still failed to answer the final
question above.

--
-Dave

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution