[swift-evolution] [Proposal] Formalized Ordering, take 2
Pyry Jahkola
pyry.jahkola at iki.fi
Mon Jul 25 06:41:33 CDT 2016
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>
}
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160725/dfdcc37f/attachment.html>
More information about the swift-evolution
mailing list