<div dir="ltr">Sorry to overwhelm with more emails. I'd like to show some work and further analysis for your consideration that refines the sketch I just wrote:<div><br></div><div>Two FP values a and b can be, with respect to each other:</div><div><br></div><div>* ordered or unordered (per IEEE, NaN compares unordered to everything, including itself)</div><div>* identical or not identical (for these purposes, we adopt Steve's proposed test for identity: substitutable for all operations; thus +0 is not identical to -0, but different binary representations of the same value are identical)</div><div>* equal or not equal (i.e. the behavior of the == operator today)</div><div><br></div><div>So, if a and b are, with respect to each other:</div><div><br></div><div>* ordered, identical, equal -- this is what happens ordinarily with two equal, non-NaN values</div><div>* ordered, identical, not equal -- this can never happen</div><div>* ordered, not identical, equal -- only +0 and -0</div><div>* ordered, not identical, not equal -- this is what happens ordinarily with two unequal, non-NaN values</div><div><br></div><div>* unordered, identical, equal -- this can never happen, but if NaNs are to be well-behaved (for a true equivalence relation), then we will need an equivalence relation in which NaN == NaN</div><div>* unordered, identical, not equal -- this is what always happens, but if NaNs are to be well-behaved, then such behavior will need to change</div><div>* unordered, not identical, equal -- this can never happen</div><div>* unordered, not identical, not equal -- this is what ordinarily happens with one NaN and one non-NaN value</div><div><br></div><div>Equatable can have === and my proposed ==? as part of its protocol; a generic ==, as originally proposed, would be defined outside the protocol.</div><div>A default implementation of ==? will forward to ===, and the generic == will be defined as `{ return (lhs ==? rhs) ?? (lhs === rhs) }`.</div><div>For floating point, ==? will be specialized and cease to forward to === so that +0 and -0 compare true and NaN and anything compare nil, and floating point == will be defined notionally as `{ return (lhs ==? rhs) ?? false }`.</div><div><br><div class="gmail_extra"><br><div class="gmail_quote">On Sat, Jul 23, 2016 at 3:09 PM, Xiaodi Wu <span dir="ltr"><<a href="mailto:xiaodi.wu@gmail.com" target="_blank">xiaodi.wu@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Throwing out some more radical ideas here. Suppose we had instead (taking inspiration from IEEE notation):<div><br></div><div>[Pardon any errors; I'm writing freehand in Gmail]<br><div><br></div><div>infix operator ==? { /* figure out precedence later */ }</div><div><br></div><div>protocol Equatable {</div><div> static func ==? (lhs: Self, rhs: Self) -> Bool?</div><div> /* semantics:</div><div> this function returns nil if lhs and rhs are unordered with respect to each other</div><div> otherwise, evaluate by means of a legal equivalence relation */</div><div>}</div><div><br></div><div>func == <T: Equatable>(lhs: T, rhs: T) -> Bool {</div><div> return (lhs ==? rhs) ?? false</div><span class=""><div>}</div><div><br></div><div>protocol Comparable : Equatable {</div><div> static func <=> (lhs: Self, rhs: Self) -> Ordering</div></span><div> /* semantics:</div><div> this is a total ordering; thus:</div><div> if `(a ==? b) == true`, then `(a <=> b) == .same`</div><div> if `(a ==? b) == false`, then `(a <=> b) != .same`</div><div> but, if `(a ==? b) == nil`, then `a <=> b` may yield any result</div><div> */</div><div><div class="h5"><div>}</div><div><br></div><div class="gmail_extra"><br><div class="gmail_quote">On Sat, Jul 23, 2016 at 2:35 PM, Pyry Jahkola <span dir="ltr"><<a href="mailto:pyry.jahkola@iki.fi" target="_blank">pyry.jahkola@iki.fi</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Given all this, I propose a simpler model that makes `a <=> b` follow the expected behaviour of < and ==, with the tradeoff that `a <=> .nan` and `.nan <=> b` will abort with a precondition failure:<br>
<br>
1) We keep the current Interface of Equatable unchanged, with != defined in terms of ==.<br>
<br>
2) Comparable would still refine Equatable, and include all the comparison operators, adding the new <=>:<br>
<br>
protocol Comparable : Equatable {<br>
static func <=>(lhs: Self, rhs: Self) -> Ordering<br>
<span> static func <(lhs: Self, rhs: Self) -> Bool<br>
static func >(lhs: Self, rhs: Self) -> Bool<br>
</span><span> static func <=(lhs: Self, rhs: Self) -> Bool<br>
static func >=(lhs: Self, rhs: Self) -> Bool<br>
}<br>
<br>
</span>The comparison operators are kept in the interface so that partially ordered types such as Double can be supported in generic code. However, the documentation should recommend against defining `<` manually.<br>
<br>
3) Default implementations for <Self : Comparable> are provided for the following operators: ==, <, >, <=, and >=.<br>
<br>
4) User-defined types will need to define just <=> to conform to Comparable. (Even == can be omitted!)<br>
<br>
5) FloatingPoint types implement custom versions of ==, <, >, <=, and >= using the standard IEEE 754 definition (i.e. comparisons involving NaN return false). Zero is zero; `0.0 == -0.0 && !(-0.0 < 0.0)` holds.<br>
<br>
6) FloatingPoint types implement <=> as:<br>
<br>
func <=> <T : FloatingPoint>(lhs: T, rhs: T) -> Ordering {<br>
if lhs < rhs { return .ascending }<br>
if rhs < lhs { return .descending }<br>
precondition(lhs == rhs)<br>
return .same<br>
}<br>
<br>
7) Algorithms using <=> directly should mention so in their documentation as a precondition that they require total order between elements. Many generic algorithms can be defined in terms of == or <, and should.<br>
<br>
If we took the oroginally planned route that distinguished between identities such as -0.0 vs. +0.0, or between the 2⁴⁹ - 2 ≈ 5.6 × 10¹⁴ possible NaN values that Double has, we'd also need to consider other oddballs like the difference and ordering between the Strings "ä" and "a\u{308}", which are considered equal but produce a different Unicode representation. I think it's best to hide those identities behind another interface than Equatable and Comparable, and let the protocols serve more mundane application logic.<br>
<span><font color="#888888"><br>
— Pyry<br>
</font></span><div><div><br>
> Dave Abrahams wrote:<br>
><br>
><br>
>> on Sat Jul 23 2016, Xiaodi Wu <<a href="http://xiaodi.wu-AT-gmail.com" rel="noreferrer" target="_blank">xiaodi.wu-AT-gmail.com</a>> wrote:<br>
>><br>
>> On Fri, Jul 22, 2016 at 11:34 PM, Stephen Canon <<a href="mailto:scanon@apple.com" target="_blank">scanon@apple.com</a>> wrote:<br>
>><br>
>>>> The point of this design is that `===` means identity and that `.same `<br>
>>>> also means identity.<br>
>>>><br>
>>>> Since this is new territory I suppose we get to decide what identity<br>
>>>> means for floating point. Should +0 and -0 have the same identity or<br>
>>>> not? I’ll leave the answer to folks more knowledgable about numerics<br>
>>>> than I.<br>
>>><br>
>>> Boy, I take my wife out for a movie and come back to 50 new messages on SE.<br>
>>><br>
>>> I need to read the entire thread more carefully, but off the top of my<br>
>>> head, I think that `-0 === +0` is False. If we’re going to have an<br>
>>> `isSame` / `isIdentical` / whatever it's called, I would expect it to imply<br>
>>> substitutability. Although -0 == +0, they are not equivalent when<br>
>>> substituted:<br>
>>><br>
>>> - 1/(-0) != 1/0<br>
>>> - Float(-0).sign != Float(+0).sign<br>
>>> - etc<br>
>>><br>
>>> This probably then implies that `<=>` is not `.same` either. I’ll read<br>
>>> the rest of this and respond more completely tomorrow.<br>
>><br>
>> Eagerly await your evaluation of the discussion. In the meantime:<br>
>><br>
>> I think Dave's view that `===` defines identity in terms of "essential"<br>
>> qualities implies that two identical values can be<br>
>> different/non-substitutable in "inessential" qualities. For generic<br>
>> purposes, the sign of zero could be one such inessential quality.<br>
><br>
> Yes, and I think our view of how people work with numbers in swift (and<br>
> their protocol conformances) reflect this approach.<br>
><br>
> <a href="http://article.gmane.org/gmane.comp.lang.swift.evolution/16321" rel="noreferrer" target="_blank">http://article.gmane.org/gmane.comp.lang.swift.evolution/16321</a><br>
><br>
> My sense is that we want to choose the default notions of identity and<br>
> ordering so as to support the way people think about these numeric<br>
> types, inexact though it may be. Therefore, finding 0.0 in a sequence<br>
> of floats should succeed when the sequence contains -0.0, and a stable<br>
> sort on floating point keys should preserve the relative order of all<br>
> elements having +0.0 and -0.0 keys.<br>
><br>
> People that want to work with inessential qualities such as the sign of<br>
> zero can always pass Float.totalOrdering (or whatever) to their<br>
> closure-accepting algorithms.<br>
><br>
> [In order to support the user model, we still need to fix the semantics<br>
> of the default identity and ordering operations so that things like<br>
> sorting and searching work, which is why == and < won't cut it for these<br>
> purposes]<br>
><br>
>> On the other hand, the stdlib stride algorithm is going to be borked if -0<br>
>> < +0. Of course, as we already started to do there, we could specialize for<br>
>> floating point and then adjust accordingly. However, it seems to me that<br>
>> every generic algorithm that performs comparisons and can take floating<br>
>> point arguments would have to be specialized to account for floating point<br>
>> -0 != +0 (`index(of:)` being the previous example). This appears to defeat<br>
>> the aim of trying to accommodate FP at all in this revised design for<br>
>> Comparables.<br>
><br>
> Yes, that would be a disaster, generically speaking.<br>
><br>
>> The argument for `-0 === +0` is that -0 and +0 should be equivalent when<br>
>> substituted for every comparison operation. For FP operations, you'd<br>
>> continue to test (as you have to test now) `a == b && a.sign == b.sign` if<br>
>> you cared about the sign of zero. For non-FP arithmetic operations, hmm,<br>
>> not sure how to square that circle.<br>
><br>
> I followed all of this... except, what are you getting at with that last<br>
> sentence?<br>
><br>
> --<br>
> Dave<br>
</div></div><div><div>> _______________________________________________<br>
> swift-evolution mailing list<br>
> <a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a><br>
> <a href="https://lists.swift.org/mailman/listinfo/swift-evolution" rel="noreferrer" target="_blank">https://lists.swift.org/mailman/listinfo/swift-evolution</a><br>
</div></div></blockquote></div><br></div></div></div></div></div>
</blockquote></div><br></div></div></div>