[swift-evolution] [pitch] Comparison Reform
Xiaodi Wu
xiaodi.wu at gmail.com
Tue Apr 25 00:54:18 CDT 2017
On Tue, Apr 25, 2017 at 12:52 AM, Jonathan Hull <jhull at gbis.com> wrote:
> The only other alternative I can think of is to include a notion of
> unordered to our comparisons…
>
> What if we made <=> return an optional comparison result, with nil meaning
> unordered (which is how Ruby does it)?
>
Have you seen my Gist? It's a whole design based on that idea.
> For == and <, we still require a strict total ordering (i.e. they would
> not be optional). Most of the time, <=> and <, == would have the same
> comparison (<=> could have a default implementation based on == and <), but
> in the case of floating point it would be slightly different: <=> would
> return nil for anything involving NaN (in full accordance with IEEE 754),
> while < and == would somehow jam it into a strict total order (preferably
> with Nan == NaN so we don’t break collections).
>
As I say above, nan == nan is a non-starter for the numerics crowd, and I
have to agree. NaN *must not be equal to* NaN, or all sorts of numerics
recipes are likely to break in weird ways when ported to Swift.
>
> Thanks,
> Jon
>
> On Apr 24, 2017, at 8:25 PM, Xiaodi Wu <xiaodi.wu at gmail.com> wrote:
>
> On Mon, Apr 24, 2017 at 9:06 PM, Jonathan Hull via swift-evolution <swift-
> evolution at swift.org> wrote:
>
>> As I am thinking about it more, this means that for == and <
>>
>> NaN == NaN
>> -0 == +0
>> +Inf < NaN
>>
>> Since this would break from IEEE,
>
>
> Yeah, as Steve mentioned, it's a huge deal to break from IEEE rules. Both
> the existing design and Dave's proposed design jump through huge hoops to
> preserve the behavior of these operators and reconcile them with the rest
> of Swift. The biggest weakness of my alternative idea as written up earlier
> is that it cannot preserve the spelling of these operators but requires a
> minor adjustment (`&`). It's simply a no-go to move `==` to `compare(with:
> other, using: .ieee)`. No one will write numerics algorithms like that.
>
> I think we should also consider taking the opportunity to make == and <
>> work with a default tolerance. That is, 'a == b' would check that (a - b)
>> < epsilon for some reasonable choice of epsilon that works for common
>> usage. I know this would make the hash function harder to write, but I
>> think it is worthwhile.
>>
>> Then, as I mentioned before, people who need strict IEEE conformance
>> would explicitly declare that need by using 'compare(with: other, using:
>> .IEEE)' or whatever we want to call that metric. We can even provide
>> metrics for different IEEE levels, if desired.
>>
>> We could also provide a function ‘tolerance(_:Self) -> Comparable.Metric’
>> on FloatingPoint which returns a comparison metric that defines equality as
>> (a - b) < tolerance, for those who want to specify a specific tolerance for
>> their use-case/algorithm...
>>
>> Thanks,
>> Jon
>>
>>
>>
>> > On Apr 23, 2017, at 7:18 AM, Jonathan Hull via swift-evolution <
>> swift-evolution at swift.org> wrote:
>> >
>> > There is one more option which hasn’t really been considered:
>> >
>> > • == and != are tied to the Equatable protocol, which is essentially
>> the == operation.
>> > • <, <=, >, >= are tied to the Comparable protocol (which is kept the
>> same except for minor changes/additions listed below)
>> > • Hashable still requires Equatable
>> > • There is a new ComparisonMetric concept which lets an algorithm
>> specify exactly how the comparison is done (see below)
>> >
>> >
>> > Tl;dr: There are different definitions of ‘comparison’ which make sense
>> in different domains… so let’s make it explicit so it doesn’t surprise
>> anyone.
>> >
>> > The question then becomes, which metric should be the default (i.e. the
>> one defined by ‘<‘ and ‘==‘), and the answer is: the one which lets us use
>> floats/doubles in dictionaries and sets. People and algorithms which need
>> full IEEE correctness can use a different metric which specifically
>> guarantees it. They can even build their own metric if needed.
>> >
>> >
>> > ====The Design====
>> > // (Note: I wrote this code in mail, so it may not compile)
>> >
>> >
>> > //This defines the result of a comparison. It would ideally be nested
>> in the protocol below if that becomes possible.
>> > enum ComparisonResult : Int {
>> > case ascending = -1
>> > case equal = 0
>> > case descending = 1
>> > }
>> >
>> > protocol Comparable {
>> > typealias Metric = (Self, Self) -> ComparisonResult //Give
>> ourselves an easy way to refer to this function type
>> >
>> > var defaultMetric: Metric
>> > static func <(lhs: Self, rhs: Self) -> Bool
>> > }
>> >
>> > extension Comparable {
>> > //Not shown: We would define <=, etc… plus ≤,≥,and ≠ (because,
>> hey, it is my proposal)
>> >
>> > func compare(with other: Self, using metric: Metric) ->
>> ComparisonResult {
>> > return metric(self, other)
>> > }
>> >
>> > func compare(with other: Self) -> ComparisonResult {
>> > return self.defaultMetric(self, other)
>> > }
>> >
>> > static func <=> (lhs: Self, rhs: Self) -> Int {
>> > return self.defaultMetric(lhs, rhs).rawValue
>> > }
>> >
>> > var defaultMetric: Metric {
>> > return { lhs, rhs in
>> > if lhs == rhs {
>> > return .equal
>> > } else if lhs < rhs {
>> > return .ascending
>> > }
>> > return .descending
>> > }
>> > }
>> > }
>> >
>> > ============
>> >
>> > Then for Double, we would make a second metric for IEEE compliant (or
>> multiple for different levels)
>> >
>> > extension Double : Comparable {
>> >
>> > static func < (lhs: Self, rhs: Self) -> Bool {
>> > //define using best for dictionaries / sets / layman
>> understanding
>> > }
>> >
>> > static func == (lhs: Self, rhs: Self) -> Bool {
>> > //define using best for dictionaries / sets / layman
>> understanding
>> > }
>> >
>> > static var IEEEcompare:Comparable.Metric {
>> > //return function here that does full IEEE comparison
>> > }
>> >
>> > }
>> >
>> > Then we can call ‘myDouble.compare(with: otherDouble, using:
>> .IEEEcompare)’ when needed.
>> >
>> >
>> > Thanks,
>> > Jon
>> >
>> >
>> >
>> >> On Apr 22, 2017, at 9:58 PM, Chris Lattner via swift-evolution <
>> swift-evolution at swift.org> wrote:
>> >>
>> >> On Apr 22, 2017, at 6:06 PM, Xiaodi Wu <xiaodi.wu at gmail.com> wrote:
>> >>> but my quick reaction to `&==` is that it would make me quite nervous
>> to have `==` not bound to 754-equals as it is in essentially every other
>> language. In particular, I worry about the risk of people porting numerical
>> code that depends on isnan(x) <—> !(x < y) in non-obvious ways that they
>> are unlikely to test. I’ll try to follow up with more detailed thoughts
>> tomorrow.
>> >>>
>> >>> Indeed, it makes me a little nervous too. That said, `==` being
>> either bound or not bound to 754 depending on the context is what makes me
>> even more nervous.
>> >>>
>> >>> I was once adamantly against a new spelling for `==`, but on
>> reconsideration it's clear to me that few if any numerical recipes can be
>> ported verbatim from C-like languages and we should probably not encourage
>> people to do so. Already, `+` needs to be rewritten as `&+`, `<<` probably
>> should be rewritten as `&<<` (I still haven't had enough time to think
>> about this), and the bitwise operators have differing precedences that
>> require careful proofreading.
>> >>
>> >>
>> >> I haven’t been following this proposal or discussion closely, but it
>> seems to me that there are a few workable approaches with different
>> tradeoffs:
>> >>
>> >> 1. The strictly correct but user hostile approach:
>> >>
>> >> * == and != are tied to the Equatable protocol, which is essentially
>> the == operation.
>> >> * <, <=, >, >= are tied to the Comparable protocol, which is
>> essentially the <=> operation.
>> >> * Hashable doesn’t require equatable, it requires a related
>> StrictlyEquatable protocol.
>> >> * StrictlyEquatable refines Equatable (with no other requirements, it
>> is just a marker protocol), in which case FP types can’t conform to it, and
>> thus can’t participate as dictionary keys
>> >>
>> >> => This approach sucks because you can’t have Set<Float>, or
>> Dictionary<Float, String>.
>> >>
>> >> 2. The strictly correct but somewhat user hostile approach:
>> >>
>> >> * == and != are tied to the Equatable protocol, which is essentially
>> the == operation.
>> >> * <, <=, >, >= are tied to the Comparable protocol, which is
>> essentially the <=> operation.
>> >> * Hashable doesn’t require equatable, it requires a related
>> StrictlyEquatable protocol.
>> >> * StrictlyEquatable doesn’t refine Equatable: it has a different
>> requirement, and FP types can therefore implement both Equatable and
>> StrictlyEquatable.
>> >>
>> >> => This approach is suboptimal because implementing your own type
>> requires you to implement the <=> operation, as well as the
>> StrictlyEquatable protocol, both.
>> >>
>> >> 3. The user friendly but incorrect model:
>> >>
>> >> * == and != are tied to the Equatable protocol, which is essentially
>> the == operation.
>> >> * <, <=, >, >= are tied to the Comparable protocol, which is
>> essentially the <=> operation.
>> >> * Hashable is defined in terms of Equatable.
>> >>
>> >> => This is easy (types just have to define <=>), but fails for FP
>> types.
>> >>
>> >>
>> >> I don’t think that this proposal is acceptable as written. I think it
>> is really bad that abstracting a concrete algorithm would change its
>> behavior so substantially. I don’t care about SNaNs, but I do care about
>> the difference between +0/-1 and secondarily that of NaN handling. It
>> seems really bad that generalizing something like:
>> >>
>> >> func doThing(a : Double, b : Double) -> Bool {
>> >> ….
>> >> return a != b
>> >> }
>> >>
>> >> to:
>> >>
>> >> func doThing<T : FloatingPoint> (a : T, b : T) -> Bool {
>> >> ….
>> >> return a != b
>> >> }
>> >>
>> >> would change behavior (e.g. when a is -0.0 and b is +0.0). Likewise,
>> "T : Equatable".
>> >>
>> >> -Chris
>> >>
>> >>
>> >> _______________________________________________
>> >> swift-evolution mailing list
>> >> swift-evolution at swift.org
>> >> https://lists.swift.org/mailman/listinfo/swift-evolution
>> >
>> > _______________________________________________
>> > swift-evolution mailing list
>> > swift-evolution at swift.org
>> > https://lists.swift.org/mailman/listinfo/swift-evolution
>>
>> _______________________________________________
>> swift-evolution mailing list
>> swift-evolution at swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20170425/e3f6ed66/attachment.html>
More information about the swift-evolution
mailing list