Daniel Duan Sent from my iPhone
> On Jul 23, 2016, at 3:15 PM, Ross O'Brien via swift-evolution > <swift-evolution@swift.org> wrote: > > This might be a radical suggestion ... or possibly a naive or unoriginal one, > I'll find out once I suggest it. > > Swift took the bold step of establishing optionals as a central type, rather > than assigning dual meanings to 'default' values such as zero or false. > Recognising the concept of not having a value, and safeguarding against that, > is core to Swift. Optional is nothing new or "bold". It's been main stream for years. Even C++ has it :) > Is it possible for Swift to recognise that there are values which simply > aren't comparable, rather than forcing a choice between ascending, same, > descending? Could we add a fourth: incomparable? > The problem we are trying to solve here is strict total ordering: https://en.m.wikipedia.org/wiki/Total_order > What if a sort operation didn't simply return an array of ordered values? > What if it partitioned the values into comparable and incomparable values, > and returned a sorted array of the former and an unordered collection of the > latter? > Maybe, this being Swift, we could use some kind of 'sort!' exclamation mark > to forcibly express that every value in the collection-to-be-sorted is > implicitly comparable, if we're sure. > > >> On Sat, Jul 23, 2016 at 10:37 PM, Xiaodi Wu via swift-evolution >> <swift-evolution@swift.org> wrote: >>> On Sat, Jul 23, 2016 at 4:19 PM, Nevin Brackett-Rozinsky >>> <nevin.brackettrozin...@gmail.com> wrote: >>> Another option would be to leave the IEEE 754 NaN hijinks in Float and >>> Double (as numerics people expect), and create a new type (with a nice >>> approachable name) that “acts like” Double but does not model NaN. Then any >>> operation which would ordinarily produce a NaN, instead traps for the new >>> type. That way its comparison operators only have to worry about non-NaN >>> values, which makes everything much cleaner. >>> >>> Sorting Doubles would retain its present functionality, warts and all, >>> which numerics people should be expected to handle. Whereas the new type >>> (“Number” sounds good, especially if we can make it subsume NSNumber) would >>> never have a NaN in the first place. >> >> The other comment I would make here is that, as mentioned earlier by Pyry, >> there are other types for which we'll need to reckon with domain-specific >> "hijinks" that don't offer easy notions of identity, Unicode being one >> example. I'd expect that many types that model an existing domain of human >> endeavor will run into something like this. Thus, carefully working through >> a design for fundamental protocols like Equatable and Comparable that don't >> fall down with FP will prove more broadly fruitful. I don't think that >> segregating all hijinks and modeling what we *wish* the world to be is as >> beneficial in terms of allowing generic algorithms to work meaningfully with >> types that people actually use in real-world scenarios. >> >>> Nevin >>> >>> >>> >>>> On Sat, Jul 23, 2016 at 4:57 PM, Xiaodi Wu via swift-evolution >>>> <swift-evolution@swift.org> wrote: >>>> 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: >>>> >>>> Two FP values a and b can be, with respect to each other: >>>> >>>> * ordered or unordered (per IEEE, NaN compares unordered to everything, >>>> including itself) >>>> * 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) >>>> * equal or not equal (i.e. the behavior of the == operator today) >>>> >>>> So, if a and b are, with respect to each other: >>>> >>>> * ordered, identical, equal -- this is what happens ordinarily with two >>>> equal, non-NaN values >>>> * ordered, identical, not equal -- this can never happen >>>> * ordered, not identical, equal -- only +0 and -0 >>>> * ordered, not identical, not equal -- this is what happens ordinarily >>>> with two unequal, non-NaN values >>>> >>>> * 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 >>>> * unordered, identical, not equal -- this is what always happens, but if >>>> NaNs are to be well-behaved, then such behavior will need to change >>>> * unordered, not identical, equal -- this can never happen >>>> * unordered, not identical, not equal -- this is what ordinarily happens >>>> with one NaN and one non-NaN value >>>> >>>> Equatable can have === and my proposed ==? as part of its protocol; a >>>> generic ==, as originally proposed, would be defined outside the protocol. >>>> A default implementation of ==? will forward to ===, and the generic == >>>> will be defined as `{ return (lhs ==? rhs) ?? (lhs === rhs) }`. >>>> 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 }`. >>>> >>>> >>>> On Sat, Jul 23, 2016 at 3:09 PM, Xiaodi Wu <xiaodi...@gmail.com> wrote: >>>>> Throwing out some more radical ideas here. Suppose we had instead (taking >>>>> inspiration from IEEE notation): >>>>> >>>>> [Pardon any errors; I'm writing freehand in Gmail] >>>>> >>>>> infix operator ==? { /* figure out precedence later */ } >>>>> >>>>> protocol Equatable { >>>>> static func ==? (lhs: Self, rhs: Self) -> Bool? >>>>> /* semantics: >>>>> this function returns nil if lhs and rhs are unordered with respect >>>>> to each other >>>>> otherwise, evaluate by means of a legal equivalence relation */ >>>>> } >>>>> >>>>> func == <T: Equatable>(lhs: T, rhs: T) -> Bool { >>>>> return (lhs ==? rhs) ?? false >>>>> } >>>>> >>>>> protocol Comparable : Equatable { >>>>> static func <=> (lhs: Self, rhs: Self) -> Ordering >>>>> /* semantics: >>>>> this is a total ordering; thus: >>>>> if `(a ==? b) == true`, then `(a <=> b) == .same` >>>>> if `(a ==? b) == false`, then `(a <=> b) != .same` >>>>> but, if `(a ==? b) == nil`, then `a <=> b` may yield any result >>>>> */ >>>>> } >>>>> >>>>> >>>>>> On Sat, Jul 23, 2016 at 2:35 PM, Pyry Jahkola <pyry.jahk...@iki.fi> >>>>>> wrote: >>>>>> 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: >>>>>> >>>>>> 1) We keep the current Interface of Equatable unchanged, with != >>>>>> defined in terms of ==. >>>>>> >>>>>> 2) Comparable would still refine Equatable, and include all the >>>>>> comparison operators, adding the new <=>: >>>>>> >>>>>> protocol Comparable : Equatable { >>>>>> static func <=>(lhs: Self, rhs: Self) -> Ordering >>>>>> static func <(lhs: Self, rhs: Self) -> Bool >>>>>> static func >(lhs: Self, rhs: Self) -> Bool >>>>>> static func <=(lhs: Self, rhs: Self) -> Bool >>>>>> static func >=(lhs: Self, rhs: Self) -> Bool >>>>>> } >>>>>> >>>>>> 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. >>>>>> >>>>>> 3) Default implementations for <Self : Comparable> are provided for the >>>>>> following operators: ==, <, >, <=, and >=. >>>>>> >>>>>> 4) User-defined types will need to define just <=> to conform to >>>>>> Comparable. (Even == can be omitted!) >>>>>> >>>>>> 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. >>>>>> >>>>>> 6) FloatingPoint types implement <=> as: >>>>>> >>>>>> func <=> <T : FloatingPoint>(lhs: T, rhs: T) -> Ordering { >>>>>> if lhs < rhs { return .ascending } >>>>>> if rhs < lhs { return .descending } >>>>>> precondition(lhs == rhs) >>>>>> return .same >>>>>> } >>>>>> >>>>>> 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. >>>>>> >>>>>> 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. >>>>>> >>>>>> — Pyry >>>>>> >>>>>> > Dave Abrahams wrote: >>>>>> > >>>>>> > >>>>>> >> on Sat Jul 23 2016, Xiaodi Wu <xiaodi.wu-AT-gmail.com> wrote: >>>>>> >> >>>>>> >> On Fri, Jul 22, 2016 at 11:34 PM, Stephen Canon <sca...@apple.com> >>>>>> >> wrote: >>>>>> >> >>>>>> >>>> The point of this design is that `===` means identity and that >>>>>> >>>> `.same ` >>>>>> >>>> also means identity. >>>>>> >>>> >>>>>> >>>> Since this is new territory I suppose we get to decide what identity >>>>>> >>>> means for floating point. Should +0 and -0 have the same identity >>>>>> >>>> or >>>>>> >>>> not? I’ll leave the answer to folks more knowledgable about >>>>>> >>>> numerics >>>>>> >>>> than I. >>>>>> >>> >>>>>> >>> Boy, I take my wife out for a movie and come back to 50 new messages >>>>>> >>> on SE. >>>>>> >>> >>>>>> >>> I need to read the entire thread more carefully, but off the top of >>>>>> >>> my >>>>>> >>> head, I think that `-0 === +0` is False. If we’re going to have an >>>>>> >>> `isSame` / `isIdentical` / whatever it's called, I would expect it >>>>>> >>> to imply >>>>>> >>> substitutability. Although -0 == +0, they are not equivalent when >>>>>> >>> substituted: >>>>>> >>> >>>>>> >>> - 1/(-0) != 1/0 >>>>>> >>> - Float(-0).sign != Float(+0).sign >>>>>> >>> - etc >>>>>> >>> >>>>>> >>> This probably then implies that `<=>` is not `.same` either. I’ll >>>>>> >>> read >>>>>> >>> the rest of this and respond more completely tomorrow. >>>>>> >> >>>>>> >> Eagerly await your evaluation of the discussion. In the meantime: >>>>>> >> >>>>>> >> I think Dave's view that `===` defines identity in terms of >>>>>> >> "essential" >>>>>> >> qualities implies that two identical values can be >>>>>> >> different/non-substitutable in "inessential" qualities. For generic >>>>>> >> purposes, the sign of zero could be one such inessential quality. >>>>>> > >>>>>> > Yes, and I think our view of how people work with numbers in swift (and >>>>>> > their protocol conformances) reflect this approach. >>>>>> > >>>>>> > http://article.gmane.org/gmane.comp.lang.swift.evolution/16321 >>>>>> > >>>>>> > My sense is that we want to choose the default notions of identity and >>>>>> > ordering so as to support the way people think about these numeric >>>>>> > types, inexact though it may be. Therefore, finding 0.0 in a sequence >>>>>> > of floats should succeed when the sequence contains -0.0, and a stable >>>>>> > sort on floating point keys should preserve the relative order of all >>>>>> > elements having +0.0 and -0.0 keys. >>>>>> > >>>>>> > People that want to work with inessential qualities such as the sign of >>>>>> > zero can always pass Float.totalOrdering (or whatever) to their >>>>>> > closure-accepting algorithms. >>>>>> > >>>>>> > [In order to support the user model, we still need to fix the semantics >>>>>> > of the default identity and ordering operations so that things like >>>>>> > sorting and searching work, which is why == and < won't cut it for >>>>>> > these >>>>>> > purposes] >>>>>> > >>>>>> >> On the other hand, the stdlib stride algorithm is going to be borked >>>>>> >> if -0 >>>>>> >> < +0. Of course, as we already started to do there, we could >>>>>> >> specialize for >>>>>> >> floating point and then adjust accordingly. However, it seems to me >>>>>> >> that >>>>>> >> every generic algorithm that performs comparisons and can take >>>>>> >> floating >>>>>> >> point arguments would have to be specialized to account for floating >>>>>> >> point >>>>>> >> -0 != +0 (`index(of:)` being the previous example). This appears to >>>>>> >> defeat >>>>>> >> the aim of trying to accommodate FP at all in this revised design for >>>>>> >> Comparables. >>>>>> > >>>>>> > Yes, that would be a disaster, generically speaking. >>>>>> > >>>>>> >> The argument for `-0 === +0` is that -0 and +0 should be equivalent >>>>>> >> when >>>>>> >> substituted for every comparison operation. For FP operations, you'd >>>>>> >> continue to test (as you have to test now) `a == b && a.sign == >>>>>> >> b.sign` if >>>>>> >> you cared about the sign of zero. For non-FP arithmetic operations, >>>>>> >> hmm, >>>>>> >> not sure how to square that circle. >>>>>> > >>>>>> > I followed all of this... except, what are you getting at with that >>>>>> > last >>>>>> > sentence? >>>>>> > >>>>>> > -- >>>>>> > Dave >>>>>> > _______________________________________________ >>>>>> > 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 >>>> >>> >> >> >> _______________________________________________ >> 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
_______________________________________________ swift-evolution mailing list swift-evolution@swift.org https://lists.swift.org/mailman/listinfo/swift-evolution
