[pitch] Comparison Reform


(Ben Cohen) #1

Hi swift evolution,

Here’s another pitch, for The Propoosal Formerly Known As Spaceship.
Comparison Reform

Proposal: SE-NNNN <file:///Users/ben_cohen/Documents/swift-evolution/proposals/NNNN-filename.md>
Authors: Robert Widmann <https://github.com/codafi>, Jaden Geller <https://github.com/jadengeller>, Harlan Haskins <https://github.com/harlanhaskins>, Alexis Beingessner <https://github.com/Gankro>, Ben Cohen <https://github.com/airspeedswift>
Status: Awaiting review
Review manager: TBD
Introduction

This proposal is for changes that we believe should be made to the existing comparison system by:

Making FloatingPoint comparison context sensitive, so that its Comparable conformance provides a proper total ordering.
Introducing a new ternary-valued compare(_ other: Self) -> ComparisonResult method.
Removing unnecessary customization points from Comparable.
Motivation

The motivation comes from several independent points:

1: 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 while still maintaining the traditional definition of “comparison” for these types. Take, for example, sorting an array of Floats. 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 unspecified. Similarly, a Dictionary keyed off floats can leak entries and memory.

2: Generic algorithms in the Swift Standard Library that make use of the current Comparable protocol may have to make extra comparisons to determine the ordering of values when <, ==, and > should have different behaviours. Having a central operation to return complete ordering information should provide a speedup for these operations.

3: The existing comparison operators don’t “generalize” well. There’s no clean way to add a third or fourth argument to < to ask for non-default semantics. An example where this would be desirable would be specifying the locale or case-sensitivity when comparing Strings.

4: Comparable is over-engineered in the customization points it provides: to our knowledge, there’s no good reason to ever override >=, >, or <=. Each customization point bloats vtables and mandates additional dynamic dispatch.

5: When quickly writing a Comparable type, it is easier to implement a single ternary statement than to separately implement == and <.

Proposed solution

ComparisonResult

Foundation’s ComparisonResult type will be mapped into Swift as

@objc public enum ComparisonResult : Int {
  case orderedAscending = -1
  case orderedSame = 0
  case orderedDescending = 1
}
Comparable

Comparable will be changed to have a new ternary comparison method: compare(_ other: Self) -> ComparisonResult. x.compare(y) specifies where to place x relative to y. So if it yields .orderedAscending, then x comes before y. This will be considered the new “main” dispatch point of Comparable that implementors should provide.

Most code will continue to use < or ==, as it will be optimal for their purposes. However code that needs to make a three-way branch on comparison can use the potentially more efficient compare. Note that compare is only expected to be more efficient in this specific case. If a two-way branch is all that’s being done, < will be more efficient in many cases (if only because it’s easier for the optimizer).

For backwards compatibility reasons, compare will have a default implementation defined in terms of <, but to enable only using compare, < and == will also have default implementations in terms of compare.

The compiler will verify that either compare, or < and ==, are provided by every type that claims to conform to Comparable. This will be done in some unspecified way unavailable outside the standard library (it can be made available to in the future, but that’s an unnecessary distraction for this proposal).

Types that wish to provide comparison “variants” can do so naturally by adding compare methods with additional arguments. e.g. String.compare(_ other: Self, in: Locale) -> ComparisonResult. These have no language-level connection to Comparable, but are still syntactically connected, implying the same total order semantics. This makes them easier to discover, learn, and migrate to.

To reduce bloat, the operators <=, >=, and > will be removed from the set of requirements that the Comparable protocol declares. These operators will however continue to exist with the current default implementations.

FloatingPoint

No changes will be made to the FloatingPoint protocol itself. Instead, new extensions will be added to it to change the behaviour of comparison.

The new behaviour centers around the fact that compare(_: Self) -> ComparisonResult will provide a total ordering that’s consistent with Level 2 in the IEEE 754 (2008) spec. This is mostly the same as the standard (Level 1) IEEE ordering, except:

-0 < +0
NaN == NaN
NaN > +Inf (an arbitrary choice, NaN can be placed anywhere in the number line)
Level 2’s distinguishing of -0 and +0 is a bit strange, but is consistent with Equatable’s Substitutability requirement. -0 and +0 have different behaviours: 1/-0 = -Inf while 1/+0 = +Inf. The main problem this can lead to is that a keyed collection may have two “0” entries. In practice this probably won’t be a problem because it’s fairly difficult for the same algorithm to produce both -0 and +0. Any algorithm that does is also probably concerned with the fact that 1.0E-128 and 2.0E-128 are considered distinct values.

Note: IEEE specifies several other potential total orderings: level 3, level 4, and the totalOrder predicate. For our purposes, these orderings are too aggressive in distinguishing values that are semantically equivalent in Swift. For most cases, the relevant issue is that they distinguish different encodings of NaN. For more exotic encodings that don’t guarantee normalization, these predicates also consider 10.0e0 < 1.0e1 to be true. An example where this can occur is IEEE-754 decimal coded floating point, which FloatingPoint is intended to support.

We will then make the comparison operators (<, <=, ==, !=, >=, >) dispatch to one of compare(_:slight_smile: or FloatingPoint’s IEEE comparison methods (isLess, isEqual, isLessThanOrEqualTo) based on the context.

If the context knows the type is FloatingPoint, then level 1 ordering will be used.
If the context only knows the type is Comparable or Equatable, then level 2 ordering will be used.
This results in code that is explicitly designed to work with FloatingPoint types getting the expected IEEE behaviour, while code that is only designed to work with Comparable types (e.g. sort and Dictionary) gets more reasonable total ordering behaviour.

To clarify: Dictionary and sort won’t somehow detect that they’re being used with FloatingPoint types and use level 1 comparisons. Instead they will unconditional use level 2 behaviour. For example:

let nan = 0.0/0.0

func printEqual<T: Equatable>(_ x: T, _ y: T) {
  print(x == y)
}

func printEqualFloats<T: FloatingPoint>(_ x: T, _ y: T) {
  print(x == y)
}

print(nan == nan) // false, (concrete)
printEqual(nan, nan) // true, (generic Equatable but not FloatingPoint)
printEqualFloats(nan, nan) // false, (generic FloatingPoint)
If one wishes to have a method that works with all Equatable/Comparable types, but uses level 1 semantics for FloatingPoint types, then they can simply provide two identical implementations that differ only in the bounds:

let nan = 0.0/0.0

func printEqual<T: Equatable>(_ x: T, _ y: T) {
  print(x == y)
}

func printEqual<T: FloatingPoint>(_ x: T, _ y: T) {
  print(x == y)
}

printEqual(0, 0) // true (integers use `<T: Equatable>` overload)
printEqual(nan, nan) // false (floats use `<T: FloatingPoint>` overload)
As a result of this change, hashing of floats must be updated to make all NaNs hash equally. -0 and +0 will also no longer be expected to hash equally. (Although they might as an implementation detail – equal values must hash the same, unequal values may hash the same.)

Misc Standard Library

Types that conform to Comparable should be audited for places where implementing or using Comparable would be a win. This update can be done incrementally, as the only potential impact should be performance. As an example, a default implementation of compare(_:slight_smile: for Array will likely be suboptimal, performing two linear scans to determine the result in the worst-case. (See the default implementation provided in the detailed design.)

Some free functions will have <T: FloatingPoint> overloads to better align with IEEE-754 semantics. This will be addressed in a follow-up proposal. (example: min and max)

Detailed Design

The protocols will be changed as follows:

ComparisonResult, currently a type found in Foundation, will be sunk into the Swift Standard Library:

@objc public enum ComparisonResult: Int, Equatable {
  case orderedAscending = -1
  case orderedSame = 0
  case orderedDescending = 1
}

public protocol Comparable: Equatable {
  func compare(_ other: Self) -> ComparisonResult

  static func < (lhs: Self, rhs: Self) -> Bool
}

extension Comparable {
  func compare(_ other: Self) -> ComparisonResult {
    if self == other {
      return .orderedSame
    } else if self < other {
      return .orderedAscending
    } else {
      return .orderedDescending
    }
  }
}

public func < <T: Comparable>(lhs: T, rhs: T) -> Bool {
  return lhs.compare(rhs) == .orderedAscending
}

// IEEE comparison operators (these implementations already exist in std)
extension FloatingPoint {
  public static func == (lhs: T, rhs: T) -> Bool {
    return lhs.isEqual(to: rhs)
  }

  public static func < (lhs: T, rhs: T) -> Bool {
    return lhs.isLess(than: rhs)
  }

  public static func <= (lhs: T, rhs: T) -> Bool {
    return lhs.isLessThanOrEqualTo(rhs)
  }

  public static func > (lhs: T, rhs: T) -> Bool {
    return rhs.isLess(than: lhs)
  }

  public static func >= (lhs: T, rhs: T) -> Bool {
    return rhs.isLessThanOrEqualTo(lhs)
  }
}

// Comparable comparison operators (provides a total ordering)
extension FloatingPoint {
  @_inline
  public func compare(_ other: Self) -> ComparisonResult {
    // Can potentially be implemented more efficiently -- this is just the clearest version
    if self.isLess(than: other) {
      return .orderedAscending
    } else if other.isLess(than: self) {
      return .orderedDescending
    } else {
      // Special cases

      // -0 < +0
      if self.isZero && other.isZero {
        // .plus == 0 and .minus == 1, so flip ordering to get - < +
        return (other.sign as Int).compare(self.sign as Int)
      }

      // NaN == NaN, NaN > +Inf
      if self.isNaN {
        if other.isNaN {
          return .orderedSame
        } else {
          return .orderedDescending
        }
      } else if other.isNaN {
        return .orderedAscending
      }

      // Otherwise equality agrees with normal IEEE
      return .orderedSame
    }
  }

  @_implements(Equatable.==)
  public static func _comparableEqual(lhs: Self, rhs: Self) -> Bool {
    lhs.compare(rhs) == .orderedSame
  }

  @_implements(Comparable.<)
  public static func _comparableLessThan(lhs: Self, rhs: Self) -> Bool {
    lhs.compare(rhs) == .orderedDescending
  }
}
Note that this design mandates changes to the compiler:

@_implements (or an equivalent mechanism) must be implemented to get the context-sensitive FloatingPoint behaviour.
The compiler must verify that either == and <, or compare(_:slight_smile: is overridden by every type that conforms to Comparable.
Source compatibility

Users of ComparisonResult will be able to use it as normal once it becomes a standard library type.

Existing implementors of Comparable will be unaffected, though they should consider implementing the new compare method as the default implementation may be suboptimal.

Consumers of Comparable will be unaffected, though they should consider calling the compare method if it offers a performance advantage for their particular algorithm.

Existing implementors of FloatingPoint should be unaffected – they will automatically get the new behaviour as long as they aren’t manually implementing the requirements of Equatable/Comparable.

Existing code that works with floats may break if it’s relying on some code bounded on <T: Equatable/Comparable>providing IEEE semantics. For most algorithms, NaNs would essentially lead to unspecified behaviour, so the primary concern is whether -0.0 == +0.0 matters.

ABI stability

This must be implemented before ABI stability is declared.

Effect on API resilience

N/A

Alternatives Considered

Spaceship

Early versions of this proposal aimed to instead provide a <=> operator in place of compare. The only reason we moved away from this was that it didn’t solve the problem that comparison didn’t generalize.

Spaceship as an operator has a two concrete benefits over compare today:

It can be passed to a higher-order function
Tuples can implement it
In our opinion, these aren’t serious problems, especially in the long term.

Passing <=> as a higher order function basically allows types that aren’t Comparable, but do provide <=>, to be very ergonomically handled by algorithms which take an optional ordering function. Types which provide the comparable operators but don’t conform to Comparable are only pervasive due to the absence of conditional conformance. We shouldn’t be designing our APIs around the assumption that conditional conformance doesn’t exist.

When conditional conformance is implemented, the only should-be-comparable-but-aren’t types that will remain are tuples, which we should potentially have the compiler synthesize conformances for.

Similarly, it should one day be possible to extend tuples, although this is a more “far future” matter. Until then, the (T, T) -> Bool predicate will always also be available, and < can be used there with the only downside being a potential performance hit.

Just Leave Floats Alone

The fact that sorting floats leads to a mess, and storing floats can lead to memory leaks and data loss isn’t acceptable.

Just Make Floats Only Have A Total Order

This was deemed too surprising for anyone familiar with floats from any other language. It would also probably break a lot more code than this change will.

Just Make Floats Not Comparable

Although floats are more subtle than integers, having places where integers work but floats don’t is a poor state of affairs. One should be able to sort an array of floats and use floats as keys in data structures, even if the latter is difficult to do correctly.

PartialComparable

PartialComparable would essentially just be Comparable without any stated ordering requirements, that Comparable extends to provide ordering requirements. This would be a protocol that standard IEEE comparison could satisfy, but in the absence of total ordering requirements, PartialComparable is effectively useless. Either everyone would consume PartialComparable (to accept floats) or Comparable (to have reasonable behaviour).

The Rust community adopted this strategy to little benefit. The Rust libs team has frequently considered removing the distinction, but hasn’t because doing it backwards compatibly would be complicated. Also because merging the two would just lead to the problems Swift has today.

Different Names For compare and ComparisonResult

A few different variants for ComparisonResult and its variants were considered:

Dropping the ordered part of ComparisonResult’s cases e.g. .ascending
Naming of ComparisonResult as SortOrder
enum Ordering { case less, equal, greater } (as used by Rust <https://doc.rust-lang.org/std/cmp/enum.Ordering.html>)
Case values of inOrder, same, outOfOrder
The choice of case names is non-trivial because the enum shows up in different contexts where different names makes more sense. Effectively, one needs to keep in mind that the “default” sort order is ascending to map between the concept of “before” and “less”.

The before/after naming to provide the most intuitive model for custom sorts – referring to ascending or less is confusing when trying to implement a descending ordering. Similarly the inOrder/outOfOrder naming was too indirect – it’s more natural to just say where to put the element. If the enum should focus on the sorting case, calling it SortOrder would help to emphasize this fact.

This proposal elects to leave the existing Foundation name in-place. The primary motivation for this is that use of the compare function will be relatively rare. It is expected that in most cases users will continue to make use of == or <, returning boolean values (the main exception to this will be in use of the parameterized String comparisons). As such, the source compatibility consequences of introducing naming changes to an existing type seems of insufficient benefit.

The method compare(_:slight_smile: does not fully comport with the API naming guidelines. However, it is firmly established with current usage in Objective-C APIs, will be fairly rarely seen/used (users will usually prefer <, == etc), and alternatives considered, for example compared(to:), were not a significant improvement.

Add Overloads for (T, T) -> ComparisonResult

It would be slightly more ergonomic to work with ComparisonResult if existing methods that took an ordering predicate also had an overload for (T, T) -> ComparisonResult. As it stands, a case-insensitive sort must be written as follows:

myStrings.sort { $0.compare(_ other: $1, case: .insensitive) == .orderedAscending }
With the overload, one could write:

myStrings.sort { $0.compare($1, case: .insensitive) }
we decided against providing these overloads because:

The existing algorithms in the standard library can’t benefit from them (only binary comparisons).
They bloat up the standard library (and any library which intends to match our API guidelines).
They potentially introduce confusion over “which” comparison overload to use.
And because we can change our mind later without concern for source or ABI stability, as these overloads would be additive.

Future Work

This section covers some topics which were briefly considered, but were identified as reasonable and possible to defer to future releases. Specifically they should be backwards compatible to introduce even after ABI stability. Two paths that are worth exploring:

Ergonomic Generalized Comparison for Keyed Containers

Can we make it ergonomic to use an (arbitrary) alternative comparison strategy for a Dictionary or a BinaryTree? Should they be type-level Comparators, or should those types always store a (Key, Key) -> ComparisonResult closure?

We can avoid answering this question because Dictionary is expected to keep a relatively opaque (resilient) ABI for the foreseeable future, as many interesting optimizations will change its internal layout. Although if the answer is type-level, then Default Generic Parameters must be accepted to proceed down this path.

ComparisonResult Conveniences

There are a few conveniences we could consider providing to make ComparisonResult more ergonomic to manipulate. Such as:

// A way to combine orderings
func ComparisonResult.breakingTiesWith(_ order: () -> ComparisonResult) -> ComparisonResult

array.sort {
  $0.x.compare($0.y)
  .breakingTiesWith { $0.y.compare($1.y) }
  == .orderedAscending
}
and

var inverted: ComparisonResult

// A perhaps more "clear" way to express reversing order than `y.compared(to: x)`
x.compare(y).inverted
But these can all be added later once everyone has had a chance to use them.


Comparable and FloatingPoint types
(Ben Cohen) #2

Online copy here:

https://github.com/airspeedswift/swift-evolution/blob/fa007138a54895e94d22e053122ca24ffa0b2eeb/proposals/NNNN-ComparisonReform.md

···

On Apr 13, 2017, at 1:17 PM, Ben Cohen via swift-evolution <swift-evolution@swift.org> wrote:

Hi swift evolution,

Here’s another pitch, for The Propoosal Formerly Known As Spaceship.
Comparison Reform

Proposal: SE-NNNN <file:///Users/ben_cohen/Documents/swift-evolution/proposals/NNNN-filename.md>
Authors: Robert Widmann <https://github.com/codafi>, Jaden Geller <https://github.com/jadengeller>, Harlan Haskins <https://github.com/harlanhaskins>, Alexis Beingessner <https://github.com/Gankro>, Ben Cohen <https://github.com/airspeedswift>
Status: Awaiting review
Review manager: TBD
Introduction

This proposal is for changes that we believe should be made to the existing comparison system by:

Making FloatingPoint comparison context sensitive, so that its Comparable conformance provides a proper total ordering.
Introducing a new ternary-valued compare(_ other: Self) -> ComparisonResult method.
Removing unnecessary customization points from Comparable.
Motivation

The motivation comes from several independent points:

1: 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 while still maintaining the traditional definition of “comparison” for these types. Take, for example, sorting an array of Floats. 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 unspecified. Similarly, a Dictionary keyed off floats can leak entries and memory.

2: Generic algorithms in the Swift Standard Library that make use of the current Comparable protocol may have to make extra comparisons to determine the ordering of values when <, ==, and > should have different behaviours. Having a central operation to return complete ordering information should provide a speedup for these operations.

3: The existing comparison operators don’t “generalize” well. There’s no clean way to add a third or fourth argument to < to ask for non-default semantics. An example where this would be desirable would be specifying the locale or case-sensitivity when comparing Strings.

4: Comparable is over-engineered in the customization points it provides: to our knowledge, there’s no good reason to ever override >=, >, or <=. Each customization point bloats vtables and mandates additional dynamic dispatch.

5: When quickly writing a Comparable type, it is easier to implement a single ternary statement than to separately implement == and <.

Proposed solution

ComparisonResult

Foundation’s ComparisonResult type will be mapped into Swift as

@objc public enum ComparisonResult : Int {
  case orderedAscending = -1
  case orderedSame = 0
  case orderedDescending = 1
}
Comparable

Comparable will be changed to have a new ternary comparison method: compare(_ other: Self) -> ComparisonResult. x.compare(y) specifies where to place x relative to y. So if it yields .orderedAscending, then x comes before y. This will be considered the new “main” dispatch point of Comparable that implementors should provide.

Most code will continue to use < or ==, as it will be optimal for their purposes. However code that needs to make a three-way branch on comparison can use the potentially more efficient compare. Note that compare is only expected to be more efficient in this specific case. If a two-way branch is all that’s being done, < will be more efficient in many cases (if only because it’s easier for the optimizer).

For backwards compatibility reasons, compare will have a default implementation defined in terms of <, but to enable only using compare, < and == will also have default implementations in terms of compare.

The compiler will verify that either compare, or < and ==, are provided by every type that claims to conform to Comparable. This will be done in some unspecified way unavailable outside the standard library (it can be made available to in the future, but that’s an unnecessary distraction for this proposal).

Types that wish to provide comparison “variants” can do so naturally by adding compare methods with additional arguments. e.g. String.compare(_ other: Self, in: Locale) -> ComparisonResult. These have no language-level connection to Comparable, but are still syntactically connected, implying the same total order semantics. This makes them easier to discover, learn, and migrate to.

To reduce bloat, the operators <=, >=, and > will be removed from the set of requirements that the Comparable protocol declares. These operators will however continue to exist with the current default implementations.

FloatingPoint

No changes will be made to the FloatingPoint protocol itself. Instead, new extensions will be added to it to change the behaviour of comparison.

The new behaviour centers around the fact that compare(_: Self) -> ComparisonResult will provide a total ordering that’s consistent with Level 2 in the IEEE 754 (2008) spec. This is mostly the same as the standard (Level 1) IEEE ordering, except:

-0 < +0
NaN == NaN
NaN > +Inf (an arbitrary choice, NaN can be placed anywhere in the number line)
Level 2’s distinguishing of -0 and +0 is a bit strange, but is consistent with Equatable’s Substitutability requirement. -0 and +0 have different behaviours: 1/-0 = -Inf while 1/+0 = +Inf. The main problem this can lead to is that a keyed collection may have two “0” entries. In practice this probably won’t be a problem because it’s fairly difficult for the same algorithm to produce both -0 and +0. Any algorithm that does is also probably concerned with the fact that 1.0E-128 and 2.0E-128 are considered distinct values.

Note: IEEE specifies several other potential total orderings: level 3, level 4, and the totalOrder predicate. For our purposes, these orderings are too aggressive in distinguishing values that are semantically equivalent in Swift. For most cases, the relevant issue is that they distinguish different encodings of NaN. For more exotic encodings that don’t guarantee normalization, these predicates also consider 10.0e0 < 1.0e1 to be true. An example where this can occur is IEEE-754 decimal coded floating point, which FloatingPoint is intended to support.

We will then make the comparison operators (<, <=, ==, !=, >=, >) dispatch to one of compare(_:slight_smile: or FloatingPoint’s IEEE comparison methods (isLess, isEqual, isLessThanOrEqualTo) based on the context.

If the context knows the type is FloatingPoint, then level 1 ordering will be used.
If the context only knows the type is Comparable or Equatable, then level 2 ordering will be used.
This results in code that is explicitly designed to work with FloatingPoint types getting the expected IEEE behaviour, while code that is only designed to work with Comparable types (e.g. sort and Dictionary) gets more reasonable total ordering behaviour.

To clarify: Dictionary and sort won’t somehow detect that they’re being used with FloatingPoint types and use level 1 comparisons. Instead they will unconditional use level 2 behaviour. For example:

let nan = 0.0/0.0

func printEqual<T: Equatable>(_ x: T, _ y: T) {
  print(x == y)
}

func printEqualFloats<T: FloatingPoint>(_ x: T, _ y: T) {
  print(x == y)
}

print(nan == nan) // false, (concrete)
printEqual(nan, nan) // true, (generic Equatable but not FloatingPoint)
printEqualFloats(nan, nan) // false, (generic FloatingPoint)
If one wishes to have a method that works with all Equatable/Comparable types, but uses level 1 semantics for FloatingPoint types, then they can simply provide two identical implementations that differ only in the bounds:

let nan = 0.0/0.0

func printEqual<T: Equatable>(_ x: T, _ y: T) {
  print(x == y)
}

func printEqual<T: FloatingPoint>(_ x: T, _ y: T) {
  print(x == y)
}

printEqual(0, 0) // true (integers use `<T: Equatable>` overload)
printEqual(nan, nan) // false (floats use `<T: FloatingPoint>` overload)
As a result of this change, hashing of floats must be updated to make all NaNs hash equally. -0 and +0 will also no longer be expected to hash equally. (Although they might as an implementation detail – equal values must hash the same, unequal values may hash the same.)

Misc Standard Library

Types that conform to Comparable should be audited for places where implementing or using Comparable would be a win. This update can be done incrementally, as the only potential impact should be performance. As an example, a default implementation of compare(_:slight_smile: for Array will likely be suboptimal, performing two linear scans to determine the result in the worst-case. (See the default implementation provided in the detailed design.)

Some free functions will have <T: FloatingPoint> overloads to better align with IEEE-754 semantics. This will be addressed in a follow-up proposal. (example: min and max)

Detailed Design

The protocols will be changed as follows:

ComparisonResult, currently a type found in Foundation, will be sunk into the Swift Standard Library:

@objc public enum ComparisonResult: Int, Equatable {
  case orderedAscending = -1
  case orderedSame = 0
  case orderedDescending = 1
}

public protocol Comparable: Equatable {
  func compare(_ other: Self) -> ComparisonResult

  static func < (lhs: Self, rhs: Self) -> Bool
}

extension Comparable {
  func compare(_ other: Self) -> ComparisonResult {
    if self == other {
      return .orderedSame
    } else if self < other {
      return .orderedAscending
    } else {
      return .orderedDescending
    }
  }
}

public func < <T: Comparable>(lhs: T, rhs: T) -> Bool {
  return lhs.compare(rhs) == .orderedAscending
}

// IEEE comparison operators (these implementations already exist in std)
extension FloatingPoint {
  public static func == (lhs: T, rhs: T) -> Bool {
    return lhs.isEqual(to: rhs)
  }

  public static func < (lhs: T, rhs: T) -> Bool {
    return lhs.isLess(than: rhs)
  }

  public static func <= (lhs: T, rhs: T) -> Bool {
    return lhs.isLessThanOrEqualTo(rhs)
  }

  public static func > (lhs: T, rhs: T) -> Bool {
    return rhs.isLess(than: lhs)
  }

  public static func >= (lhs: T, rhs: T) -> Bool {
    return rhs.isLessThanOrEqualTo(lhs)
  }
}

// Comparable comparison operators (provides a total ordering)
extension FloatingPoint {
  @_inline
  public func compare(_ other: Self) -> ComparisonResult {
    // Can potentially be implemented more efficiently -- this is just the clearest version
    if self.isLess(than: other) {
      return .orderedAscending
    } else if other.isLess(than: self) {
      return .orderedDescending
    } else {
      // Special cases

      // -0 < +0
      if self.isZero && other.isZero {
        // .plus == 0 and .minus == 1, so flip ordering to get - < +
        return (other.sign as Int).compare(self.sign as Int)
      }

      // NaN == NaN, NaN > +Inf
      if self.isNaN {
        if other.isNaN {
          return .orderedSame
        } else {
          return .orderedDescending
        }
      } else if other.isNaN {
        return .orderedAscending
      }

      // Otherwise equality agrees with normal IEEE
      return .orderedSame
    }
  }

  @_implements(Equatable.==)
  public static func _comparableEqual(lhs: Self, rhs: Self) -> Bool {
    lhs.compare(rhs) == .orderedSame
  }

  @_implements(Comparable.<)
  public static func _comparableLessThan(lhs: Self, rhs: Self) -> Bool {
    lhs.compare(rhs) == .orderedDescending
  }
}
Note that this design mandates changes to the compiler:

@_implements (or an equivalent mechanism) must be implemented to get the context-sensitive FloatingPoint behaviour.
The compiler must verify that either == and <, or compare(_:slight_smile: is overridden by every type that conforms to Comparable.
Source compatibility

Users of ComparisonResult will be able to use it as normal once it becomes a standard library type.

Existing implementors of Comparable will be unaffected, though they should consider implementing the new compare method as the default implementation may be suboptimal.

Consumers of Comparable will be unaffected, though they should consider calling the compare method if it offers a performance advantage for their particular algorithm.

Existing implementors of FloatingPoint should be unaffected – they will automatically get the new behaviour as long as they aren’t manually implementing the requirements of Equatable/Comparable.

Existing code that works with floats may break if it’s relying on some code bounded on <T: Equatable/Comparable>providing IEEE semantics. For most algorithms, NaNs would essentially lead to unspecified behaviour, so the primary concern is whether -0.0 == +0.0 matters.

ABI stability

This must be implemented before ABI stability is declared.

Effect on API resilience

N/A

Alternatives Considered

Spaceship

Early versions of this proposal aimed to instead provide a <=> operator in place of compare. The only reason we moved away from this was that it didn’t solve the problem that comparison didn’t generalize.

Spaceship as an operator has a two concrete benefits over compare today:

It can be passed to a higher-order function
Tuples can implement it
In our opinion, these aren’t serious problems, especially in the long term.

Passing <=> as a higher order function basically allows types that aren’t Comparable, but do provide <=>, to be very ergonomically handled by algorithms which take an optional ordering function. Types which provide the comparable operators but don’t conform to Comparable are only pervasive due to the absence of conditional conformance. We shouldn’t be designing our APIs around the assumption that conditional conformance doesn’t exist.

When conditional conformance is implemented, the only should-be-comparable-but-aren’t types that will remain are tuples, which we should potentially have the compiler synthesize conformances for.

Similarly, it should one day be possible to extend tuples, although this is a more “far future” matter. Until then, the (T, T) -> Bool predicate will always also be available, and < can be used there with the only downside being a potential performance hit.

Just Leave Floats Alone

The fact that sorting floats leads to a mess, and storing floats can lead to memory leaks and data loss isn’t acceptable.

Just Make Floats Only Have A Total Order

This was deemed too surprising for anyone familiar with floats from any other language. It would also probably break a lot more code than this change will.

Just Make Floats Not Comparable

Although floats are more subtle than integers, having places where integers work but floats don’t is a poor state of affairs. One should be able to sort an array of floats and use floats as keys in data structures, even if the latter is difficult to do correctly.

PartialComparable

PartialComparable would essentially just be Comparable without any stated ordering requirements, that Comparable extends to provide ordering requirements. This would be a protocol that standard IEEE comparison could satisfy, but in the absence of total ordering requirements, PartialComparable is effectively useless. Either everyone would consume PartialComparable (to accept floats) or Comparable (to have reasonable behaviour).

The Rust community adopted this strategy to little benefit. The Rust libs team has frequently considered removing the distinction, but hasn’t because doing it backwards compatibly would be complicated. Also because merging the two would just lead to the problems Swift has today.

Different Names For compare and ComparisonResult

A few different variants for ComparisonResult and its variants were considered:

Dropping the ordered part of ComparisonResult’s cases e.g. .ascending
Naming of ComparisonResult as SortOrder
enum Ordering { case less, equal, greater } (as used by Rust <https://doc.rust-lang.org/std/cmp/enum.Ordering.html>)
Case values of inOrder, same, outOfOrder
The choice of case names is non-trivial because the enum shows up in different contexts where different names makes more sense. Effectively, one needs to keep in mind that the “default” sort order is ascending to map between the concept of “before” and “less”.

The before/after naming to provide the most intuitive model for custom sorts – referring to ascending or less is confusing when trying to implement a descending ordering. Similarly the inOrder/outOfOrder naming was too indirect – it’s more natural to just say where to put the element. If the enum should focus on the sorting case, calling it SortOrder would help to emphasize this fact.

This proposal elects to leave the existing Foundation name in-place. The primary motivation for this is that use of the compare function will be relatively rare. It is expected that in most cases users will continue to make use of == or <, returning boolean values (the main exception to this will be in use of the parameterized String comparisons). As such, the source compatibility consequences of introducing naming changes to an existing type seems of insufficient benefit.

The method compare(_:slight_smile: does not fully comport with the API naming guidelines. However, it is firmly established with current usage in Objective-C APIs, will be fairly rarely seen/used (users will usually prefer <, == etc), and alternatives considered, for example compared(to:), were not a significant improvement.

Add Overloads for (T, T) -> ComparisonResult

It would be slightly more ergonomic to work with ComparisonResult if existing methods that took an ordering predicate also had an overload for (T, T) -> ComparisonResult. As it stands, a case-insensitive sort must be written as follows:

myStrings.sort { $0.compare(_ other: $1, case: .insensitive) == .orderedAscending }
With the overload, one could write:

myStrings.sort { $0.compare($1, case: .insensitive) }
we decided against providing these overloads because:

The existing algorithms in the standard library can’t benefit from them (only binary comparisons).
They bloat up the standard library (and any library which intends to match our API guidelines).
They potentially introduce confusion over “which” comparison overload to use.
And because we can change our mind later without concern for source or ABI stability, as these overloads would be additive.

Future Work

This section covers some topics which were briefly considered, but were identified as reasonable and possible to defer to future releases. Specifically they should be backwards compatible to introduce even after ABI stability. Two paths that are worth exploring:

Ergonomic Generalized Comparison for Keyed Containers

Can we make it ergonomic to use an (arbitrary) alternative comparison strategy for a Dictionary or a BinaryTree? Should they be type-level Comparators, or should those types always store a (Key, Key) -> ComparisonResult closure?

We can avoid answering this question because Dictionary is expected to keep a relatively opaque (resilient) ABI for the foreseeable future, as many interesting optimizations will change its internal layout. Although if the answer is type-level, then Default Generic Parameters must be accepted to proceed down this path.

ComparisonResult Conveniences

There are a few conveniences we could consider providing to make ComparisonResult more ergonomic to manipulate. Such as:

// A way to combine orderings
func ComparisonResult.breakingTiesWith(_ order: () -> ComparisonResult) -> ComparisonResult

array.sort {
  $0.x.compare($0.y)
  .breakingTiesWith { $0.y.compare($1.y) }
  == .orderedAscending
}
and

var inverted: ComparisonResult

// A perhaps more "clear" way to express reversing order than `y.compared(to: x)`
x.compare(y).inverted
But these can all be added later once everyone has had a chance to use them.

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Remy Demarest) #3

Remy Demarest
remy.demarest@gmail.com

Hi swift evolution,

Here’s another pitch, for The Propoosal Formerly Known As Spaceship.
Comparison Reform

Proposal: SE-NNNN <file:///Users/ben_cohen/Documents/swift-evolution/proposals/NNNN-filename.md>
Authors: Robert Widmann <https://github.com/codafi>, Jaden Geller <https://github.com/jadengeller>, Harlan Haskins <https://github.com/harlanhaskins>, Alexis Beingessner <https://github.com/Gankro>, Ben Cohen <https://github.com/airspeedswift>
Status: Awaiting review
Review manager: TBD
Introduction

This proposal is for changes that we believe should be made to the existing comparison system by:

Making FloatingPoint comparison context sensitive, so that its Comparable conformance provides a proper total ordering.
Introducing a new ternary-valued compare(_ other: Self) -> ComparisonResult method.
Removing unnecessary customization points from Comparable.
Motivation

The motivation comes from several independent points:

1: 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 while still maintaining the traditional definition of “comparison” for these types. Take, for example, sorting an array of Floats. 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 unspecified. Similarly, a Dictionary keyed off floats can leak entries and memory.

2: Generic algorithms in the Swift Standard Library that make use of the current Comparable protocol may have to make extra comparisons to determine the ordering of values when <, ==, and > should have different behaviours. Having a central operation to return complete ordering information should provide a speedup for these operations.

3: The existing comparison operators don’t “generalize” well. There’s no clean way to add a third or fourth argument to < to ask for non-default semantics. An example where this would be desirable would be specifying the locale or case-sensitivity when comparing Strings.

4: Comparable is over-engineered in the customization points it provides: to our knowledge, there’s no good reason to ever override >=, >, or <=. Each customization point bloats vtables and mandates additional dynamic dispatch.

5: When quickly writing a Comparable type, it is easier to implement a single ternary statement than to separately implement == and <.

Proposed solution

ComparisonResult

Foundation’s ComparisonResult type will be mapped into Swift as

@objc public enum ComparisonResult : Int {
  case orderedAscending = -1
  case orderedSame = 0
  case orderedDescending = 1
}
Comparable

Comparable will be changed to have a new ternary comparison method: compare(_ other: Self) -> ComparisonResult. x.compare(y) specifies where to place x relative to y. So if it yields .orderedAscending, then x comes before y. This will be considered the new “main” dispatch point of Comparable that implementors should provide.

Most code will continue to use < or ==, as it will be optimal for their purposes. However code that needs to make a three-way branch on comparison can use the potentially more efficient compare. Note that compare is only expected to be more efficient in this specific case. If a two-way branch is all that’s being done, < will be more efficient in many cases (if only because it’s easier for the optimizer).

For backwards compatibility reasons, compare will have a default implementation defined in terms of <, but to enable only using compare, < and == will also have default implementations in terms of compare.

The compiler will verify that either compare, or < and ==, are provided by every type that claims to conform to Comparable. This will be done in some unspecified way unavailable outside the standard library (it can be made available to in the future, but that’s an unnecessary distraction for this proposal).

Is it really necessary? Can't you have two separate protocols like this:

protocol Comparable: Equatable {
    static func < (lhs: Self, rhs: Self) -> Bool
}

protocol ThreeWayComparable: Equatable {
    func compare(_ other: Self) -> ComparisonResult
}

extension Comparable where Self: ThreeWayComparable {
    static func < (lhs: Self, rhs: Self) -> Bool {
        return lhs.compare(rhs) == .orderedAscending
    }
}

···

Le 13 avr. 2017 à 13:17, Ben Cohen via swift-evolution <swift-evolution@swift.org> a écrit :
Types that wish to provide comparison “variants” can do so naturally by adding compare methods with additional arguments. e.g. String.compare(_ other: Self, in: Locale) -> ComparisonResult. These have no language-level connection to Comparable, but are still syntactically connected, implying the same total order semantics. This makes them easier to discover, learn, and migrate to.

To reduce bloat, the operators <=, >=, and > will be removed from the set of requirements that the Comparable protocol declares. These operators will however continue to exist with the current default implementations.

FloatingPoint

No changes will be made to the FloatingPoint protocol itself. Instead, new extensions will be added to it to change the behaviour of comparison.

The new behaviour centers around the fact that compare(_: Self) -> ComparisonResult will provide a total ordering that’s consistent with Level 2 in the IEEE 754 (2008) spec. This is mostly the same as the standard (Level 1) IEEE ordering, except:

-0 < +0
NaN == NaN
NaN > +Inf (an arbitrary choice, NaN can be placed anywhere in the number line)
Level 2’s distinguishing of -0 and +0 is a bit strange, but is consistent with Equatable’s Substitutability requirement. -0 and +0 have different behaviours: 1/-0 = -Inf while 1/+0 = +Inf. The main problem this can lead to is that a keyed collection may have two “0” entries. In practice this probably won’t be a problem because it’s fairly difficult for the same algorithm to produce both -0 and +0. Any algorithm that does is also probably concerned with the fact that 1.0E-128 and 2.0E-128 are considered distinct values.

Note: IEEE specifies several other potential total orderings: level 3, level 4, and the totalOrder predicate. For our purposes, these orderings are too aggressive in distinguishing values that are semantically equivalent in Swift. For most cases, the relevant issue is that they distinguish different encodings of NaN. For more exotic encodings that don’t guarantee normalization, these predicates also consider 10.0e0 < 1.0e1 to be true. An example where this can occur is IEEE-754 decimal coded floating point, which FloatingPoint is intended to support.

We will then make the comparison operators (<, <=, ==, !=, >=, >) dispatch to one of compare(_:slight_smile: or FloatingPoint’s IEEE comparison methods (isLess, isEqual, isLessThanOrEqualTo) based on the context.

If the context knows the type is FloatingPoint, then level 1 ordering will be used.
If the context only knows the type is Comparable or Equatable, then level 2 ordering will be used.
This results in code that is explicitly designed to work with FloatingPoint types getting the expected IEEE behaviour, while code that is only designed to work with Comparable types (e.g. sort and Dictionary) gets more reasonable total ordering behaviour.

To clarify: Dictionary and sort won’t somehow detect that they’re being used with FloatingPoint types and use level 1 comparisons. Instead they will unconditional use level 2 behaviour. For example:

let nan = 0.0/0.0

func printEqual<T: Equatable>(_ x: T, _ y: T) {
  print(x == y)
}

func printEqualFloats<T: FloatingPoint>(_ x: T, _ y: T) {
  print(x == y)
}

print(nan == nan) // false, (concrete)
printEqual(nan, nan) // true, (generic Equatable but not FloatingPoint)
printEqualFloats(nan, nan) // false, (generic FloatingPoint)
If one wishes to have a method that works with all Equatable/Comparable types, but uses level 1 semantics for FloatingPoint types, then they can simply provide two identical implementations that differ only in the bounds:

let nan = 0.0/0.0

func printEqual<T: Equatable>(_ x: T, _ y: T) {
  print(x == y)
}

func printEqual<T: FloatingPoint>(_ x: T, _ y: T) {
  print(x == y)
}

printEqual(0, 0) // true (integers use `<T: Equatable>` overload)
printEqual(nan, nan) // false (floats use `<T: FloatingPoint>` overload)
As a result of this change, hashing of floats must be updated to make all NaNs hash equally. -0 and +0 will also no longer be expected to hash equally. (Although they might as an implementation detail – equal values must hash the same, unequal values may hash the same.)

Misc Standard Library

Types that conform to Comparable should be audited for places where implementing or using Comparable would be a win. This update can be done incrementally, as the only potential impact should be performance. As an example, a default implementation of compare(_:slight_smile: for Array will likely be suboptimal, performing two linear scans to determine the result in the worst-case. (See the default implementation provided in the detailed design.)

Some free functions will have <T: FloatingPoint> overloads to better align with IEEE-754 semantics. This will be addressed in a follow-up proposal. (example: min and max)

Detailed Design

The protocols will be changed as follows:

ComparisonResult, currently a type found in Foundation, will be sunk into the Swift Standard Library:

@objc public enum ComparisonResult: Int, Equatable {
  case orderedAscending = -1
  case orderedSame = 0
  case orderedDescending = 1
}

public protocol Comparable: Equatable {
  func compare(_ other: Self) -> ComparisonResult

  static func < (lhs: Self, rhs: Self) -> Bool
}

extension Comparable {
  func compare(_ other: Self) -> ComparisonResult {
    if self == other {
      return .orderedSame
    } else if self < other {
      return .orderedAscending
    } else {
      return .orderedDescending
    }
  }
}

public func < <T: Comparable>(lhs: T, rhs: T) -> Bool {
  return lhs.compare(rhs) == .orderedAscending
}

// IEEE comparison operators (these implementations already exist in std)
extension FloatingPoint {
  public static func == (lhs: T, rhs: T) -> Bool {
    return lhs.isEqual(to: rhs)
  }

  public static func < (lhs: T, rhs: T) -> Bool {
    return lhs.isLess(than: rhs)
  }

  public static func <= (lhs: T, rhs: T) -> Bool {
    return lhs.isLessThanOrEqualTo(rhs)
  }

  public static func > (lhs: T, rhs: T) -> Bool {
    return rhs.isLess(than: lhs)
  }

  public static func >= (lhs: T, rhs: T) -> Bool {
    return rhs.isLessThanOrEqualTo(lhs)
  }
}

// Comparable comparison operators (provides a total ordering)
extension FloatingPoint {
  @_inline
  public func compare(_ other: Self) -> ComparisonResult {
    // Can potentially be implemented more efficiently -- this is just the clearest version
    if self.isLess(than: other) {
      return .orderedAscending
    } else if other.isLess(than: self) {
      return .orderedDescending
    } else {
      // Special cases

      // -0 < +0
      if self.isZero && other.isZero {
        // .plus == 0 and .minus == 1, so flip ordering to get - < +
        return (other.sign as Int).compare(self.sign as Int)
      }

      // NaN == NaN, NaN > +Inf
      if self.isNaN {
        if other.isNaN {
          return .orderedSame
        } else {
          return .orderedDescending
        }
      } else if other.isNaN {
        return .orderedAscending
      }

      // Otherwise equality agrees with normal IEEE
      return .orderedSame
    }
  }

  @_implements(Equatable.==)
  public static func _comparableEqual(lhs: Self, rhs: Self) -> Bool {
    lhs.compare(rhs) == .orderedSame
  }

  @_implements(Comparable.<)
  public static func _comparableLessThan(lhs: Self, rhs: Self) -> Bool {
    lhs.compare(rhs) == .orderedDescending
  }
}
Note that this design mandates changes to the compiler:

@_implements (or an equivalent mechanism) must be implemented to get the context-sensitive FloatingPoint behaviour.
The compiler must verify that either == and <, or compare(_:slight_smile: is overridden by every type that conforms to Comparable.
Source compatibility

Users of ComparisonResult will be able to use it as normal once it becomes a standard library type.

Existing implementors of Comparable will be unaffected, though they should consider implementing the new compare method as the default implementation may be suboptimal.

Consumers of Comparable will be unaffected, though they should consider calling the compare method if it offers a performance advantage for their particular algorithm.

Existing implementors of FloatingPoint should be unaffected – they will automatically get the new behaviour as long as they aren’t manually implementing the requirements of Equatable/Comparable.

Existing code that works with floats may break if it’s relying on some code bounded on <T: Equatable/Comparable>providing IEEE semantics. For most algorithms, NaNs would essentially lead to unspecified behaviour, so the primary concern is whether -0.0 == +0.0 matters.

ABI stability

This must be implemented before ABI stability is declared.

Effect on API resilience

N/A

Alternatives Considered

Spaceship

Early versions of this proposal aimed to instead provide a <=> operator in place of compare. The only reason we moved away from this was that it didn’t solve the problem that comparison didn’t generalize.

Spaceship as an operator has a two concrete benefits over compare today:

It can be passed to a higher-order function
Tuples can implement it
In our opinion, these aren’t serious problems, especially in the long term.

Passing <=> as a higher order function basically allows types that aren’t Comparable, but do provide <=>, to be very ergonomically handled by algorithms which take an optional ordering function. Types which provide the comparable operators but don’t conform to Comparable are only pervasive due to the absence of conditional conformance. We shouldn’t be designing our APIs around the assumption that conditional conformance doesn’t exist.

When conditional conformance is implemented, the only should-be-comparable-but-aren’t types that will remain are tuples, which we should potentially have the compiler synthesize conformances for.

Similarly, it should one day be possible to extend tuples, although this is a more “far future” matter. Until then, the (T, T) -> Bool predicate will always also be available, and < can be used there with the only downside being a potential performance hit.

Just Leave Floats Alone

The fact that sorting floats leads to a mess, and storing floats can lead to memory leaks and data loss isn’t acceptable.

Just Make Floats Only Have A Total Order

This was deemed too surprising for anyone familiar with floats from any other language. It would also probably break a lot more code than this change will.

Just Make Floats Not Comparable

Although floats are more subtle than integers, having places where integers work but floats don’t is a poor state of affairs. One should be able to sort an array of floats and use floats as keys in data structures, even if the latter is difficult to do correctly.

PartialComparable

PartialComparable would essentially just be Comparable without any stated ordering requirements, that Comparable extends to provide ordering requirements. This would be a protocol that standard IEEE comparison could satisfy, but in the absence of total ordering requirements, PartialComparable is effectively useless. Either everyone would consume PartialComparable (to accept floats) or Comparable (to have reasonable behaviour).

The Rust community adopted this strategy to little benefit. The Rust libs team has frequently considered removing the distinction, but hasn’t because doing it backwards compatibly would be complicated. Also because merging the two would just lead to the problems Swift has today.

Different Names For compare and ComparisonResult

A few different variants for ComparisonResult and its variants were considered:

Dropping the ordered part of ComparisonResult’s cases e.g. .ascending
Naming of ComparisonResult as SortOrder
enum Ordering { case less, equal, greater } (as used by Rust <https://doc.rust-lang.org/std/cmp/enum.Ordering.html>)
Case values of inOrder, same, outOfOrder
The choice of case names is non-trivial because the enum shows up in different contexts where different names makes more sense. Effectively, one needs to keep in mind that the “default” sort order is ascending to map between the concept of “before” and “less”.

The before/after naming to provide the most intuitive model for custom sorts – referring to ascending or less is confusing when trying to implement a descending ordering. Similarly the inOrder/outOfOrder naming was too indirect – it’s more natural to just say where to put the element. If the enum should focus on the sorting case, calling it SortOrder would help to emphasize this fact.

This proposal elects to leave the existing Foundation name in-place. The primary motivation for this is that use of the compare function will be relatively rare. It is expected that in most cases users will continue to make use of == or <, returning boolean values (the main exception to this will be in use of the parameterized String comparisons). As such, the source compatibility consequences of introducing naming changes to an existing type seems of insufficient benefit.

The method compare(_:slight_smile: does not fully comport with the API naming guidelines. However, it is firmly established with current usage in Objective-C APIs, will be fairly rarely seen/used (users will usually prefer <, == etc), and alternatives considered, for example compared(to:), were not a significant improvement.

Add Overloads for (T, T) -> ComparisonResult

It would be slightly more ergonomic to work with ComparisonResult if existing methods that took an ordering predicate also had an overload for (T, T) -> ComparisonResult. As it stands, a case-insensitive sort must be written as follows:

myStrings.sort { $0.compare(_ other: $1, case: .insensitive) == .orderedAscending }
With the overload, one could write:

myStrings.sort { $0.compare($1, case: .insensitive) }
we decided against providing these overloads because:

The existing algorithms in the standard library can’t benefit from them (only binary comparisons).
They bloat up the standard library (and any library which intends to match our API guidelines).
They potentially introduce confusion over “which” comparison overload to use.
And because we can change our mind later without concern for source or ABI stability, as these overloads would be additive.

Future Work

This section covers some topics which were briefly considered, but were identified as reasonable and possible to defer to future releases. Specifically they should be backwards compatible to introduce even after ABI stability. Two paths that are worth exploring:

Ergonomic Generalized Comparison for Keyed Containers

Can we make it ergonomic to use an (arbitrary) alternative comparison strategy for a Dictionary or a BinaryTree? Should they be type-level Comparators, or should those types always store a (Key, Key) -> ComparisonResult closure?

We can avoid answering this question because Dictionary is expected to keep a relatively opaque (resilient) ABI for the foreseeable future, as many interesting optimizations will change its internal layout. Although if the answer is type-level, then Default Generic Parameters must be accepted to proceed down this path.

ComparisonResult Conveniences

There are a few conveniences we could consider providing to make ComparisonResult more ergonomic to manipulate. Such as:

// A way to combine orderings
func ComparisonResult.breakingTiesWith(_ order: () -> ComparisonResult) -> ComparisonResult

array.sort {
  $0.x.compare($0.y)
  .breakingTiesWith { $0.y.compare($1.y) }
  == .orderedAscending
}
and

var inverted: ComparisonResult

// A perhaps more "clear" way to express reversing order than `y.compared(to: x)`
x.compare(y).inverted
But these can all be added later once everyone has had a chance to use them.

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Jon Hull) #4

I still like the ordering of floats defined in this proposal best (and think we should use it), but I imagine that there are other types which are almost (but not quite) comparable as well. Would there be any utility in having a ‘PartialComparable’ protocol that defined a single method:

  func compare(_:)->ComparisonResult?

That is, it is just like our compare, but it returns nil if two values can’t be meaningfully compared. It would force you to deal with the cases where the comparison didn’t make sense, and handle it in a reasonable way in your code. (e.g. filtering those values out, or sticking them at the end).

You can think of it as failable compare...

Thanks,
Jon

···

On Apr 13, 2017, at 1:17 PM, Ben Cohen via swift-evolution <swift-evolution@swift.org> wrote:
PartialComparable

PartialComparable would essentially just be Comparable without any stated ordering requirements, that Comparable extends to provide ordering requirements. This would be a protocol that standard IEEE comparison could satisfy, but in the absence of total ordering requirements, PartialComparable is effectively useless. Either everyone would consume PartialComparable (to accept floats) or Comparable (to have reasonable behaviour).

The Rust community adopted this strategy to little benefit. The Rust libs team has frequently considered removing the distinction, but hasn’t because doing it backwards compatibly would be complicated. Also because merging the two would just lead to the problems Swift has today.


(John McCall) #5

ComparisonResult Conveniences

There are a few conveniences we could consider providing to make ComparisonResult more ergonomic to manipulate. Such as:

// A way to combine orderings
func ComparisonResult.breakingTiesWith(_ order: () -> ComparisonResult) -> ComparisonResult

array.sort {
  $0.x.compare($0.y)
  .breakingTiesWith { $0.y.compare($1.y) }
  == .orderedAscending
}

The really nice thing about compare being an operator is that you can very nicely combine it with an operator here and get a much more light-weight syntax for chained comparisons, e.g.:

struct MyPoint : Comparable {
  var x, y, z: Double
  func compare(_ other: MyPointer) -> ComparisonResult {
    return self.x <=> other.x || self.y <=> other.y || self.z <=> other.z
  }
}

as opposed to, I guess,
  return self.x.compare(other.x).breakingTiesWith { self.y.compare(other.y).breakingTiesWith { self.z.compare(other.z) } }

But this is mostly useful for defining custom comparisons, so perhaps it's not worth having to paint a bikeshed for <=> and whatever the combining operator is.

Also, in this example:

// A way to combine orderings
func ComparisonResult.breakingTiesWith(_ order: () -> ComparisonResult) -> ComparisonResult

array.sort {
  $0.x.compare($0.y)
  .breakingTiesWith { $0.y.compare($1.y) }
  == .orderedAscending
}

Requiring this last "== .orderedAscending" seems like a tragic failure of ergonomics. I understand that sorting doesn't actually require a tri-valued comparison, but is it really worth maintaining two currencies of comparison result over that? Are there any types that can answer '<' substantially more efficiently than they can answer 'compare'? And I assume this is related to why you've kept < in the protocol.

John.

···

On Apr 13, 2017, at 4:17 PM, Ben Cohen via swift-evolution <swift-evolution@swift.org> wrote:


(Xiaodi Wu) #6

Getting this sorted out is definitely a worthwhile effort. I do have
thoughts about this proposal:

I continue to have reservations about an identical spelling (e.g. `==`)
giving two different answers with the same values of the same type,
depending on the generic context. It is a very *clever* design, but it is
also a very *subtle* behavior that I can see leading to much confusion and
befuddlement for any user who is not well versed *both* in the intricacies
of IEEE floating point *and* in the intricacies of Swift.

Actually, the fact that this behavior cannot even be achieved without
currently non-existent compiler features means that it is not possible to
understand what's truly going on without reading *this document*, after
mastering *both* IEEE floating point *and* Swift
generics/protocols/extensions/static vs. dynamic dispatch. All to use `==`
correctly. Which is to say, most people will simply not even know if they
happen to be using the `==` they did not intend to use.

I think consideration should be given to a design that achieves a
user-facing but not onerous differentiation between level 1 and level 2
equality. However, the only one I can think of is essentially a different
shade of the `PartiallyComparable` alternative already outlined in the
document. Yet I cannot help but think that the rejected alternative may be
advantageous in one key aspect. `FloatingPoint` comparison is in a sense
"less refined" (not exactly precise language, I know) than the level 2
ordering proposed here, at least in the sense that the latter offers more
semantic guarantees about the relationships between comparison operators.
It's weird that the less refined `FloatingPoint` refines the more refined
`Comparable`, and I think the acrobatics with compiler support illustrate
how the design is actively working against Swift's overarching direction.

Anyway, so much for that about the design overall.

As for nitpicking details, I agree with others and think it's a poor
precedent to say that we're going to use an Obj-C name because it's not
clearly worse than the obvious Swift API guideline-compliant name. When
that's the case, it seems to me that the whole point of having Swift API
naming guidelines and making that huge migration from Swift 2 to 3 was so
that going forward we could name things consistently using one consensus
style. `compare(_:)` does not merit a term-of-art exception when the Swift
name is clearly `compared(to:)`.

···

On Thu, Apr 13, 2017 at 3:17 PM, Ben Cohen via swift-evolution < swift-evolution@swift.org> wrote:

Hi swift evolution,

Here’s another pitch, for The Propoosal Formerly Known As Spaceship.
Comparison Reform

   - Proposal: SE-NNNN
   - Authors: Robert Widmann <https://github.com/codafi>, Jaden Geller
   <https://github.com/jadengeller>, Harlan Haskins
   <https://github.com/harlanhaskins>, Alexis Beingessner
   <https://github.com/Gankro>, Ben Cohen
   <https://github.com/airspeedswift>
   - Status: *Awaiting review*
   - Review manager: TBD

Introduction

This proposal is for changes that we believe should be made to the
existing comparison system by:

   - Making FloatingPoint comparison context sensitive, so that its
   Comparable conformance provides a proper total ordering.
   - Introducing a new ternary-valued compare(_ other: Self) ->
   ComparisonResult method.
   - Removing unnecessary customization points from Comparable.

Motivation

The motivation comes from several independent points:

1: 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 while still
maintaining the traditional definition of “comparison” for these types.
Take, for example, sorting an array of Floats. 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 unspecified. Similarly,
a Dictionary keyed off floats can leak entries and memory.

2: Generic algorithms in the Swift Standard Library that make use of the
current Comparable protocol may have to make extra comparisons to
determine the ordering of values when <, ==, and > should have different
behaviours. Having a central operation to return complete ordering
information should provide a speedup for these operations.

3: The existing comparison operators don’t “generalize” well. There’s no
clean way to add a third or fourth argument to < to ask for non-default
semantics. An example where this would be desirable would be specifying the
locale or case-sensitivity when comparing Strings.

4: Comparable is over-engineered in the customization points it provides:
to our knowledge, there’s no good reason to ever override >=, >, or <=.
Each customization point bloats vtables and mandates additional dynamic
dispatch.

5: When quickly writing a Comparable type, it is easier to implement a
single ternary statement than to separately implement == and <.
Proposed solutionComparisonResult

Foundation’s ComparisonResult type will be mapped into Swift as

@objc public enum ComparisonResult : Int {
  case orderedAscending = -1
  case orderedSame = 0
  case orderedDescending = 1
}

Comparable

Comparable will be changed to have a new ternary comparison method: compare(_
other: Self) -> ComparisonResult. x.compare(y) specifies where to place x
relative to y. So if it yields .orderedAscending, then x comes before y.
This will be considered the new “main” dispatch point of Comparable that
implementors should provide.

Most code will continue to use < or ==, as it will be optimal for their
purposes. However code that needs to make a three-way branch on comparison
can use the potentially more efficient compare. Note that compare is only
expected to be more efficient in this specific case. If a two-way branch is
all that’s being done, < will be more efficient in many cases (if only
because it’s easier for the optimizer).

For backwards compatibility reasons, compare will have a default
implementation defined in terms of <, but to enable only using compare, <
and == will also have default implementations in terms of compare.

The compiler will verify that either compare, or < and ==, are provided
by every type that claims to conform to Comparable. This will be done in
some unspecified way unavailable outside the standard library (it can be
made available to in the future, but that’s an unnecessary distraction for
this proposal).

Types that wish to provide comparison “variants” can do so naturally by
adding compare methods with additional arguments. e.g. String.compare(_
other: Self, in: Locale) -> ComparisonResult. These have no
language-level connection to Comparable, but are still syntactically
connected, implying the same total order semantics. This makes them easier
to discover, learn, and migrate to.

To reduce bloat, the operators <=, >=, and > will be removed from the set
of requirements that the Comparable protocol declares. These operators
will however continue to exist with the current default implementations.
FloatingPoint

No changes will be made to the FloatingPoint protocol itself. Instead,
new extensions will be added to it to change the behaviour of comparison.

The new behaviour centers around the fact that compare(_: Self) ->
ComparisonResult will provide a total ordering that’s consistent with
Level 2 in the IEEE 754 (2008) spec. This is mostly the same as the
standard (Level 1) IEEE ordering, except:

   - -0 < +0
   - NaN == NaN
   - NaN > +Inf (an arbitrary choice, NaN can be placed anywhere in the
   number line)

Level 2’s distinguishing of -0 and +0 is a bit strange, but is consistent
with Equatable’s Substitutability requirement. -0 and +0 have different
behaviours: 1/-0 = -Inf while 1/+0 = +Inf. The main problem this can lead
to is that a keyed collection may have two “0” entries. In practice this
probably won’t be a problem because it’s fairly difficult for the same
algorithm to produce both -0 and +0. Any algorithm that does is also
probably concerned with the fact that 1.0E-128 and 2.0E-128 are
considered distinct values.

Note: IEEE specifies several other potential total orderings: level 3,
level 4, and the totalOrder predicate. For our purposes, these orderings
are too aggressive in distinguishing values that are semantically
equivalent in Swift. For most cases, the relevant issue is that they
distinguish different encodings of NaN. For more exotic encodings that
don’t guarantee normalization, these predicates also consider 10.0e0 <
1.0e1 to be true. An example where this can occur is *IEEE-754 decimal
coded floating point*, which FloatingPoint is intended to support.

We will then make the comparison operators (<, <=, ==, !=, >=, >)
dispatch to one of compare(_:slight_smile: or FloatingPoint’s IEEE comparison methods
(isLess, isEqual, isLessThanOrEqualTo) based on the context.

   - If the context knows the type is FloatingPoint, then level 1
   ordering will be used.
   - If the context only knows the type is Comparable or Equatable, then
   level 2 ordering will be used.

This results in code that is explicitly designed to work with
FloatingPoint types getting the expected IEEE behaviour, while code that is
only designed to work with Comparable types (e.g. sort and Dictionary)
gets more reasonable total ordering behaviour.

To clarify: Dictionary and sort won’t somehow detect that they’re being
used with FloatingPoint types and use level 1 comparisons. Instead they
will unconditional use level 2 behaviour. For example:

let nan = 0.0/0.0
func printEqual<T: Equatable>(_ x: T, _ y: T) {
  print(x == y)
}
func printEqualFloats<T: FloatingPoint>(_ x: T, _ y: T) {
  print(x == y)
}
print(nan == nan) // false, (concrete)
printEqual(nan, nan) // true, (generic Equatable but not FloatingPoint)
printEqualFloats(nan, nan) // false, (generic FloatingPoint)

If one wishes to have a method that works with all Equatable/Comparable
types, but uses level 1 semantics for FloatingPoint types, then they can
simply provide two identical implementations that differ only in the bounds:

let nan = 0.0/0.0
func printEqual<T: Equatable>(_ x: T, _ y: T) {
  print(x == y)
}
func printEqual<T: FloatingPoint>(_ x: T, _ y: T) {
  print(x == y)
}

printEqual(0, 0) // true (integers use `<T: Equatable>` overload)
printEqual(nan, nan) // false (floats use `<T: FloatingPoint>` overload)

As a result of this change, hashing of floats must be updated to make all
NaNs hash equally. -0 and +0 will also no longer be expected to hash
equally. (Although they might as an implementation detail – equal values
must hash the same, unequal values *may* hash the same.)
Misc Standard Library

Types that conform to Comparable should be audited for places where
implementing or using Comparable would be a win. This update can be done
incrementally, as the only potential impact should be performance. As an
example, a default implementation of compare(_:slight_smile: for Array will likely be
suboptimal, performing two linear scans to determine the result in the
worst-case. (See the default implementation provided in the detailed
design.)

Some free functions will have <T: FloatingPoint> overloads to better
align with IEEE-754 semantics. This will be addressed in a follow-up
proposal. (example: min and max)
Detailed Design

The protocols will be changed as follows:

ComparisonResult, currently a type found in Foundation, will be sunk into
the Swift Standard Library:

@objc public enum ComparisonResult: Int, Equatable {
  case orderedAscending = -1
  case orderedSame = 0
  case orderedDescending = 1
}
public protocol Comparable: Equatable {
  func compare(_ other: Self) -> ComparisonResult

  static func < (lhs: Self, rhs: Self) -> Bool
}
extension Comparable {
  func compare(_ other: Self) -> ComparisonResult {
    if self == other {
      return .orderedSame
    } else if self < other {
      return .orderedAscending
    } else {
      return .orderedDescending
    }
  }
}
public func < <T: Comparable>(lhs: T, rhs: T) -> Bool {
  return lhs.compare(rhs) == .orderedAscending
}
// IEEE comparison operators (these implementations already exist in std)extension FloatingPoint {
  public static func == (lhs: T, rhs: T) -> Bool {
    return lhs.isEqual(to: rhs)
  }

  public static func < (lhs: T, rhs: T) -> Bool {
    return lhs.isLess(than: rhs)
  }

  public static func <= (lhs: T, rhs: T) -> Bool {
    return lhs.isLessThanOrEqualTo(rhs)
  }

  public static func > (lhs: T, rhs: T) -> Bool {
    return rhs.isLess(than: lhs)
  }

  public static func >= (lhs: T, rhs: T) -> Bool {
    return rhs.isLessThanOrEqualTo(lhs)
  }
}

// Comparable comparison operators (provides a total ordering)extension FloatingPoint {
  @_inline
  public func compare(_ other: Self) -> ComparisonResult {
    // Can potentially be implemented more efficiently -- this is just the clearest version
    if self.isLess(than: other) {
      return .orderedAscending
    } else if other.isLess(than: self) {
      return .orderedDescending
    } else {
      // Special cases

      // -0 < +0
      if self.isZero && other.isZero {
        // .plus == 0 and .minus == 1, so flip ordering to get - < +
        return (other.sign as Int).compare(self.sign as Int)
      }

      // NaN == NaN, NaN > +Inf
      if self.isNaN {
        if other.isNaN {
          return .orderedSame
        } else {
          return .orderedDescending
        }
      } else if other.isNaN {
        return .orderedAscending
      }

      // Otherwise equality agrees with normal IEEE
      return .orderedSame
    }
  }

  @_implements(Equatable.==)
  public static func _comparableEqual(lhs: Self, rhs: Self) -> Bool {
    lhs.compare(rhs) == .orderedSame
  }

  @_implements(Comparable.<)
  public static func _comparableLessThan(lhs: Self, rhs: Self) -> Bool {
    lhs.compare(rhs) == .orderedDescending
  }
}

Note that this design mandates changes to the compiler:

   - @_implements (or an equivalent mechanism) must be implemented to get
   the context-sensitive FloatingPoint behaviour.
   - The compiler must verify that either == and <, or compare(_:slight_smile: is
   overridden by every type that conforms to Comparable.

Source compatibility

Users of ComparisonResult will be able to use it as normal once it
becomes a standard library type.

Existing implementors of Comparable will be unaffected, though they
should consider implementing the new compare method as the default
implementation may be suboptimal.

Consumers of Comparable will be unaffected, though they should consider
calling the compare method if it offers a performance advantage for their
particular algorithm.

Existing implementors of FloatingPoint should be unaffected – they will
automatically get the new behaviour as long as they aren’t manually
implementing the requirements of Equatable/Comparable.

Existing code that works with floats may break if it’s relying on some
code bounded on <T: Equatable/Comparable>providing IEEE semantics. For
most algorithms, NaNs would essentially lead to unspecified behaviour, so
the primary concern is whether -0.0 == +0.0 matters.
ABI stability

This must be implemented before ABI stability is declared.
Effect on API resilience

N/A
Alternatives ConsideredSpaceship

Early versions of this proposal aimed to instead provide a <=> operator
in place of compare. The only reason we moved away from this was that it
didn’t solve the problem that comparison didn’t generalize.

Spaceship as an operator has a two concrete benefits over compare today:

   - It can be passed to a higher-order function
   - Tuples can implement it

In our opinion, these aren’t serious problems, especially in the long term.

Passing <=> as a higher order function basically allows types that aren’t
Comparable, but do provide <=>, to be very ergonomically handled by
algorithms which take an optional ordering function. Types which provide
the comparable operators but don’t conform to Comparable are only pervasive
due to the absence of conditional conformance. We shouldn’t be designing
our APIs around the assumption that conditional conformance doesn’t exist.

When conditional conformance is implemented, the only
should-be-comparable-but-aren’t types that will remain are tuples, which
we should potentially have the compiler synthesize conformances for.

Similarly, it should one day be possible to extend tuples, although this
is a more “far future” matter. Until then, the (T, T) -> Bool predicate
will always also be available, and < can be used there with the only
downside being a potential performance hit.
Just Leave Floats Alone

The fact that sorting floats leads to a mess, and storing floats can lead
to memory leaks and data loss isn’t acceptable.
Just Make Floats Only Have A Total Order

This was deemed too surprising for anyone familiar with floats from any
other language. It would also probably break a lot more code than this
change will.
Just Make Floats Not Comparable

Although floats are more subtle than integers, having places where
integers work but floats don’t is a poor state of affairs. One should be
able to sort an array of floats and use floats as keys in data structures,
even if the latter is difficult to do correctly.
PartialComparable

PartialComparable would essentially just be Comparable without any stated
ordering requirements, that Comparable extends to provide ordering
requirements. This would be a protocol that standard IEEE comparison could
satisfy, but in the absence of total ordering requirements,
PartialComparable is effectively useless. Either everyone would consume
PartialComparable (to accept floats) or Comparable (to have reasonable
behaviour).

The Rust community adopted this strategy to little benefit. The Rust libs
team has frequently considered removing the distinction, but hasn’t because
doing it backwards compatibly would be complicated. Also because merging
the two would just lead to the problems Swift has today.
Different Names For compare and ComparisonResult

A few different variants for ComparisonResult and its variants were
considered:

   - Dropping the ordered part of ComparisonResult’s cases e.g. .ascending
   - Naming of ComparisonResult as SortOrder
   - enum Ordering { case less, equal, greater } (as used by Rust
   <https://doc.rust-lang.org/std/cmp/enum.Ordering.html>)
   - Case values of inOrder, same, outOfOrder

The choice of case names is non-trivial because the enum shows up in
different contexts where different names makes more sense. Effectively, one
needs to keep in mind that the “default” sort order is ascending to map
between the concept of “before” and “less”.

The before/after naming to provide the most intuitive model for custom
sorts – referring to ascending or less is confusing when trying to
implement a descending ordering. Similarly the inOrder/outOfOrder naming
was too indirect – it’s more natural to just say where to put the element.
If the enum should focus on the sorting case, calling it SortOrder would
help to emphasize this fact.

This proposal elects to leave the existing Foundation name in-place. The
primary motivation for this is that use of the compare function will be
relatively rare. It is expected that in most cases users will continue to
make use of == or <, returning boolean values (the main exception to this
will be in use of the parameterized String comparisons). As such, the
source compatibility consequences of introducing naming changes to an
existing type seems of insufficient benefit.

The method compare(_:slight_smile: does not fully comport with the API naming
guidelines. However, it is firmly established with current usage in
Objective-C APIs, will be fairly rarely seen/used (users will usually
prefer <, == etc), and alternatives considered, for example compared(to:),
were not a significant improvement.
Add Overloads for (T, T) -> ComparisonResult

It would be slightly more ergonomic to work with ComparisonResult if
existing methods that took an ordering predicate also had an overload for (T,
T) -> ComparisonResult. As it stands, a case-insensitive sort must be
written as follows:

myStrings.sort { $0.compare(_ other: $1, case: .insensitive) == .orderedAscending }

With the overload, one could write:

myStrings.sort { $0.compare($1, case: .insensitive) }

we decided against providing these overloads because:

   - The existing algorithms in the standard library can’t benefit from
   them (only binary comparisons).
   - They bloat up the standard library (and any library which intends to
   match our API guidelines).
   - They potentially introduce confusion over “which” comparison
   overload to use.

And because we can change our mind later without concern for source or ABI
stability, as these overloads would be additive.
Future Work

This section covers some topics which were briefly considered, but were
identified as reasonable and possible to defer to future releases.
Specifically they should be backwards compatible to introduce even after
ABI stability. Two paths that are worth exploring:
Ergonomic Generalized Comparison for Keyed Containers

Can we make it ergonomic to use an (arbitrary) alternative comparison
strategy for a Dictionary or a BinaryTree? Should they be type-level
Comparators, or should those types always store a (Key, Key) ->
ComparisonResult closure?

We can avoid answering this question because Dictionary is expected to
keep a relatively opaque (resilient) ABI for the foreseeable future, as
many interesting optimizations will change its internal layout. Although if
the answer is type-level, then Default Generic Parameters must be accepted
to proceed down this path.
ComparisonResult Conveniences

There are a few conveniences we could consider providing to make
ComparisonResult more ergonomic to manipulate. Such as:

// A way to combine orderingsfunc ComparisonResult.breakingTiesWith(_ order: () -> ComparisonResult) -> ComparisonResult

array.sort {
  $0.x.compare($0.y)
  .breakingTiesWith { $0.y.compare($1.y) }
  == .orderedAscending
}

and

var inverted: ComparisonResult
// A perhaps more "clear" way to express reversing order than `y.compared(to: x)`
x.compare(y).inverted

But these can all be added later once everyone has had a chance to use
them.

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(David Hart) #7

Looking good. A few comments inline:

Hi swift evolution,

Here’s another pitch, for The Propoosal Formerly Known As Spaceship.
Comparison Reform

Proposal: SE-NNNN <file:///Users/ben_cohen/Documents/swift-evolution/proposals/NNNN-filename.md>
Authors: Robert Widmann <https://github.com/codafi>, Jaden Geller <https://github.com/jadengeller>, Harlan Haskins <https://github.com/harlanhaskins>, Alexis Beingessner <https://github.com/Gankro>, Ben Cohen <https://github.com/airspeedswift>
Status: Awaiting review
Review manager: TBD
Introduction

This proposal is for changes that we believe should be made to the existing comparison system by:

Making FloatingPoint comparison context sensitive, so that its Comparable conformance provides a proper total ordering.
Introducing a new ternary-valued compare(_ other: Self) -> ComparisonResult method.
Removing unnecessary customization points from Comparable.
Motivation

The motivation comes from several independent points:

1: 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 while still maintaining the traditional definition of “comparison” for these types. Take, for example, sorting an array of Floats. 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 unspecified. Similarly, a Dictionary keyed off floats can leak entries and memory.

2: Generic algorithms in the Swift Standard Library that make use of the current Comparable protocol may have to make extra comparisons to determine the ordering of values when <, ==, and > should have different behaviours. Having a central operation to return complete ordering information should provide a speedup for these operations.

3: The existing comparison operators don’t “generalize” well. There’s no clean way to add a third or fourth argument to < to ask for non-default semantics. An example where this would be desirable would be specifying the locale or case-sensitivity when comparing Strings.

4: Comparable is over-engineered in the customization points it provides: to our knowledge, there’s no good reason to ever override >=, >, or <=. Each customization point bloats vtables and mandates additional dynamic dispatch.

5: When quickly writing a Comparable type, it is easier to implement a single ternary statement than to separately implement == and <.

Proposed solution

ComparisonResult

Foundation’s ComparisonResult type will be mapped into Swift as

@objc public enum ComparisonResult : Int {
  case orderedAscending = -1
  case orderedSame = 0
  case orderedDescending = 1
}
Comparable

Comparable will be changed to have a new ternary comparison method: compare(_ other: Self) -> ComparisonResult. x.compare(y) specifies where to place x relative to y. So if it yields .orderedAscending, then x comes before y. This will be considered the new “main” dispatch point of Comparable that implementors should provide.

Most code will continue to use < or ==, as it will be optimal for their purposes. However code that needs to make a three-way branch on comparison can use the potentially more efficient compare. Note that compare is only expected to be more efficient in this specific case. If a two-way branch is all that’s being done, < will be more efficient in many cases (if only because it’s easier for the optimizer).

For backwards compatibility reasons, compare will have a default implementation defined in terms of <, but to enable only using compare, < and == will also have default implementations in terms of compare.

The compiler will verify that either compare, or < and ==, are provided by every type that claims to conform to Comparable. This will be done in some unspecified way unavailable outside the standard library (it can be made available to in the future, but that’s an unnecessary distraction for this proposal).

It feels weird to me to jump through all these hoops just for backwards compatibility. Seeing how even big projects might only have several Comparable conformances, wouldn’t it be worth removing the default implementation of compare and removing < from Comparable?

Types that wish to provide comparison “variants” can do so naturally by adding compare methods with additional arguments. e.g. String.compare(_ other: Self, in: Locale) -> ComparisonResult. These have no language-level connection to Comparable, but are still syntactically connected, implying the same total order semantics. This makes them easier to discover, learn, and migrate to.

To reduce bloat, the operators <=, >=, and > will be removed from the set of requirements that the Comparable protocol declares. These operators will however continue to exist with the current default implementations.

FloatingPoint

No changes will be made to the FloatingPoint protocol itself. Instead, new extensions will be added to it to change the behaviour of comparison.

The new behaviour centers around the fact that compare(_: Self) -> ComparisonResult will provide a total ordering that’s consistent with Level 2 in the IEEE 754 (2008) spec. This is mostly the same as the standard (Level 1) IEEE ordering, except:

-0 < +0
NaN == NaN
NaN > +Inf (an arbitrary choice, NaN can be placed anywhere in the number line)
Level 2’s distinguishing of -0 and +0 is a bit strange, but is consistent with Equatable’s Substitutability requirement. -0 and +0 have different behaviours: 1/-0 = -Inf while 1/+0 = +Inf. The main problem this can lead to is that a keyed collection may have two “0” entries. In practice this probably won’t be a problem because it’s fairly difficult for the same algorithm to produce both -0 and +0. Any algorithm that does is also probably concerned with the fact that 1.0E-128 and 2.0E-128 are considered distinct values.

Note: IEEE specifies several other potential total orderings: level 3, level 4, and the totalOrder predicate. For our purposes, these orderings are too aggressive in distinguishing values that are semantically equivalent in Swift. For most cases, the relevant issue is that they distinguish different encodings of NaN. For more exotic encodings that don’t guarantee normalization, these predicates also consider 10.0e0 < 1.0e1 to be true. An example where this can occur is IEEE-754 decimal coded floating point, which FloatingPoint is intended to support.

We will then make the comparison operators (<, <=, ==, !=, >=, >) dispatch to one of compare(_:slight_smile: or FloatingPoint’s IEEE comparison methods (isLess, isEqual, isLessThanOrEqualTo) based on the context.

If the context knows the type is FloatingPoint, then level 1 ordering will be used.
If the context only knows the type is Comparable or Equatable, then level 2 ordering will be used.
This results in code that is explicitly designed to work with FloatingPoint types getting the expected IEEE behaviour, while code that is only designed to work with Comparable types (e.g. sort and Dictionary) gets more reasonable total ordering behaviour.

To clarify: Dictionary and sort won’t somehow detect that they’re being used with FloatingPoint types and use level 1 comparisons. Instead they will unconditional use level 2 behaviour. For example:

let nan = 0.0/0.0

func printEqual<T: Equatable>(_ x: T, _ y: T) {
  print(x == y)
}

func printEqualFloats<T: FloatingPoint>(_ x: T, _ y: T) {
  print(x == y)
}

print(nan == nan) // false, (concrete)
printEqual(nan, nan) // true, (generic Equatable but not FloatingPoint)
printEqualFloats(nan, nan) // false, (generic FloatingPoint)
If one wishes to have a method that works with all Equatable/Comparable types, but uses level 1 semantics for FloatingPoint types, then they can simply provide two identical implementations that differ only in the bounds:

let nan = 0.0/0.0

func printEqual<T: Equatable>(_ x: T, _ y: T) {
  print(x == y)
}

func printEqual<T: FloatingPoint>(_ x: T, _ y: T) {
  print(x == y)
}

printEqual(0, 0) // true (integers use `<T: Equatable>` overload)
printEqual(nan, nan) // false (floats use `<T: FloatingPoint>` overload)
As a result of this change, hashing of floats must be updated to make all NaNs hash equally. -0 and +0 will also no longer be expected to hash equally. (Although they might as an implementation detail – equal values must hash the same, unequal values may hash the same.)

Misc Standard Library

Types that conform to Comparable should be audited for places where implementing or using Comparable would be a win. This update can be done incrementally, as the only potential impact should be performance. As an example, a default implementation of compare(_:slight_smile: for Array will likely be suboptimal, performing two linear scans to determine the result in the worst-case. (See the default implementation provided in the detailed design.)

Some free functions will have <T: FloatingPoint> overloads to better align with IEEE-754 semantics. This will be addressed in a follow-up proposal. (example: min and max)

Detailed Design

The protocols will be changed as follows:

ComparisonResult, currently a type found in Foundation, will be sunk into the Swift Standard Library:

@objc public enum ComparisonResult: Int, Equatable {
  case orderedAscending = -1
  case orderedSame = 0
  case orderedDescending = 1
}

public protocol Comparable: Equatable {
  func compare(_ other: Self) -> ComparisonResult

  static func < (lhs: Self, rhs: Self) -> Bool
}

extension Comparable {
  func compare(_ other: Self) -> ComparisonResult {
    if self == other {
      return .orderedSame
    } else if self < other {
      return .orderedAscending
    } else {
      return .orderedDescending
    }
  }
}

public func < <T: Comparable>(lhs: T, rhs: T) -> Bool {
  return lhs.compare(rhs) == .orderedAscending
}

// IEEE comparison operators (these implementations already exist in std)
extension FloatingPoint {
  public static func == (lhs: T, rhs: T) -> Bool {
    return lhs.isEqual(to: rhs)
  }

  public static func < (lhs: T, rhs: T) -> Bool {
    return lhs.isLess(than: rhs)
  }

  public static func <= (lhs: T, rhs: T) -> Bool {
    return lhs.isLessThanOrEqualTo(rhs)
  }

  public static func > (lhs: T, rhs: T) -> Bool {
    return rhs.isLess(than: lhs)
  }

  public static func >= (lhs: T, rhs: T) -> Bool {
    return rhs.isLessThanOrEqualTo(lhs)
  }
}

// Comparable comparison operators (provides a total ordering)
extension FloatingPoint {
  @_inline
  public func compare(_ other: Self) -> ComparisonResult {
    // Can potentially be implemented more efficiently -- this is just the clearest version
    if self.isLess(than: other) {
      return .orderedAscending
    } else if other.isLess(than: self) {
      return .orderedDescending
    } else {
      // Special cases

      // -0 < +0
      if self.isZero && other.isZero {
        // .plus == 0 and .minus == 1, so flip ordering to get - < +
        return (other.sign as Int).compare(self.sign as Int)
      }

      // NaN == NaN, NaN > +Inf
      if self.isNaN {
        if other.isNaN {
          return .orderedSame
        } else {
          return .orderedDescending
        }
      } else if other.isNaN {
        return .orderedAscending
      }

      // Otherwise equality agrees with normal IEEE
      return .orderedSame
    }
  }

  @_implements(Equatable.==)
  public static func _comparableEqual(lhs: Self, rhs: Self) -> Bool {
    lhs.compare(rhs) == .orderedSame
  }

  @_implements(Comparable.<)
  public static func _comparableLessThan(lhs: Self, rhs: Self) -> Bool {
    lhs.compare(rhs) == .orderedDescending
  }
}
Note that this design mandates changes to the compiler:

@_implements (or an equivalent mechanism) must be implemented to get the context-sensitive FloatingPoint behaviour.
The compiler must verify that either == and <, or compare(_:slight_smile: is overridden by every type that conforms to Comparable.
Source compatibility

Users of ComparisonResult will be able to use it as normal once it becomes a standard library type.

Existing implementors of Comparable will be unaffected, though they should consider implementing the new compare method as the default implementation may be suboptimal.

Consumers of Comparable will be unaffected, though they should consider calling the compare method if it offers a performance advantage for their particular algorithm.

Existing implementors of FloatingPoint should be unaffected – they will automatically get the new behaviour as long as they aren’t manually implementing the requirements of Equatable/Comparable.

Existing code that works with floats may break if it’s relying on some code bounded on <T: Equatable/Comparable>providing IEEE semantics. For most algorithms, NaNs would essentially lead to unspecified behaviour, so the primary concern is whether -0.0 == +0.0 matters.

ABI stability

This must be implemented before ABI stability is declared.

Effect on API resilience

N/A

Alternatives Considered

Spaceship

Early versions of this proposal aimed to instead provide a <=> operator in place of compare. The only reason we moved away from this was that it didn’t solve the problem that comparison didn’t generalize.

Spaceship as an operator has a two concrete benefits over compare today:

It can be passed to a higher-order function
Tuples can implement it
In our opinion, these aren’t serious problems, especially in the long term.

Passing <=> as a higher order function basically allows types that aren’t Comparable, but do provide <=>, to be very ergonomically handled by algorithms which take an optional ordering function. Types which provide the comparable operators but don’t conform to Comparable are only pervasive due to the absence of conditional conformance. We shouldn’t be designing our APIs around the assumption that conditional conformance doesn’t exist.

When conditional conformance is implemented, the only should-be-comparable-but-aren’t types that will remain are tuples, which we should potentially have the compiler synthesize conformances for.

Similarly, it should one day be possible to extend tuples, although this is a more “far future” matter. Until then, the (T, T) -> Bool predicate will always also be available, and < can be used there with the only downside being a potential performance hit.

Just Leave Floats Alone

The fact that sorting floats leads to a mess, and storing floats can lead to memory leaks and data loss isn’t acceptable.

Just Make Floats Only Have A Total Order

This was deemed too surprising for anyone familiar with floats from any other language. It would also probably break a lot more code than this change will.

Just Make Floats Not Comparable

Although floats are more subtle than integers, having places where integers work but floats don’t is a poor state of affairs. One should be able to sort an array of floats and use floats as keys in data structures, even if the latter is difficult to do correctly.

PartialComparable

PartialComparable would essentially just be Comparable without any stated ordering requirements, that Comparable extends to provide ordering requirements. This would be a protocol that standard IEEE comparison could satisfy, but in the absence of total ordering requirements, PartialComparable is effectively useless. Either everyone would consume PartialComparable (to accept floats) or Comparable (to have reasonable behaviour).

The Rust community adopted this strategy to little benefit. The Rust libs team has frequently considered removing the distinction, but hasn’t because doing it backwards compatibly would be complicated. Also because merging the two would just lead to the problems Swift has today.

Different Names For compare and ComparisonResult

A few different variants for ComparisonResult and its variants were considered:

Dropping the ordered part of ComparisonResult’s cases e.g. .ascending
Naming of ComparisonResult as SortOrder
enum Ordering { case less, equal, greater } (as used by Rust <https://doc.rust-lang.org/std/cmp/enum.Ordering.html>)
Case values of inOrder, same, outOfOrder
The choice of case names is non-trivial because the enum shows up in different contexts where different names makes more sense. Effectively, one needs to keep in mind that the “default” sort order is ascending to map between the concept of “before” and “less”.

The before/after naming to provide the most intuitive model for custom sorts – referring to ascending or less is confusing when trying to implement a descending ordering. Similarly the inOrder/outOfOrder naming was too indirect – it’s more natural to just say where to put the element. If the enum should focus on the sorting case, calling it SortOrder would help to emphasize this fact.

Can you give an example where ascending/descending/equal can be confusing?

This proposal elects to leave the existing Foundation name in-place. The primary motivation for this is that use of the compare function will be relatively rare. It is expected that in most cases users will continue to make use of == or <, returning boolean values (the main exception to this will be in use of the parameterized String comparisons). As such, the source compatibility consequences of introducing naming changes to an existing type seems of insufficient benefit.

The method compare(_:slight_smile: does not fully comport with the API naming guidelines. However, it is firmly established with current usage in Objective-C APIs, will be fairly rarely seen/used (users will usually prefer <, == etc), and alternatives considered, for example compared(to:), were not a significant improvement.

Uses of the compare function might be rare, but I still think it should follow the API naming guidelines. I don’t think that Objective-C conventions are a strong enough argument to warrant breaking those guidelines, especially in the Standard Library.

···

On 13 Apr 2017, at 22:17, Ben Cohen via swift-evolution <swift-evolution@swift.org> wrote:
Add Overloads for (T, T) -> ComparisonResult

It would be slightly more ergonomic to work with ComparisonResult if existing methods that took an ordering predicate also had an overload for (T, T) -> ComparisonResult. As it stands, a case-insensitive sort must be written as follows:

myStrings.sort { $0.compare(_ other: $1, case: .insensitive) == .orderedAscending }
With the overload, one could write:

myStrings.sort { $0.compare($1, case: .insensitive) }
we decided against providing these overloads because:

The existing algorithms in the standard library can’t benefit from them (only binary comparisons).
They bloat up the standard library (and any library which intends to match our API guidelines).
They potentially introduce confusion over “which” comparison overload to use.
And because we can change our mind later without concern for source or ABI stability, as these overloads would be additive.

Future Work

This section covers some topics which were briefly considered, but were identified as reasonable and possible to defer to future releases. Specifically they should be backwards compatible to introduce even after ABI stability. Two paths that are worth exploring:

Ergonomic Generalized Comparison for Keyed Containers

Can we make it ergonomic to use an (arbitrary) alternative comparison strategy for a Dictionary or a BinaryTree? Should they be type-level Comparators, or should those types always store a (Key, Key) -> ComparisonResult closure?

We can avoid answering this question because Dictionary is expected to keep a relatively opaque (resilient) ABI for the foreseeable future, as many interesting optimizations will change its internal layout. Although if the answer is type-level, then Default Generic Parameters must be accepted to proceed down this path.

ComparisonResult Conveniences

There are a few conveniences we could consider providing to make ComparisonResult more ergonomic to manipulate. Such as:

// A way to combine orderings
func ComparisonResult.breakingTiesWith(_ order: () -> ComparisonResult) -> ComparisonResult

array.sort {
  $0.x.compare($0.y)
  .breakingTiesWith { $0.y.compare($1.y) }
  == .orderedAscending
}
and

var inverted: ComparisonResult

// A perhaps more "clear" way to express reversing order than `y.compared(to: x)`
x.compare(y).inverted
But these can all be added later once everyone has had a chance to use them.

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(David Waite) #8

To me, there are two proposals here, partly interrelated but worth considering separately.

1. Use of @_implements to allow floating point to have an IEEE implementation of operators, while still having Comparable implement strict total order across every unique value (NaN.)

This includes normalizing NaN to always be considered a single unique value within each floating point type.

2. Defining a comparison function which can encompass implementations of all of the operator overloads, and eliminating all operator overloads other than < (preserved for backwards compatibility)

The interrelation these seems to be limited to the backward compatibility with Comparable - if not for Comparable originally being defined in terms of operator <, it might be possible to instead say that the compare method always adheres to strict total ordering. While a default implementation of the operators are provided based on Comparable, implementing types may choose to have overloads which do not adhere to strict total ordering.

Most superfluous feedback first: I think the enum cases could be shortened to .ascending, .same, .descending

More worthy of discussion is whether or not at the equatable level, +0 == -0. This is not a requirement of strict total ordering, but of the substitutability requirement of equality. My worry is that people may run into inconsistent behavior around this due to the use of the specific vs generic type more often than they would with the NaN value.

-DW

···

On Apr 13, 2017, at 2:17 PM, Ben Cohen via swift-evolution <swift-evolution@swift.org> wrote:

Hi swift evolution,

Here’s another pitch, for The Propoosal Formerly Known As Spaceship.
Comparison Reform

Proposal: SE-NNNN <file:///Users/ben_cohen/Documents/swift-evolution/proposals/NNNN-filename.md>
Authors: Robert Widmann <https://github.com/codafi>, Jaden Geller <https://github.com/jadengeller>, Harlan Haskins <https://github.com/harlanhaskins>, Alexis Beingessner <https://github.com/Gankro>, Ben Cohen <https://github.com/airspeedswift>
Status: Awaiting review
Review manager: TBD
Introduction

This proposal is for changes that we believe should be made to the existing comparison system by:

Making FloatingPoint comparison context sensitive, so that its Comparable conformance provides a proper total ordering.
Introducing a new ternary-valued compare(_ other: Self) -> ComparisonResult method.
Removing unnecessary customization points from Comparable.
Motivation

The motivation comes from several independent points:

1: 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 while still maintaining the traditional definition of “comparison” for these types. Take, for example, sorting an array of Floats. 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 unspecified. Similarly, a Dictionary keyed off floats can leak entries and memory.

2: Generic algorithms in the Swift Standard Library that make use of the current Comparable protocol may have to make extra comparisons to determine the ordering of values when <, ==, and > should have different behaviours. Having a central operation to return complete ordering information should provide a speedup for these operations.

3: The existing comparison operators don’t “generalize” well. There’s no clean way to add a third or fourth argument to < to ask for non-default semantics. An example where this would be desirable would be specifying the locale or case-sensitivity when comparing Strings.

4: Comparable is over-engineered in the customization points it provides: to our knowledge, there’s no good reason to ever override >=, >, or <=. Each customization point bloats vtables and mandates additional dynamic dispatch.

5: When quickly writing a Comparable type, it is easier to implement a single ternary statement than to separately implement == and <.

Proposed solution

ComparisonResult

Foundation’s ComparisonResult type will be mapped into Swift as

@objc public enum ComparisonResult : Int {
  case orderedAscending = -1
  case orderedSame = 0
  case orderedDescending = 1
}
Comparable

Comparable will be changed to have a new ternary comparison method: compare(_ other: Self) -> ComparisonResult. x.compare(y) specifies where to place x relative to y. So if it yields .orderedAscending, then x comes before y. This will be considered the new “main” dispatch point of Comparable that implementors should provide.

Most code will continue to use < or ==, as it will be optimal for their purposes. However code that needs to make a three-way branch on comparison can use the potentially more efficient compare. Note that compare is only expected to be more efficient in this specific case. If a two-way branch is all that’s being done, < will be more efficient in many cases (if only because it’s easier for the optimizer).

For backwards compatibility reasons, compare will have a default implementation defined in terms of <, but to enable only using compare, < and == will also have default implementations in terms of compare.

The compiler will verify that either compare, or < and ==, are provided by every type that claims to conform to Comparable. This will be done in some unspecified way unavailable outside the standard library (it can be made available to in the future, but that’s an unnecessary distraction for this proposal).

Types that wish to provide comparison “variants” can do so naturally by adding compare methods with additional arguments. e.g. String.compare(_ other: Self, in: Locale) -> ComparisonResult. These have no language-level connection to Comparable, but are still syntactically connected, implying the same total order semantics. This makes them easier to discover, learn, and migrate to.

To reduce bloat, the operators <=, >=, and > will be removed from the set of requirements that the Comparable protocol declares. These operators will however continue to exist with the current default implementations.

FloatingPoint

No changes will be made to the FloatingPoint protocol itself. Instead, new extensions will be added to it to change the behaviour of comparison.

The new behaviour centers around the fact that compare(_: Self) -> ComparisonResult will provide a total ordering that’s consistent with Level 2 in the IEEE 754 (2008) spec. This is mostly the same as the standard (Level 1) IEEE ordering, except:

-0 < +0
NaN == NaN
NaN > +Inf (an arbitrary choice, NaN can be placed anywhere in the number line)
Level 2’s distinguishing of -0 and +0 is a bit strange, but is consistent with Equatable’s Substitutability requirement. -0 and +0 have different behaviours: 1/-0 = -Inf while 1/+0 = +Inf. The main problem this can lead to is that a keyed collection may have two “0” entries. In practice this probably won’t be a problem because it’s fairly difficult for the same algorithm to produce both -0 and +0. Any algorithm that does is also probably concerned with the fact that 1.0E-128 and 2.0E-128 are considered distinct values.

Note: IEEE specifies several other potential total orderings: level 3, level 4, and the totalOrder predicate. For our purposes, these orderings are too aggressive in distinguishing values that are semantically equivalent in Swift. For most cases, the relevant issue is that they distinguish different encodings of NaN. For more exotic encodings that don’t guarantee normalization, these predicates also consider 10.0e0 < 1.0e1 to be true. An example where this can occur is IEEE-754 decimal coded floating point, which FloatingPoint is intended to support.

We will then make the comparison operators (<, <=, ==, !=, >=, >) dispatch to one of compare(_:slight_smile: or FloatingPoint’s IEEE comparison methods (isLess, isEqual, isLessThanOrEqualTo) based on the context.

If the context knows the type is FloatingPoint, then level 1 ordering will be used.
If the context only knows the type is Comparable or Equatable, then level 2 ordering will be used.
This results in code that is explicitly designed to work with FloatingPoint types getting the expected IEEE behaviour, while code that is only designed to work with Comparable types (e.g. sort and Dictionary) gets more reasonable total ordering behaviour.

To clarify: Dictionary and sort won’t somehow detect that they’re being used with FloatingPoint types and use level 1 comparisons. Instead they will unconditional use level 2 behaviour. For example:

let nan = 0.0/0.0

func printEqual<T: Equatable>(_ x: T, _ y: T) {
  print(x == y)
}

func printEqualFloats<T: FloatingPoint>(_ x: T, _ y: T) {
  print(x == y)
}

print(nan == nan) // false, (concrete)
printEqual(nan, nan) // true, (generic Equatable but not FloatingPoint)
printEqualFloats(nan, nan) // false, (generic FloatingPoint)
If one wishes to have a method that works with all Equatable/Comparable types, but uses level 1 semantics for FloatingPoint types, then they can simply provide two identical implementations that differ only in the bounds:

let nan = 0.0/0.0

func printEqual<T: Equatable>(_ x: T, _ y: T) {
  print(x == y)
}

func printEqual<T: FloatingPoint>(_ x: T, _ y: T) {
  print(x == y)
}

printEqual(0, 0) // true (integers use `<T: Equatable>` overload)
printEqual(nan, nan) // false (floats use `<T: FloatingPoint>` overload)
As a result of this change, hashing of floats must be updated to make all NaNs hash equally. -0 and +0 will also no longer be expected to hash equally. (Although they might as an implementation detail – equal values must hash the same, unequal values may hash the same.)

Misc Standard Library

Types that conform to Comparable should be audited for places where implementing or using Comparable would be a win. This update can be done incrementally, as the only potential impact should be performance. As an example, a default implementation of compare(_:slight_smile: for Array will likely be suboptimal, performing two linear scans to determine the result in the worst-case. (See the default implementation provided in the detailed design.)

Some free functions will have <T: FloatingPoint> overloads to better align with IEEE-754 semantics. This will be addressed in a follow-up proposal. (example: min and max)

Detailed Design

The protocols will be changed as follows:

ComparisonResult, currently a type found in Foundation, will be sunk into the Swift Standard Library:

@objc public enum ComparisonResult: Int, Equatable {
  case orderedAscending = -1
  case orderedSame = 0
  case orderedDescending = 1
}

public protocol Comparable: Equatable {
  func compare(_ other: Self) -> ComparisonResult

  static func < (lhs: Self, rhs: Self) -> Bool
}

extension Comparable {
  func compare(_ other: Self) -> ComparisonResult {
    if self == other {
      return .orderedSame
    } else if self < other {
      return .orderedAscending
    } else {
      return .orderedDescending
    }
  }
}

public func < <T: Comparable>(lhs: T, rhs: T) -> Bool {
  return lhs.compare(rhs) == .orderedAscending
}

// IEEE comparison operators (these implementations already exist in std)
extension FloatingPoint {
  public static func == (lhs: T, rhs: T) -> Bool {
    return lhs.isEqual(to: rhs)
  }

  public static func < (lhs: T, rhs: T) -> Bool {
    return lhs.isLess(than: rhs)
  }

  public static func <= (lhs: T, rhs: T) -> Bool {
    return lhs.isLessThanOrEqualTo(rhs)
  }

  public static func > (lhs: T, rhs: T) -> Bool {
    return rhs.isLess(than: lhs)
  }

  public static func >= (lhs: T, rhs: T) -> Bool {
    return rhs.isLessThanOrEqualTo(lhs)
  }
}

// Comparable comparison operators (provides a total ordering)
extension FloatingPoint {
  @_inline
  public func compare(_ other: Self) -> ComparisonResult {
    // Can potentially be implemented more efficiently -- this is just the clearest version
    if self.isLess(than: other) {
      return .orderedAscending
    } else if other.isLess(than: self) {
      return .orderedDescending
    } else {
      // Special cases

      // -0 < +0
      if self.isZero && other.isZero {
        // .plus == 0 and .minus == 1, so flip ordering to get - < +
        return (other.sign as Int).compare(self.sign as Int)
      }

      // NaN == NaN, NaN > +Inf
      if self.isNaN {
        if other.isNaN {
          return .orderedSame
        } else {
          return .orderedDescending
        }
      } else if other.isNaN {
        return .orderedAscending
      }

      // Otherwise equality agrees with normal IEEE
      return .orderedSame
    }
  }

  @_implements(Equatable.==)
  public static func _comparableEqual(lhs: Self, rhs: Self) -> Bool {
    lhs.compare(rhs) == .orderedSame
  }

  @_implements(Comparable.<)
  public static func _comparableLessThan(lhs: Self, rhs: Self) -> Bool {
    lhs.compare(rhs) == .orderedDescending
  }
}
Note that this design mandates changes to the compiler:

@_implements (or an equivalent mechanism) must be implemented to get the context-sensitive FloatingPoint behaviour.
The compiler must verify that either == and <, or compare(_:slight_smile: is overridden by every type that conforms to Comparable.
Source compatibility

Users of ComparisonResult will be able to use it as normal once it becomes a standard library type.

Existing implementors of Comparable will be unaffected, though they should consider implementing the new compare method as the default implementation may be suboptimal.

Consumers of Comparable will be unaffected, though they should consider calling the compare method if it offers a performance advantage for their particular algorithm.

Existing implementors of FloatingPoint should be unaffected – they will automatically get the new behaviour as long as they aren’t manually implementing the requirements of Equatable/Comparable.

Existing code that works with floats may break if it’s relying on some code bounded on <T: Equatable/Comparable>providing IEEE semantics. For most algorithms, NaNs would essentially lead to unspecified behaviour, so the primary concern is whether -0.0 == +0.0 matters.

ABI stability

This must be implemented before ABI stability is declared.

Effect on API resilience

N/A

Alternatives Considered

Spaceship

Early versions of this proposal aimed to instead provide a <=> operator in place of compare. The only reason we moved away from this was that it didn’t solve the problem that comparison didn’t generalize.

Spaceship as an operator has a two concrete benefits over compare today:

It can be passed to a higher-order function
Tuples can implement it
In our opinion, these aren’t serious problems, especially in the long term.

Passing <=> as a higher order function basically allows types that aren’t Comparable, but do provide <=>, to be very ergonomically handled by algorithms which take an optional ordering function. Types which provide the comparable operators but don’t conform to Comparable are only pervasive due to the absence of conditional conformance. We shouldn’t be designing our APIs around the assumption that conditional conformance doesn’t exist.

When conditional conformance is implemented, the only should-be-comparable-but-aren’t types that will remain are tuples, which we should potentially have the compiler synthesize conformances for.

Similarly, it should one day be possible to extend tuples, although this is a more “far future” matter. Until then, the (T, T) -> Bool predicate will always also be available, and < can be used there with the only downside being a potential performance hit.

Just Leave Floats Alone

The fact that sorting floats leads to a mess, and storing floats can lead to memory leaks and data loss isn’t acceptable.

Just Make Floats Only Have A Total Order

This was deemed too surprising for anyone familiar with floats from any other language. It would also probably break a lot more code than this change will.

Just Make Floats Not Comparable

Although floats are more subtle than integers, having places where integers work but floats don’t is a poor state of affairs. One should be able to sort an array of floats and use floats as keys in data structures, even if the latter is difficult to do correctly.

PartialComparable

PartialComparable would essentially just be Comparable without any stated ordering requirements, that Comparable extends to provide ordering requirements. This would be a protocol that standard IEEE comparison could satisfy, but in the absence of total ordering requirements, PartialComparable is effectively useless. Either everyone would consume PartialComparable (to accept floats) or Comparable (to have reasonable behaviour).

The Rust community adopted this strategy to little benefit. The Rust libs team has frequently considered removing the distinction, but hasn’t because doing it backwards compatibly would be complicated. Also because merging the two would just lead to the problems Swift has today.

Different Names For compare and ComparisonResult

A few different variants for ComparisonResult and its variants were considered:

Dropping the ordered part of ComparisonResult’s cases e.g. .ascending
Naming of ComparisonResult as SortOrder
enum Ordering { case less, equal, greater } (as used by Rust <https://doc.rust-lang.org/std/cmp/enum.Ordering.html>)
Case values of inOrder, same, outOfOrder
The choice of case names is non-trivial because the enum shows up in different contexts where different names makes more sense. Effectively, one needs to keep in mind that the “default” sort order is ascending to map between the concept of “before” and “less”.

The before/after naming to provide the most intuitive model for custom sorts – referring to ascending or less is confusing when trying to implement a descending ordering. Similarly the inOrder/outOfOrder naming was too indirect – it’s more natural to just say where to put the element. If the enum should focus on the sorting case, calling it SortOrder would help to emphasize this fact.

This proposal elects to leave the existing Foundation name in-place. The primary motivation for this is that use of the compare function will be relatively rare. It is expected that in most cases users will continue to make use of == or <, returning boolean values (the main exception to this will be in use of the parameterized String comparisons). As such, the source compatibility consequences of introducing naming changes to an existing type seems of insufficient benefit.

The method compare(_:slight_smile: does not fully comport with the API naming guidelines. However, it is firmly established with current usage in Objective-C APIs, will be fairly rarely seen/used (users will usually prefer <, == etc), and alternatives considered, for example compared(to:), were not a significant improvement.

Add Overloads for (T, T) -> ComparisonResult

It would be slightly more ergonomic to work with ComparisonResult if existing methods that took an ordering predicate also had an overload for (T, T) -> ComparisonResult. As it stands, a case-insensitive sort must be written as follows:

myStrings.sort { $0.compare(_ other: $1, case: .insensitive) == .orderedAscending }
With the overload, one could write:

myStrings.sort { $0.compare($1, case: .insensitive) }
we decided against providing these overloads because:

The existing algorithms in the standard library can’t benefit from them (only binary comparisons).
They bloat up the standard library (and any library which intends to match our API guidelines).
They potentially introduce confusion over “which” comparison overload to use.
And because we can change our mind later without concern for source or ABI stability, as these overloads would be additive.

Future Work

This section covers some topics which were briefly considered, but were identified as reasonable and possible to defer to future releases. Specifically they should be backwards compatible to introduce even after ABI stability. Two paths that are worth exploring:

Ergonomic Generalized Comparison for Keyed Containers

Can we make it ergonomic to use an (arbitrary) alternative comparison strategy for a Dictionary or a BinaryTree? Should they be type-level Comparators, or should those types always store a (Key, Key) -> ComparisonResult closure?

We can avoid answering this question because Dictionary is expected to keep a relatively opaque (resilient) ABI for the foreseeable future, as many interesting optimizations will change its internal layout. Although if the answer is type-level, then Default Generic Parameters must be accepted to proceed down this path.

ComparisonResult Conveniences

There are a few conveniences we could consider providing to make ComparisonResult more ergonomic to manipulate. Such as:

// A way to combine orderings
func ComparisonResult.breakingTiesWith(_ order: () -> ComparisonResult) -> ComparisonResult

array.sort {
  $0.x.compare($0.y)
  .breakingTiesWith { $0.y.compare($1.y) }
  == .orderedAscending
}
and

var inverted: ComparisonResult

// A perhaps more "clear" way to express reversing order than `y.compared(to: x)`
x.compare(y).inverted
But these can all be added later once everyone has had a chance to use them.

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Jon Hull) #9

It feels weird to me to jump through all these hoops just for backwards compatibility. Seeing how even big projects might only have several Comparable conformances, wouldn’t it be worth removing the default implementation of compare and removing < from Comparable?

It isn’t just backwards compatibility. As someone who has worked with both forms of comparable, I can say that just implementing ‘<‘ is much easier, especially when you are just chaining results of comparing components. In one case I can just use ‘||' and ‘&&’, the other may require pattern matching in a switch. (I usually still have to implement ‘==‘ anyway in both cases, so it isn’t a difference between the two).

Different Names For compare and ComparisonResult

A few different variants for ComparisonResult and its variants were considered:

Dropping the ordered part of ComparisonResult’s cases e.g. .ascending
Naming of ComparisonResult as SortOrder
enum Ordering { case less, equal, greater } (as used by Rust <https://doc.rust-lang.org/std/cmp/enum.Ordering.html>)
Case values of inOrder, same, outOfOrder
The choice of case names is non-trivial because the enum shows up in different contexts where different names makes more sense. Effectively, one needs to keep in mind that the “default” sort order is ascending to map between the concept of “before” and “less”.

The before/after naming to provide the most intuitive model for custom sorts – referring to ascending or less is confusing when trying to implement a descending ordering. Similarly the inOrder/outOfOrder naming was too indirect – it’s more natural to just say where to put the element. If the enum should focus on the sorting case, calling it SortOrder would help to emphasize this fact.

Can you give an example where ascending/descending/equal can be confusing?

Agreed. Ascending & Descending imply an ordering to me. I don’t see how the extra ‘ordered’ clarifies anything…

This proposal elects to leave the existing Foundation name in-place. The primary motivation for this is that use of the compare function will be relatively rare. It is expected that in most cases users will continue to make use of == or <, returning boolean values (the main exception to this will be in use of the parameterized String comparisons). As such, the source compatibility consequences of introducing naming changes to an existing type seems of insufficient benefit.

The method compare(_:slight_smile: does not fully comport with the API naming guidelines. However, it is firmly established with current usage in Objective-C APIs, will be fairly rarely seen/used (users will usually prefer <, == etc), and alternatives considered, for example compared(to:), were not a significant improvement.

Uses of the compare function might be rare, but I still think it should follow the API naming guidelines. I don’t think that Objective-C conventions are a strong enough argument to warrant breaking those guidelines, especially in the Standard Library.

Agreed.

Thanks,
Jon

···

On Apr 13, 2017, at 2:42 PM, David Hart via swift-evolution <swift-evolution@swift.org> wrote:


(Jon Hull) #10

This is a sugar request, but if we are rearranging these things anyway, can we *please* add the ‘≤’, ‘≥’, and ‘≠’ operators to comparable. I know they would do the same thing as ‘<=‘, ‘>=‘, and ‘!=‘, but they can’t really be used for anything else without being confusing (because they literally have that meaning in mathematics), and they make my code so much more readable.

Thanks,
Jon

···

On Apr 13, 2017, at 1:24 PM, Ben Cohen via swift-evolution <swift-evolution@swift.org> wrote:

Online copy here:

https://github.com/airspeedswift/swift-evolution/blob/fa007138a54895e94d22e053122ca24ffa0b2eeb/proposals/NNNN-ComparisonReform.md


(TJ Usiyan) #11

+1 from me. I've ended up at a solution like this for my own code. It would
be a great to have in the standard lib.

···

On Thu, Apr 13, 2017 at 4:24 PM, Ben Cohen via swift-evolution < swift-evolution@swift.org> wrote:

Online copy here:

https://github.com/airspeedswift/swift-evolution/blob/
fa007138a54895e94d22e053122ca24ffa0b2eeb/proposals/NNNN-
ComparisonReform.md

On Apr 13, 2017, at 1:17 PM, Ben Cohen via swift-evolution < > swift-evolution@swift.org> wrote:

Hi swift evolution,

Here’s another pitch, for The Propoosal Formerly Known As Spaceship.
Comparison Reform

   - Proposal: SE-NNNN
   - Authors: Robert Widmann <https://github.com/codafi>, Jaden Geller
   <https://github.com/jadengeller>, Harlan Haskins
   <https://github.com/harlanhaskins>, Alexis Beingessner
   <https://github.com/Gankro>, Ben Cohen
   <https://github.com/airspeedswift>
   - Status: *Awaiting review*
   - Review manager: TBD

Introduction

This proposal is for changes that we believe should be made to the
existing comparison system by:

   - Making FloatingPoint comparison context sensitive, so that its
   Comparable conformance provides a proper total ordering.
   - Introducing a new ternary-valued compare(_ other: Self) ->
   ComparisonResult method.
   - Removing unnecessary customization points from Comparable.

Motivation

The motivation comes from several independent points:

1: 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 while still
maintaining the traditional definition of “comparison” for these types.
Take, for example, sorting an array of Floats. 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 unspecified. Similarly,
a Dictionary keyed off floats can leak entries and memory.

2: Generic algorithms in the Swift Standard Library that make use of the
current Comparable protocol may have to make extra comparisons to
determine the ordering of values when <, ==, and > should have different
behaviours. Having a central operation to return complete ordering
information should provide a speedup for these operations.

3: The existing comparison operators don’t “generalize” well. There’s no
clean way to add a third or fourth argument to < to ask for non-default
semantics. An example where this would be desirable would be specifying the
locale or case-sensitivity when comparing Strings.

4: Comparable is over-engineered in the customization points it provides:
to our knowledge, there’s no good reason to ever override >=, >, or <=.
Each customization point bloats vtables and mandates additional dynamic
dispatch.

5: When quickly writing a Comparable type, it is easier to implement a
single ternary statement than to separately implement == and <.
Proposed solutionComparisonResult

Foundation’s ComparisonResult type will be mapped into Swift as

@objc public enum ComparisonResult : Int {
  case orderedAscending = -1
  case orderedSame = 0
  case orderedDescending = 1
}

Comparable

Comparable will be changed to have a new ternary comparison method: compare(_
other: Self) -> ComparisonResult. x.compare(y) specifies where to place x
relative to y. So if it yields .orderedAscending, then x comes before y.
This will be considered the new “main” dispatch point of Comparable that
implementors should provide.

Most code will continue to use < or ==, as it will be optimal for their
purposes. However code that needs to make a three-way branch on comparison
can use the potentially more efficient compare. Note that compare is only
expected to be more efficient in this specific case. If a two-way branch is
all that’s being done, < will be more efficient in many cases (if only
because it’s easier for the optimizer).

For backwards compatibility reasons, compare will have a default
implementation defined in terms of <, but to enable only using compare, <
and == will also have default implementations in terms of compare.

The compiler will verify that either compare, or < and ==, are provided
by every type that claims to conform to Comparable. This will be done in
some unspecified way unavailable outside the standard library (it can be
made available to in the future, but that’s an unnecessary distraction for
this proposal).

Types that wish to provide comparison “variants” can do so naturally by
adding compare methods with additional arguments. e.g. String.compare(_
other: Self, in: Locale) -> ComparisonResult. These have no
language-level connection to Comparable, but are still syntactically
connected, implying the same total order semantics. This makes them easier
to discover, learn, and migrate to.

To reduce bloat, the operators <=, >=, and > will be removed from the set
of requirements that the Comparable protocol declares. These operators
will however continue to exist with the current default implementations.
FloatingPoint

No changes will be made to the FloatingPoint protocol itself. Instead,
new extensions will be added to it to change the behaviour of comparison.

The new behaviour centers around the fact that compare(_: Self) ->
ComparisonResult will provide a total ordering that’s consistent with
Level 2 in the IEEE 754 (2008) spec. This is mostly the same as the
standard (Level 1) IEEE ordering, except:

   - -0 < +0
   - NaN == NaN
   - NaN > +Inf (an arbitrary choice, NaN can be placed anywhere in the
   number line)

Level 2’s distinguishing of -0 and +0 is a bit strange, but is consistent
with Equatable’s Substitutability requirement. -0 and +0 have different
behaviours: 1/-0 = -Inf while 1/+0 = +Inf. The main problem this can lead
to is that a keyed collection may have two “0” entries. In practice this
probably won’t be a problem because it’s fairly difficult for the same
algorithm to produce both -0 and +0. Any algorithm that does is also
probably concerned with the fact that 1.0E-128 and 2.0E-128 are
considered distinct values.

Note: IEEE specifies several other potential total orderings: level 3,
level 4, and the totalOrder predicate. For our purposes, these orderings
are too aggressive in distinguishing values that are semantically
equivalent in Swift. For most cases, the relevant issue is that they
distinguish different encodings of NaN. For more exotic encodings that
don’t guarantee normalization, these predicates also consider 10.0e0 <
1.0e1 to be true. An example where this can occur is *IEEE-754 decimal
coded floating point*, which FloatingPoint is intended to support.

We will then make the comparison operators (<, <=, ==, !=, >=, >)
dispatch to one of compare(_:slight_smile: or FloatingPoint’s IEEE comparison methods
(isLess, isEqual, isLessThanOrEqualTo) based on the context.

   - If the context knows the type is FloatingPoint, then level 1
   ordering will be used.
   - If the context only knows the type is Comparable or Equatable, then
   level 2 ordering will be used.

This results in code that is explicitly designed to work with
FloatingPoint types getting the expected IEEE behaviour, while code that is
only designed to work with Comparable types (e.g. sort and Dictionary)
gets more reasonable total ordering behaviour.

To clarify: Dictionary and sort won’t somehow detect that they’re being
used with FloatingPoint types and use level 1 comparisons. Instead they
will unconditional use level 2 behaviour. For example:

let nan = 0.0/0.0
func printEqual<T: Equatable>(_ x: T, _ y: T) {
  print(x == y)
}
func printEqualFloats<T: FloatingPoint>(_ x: T, _ y: T) {
  print(x == y)
}
print(nan == nan) // false, (concrete)
printEqual(nan, nan) // true, (generic Equatable but not FloatingPoint)
printEqualFloats(nan, nan) // false, (generic FloatingPoint)

If one wishes to have a method that works with all Equatable/Comparable
types, but uses level 1 semantics for FloatingPoint types, then they can
simply provide two identical implementations that differ only in the bounds:

let nan = 0.0/0.0
func printEqual<T: Equatable>(_ x: T, _ y: T) {
  print(x == y)
}
func printEqual<T: FloatingPoint>(_ x: T, _ y: T) {
  print(x == y)
}

printEqual(0, 0) // true (integers use `<T: Equatable>` overload)
printEqual(nan, nan) // false (floats use `<T: FloatingPoint>` overload)

As a result of this change, hashing of floats must be updated to make all
NaNs hash equally. -0 and +0 will also no longer be expected to hash
equally. (Although they might as an implementation detail – equal values
must hash the same, unequal values *may* hash the same.)
Misc Standard Library

Types that conform to Comparable should be audited for places where
implementing or using Comparable would be a win. This update can be done
incrementally, as the only potential impact should be performance. As an
example, a default implementation of compare(_:slight_smile: for Array will likely be
suboptimal, performing two linear scans to determine the result in the
worst-case. (See the default implementation provided in the detailed
design.)

Some free functions will have <T: FloatingPoint> overloads to better
align with IEEE-754 semantics. This will be addressed in a follow-up
proposal. (example: min and max)
Detailed Design

The protocols will be changed as follows:

ComparisonResult, currently a type found in Foundation, will be sunk into
the Swift Standard Library:

@objc public enum ComparisonResult: Int, Equatable {
  case orderedAscending = -1
  case orderedSame = 0
  case orderedDescending = 1
}
public protocol Comparable: Equatable {
  func compare(_ other: Self) -> ComparisonResult

  static func < (lhs: Self, rhs: Self) -> Bool
}
extension Comparable {
  func compare(_ other: Self) -> ComparisonResult {
    if self == other {
      return .orderedSame
    } else if self < other {
      return .orderedAscending
    } else {
      return .orderedDescending
    }
  }
}
public func < <T: Comparable>(lhs: T, rhs: T) -> Bool {
  return lhs.compare(rhs) == .orderedAscending
}
// IEEE comparison operators (these implementations already exist in std)extension FloatingPoint {
  public static func == (lhs: T, rhs: T) -> Bool {
    return lhs.isEqual(to: rhs)
  }

  public static func < (lhs: T, rhs: T) -> Bool {
    return lhs.isLess(than: rhs)
  }

  public static func <= (lhs: T, rhs: T) -> Bool {
    return lhs.isLessThanOrEqualTo(rhs)
  }

  public static func > (lhs: T, rhs: T) -> Bool {
    return rhs.isLess(than: lhs)
  }

  public static func >= (lhs: T, rhs: T) -> Bool {
    return rhs.isLessThanOrEqualTo(lhs)
  }
}

// Comparable comparison operators (provides a total ordering)extension FloatingPoint {
  @_inline
  public func compare(_ other: Self) -> ComparisonResult {
    // Can potentially be implemented more efficiently -- this is just the clearest version
    if self.isLess(than: other) {
      return .orderedAscending
    } else if other.isLess(than: self) {
      return .orderedDescending
    } else {
      // Special cases

      // -0 < +0
      if self.isZero && other.isZero {
        // .plus == 0 and .minus == 1, so flip ordering to get - < +
        return (other.sign as Int).compare(self.sign as Int)
      }

      // NaN == NaN, NaN > +Inf
      if self.isNaN {
        if other.isNaN {
          return .orderedSame
        } else {
          return .orderedDescending
        }
      } else if other.isNaN {
        return .orderedAscending
      }

      // Otherwise equality agrees with normal IEEE
      return .orderedSame
    }
  }

  @_implements(Equatable.==)
  public static func _comparableEqual(lhs: Self, rhs: Self) -> Bool {
    lhs.compare(rhs) == .orderedSame
  }

  @_implements(Comparable.<)
  public static func _comparableLessThan(lhs: Self, rhs: Self) -> Bool {
    lhs.compare(rhs) == .orderedDescending
  }
}

Note that this design mandates changes to the compiler:

   - @_implements (or an equivalent mechanism) must be implemented to get
   the context-sensitive FloatingPoint behaviour.
   - The compiler must verify that either == and <, or compare(_:slight_smile: is
   overridden by every type that conforms to Comparable.

Source compatibility

Users of ComparisonResult will be able to use it as normal once it
becomes a standard library type.

Existing implementors of Comparable will be unaffected, though they
should consider implementing the new compare method as the default
implementation may be suboptimal.

Consumers of Comparable will be unaffected, though they should consider
calling the compare method if it offers a performance advantage for their
particular algorithm.

Existing implementors of FloatingPoint should be unaffected – they will
automatically get the new behaviour as long as they aren’t manually
implementing the requirements of Equatable/Comparable.

Existing code that works with floats may break if it’s relying on some
code bounded on <T: Equatable/Comparable>providing IEEE semantics. For
most algorithms, NaNs would essentially lead to unspecified behaviour, so
the primary concern is whether -0.0 == +0.0 matters.
ABI stability

This must be implemented before ABI stability is declared.
Effect on API resilience

N/A
Alternatives ConsideredSpaceship

Early versions of this proposal aimed to instead provide a <=> operator
in place of compare. The only reason we moved away from this was that it
didn’t solve the problem that comparison didn’t generalize.

Spaceship as an operator has a two concrete benefits over compare today:

   - It can be passed to a higher-order function
   - Tuples can implement it

In our opinion, these aren’t serious problems, especially in the long term.

Passing <=> as a higher order function basically allows types that aren’t
Comparable, but do provide <=>, to be very ergonomically handled by
algorithms which take an optional ordering function. Types which provide
the comparable operators but don’t conform to Comparable are only pervasive
due to the absence of conditional conformance. We shouldn’t be designing
our APIs around the assumption that conditional conformance doesn’t exist.

When conditional conformance is implemented, the only
should-be-comparable-but-aren’t types that will remain are tuples, which
we should potentially have the compiler synthesize conformances for.

Similarly, it should one day be possible to extend tuples, although this
is a more “far future” matter. Until then, the (T, T) -> Bool predicate
will always also be available, and < can be used there with the only
downside being a potential performance hit.
Just Leave Floats Alone

The fact that sorting floats leads to a mess, and storing floats can lead
to memory leaks and data loss isn’t acceptable.
Just Make Floats Only Have A Total Order

This was deemed too surprising for anyone familiar with floats from any
other language. It would also probably break a lot more code than this
change will.
Just Make Floats Not Comparable

Although floats are more subtle than integers, having places where
integers work but floats don’t is a poor state of affairs. One should be
able to sort an array of floats and use floats as keys in data structures,
even if the latter is difficult to do correctly.
PartialComparable

PartialComparable would essentially just be Comparable without any stated
ordering requirements, that Comparable extends to provide ordering
requirements. This would be a protocol that standard IEEE comparison could
satisfy, but in the absence of total ordering requirements,
PartialComparable is effectively useless. Either everyone would consume
PartialComparable (to accept floats) or Comparable (to have reasonable
behaviour).

The Rust community adopted this strategy to little benefit. The Rust libs
team has frequently considered removing the distinction, but hasn’t because
doing it backwards compatibly would be complicated. Also because merging
the two would just lead to the problems Swift has today.
Different Names For compare and ComparisonResult

A few different variants for ComparisonResult and its variants were
considered:

   - Dropping the ordered part of ComparisonResult’s cases e.g. .ascending
   - Naming of ComparisonResult as SortOrder
   - enum Ordering { case less, equal, greater } (as used by Rust
   <https://doc.rust-lang.org/std/cmp/enum.Ordering.html>)
   - Case values of inOrder, same, outOfOrder

The choice of case names is non-trivial because the enum shows up in
different contexts where different names makes more sense. Effectively, one
needs to keep in mind that the “default” sort order is ascending to map
between the concept of “before” and “less”.

The before/after naming to provide the most intuitive model for custom
sorts – referring to ascending or less is confusing when trying to
implement a descending ordering. Similarly the inOrder/outOfOrder naming
was too indirect – it’s more natural to just say where to put the element.
If the enum should focus on the sorting case, calling it SortOrder would
help to emphasize this fact.

This proposal elects to leave the existing Foundation name in-place. The
primary motivation for this is that use of the compare function will be
relatively rare. It is expected that in most cases users will continue to
make use of == or <, returning boolean values (the main exception to this
will be in use of the parameterized String comparisons). As such, the
source compatibility consequences of introducing naming changes to an
existing type seems of insufficient benefit.

The method compare(_:slight_smile: does not fully comport with the API naming
guidelines. However, it is firmly established with current usage in
Objective-C APIs, will be fairly rarely seen/used (users will usually
prefer <, == etc), and alternatives considered, for example compared(to:),
were not a significant improvement.
Add Overloads for (T, T) -> ComparisonResult

It would be slightly more ergonomic to work with ComparisonResult if
existing methods that took an ordering predicate also had an overload for (T,
T) -> ComparisonResult. As it stands, a case-insensitive sort must be
written as follows:

myStrings.sort { $0.compare(_ other: $1, case: .insensitive) == .orderedAscending }

With the overload, one could write:

myStrings.sort { $0.compare($1, case: .insensitive) }

we decided against providing these overloads because:

   - The existing algorithms in the standard library can’t benefit from
   them (only binary comparisons).
   - They bloat up the standard library (and any library which intends to
   match our API guidelines).
   - They potentially introduce confusion over “which” comparison
   overload to use.

And because we can change our mind later without concern for source or ABI
stability, as these overloads would be additive.
Future Work

This section covers some topics which were briefly considered, but were
identified as reasonable and possible to defer to future releases.
Specifically they should be backwards compatible to introduce even after
ABI stability. Two paths that are worth exploring:
Ergonomic Generalized Comparison for Keyed Containers

Can we make it ergonomic to use an (arbitrary) alternative comparison
strategy for a Dictionary or a BinaryTree? Should they be type-level
Comparators, or should those types always store a (Key, Key) ->
ComparisonResult closure?

We can avoid answering this question because Dictionary is expected to
keep a relatively opaque (resilient) ABI for the foreseeable future, as
many interesting optimizations will change its internal layout. Although if
the answer is type-level, then Default Generic Parameters must be accepted
to proceed down this path.
ComparisonResult Conveniences

There are a few conveniences we could consider providing to make
ComparisonResult more ergonomic to manipulate. Such as:

// A way to combine orderingsfunc ComparisonResult.breakingTiesWith(_ order: () -> ComparisonResult) -> ComparisonResult

array.sort {
  $0.x.compare($0.y)
  .breakingTiesWith { $0.y.compare($1.y) }
  == .orderedAscending
}

and

var inverted: ComparisonResult
// A perhaps more "clear" way to express reversing order than `y.compared(to: x)`
x.compare(y).inverted

But these can all be added later once everyone has had a chance to use
them.
_______________________________________________
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


(Matthew Johnson) #12

Remy Demarest
remy.demarest@gmail.com <mailto:remy.demarest@gmail.com>

Hi swift evolution,

Here’s another pitch, for The Propoosal Formerly Known As Spaceship.
Comparison Reform

Proposal: SE-NNNN <file:///Users/ben_cohen/Documents/swift-evolution/proposals/NNNN-filename.md>
Authors: Robert Widmann <https://github.com/codafi>, Jaden Geller <https://github.com/jadengeller>, Harlan Haskins <https://github.com/harlanhaskins>, Alexis Beingessner <https://github.com/Gankro>, Ben Cohen <https://github.com/airspeedswift>
Status: Awaiting review
Review manager: TBD
Introduction

This proposal is for changes that we believe should be made to the existing comparison system by:

Making FloatingPoint comparison context sensitive, so that its Comparable conformance provides a proper total ordering.
Introducing a new ternary-valued compare(_ other: Self) -> ComparisonResult method.
Removing unnecessary customization points from Comparable.
Motivation

The motivation comes from several independent points:

1: 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 while still maintaining the traditional definition of “comparison” for these types. Take, for example, sorting an array of Floats. 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 unspecified. Similarly, a Dictionary keyed off floats can leak entries and memory.

2: Generic algorithms in the Swift Standard Library that make use of the current Comparable protocol may have to make extra comparisons to determine the ordering of values when <, ==, and > should have different behaviours. Having a central operation to return complete ordering information should provide a speedup for these operations.

3: The existing comparison operators don’t “generalize” well. There’s no clean way to add a third or fourth argument to < to ask for non-default semantics. An example where this would be desirable would be specifying the locale or case-sensitivity when comparing Strings.

4: Comparable is over-engineered in the customization points it provides: to our knowledge, there’s no good reason to ever override >=, >, or <=. Each customization point bloats vtables and mandates additional dynamic dispatch.

5: When quickly writing a Comparable type, it is easier to implement a single ternary statement than to separately implement == and <.

Proposed solution

ComparisonResult

Foundation’s ComparisonResult type will be mapped into Swift as

@objc public enum ComparisonResult : Int {
  case orderedAscending = -1
  case orderedSame = 0
  case orderedDescending = 1
}
Comparable

Comparable will be changed to have a new ternary comparison method: compare(_ other: Self) -> ComparisonResult. x.compare(y) specifies where to place x relative to y. So if it yields .orderedAscending, then x comes before y. This will be considered the new “main” dispatch point of Comparable that implementors should provide.

Most code will continue to use < or ==, as it will be optimal for their purposes. However code that needs to make a three-way branch on comparison can use the potentially more efficient compare. Note that compare is only expected to be more efficient in this specific case. If a two-way branch is all that’s being done, < will be more efficient in many cases (if only because it’s easier for the optimizer).

For backwards compatibility reasons, compare will have a default implementation defined in terms of <, but to enable only using compare, < and == will also have default implementations in terms of compare.

The compiler will verify that either compare, or < and ==, are provided by every type that claims to conform to Comparable. This will be done in some unspecified way unavailable outside the standard library (it can be made available to in the future, but that’s an unnecessary distraction for this proposal).

Is it really necessary? Can't you have two separate protocols like this:

protocol Comparable: Equatable {
    static func < (lhs: Self, rhs: Self) -> Bool
}

protocol ThreeWayComparable: Equatable {
    func compare(_ other: Self) -> ComparisonResult
}

extension Comparable where Self: ThreeWayComparable {
    static func < (lhs: Self, rhs: Self) -> Bool {
        return lhs.compare(rhs) == .orderedAscending
    }
}

I actually really like the idea of mutually exclusive default requirement implementations. I have run across situations where I wish I could design a protocol this way and was frustrated by the alternatives. +1 to this approach and to making art available outside the standard library in the future. There is no good reason for additional protocols here.

···

On Apr 13, 2017, at 5:18 PM, Remy Demarest (Psy) via swift-evolution <swift-evolution@swift.org> wrote:

Le 13 avr. 2017 à 13:17, Ben Cohen via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> a écrit :

Types that wish to provide comparison “variants” can do so naturally by adding compare methods with additional arguments. e.g. String.compare(_ other: Self, in: Locale) -> ComparisonResult. These have no language-level connection to Comparable, but are still syntactically connected, implying the same total order semantics. This makes them easier to discover, learn, and migrate to.

To reduce bloat, the operators <=, >=, and > will be removed from the set of requirements that the Comparable protocol declares. These operators will however continue to exist with the current default implementations.

FloatingPoint

No changes will be made to the FloatingPoint protocol itself. Instead, new extensions will be added to it to change the behaviour of comparison.

The new behaviour centers around the fact that compare(_: Self) -> ComparisonResult will provide a total ordering that’s consistent with Level 2 in the IEEE 754 (2008) spec. This is mostly the same as the standard (Level 1) IEEE ordering, except:

-0 < +0
NaN == NaN
NaN > +Inf (an arbitrary choice, NaN can be placed anywhere in the number line)
Level 2’s distinguishing of -0 and +0 is a bit strange, but is consistent with Equatable’s Substitutability requirement. -0 and +0 have different behaviours: 1/-0 = -Inf while 1/+0 = +Inf. The main problem this can lead to is that a keyed collection may have two “0” entries. In practice this probably won’t be a problem because it’s fairly difficult for the same algorithm to produce both -0 and +0. Any algorithm that does is also probably concerned with the fact that 1.0E-128 and 2.0E-128 are considered distinct values.

Note: IEEE specifies several other potential total orderings: level 3, level 4, and the totalOrder predicate. For our purposes, these orderings are too aggressive in distinguishing values that are semantically equivalent in Swift. For most cases, the relevant issue is that they distinguish different encodings of NaN. For more exotic encodings that don’t guarantee normalization, these predicates also consider 10.0e0 < 1.0e1 to be true. An example where this can occur is IEEE-754 decimal coded floating point, which FloatingPoint is intended to support.

We will then make the comparison operators (<, <=, ==, !=, >=, >) dispatch to one of compare(_:slight_smile: or FloatingPoint’s IEEE comparison methods (isLess, isEqual, isLessThanOrEqualTo) based on the context.

If the context knows the type is FloatingPoint, then level 1 ordering will be used.
If the context only knows the type is Comparable or Equatable, then level 2 ordering will be used.
This results in code that is explicitly designed to work with FloatingPoint types getting the expected IEEE behaviour, while code that is only designed to work with Comparable types (e.g. sort and Dictionary) gets more reasonable total ordering behaviour.

To clarify: Dictionary and sort won’t somehow detect that they’re being used with FloatingPoint types and use level 1 comparisons. Instead they will unconditional use level 2 behaviour. For example:

let nan = 0.0/0.0

func printEqual<T: Equatable>(_ x: T, _ y: T) {
  print(x == y)
}

func printEqualFloats<T: FloatingPoint>(_ x: T, _ y: T) {
  print(x == y)
}

print(nan == nan) // false, (concrete)
printEqual(nan, nan) // true, (generic Equatable but not FloatingPoint)
printEqualFloats(nan, nan) // false, (generic FloatingPoint)
If one wishes to have a method that works with all Equatable/Comparable types, but uses level 1 semantics for FloatingPoint types, then they can simply provide two identical implementations that differ only in the bounds:

let nan = 0.0/0.0

func printEqual<T: Equatable>(_ x: T, _ y: T) {
  print(x == y)
}

func printEqual<T: FloatingPoint>(_ x: T, _ y: T) {
  print(x == y)
}

printEqual(0, 0) // true (integers use `<T: Equatable>` overload)
printEqual(nan, nan) // false (floats use `<T: FloatingPoint>` overload)
As a result of this change, hashing of floats must be updated to make all NaNs hash equally. -0 and +0 will also no longer be expected to hash equally. (Although they might as an implementation detail – equal values must hash the same, unequal values may hash the same.)

Misc Standard Library

Types that conform to Comparable should be audited for places where implementing or using Comparable would be a win. This update can be done incrementally, as the only potential impact should be performance. As an example, a default implementation of compare(_:slight_smile: for Array will likely be suboptimal, performing two linear scans to determine the result in the worst-case. (See the default implementation provided in the detailed design.)

Some free functions will have <T: FloatingPoint> overloads to better align with IEEE-754 semantics. This will be addressed in a follow-up proposal. (example: min and max)

Detailed Design

The protocols will be changed as follows:

ComparisonResult, currently a type found in Foundation, will be sunk into the Swift Standard Library:

@objc public enum ComparisonResult: Int, Equatable {
  case orderedAscending = -1
  case orderedSame = 0
  case orderedDescending = 1
}

public protocol Comparable: Equatable {
  func compare(_ other: Self) -> ComparisonResult

  static func < (lhs: Self, rhs: Self) -> Bool
}

extension Comparable {
  func compare(_ other: Self) -> ComparisonResult {
    if self == other {
      return .orderedSame
    } else if self < other {
      return .orderedAscending
    } else {
      return .orderedDescending
    }
  }
}

public func < <T: Comparable>(lhs: T, rhs: T) -> Bool {
  return lhs.compare(rhs) == .orderedAscending
}

// IEEE comparison operators (these implementations already exist in std)
extension FloatingPoint {
  public static func == (lhs: T, rhs: T) -> Bool {
    return lhs.isEqual(to: rhs)
  }

  public static func < (lhs: T, rhs: T) -> Bool {
    return lhs.isLess(than: rhs)
  }

  public static func <= (lhs: T, rhs: T) -> Bool {
    return lhs.isLessThanOrEqualTo(rhs)
  }

  public static func > (lhs: T, rhs: T) -> Bool {
    return rhs.isLess(than: lhs)
  }

  public static func >= (lhs: T, rhs: T) -> Bool {
    return rhs.isLessThanOrEqualTo(lhs)
  }
}

// Comparable comparison operators (provides a total ordering)
extension FloatingPoint {
  @_inline
  public func compare(_ other: Self) -> ComparisonResult {
    // Can potentially be implemented more efficiently -- this is just the clearest version
    if self.isLess(than: other) {
      return .orderedAscending
    } else if other.isLess(than: self) {
      return .orderedDescending
    } else {
      // Special cases

      // -0 < +0
      if self.isZero && other.isZero {
        // .plus == 0 and .minus == 1, so flip ordering to get - < +
        return (other.sign as Int).compare(self.sign as Int)
      }

      // NaN == NaN, NaN > +Inf
      if self.isNaN {
        if other.isNaN {
          return .orderedSame
        } else {
          return .orderedDescending
        }
      } else if other.isNaN {
        return .orderedAscending
      }

      // Otherwise equality agrees with normal IEEE
      return .orderedSame
    }
  }

  @_implements(Equatable.==)
  public static func _comparableEqual(lhs: Self, rhs: Self) -> Bool {
    lhs.compare(rhs) == .orderedSame
  }

  @_implements(Comparable.<)
  public static func _comparableLessThan(lhs: Self, rhs: Self) -> Bool {
    lhs.compare(rhs) == .orderedDescending
  }
}
Note that this design mandates changes to the compiler:

@_implements (or an equivalent mechanism) must be implemented to get the context-sensitive FloatingPoint behaviour.
The compiler must verify that either == and <, or compare(_:slight_smile: is overridden by every type that conforms to Comparable.
Source compatibility

Users of ComparisonResult will be able to use it as normal once it becomes a standard library type.

Existing implementors of Comparable will be unaffected, though they should consider implementing the new compare method as the default implementation may be suboptimal.

Consumers of Comparable will be unaffected, though they should consider calling the compare method if it offers a performance advantage for their particular algorithm.

Existing implementors of FloatingPoint should be unaffected – they will automatically get the new behaviour as long as they aren’t manually implementing the requirements of Equatable/Comparable.

Existing code that works with floats may break if it’s relying on some code bounded on <T: Equatable/Comparable>providing IEEE semantics. For most algorithms, NaNs would essentially lead to unspecified behaviour, so the primary concern is whether -0.0 == +0.0 matters.

ABI stability

This must be implemented before ABI stability is declared.

Effect on API resilience

N/A

Alternatives Considered

Spaceship

Early versions of this proposal aimed to instead provide a <=> operator in place of compare. The only reason we moved away from this was that it didn’t solve the problem that comparison didn’t generalize.

Spaceship as an operator has a two concrete benefits over compare today:

It can be passed to a higher-order function
Tuples can implement it
In our opinion, these aren’t serious problems, especially in the long term.

Passing <=> as a higher order function basically allows types that aren’t Comparable, but do provide <=>, to be very ergonomically handled by algorithms which take an optional ordering function. Types which provide the comparable operators but don’t conform to Comparable are only pervasive due to the absence of conditional conformance. We shouldn’t be designing our APIs around the assumption that conditional conformance doesn’t exist.

When conditional conformance is implemented, the only should-be-comparable-but-aren’t types that will remain are tuples, which we should potentially have the compiler synthesize conformances for.

Similarly, it should one day be possible to extend tuples, although this is a more “far future” matter. Until then, the (T, T) -> Bool predicate will always also be available, and < can be used there with the only downside being a potential performance hit.

Just Leave Floats Alone

The fact that sorting floats leads to a mess, and storing floats can lead to memory leaks and data loss isn’t acceptable.

Just Make Floats Only Have A Total Order

This was deemed too surprising for anyone familiar with floats from any other language. It would also probably break a lot more code than this change will.

Just Make Floats Not Comparable

Although floats are more subtle than integers, having places where integers work but floats don’t is a poor state of affairs. One should be able to sort an array of floats and use floats as keys in data structures, even if the latter is difficult to do correctly.

PartialComparable

PartialComparable would essentially just be Comparable without any stated ordering requirements, that Comparable extends to provide ordering requirements. This would be a protocol that standard IEEE comparison could satisfy, but in the absence of total ordering requirements, PartialComparable is effectively useless. Either everyone would consume PartialComparable (to accept floats) or Comparable (to have reasonable behaviour).

The Rust community adopted this strategy to little benefit. The Rust libs team has frequently considered removing the distinction, but hasn’t because doing it backwards compatibly would be complicated. Also because merging the two would just lead to the problems Swift has today.

Different Names For compare and ComparisonResult

A few different variants for ComparisonResult and its variants were considered:

Dropping the ordered part of ComparisonResult’s cases e.g. .ascending
Naming of ComparisonResult as SortOrder
enum Ordering { case less, equal, greater } (as used by Rust <https://doc.rust-lang.org/std/cmp/enum.Ordering.html>)
Case values of inOrder, same, outOfOrder
The choice of case names is non-trivial because the enum shows up in different contexts where different names makes more sense. Effectively, one needs to keep in mind that the “default” sort order is ascending to map between the concept of “before” and “less”.

The before/after naming to provide the most intuitive model for custom sorts – referring to ascending or less is confusing when trying to implement a descending ordering. Similarly the inOrder/outOfOrder naming was too indirect – it’s more natural to just say where to put the element. If the enum should focus on the sorting case, calling it SortOrder would help to emphasize this fact.

This proposal elects to leave the existing Foundation name in-place. The primary motivation for this is that use of the compare function will be relatively rare. It is expected that in most cases users will continue to make use of == or <, returning boolean values (the main exception to this will be in use of the parameterized String comparisons). As such, the source compatibility consequences of introducing naming changes to an existing type seems of insufficient benefit.

The method compare(_:slight_smile: does not fully comport with the API naming guidelines. However, it is firmly established with current usage in Objective-C APIs, will be fairly rarely seen/used (users will usually prefer <, == etc), and alternatives considered, for example compared(to:), were not a significant improvement.

Add Overloads for (T, T) -> ComparisonResult

It would be slightly more ergonomic to work with ComparisonResult if existing methods that took an ordering predicate also had an overload for (T, T) -> ComparisonResult. As it stands, a case-insensitive sort must be written as follows:

myStrings.sort { $0.compare(_ other: $1, case: .insensitive) == .orderedAscending }
With the overload, one could write:

myStrings.sort { $0.compare($1, case: .insensitive) }
we decided against providing these overloads because:

The existing algorithms in the standard library can’t benefit from them (only binary comparisons).
They bloat up the standard library (and any library which intends to match our API guidelines).
They potentially introduce confusion over “which” comparison overload to use.
And because we can change our mind later without concern for source or ABI stability, as these overloads would be additive.

Future Work

This section covers some topics which were briefly considered, but were identified as reasonable and possible to defer to future releases. Specifically they should be backwards compatible to introduce even after ABI stability. Two paths that are worth exploring:

Ergonomic Generalized Comparison for Keyed Containers

Can we make it ergonomic to use an (arbitrary) alternative comparison strategy for a Dictionary or a BinaryTree? Should they be type-level Comparators, or should those types always store a (Key, Key) -> ComparisonResult closure?

We can avoid answering this question because Dictionary is expected to keep a relatively opaque (resilient) ABI for the foreseeable future, as many interesting optimizations will change its internal layout. Although if the answer is type-level, then Default Generic Parameters must be accepted to proceed down this path.

ComparisonResult Conveniences

There are a few conveniences we could consider providing to make ComparisonResult more ergonomic to manipulate. Such as:

// A way to combine orderings
func ComparisonResult.breakingTiesWith(_ order: () -> ComparisonResult) -> ComparisonResult

array.sort {
  $0.x.compare($0.y)
  .breakingTiesWith { $0.y.compare($1.y) }
  == .orderedAscending
}
and

var inverted: ComparisonResult

// A perhaps more "clear" way to express reversing order than `y.compared(to: x)`
x.compare(y).inverted
But these can all be added later once everyone has had a chance to use them.

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto: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


(Jaden Geller) #13

If I understand correctly, I think you’re mistaken. The compiler already selects overloads based on generic context. If `T: FloatingPoint`, then it’ll choose the `==` with signature `<T: FloatingPoint> (T, T) -> Bool`. If `T: Equatable`, then it’ll choose the `==` with signature `<T: Equatable> (T, T) -> Bool`. No new compiler features are necessary for this specific behavior.

Cheers,
Jaden Geller

···

On Apr 13, 2017, at 5:18 PM, Xiaodi Wu via swift-evolution <swift-evolution@swift.org> wrote:

Actually, the fact that this behavior cannot even be achieved without currently non-existent compiler features means that it is not possible to understand what's truly going on without reading *this document*, after mastering *both* IEEE floating point *and* Swift generics/protocols/extensions/static vs. dynamic dispatch. All to use `==` correctly. Which is to say, most people will simply not even know if they happen to be using the `==` they did not intend to use.


(Jaden Geller) #14

ComparisonResult Conveniences

There are a few conveniences we could consider providing to make ComparisonResult more ergonomic to manipulate. Such as:

// A way to combine orderings
func ComparisonResult.breakingTiesWith(_ order: () -> ComparisonResult) -> ComparisonResult

array.sort {
  $0.x.compare($0.y)
  .breakingTiesWith { $0.y.compare($1.y) }
  == .orderedAscending
}

The really nice thing about compare being an operator is that you can very nicely combine it with an operator here and get a much more light-weight syntax for chained comparisons, e.g.:

struct MyPoint : Comparable {
  var x, y, z: Double
  func compare(_ other: MyPointer) -> ComparisonResult {
    return self.x <=> other.x || self.y <=> other.y || self.z <=> other.z

Wow, this is elegant!

  }
}

as opposed to, I guess,
  return self.x.compare(other.x).breakingTiesWith { self.y.compare(other.y).breakingTiesWith { self.z.compare(other.z) } }

But this is mostly useful for defining custom comparisons, so perhaps it's not worth having to paint a bikeshed for <=> and whatever the combining operator is.

For the record, I would strongly prefer `<=>` to an instance `compare` method. That said, I’d also prefer a static `compare` function to the asymmetric instance method if the spelling `compare` were absolutely desired.

It’s probably worth noting somewhere that an instance `compare` method performs dynamic dispatch on the left-hand argument while a static function (as well as the current operators `==` and `<`) perform static dispatch. I realize NSObject set a precedent with `isEqual:` and `compare:` instance methods, but I’m not convinced that’s necessarily the best design. If dynamic dispatch is desired, an implementation can always delegate to such a method.

Also, in this example:

// A way to combine orderings
func ComparisonResult.breakingTiesWith(_ order: () -> ComparisonResult) -> ComparisonResult

array.sort {
  $0.x.compare($0.y)
  .breakingTiesWith { $0.y.compare($1.y) }
  == .orderedAscending
}

Requiring this last "== .orderedAscending" seems like a tragic failure of ergonomics. I understand that sorting doesn't actually require a tri-valued comparison, but is it really worth maintaining two currencies of comparison result over that? Are there any types that can answer '<' substantially more efficiently than they can answer 'compare'? And I assume this is related to why you've kept < in the protocol.

I would strongly support replacing (T, T) -> Bool with (T, T) -> ComparisonResult variants.

The areInIncreasingOrder variant is confusing at the call-site since the definition must be consulted to determine which order the comparison expects.
The areInIncreasingOrder implementation is very dirty when an == result is desired. This is especially bad if we expect other authors to mirror this API:
if !areInIncreasingOrder(a, b) && !areInIncreasingOrder(b, a) {
  // equal!
}
Not only is this unintuitive, but it is also less performant in many cases.

···

On Apr 13, 2017, at 3:23 PM, John McCall via swift-evolution <swift-evolution@swift.org> wrote:

On Apr 13, 2017, at 4:17 PM, Ben Cohen via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

John.
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Guillaume Lessard) #15

No; in full grammatical pedanticity it should be compared(with:).
“compare to” is for dissimilar things.
“compare with” is for similar things.
(I’m not claiming that anyone cares, and I may have a traditional interpretation.)

If the whole thing remains couched in terms of comparison, I prefer the function to be named compare(_:), because it’s such an everyday term. No one expects this action to possibly have a side effect.

Cheers,
Guillaume Lessard

···

On Apr 13, 2017, at 18:18, Xiaodi Wu via swift-evolution <swift-evolution@swift.org> wrote:

`compare(_:)` does not merit a term-of-art exception when the Swift name is clearly `compared(to:)`.


(Jon Hull) #16

One more thought. I am generally in favor of this proposal, but since it is in the pitch stage, I wanted to offer an alternative approach that I didn’t see mentioned. Food for thought/discussion.

What if, instead of repurposing comparable (and adding new functions for options like case insensitive compare), we define a comparison metric (with all of the options built in) and then use that to get our comparison result. Comparable things would have a default metric that uses ‘<‘ and ‘==‘ to provide a comparison result.

The metric would have a method which takes two things and returns a ComparisonResult. The two things would usually be the same type, but wouldn’t necessarily have to be.

As a convenience, any type could have a compared(to:, using:) method where you pass a comparison metric to the using parameter and receive a ComparisonResult. Comparable things could add a compared(with:) method and the spaceship operator <=>, which both use the default metric.

Pros:
• Would work without compiler alterations
• You can create metrics that compare items of different types
• Can setup the metric once for algorithms/comparisons with high setup cost
• Things like 'compare(to: other, using: .caseInsensitiveComparison)' fall out of the design without having to create/learn various different versions of compare on different types.
• Spaceship operator <=> for those who want it
• In some cases, it can provide a much more efficient implementation based on underlying structure. For example, you can get a metric from String/Unicode which is optimized for a particular view of that string (say ASCII). Depending on the case, when one of the objects doesn’t match the optimized type, it can either convert or fallback to a more general algorithm… but it should provide a pretty big win when most of the objects have a known structure.

Cons:
• More protocols defined by the design
• Requires an extra struct/class to implement in non-standard cases (e.g. case insensitive compare)
• Probably something else I am missing

Thanks,
Jon

···

On Apr 13, 2017, at 1:24 PM, Ben Cohen via swift-evolution <swift-evolution@swift.org> wrote:

Online copy here:

https://github.com/airspeedswift/swift-evolution/blob/fa007138a54895e94d22e053122ca24ffa0b2eeb/proposals/NNNN-ComparisonReform.md


(Douglas Gregor) #17

The core team cares a *lot* about backwards compatibility. The engineering effort involved in implementing this mutually-exclusive check is very small compared with the benefits of maintaining compatibility.

  - Doug

···

On Apr 13, 2017, at 2:42 PM, David Hart via swift-evolution <swift-evolution@swift.org> wrote:

Looking good. A few comments inline:

On 13 Apr 2017, at 22:17, Ben Cohen via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
Comparable

Comparable will be changed to have a new ternary comparison method: compare(_ other: Self) -> ComparisonResult. x.compare(y) specifies where to place x relative to y. So if it yields .orderedAscending, then x comes before y. This will be considered the new “main” dispatch point of Comparable that implementors should provide.

Most code will continue to use < or ==, as it will be optimal for their purposes. However code that needs to make a three-way branch on comparison can use the potentially more efficient compare. Note that compare is only expected to be more efficient in this specific case. If a two-way branch is all that’s being done, < will be more efficient in many cases (if only because it’s easier for the optimizer).

For backwards compatibility reasons, compare will have a default implementation defined in terms of <, but to enable only using compare, < and == will also have default implementations in terms of compare.

The compiler will verify that either compare, or < and ==, are provided by every type that claims to conform to Comparable. This will be done in some unspecified way unavailable outside the standard library (it can be made available to in the future, but that’s an unnecessary distraction for this proposal).

It feels weird to me to jump through all these hoops just for backwards compatibility. Seeing how even big projects might only have several Comparable conformances, wouldn’t it be worth removing the default implementation of compare and removing < from Comparable?


(Xiaodi Wu) #18

>
> `compare(_:)` does not merit a term-of-art exception when the Swift name
is clearly `compared(to:)`.

No; in full grammatical pedanticity it should be compared(with:).
“compare to” is for dissimilar things.
“compare with” is for similar things.
(I’m not claiming that anyone cares, and I may have a traditional
interpretation.)

I have read the entirety of the OED entry on "compare," and I have found no
evidence to support that. There are some usages that prefer "to" over
"with," and some vice versa, but it is not by degree of similarity.

···

On Thu, Apr 13, 2017 at 7:46 PM, Guillaume Lessard < glessard@tffenterprises.com> wrote:

> On Apr 13, 2017, at 18:18, Xiaodi Wu via swift-evolution < > swift-evolution@swift.org> wrote:

If the whole thing remains couched in terms of comparison, I prefer the
function to be named compare(_:), because it’s such an everyday term. No
one expects this action to possibly have a side effect.

Cheers,
Guillaume Lessard


(Xiaodi Wu) #19

Jaden, the proposal literally says that a compiler feature named
"@_implements" is necessary for the proposed design to work. You can see
WIP for that feature in the apple/swift repo.

···

On Thu, Apr 13, 2017 at 19:55 Jaden Geller <jaden.geller@gmail.com> wrote:

On Apr 13, 2017, at 5:18 PM, Xiaodi Wu via swift-evolution < > swift-evolution@swift.org> wrote:

Actually, the fact that this behavior cannot even be achieved without
currently non-existent compiler features means that it is not possible to
understand what's truly going on without reading *this document*, after
mastering *both* IEEE floating point *and* Swift
generics/protocols/extensions/static vs. dynamic dispatch. All to use `==`
correctly. Which is to say, most people will simply not even know if they
happen to be using the `==` they did not intend to use.

If I understand correctly, I think you’re mistaken. The compiler already
selects overloads based on generic context. If `T: FloatingPoint`, then
it’ll choose the `==` with signature `<T: FloatingPoint> (T, T) -> Bool`.
If `T: Equatable`, then it’ll choose the `==` with signature `<T:
> (T, T) -> Bool`. No new compiler features are necessary for this
specific behavior.

Cheers,
Jaden Geller


(Dave Abrahams) #20

The first question when proposing a new protocol is always: what generic
algorithm can take advantage of this API?

···

on Thu Apr 13 2017, Jonathan Hull <swift-evolution@swift.org> wrote:

I still like the ordering of floats defined in this proposal best (and
think we should use it), but I imagine that there are other types
which are almost (but not quite) comparable as well. Would there be
any utility in having a ‘PartialComparable’ protocol that defined a
single method:

  func compare(_:)->ComparisonResult?

That is, it is just like our compare, but it returns nil if two values
can’t be meaningfully compared. It would force you to deal with the
cases where the comparison didn’t make sense, and handle it in a
reasonable way in your code. (e.g. filtering those values out, or
sticking them at the end).

You can think of it as failable compare...

--
-Dave