[swift-evolution] [Proposal] Formalized Ordering, take 2
Stephen Canon
scanon at apple.com
Mon Jul 25 13:52:46 CDT 2016
First, this is orthogonal to "adhering to the standard". isTotallyOrdered( ) provides the total order predicate required by IEEE 754. The standard has no opinion about whether or not `<=>` is bound to that predicate.
Personally, I would be OK with using the `isTotallyOrdered` semantics for `<=>`. However, it leads to some behavior that would be surprising for novices: x is NaN, and a set S is { 1, 2, NaN }, but S does not contain x. I am skeptical that the distinction between NaN payloads is salient *for generic code written on Comparable types*. It *is* salient for some (rare!) floating-point specific code, but `isTotallyOrdered` is available for floating-point types.
There’s also the issue that if we want to be able to point at IEEE 754 and say “<=> implements a total order on Level N”, distinguishing distinct NaNs has consequences for other values. In particular, it means that a decimal type should distinguish between 1e0 and 10e-1, because it would necessarily be an ordering on level 3 or 4. For { 1, 20 } to not contain 2e1 seems highly dubious to me.
– Steve
> On Jul 25, 2016, at 2:23 PM, Nevin Brackett-Rozinsky <nevin.brackettrozinsky at gmail.com> wrote:
>
> Pyry, this proposal looks great to me. My one question is, will I be able to write `someCollection.sort(.ascending)` and get the expected result? (This could be an additive future direction.)
>
> Stephen, what is your rationale for wanting `<=>` to identify NaN values with different payloads as `.equal`?
>
> I believe the IEEE 754 total order specification uses the bit-pattern just as Pyry’s proposal does, and there is value is adhering to the standard. Besides, if someone intentionally wishes to consider all NaN values as equivalent they can use `.isNaN` (or even map them to .nan first for uniformity).
>
> Nevin
>
>
> On Mon, Jul 25, 2016 at 1:26 PM, Stephen Canon via swift-evolution <swift-evolution at swift.org <mailto:swift-evolution at swift.org>> wrote:
> Hi Pyry —
>
> Dave and I spent some time discussing the details of how this applies to floating point earlier today. We’re now in agreement that <=> should treat -0 and +0 as distinct, and treat all NaNs as .equal. There are three motivating considerations:
>
> 1. Although -0 and +0 are “IEEE 754 equal”, there is no computation that can produce both of them. In the parlance of IEEE 754, for any rounding mode, the sets of real values that round to them are disjoint. Because of this, if -0 and +0 appear as members of a set, or as keys in a dictionary, they necessarily are the result of distinct computations or data.
>
> 2. Substitutability. Adopting these semantics means that if `x <=> y` is `.equal`, `f(x) <=> f(y)` is also `.equal` for any computation `f(x)` that depends on the represented value (as opposed to the encoding) of its argument.
>
> 3. 754 defines four “specification levels”, or models:
>
> - Level 1: The two-point compactification of the reals, or “extended real numbers”.
> - Level 2: The set of representable floating-point data: {-inf … -0} union { 0 … inf } union { NaN }.
> - Level 3: The set of representations of floating-point data: sign-exponent-significand triples, +/-inf, qNaN, sNaN.
> - Level 4: Floating-point encodings (bit patterns).
>
> The `<=>` semantics we propose constitute a total order on level 2, which is the computable model closest to the (reasonably familiar) extended real numbers. Treating -0 and +0 as .equal would put us in a bit of a no-man’s land between levels 1 and 2.
>
> Thanks,
> – Steve
>
>> On Jul 25, 2016, at 7:41 AM, Pyry Jahkola <pyry.jahkola at iki.fi <mailto:pyry.jahkola at iki.fi>> wrote:
>>
>> Since we're running short on time, and the previous discussion thread diverged, here's my attempt to fix the Comparable protocol.
>>
>> Pull request: https://github.com/apple/swift-evolution/pull/464 <https://github.com/apple/swift-evolution/pull/464>
>>
>> TL;DR:
>>
>> 1. Equatable remains unchanged, while Comparable bloats a bit to support several use cases.
>> 2. `a <=> b` is well-defined even if either value is NaN. Zero is equal to minus zero.
>> 3. Types are not strictly required to become totally ordered, even if it's strongly recommended.
>>
>> — — —
>>
>> I simply can't see how a pure total order version of Comparable would fit the standard way floating point values are expected to behave. However, I think we can reach a satisfactory conclusion, one that involves no crashing in the standard library, which is what I previously suggested.
>>
>> What I'm trying to fix is so that all operations listed in https://dl.dropboxusercontent.com/u/217402/Comparable.pdf <https://dl.dropboxusercontent.com/u/217402/Comparable.pdf> abide to laws for types without incomparable values, and that types with weaker order can still work in some well-defined way outside their totally ordered range.
>>
>> PS. Forgive me Robert, Jaden, and Harlan for not syncing with you, for time is tight. I can pull back or revise the proposal if you don't want to be involved.
>>
>> — Pyry
>>
>>
>>
>>
>> Formalized Ordering
>>
>> Proposal: SE-NNNN <https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-filename.md>
>> Authors: Robert Widmann <https://github.com/codafi>, Jaden Geller <https://github.com/jadengeller>, Harlan Haskins <https://github.com/harlanhaskins>, Pyry Jahkola <https://github.com/pyrtsa>
>> Status: Awaiting review
>> Review manager: TBD
>> <https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#introduction>Introduction
>>
>> This proposal cleans up the semantics of ordering relations in the standard library. Our goal is to formalize the total ordering semantics of the Comparable protocol and still provide accessible ordering definitions for types without total ordering semantics.
>>
>> <https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#motivation>Motivation
>>
>> The standard comparison operators have an intuitive meaning to programmers. Swift encourages encoding that in an implementation of Comparable that respects the rules of a total order <https://en.wikipedia.org/wiki/Total_order>. The standard library takes advantage of these rules to provide consistent implementations for sorting and searching generic collections of Comparable types.
>>
>> Not all types behave so well in this framework, unfortunately. There are cases where the semantics of a total order cannot apply and still maintain the traditional definition of “comparison” over these types. Take, for example, sorting an array of Float s. Today, Float ‘s instance of Comparable follows IEEE-754 and returns false for all comparisons of NaN . In order to sort this array, NaN s are considered outside the domain of < , and the order of a “sorted” array containing them is undefined.
>>
>> In addition, generic algorithms in the Swift Standard Library that make use of the current Comparable protocol may have to make twice as many comparisons to request the ordering of values with respect to each other than they should. Having a central operation to return information about the ordering of values once should provide a speedup for these operations.
>>
>> In the interest of cleaning up the semantics of Comparable types of all shapes and sizes and their uses in the Swift Standard Library, this proposal is going to re-arrange the requirements of the Comparable and Equatable protocols.
>>
>> <https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#proposed-solution>Proposed solution
>>
>> <https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#equatable>Equatable
>>
>> The interface of Equatable remains unchanged under this proposal. Equatable types should still respect the equivalence laws of reflexivity (a == a), symmetry (a == b iff b == a), and transitivity (if a == b and b == c, then a == c). Further, != remains a top-level binary operator for which a != b iff !(a == b).
>>
>> Types containing properties inessential to equality, however, are allowed to retain their notion of identity. For example Array's capacity isn't considered for equality; and -0.0 == 0.0 and "ä" == "a\u{308}", while (-0.0).sign != (0.0).sign and "ä".utf8.count != "a\u{308}".utf8.count.
>>
>> IEEE-754 floating point numbers are allowed to break the reflexivity law by defining that .nan != x for any value of x, which is the standard behaviour documented in IEEE-754 and implemented the same way in other programming languages.
>>
>> <https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#comparable>Comparable
>>
>> The Comparable protocol will now require (without default implementation provided) a single operator definition: <=> — the comparison operator. From this, all other comparison operators will be derived so as to respect the total order semantics of Comparable:
>>
>> To maintain compatibility with IEEE-754, the interface of Comparable also contains as customization points the operators <, <=, and == (derived from Equatable) as well as the static binary functions _min(_:_:) and _max(_:_:). User-defined types are recommended against overriding the default implementations.
>>
>> The uncustomizable top-level binary comparison operators a > b and a >= b are implemented as synonyms to b < aand b <= a, respectively.
>>
>> <https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#standard-library>Standard Library
>>
>> Unlike a previous revision of this proposal, standard library algorithms specific to FloatingPoint remain unchanged.
>>
>> Overloads of <=> for tuples of Comparable elements are provided up to a library-defined arity.
>>
>> The intent of this proposal is to later augment the standard library so that functions that take an ordering predicate by: (T, T) -> Bool will have an overload ordering: (T, T) -> Ordering that will provide a — potentially — more efficient implementation. A list of such functions is provided in Future directions.
>>
>> <https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#detailed-design>Detailed design
>>
>> The Comparable protocol will be amended by taking away > and >=, adding customisation points _min(_:_:), and _max(_:_:), and introducing the ordering operator <=> that makes use of the Ordering enum defined below.
>>
>> enum Ordering : Equatable {
>> case ascending
>> case equal
>> case descending
>> }
>>
>> infix operator <=> { associativity none precedence 130 }
>>
>> public protocol Comparable : Equatable {
>> // Implementation required:
>> static func <=>(lhs: Self, rhs: Self) -> Ordering
>>
>> // Default implementations provided:
>> static func == (lhs: Self, rhs: Self) -> Bool // derived from Equatable
>> static func < (lhs: Self, rhs: Self) -> Bool
>> static func <= (lhs: Self, rhs: Self) -> Bool
>> static func _min(_ lhs: Self, _ rhs: Self) -> Self
>> static func _max(_ lhs: Self, _ rhs: Self) -> Self
>> }
>> The <=> operator defines a relationship between == and <=> such that a == b iff (a <=> b) == .equal, unless Self chooses to break the semantics in the way of IEEE-754. Likewise, it should hold that (a <=> b) == .ascending iff a < b, and (a <=> b) != .descending iff a <= b.
>>
>> The _min(_:_:) and _max(_:_:) functions should return the lesser or greater of the two operands, respectively, while in case of equal arguments, _min(_:_:) should favour the left-hand side and _max(_:_:) the right-hand side to retain identity, as presently explained in this comment <https://github.com/apple/swift/blob/4614adc16168d612b6fc7e7a161dd5b6b34be704/stdlib/public/core/Algorithm.swift#L17-L20>. Making them customization points of Comparable, we get to fix their behaviour in the presense of unorderable values (SR-1011 <https://bugs.swift.org/browse/SR-1011>).
>>
>> Most user types should only implement <=> and leave the other members of Equatable and Comparable to their default implementations. Note that even == has a sane default implementation if Self is made Comparable:
>>
>> // Default implementations, which should be used for most Comparable types:
>> extension Comparable {
>> static func == (l: Self, r: Self) -> Bool { return (l <=> r) == .equal }
>> static func < (l: Self, r: Self) -> Bool { return (l <=> r) == .ascending }
>> static func <= (l: Self, r: Self) -> Bool { return (l <=> r) != .descending }
>> static func _min(_ l: Self, _ r: Self) -> Self { return r < l ? r : l }
>> static func _max(_ l: Self, _ r: Self) -> Self { return r < l ? l : r }
>> }
>>
>> // Unoverridable top-level operators and functions for Comparable:
>> public func > <T : Comparable>(l: T, r: T) -> Bool { return r < l }
>> public func >= <T : Comparable>(l: T, r: T) -> Bool { return r <= l }
>> public func min<T : Comparable>(_ l: T, _ r: T) -> T { return T._min(l, r) }
>> public func max<T : Comparable>(_ l: T, _ r: T) -> T { return T._max(l, r) }
>> <https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#handling-of-floating-point-comparisons>Handling of floating point comparisons
>>
>> The following text is written in terms of Double but other floating-point types (Float, Float80) are proposed the same treatment.
>>
>> The IEEE-754 floating point specification has two oddities when it comes to orderability: there are two zeros (0.0 and -0.0) which are considered equal to each other, and there are multiple not-a-number values x for which x.isNaN == true and x != y with any value of y, even x itself. (Remark: the most common NaN value is obtained by the static property Double.nan.)
>>
>> The interface of Comparable is designed so that <=> alone is able to produce a total order among all possible Doublevalues, sorting negative NaNs less than any other values, and positive NaNs greater than any other. Otherwise, within the range of totally ordered floating point values, -Double.infinity ... Double.infinity, the result of a <=> b remains in full agreement with the laws of a < b, a <= b, and a == b.
>>
>> The suggested implementation of Double : Comparable makes <=> distinguish between every different bitPatternof NaN:
>>
>> extension Double : Comparable {
>> public static func <=> (l: Double, r: Double) -> Ordering {
>> func ordinal(_ x: UInt64) -> UInt64 {
>> return x < 0x80000000_00000000 ? x + 0x7fffffff_ffffffff : ~x
>> }
>> return ordinal(l.bitPattern) <=> ordinal(r.bitPattern)
>> }
>> public static func == (l: Double, r: Double) -> Bool { return Builtin.eq(l, r) }
>> public static func < (l: Double, r: Double) -> Bool { return Builtin.lt(l, r) }
>> public static func <= (l: Double, r: Double) -> Bool { return Builtin.le(l, r) }
>> public static func _min(l: Double, r: Double) -> Double { return Builtin.fmin(l, r) }
>> public static func _max(l: Double, r: Double) -> Double { return Builtin.fmax(l, r) }
>> }
>>
>> // Likewise:
>> extension Float : Comparable { ... }
>> extension Float80 : Comparable { ... }
>> <https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#tuples-and-order-reversal>Tuples and order reversal
>>
>> Due to missing language support, tuples of Comparable elements cannot be Comparable themselves, but in the spirit of SE-0015 <https://github.com/apple/swift-evolution/blob/master/proposals/0015-tuple-comparison-operators.md>, such tuples are given their overloads of <=> up to a standard library defined maximum arity:
>>
>> public func <=> <A : Comparable, B : Comparable>(lhs: (A, B), rhs: (A, B)) -> Ordering {
>> let a = lhs.0 <=> rhs.0
>> if a != .equal { return a }
>> let b = lhs.1 <=> rhs.1
>> if b != .equal { return b }
>> return .equal
>> }
>>
>> // Similarly for <A : Comparable, B : Comparable, C : Comparable>, etc.
>> To simplify the reversal of a given ordering operation, two members of Ordering are provided in an extension:
>>
>> extension Ordering {
>> public static func reversing<T : Comparable>(_ ordering: (T, T) -> Ordering)
>> -> (T, T) -> Ordering
>> {
>> return { l, r in ordering(r, l) }
>> }
>>
>> public var reversed: Ordering {
>> switch self {
>> case .ascending: return .descending
>> case .equal: return .equal
>> case .descending: return .ascending
>> }
>> }
>> }
>> <https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#foundation>Foundation
>>
>> In addition, Foundation code will now bridge NSComparisonResult to Ordering allowing for a fluid, natural, and safe API.
>>
>> <https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#impact-on-existing-code>Impact on existing code
>>
>> The biggest drawback of the proposed design is the large surface area of Comparable's interface, as well as the possibility of overriding the comparison operators by mistake. On the other hand, since the required <=> operator is new and affects all users porting their previously Comparable data types to Swift 3, we can use documentation to suggest removing the redundant (and possibly faulty) implementations of other comparison operators.
>>
>> Existing Equatable but not Comparable types that define an equivalence relation with == will remain unchanged.
>>
>> Existing Comparable types that define a total ordering with < will need to implement <=> and should remove their existing implementation of any comparison operators, including ==. All other existing Comparable types should implement <=> that provides a total ordering, or should drop their Comparable conformance.
>>
>> Before:
>>
>> struct Date: Comparable {
>> let year: Int
>> let month: Int
>> let day: Int
>> }
>>
>> func ==(lhs: Date, rhs: Date) -> Bool {
>> return lhs.year == rhs.year
>> && lhs.month == rhs.month
>> && lhs.day == rhs.day
>> }
>>
>> func <(lhs: Date, rhs: Date) -> Bool {
>> if lhs.year != rhs.year {
>> return lhs.year < rhs.year
>> } else if lhs.month != rhs.month {
>> return lhs.month < rhs.month
>> } else {
>> return lhs.day < rhs.day
>> }
>> }
>> After, using the tuple overload of <=>:
>>
>> struct Date: Comparable {
>> let year: Int
>> let month: Int
>> let day: Int
>>
>> static func <=> (lhs: Date, rhs: Date) -> Ordering {
>> return (lhs.year, lhs.month, lhs.day)
>> <=> (rhs.year, rhs.month, rhs.day)
>> }
>>
>> // // Explicit version:
>> // static func <=> (lhs: Date, rhs: Date) -> Ordering {
>> // let yearResult = lhs.year <=> rhs.year
>> // guard case .equal = yearResult else { return yearResult }
>> // let monthResult = lhs.month <=> rhs.month
>> // guard case .equal = monthResult else { return monthResult }
>> // return lhs.day <=> rhs.day
>> // }
>> }
>> <https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#alternatives-considered>Alternatives considered
>>
>> A previous design of this proposal suggested a strict total order upon Comparable. While that would make generic algorithms more correct, the definition ended up fighting against the expected behaviour of floating point numbers.
>>
>> An alternative design that better matches the existing arithmetic-related protocols in Swift is one that uses a member function.
>>
>> public protocol Comparable: Equatable {
>> func compare(to: Self) -> Ordering
>> }
>> However, while this API does read better than an operator, we believe that this imposes a number of artificial restrictions (especially in light of SE-0091 <https://github.com/apple/swift-evolution/blob/master/proposals/0091-improving-operators-in-protocols.md>)
>>
>> There is no way to use Comparable.compare as a higher-order function in a non-generic context.
>> If a member is desired, it can be provided in a protocol extension and defined in terms of the ordering operator; to each according to their need.
>> The existing tuple overloads cannot be expressed with a member function.
>> One other that Rust has adopted is the inclusion of PartialEquatable and PartialComparable as ancestors of their flavor of Equatable and Comparable . Having protocols to organize and catalogue types that can only guarantee partial equivalence and ordering relations is a good approach for modularity but clutters the standard library with two new protocols for which few useful algorithms could be written against.
>>
>> <https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#future-directions>Future directions
>>
>> That the default sort() compares by < and not <=> should be considered a bug to be fixed in a future version of Swift. Using <=> will make sort() well-behaved in the presense of NaN. However, given that the current behaviour is to produce an unspecified order, the fix is additive and can be slipped past Swift 3.
>>
>> With <=> in place, several present and future standard library algorithms involving a <T : Comparable> requirement will possibly benefit from knowing the total ordering of two operands at once. This is a list of possible such functions (taking Array as example), to be proposed separately as an additive change:
>>
>> extension Array {
>> // Sorting
>>
>> mutating func sort(ordering: @noescape (Element, Element) throws -> Ordering) rethrows
>> func sorted(ordering: @noescape (Element, Element) throws -> Ordering) rethrows -> [Element]
>> mutating func stableSort(ordering: @noescape (Element, Element) throws -> Ordering) rethrows
>> func stableSorted(ordering: @noescape (Element, Element) throws -> Ordering) rethrows -> [Element]
>>
>> /// Reorders the elements of the collection such that all the elements
>> /// returning `.ascending` are moved to the start of the collection, and the
>> /// elements returning `.descending` are moved to the end of the collection.
>> /// - Returns: the range of elements for which `ordering(x) == .equal`.
>> mutating func partition(ordering: @noescape (Iterator.Element) throws -> Ordering) rethrows -> Range<Index>
>>
>> // Binary search
>>
>> func bisectedIndex(ordering: @noescape (Element) throws -> Ordering) rethrows -> Index?
>> func lowerBound(ordering: @noescape (Element) throws -> Ordering) rethrows -> Index
>> func upperBound(ordering: @noescape (Element) throws -> Ordering) rethrows -> Index
>> func equalRange(ordering: @noescape (Element) throws -> Ordering) rethrows -> Range<Index>
>> }
>>
>
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org <mailto:swift-evolution at swift.org>
> https://lists.swift.org/mailman/listinfo/swift-evolution <https://lists.swift.org/mailman/listinfo/swift-evolution>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160725/7a7e2f43/attachment-0001.html>
More information about the swift-evolution
mailing list