On Mon, Jul 25, 2016 at 1:26 PM, Stephen Canon via swift-evolution < swift-evolution@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@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:* Formalized ordering by pyrtsa · Pull Request #464 · apple/swift-evolution · GitHub
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 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>
)
1. There is no way to use Comparable.compare as a higher-order
function in a non-generic context.
2. 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.
3. 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@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution
