Comparable and FloatingPoint

Evolution Pitches
1

There is a small but important tangle of issues around the interaction between min and max operations and Comparable and FloatingPoint protocols and the IEEE 754 standard that I would like to attempt to resolve.

This is a subtle subject. I will attempt to give a good overview of all the issues involved. For the purposes of this discussion, the behavior of comparisons (==, !=, etc) is out of scope. I am focused on min and max operations. Please read the entire post and attempt to stay focused.

IEEE 754 (2008)
The 2008 revision of 754 defined the following four operations (these are IEEE 754 operations, not Swift functions, but I am translating the interface from IEEE 754 pseudocode into Swift for familiarity):

  • func minNum<T>(_ x: T, _ y: T) -> T
  • func maxNum<T>(_ x: T, _ y: T) -> T
  • func minNumMag<T>(_ x: T, _ y: T) -> T
  • func maxNumMag<T>(_ x: T, _ y: T) -> T

These are defined to return the lesser / greater / lesser in magnitude / greater in magnitude of x and y if neither operand is NaN, the number operand if one argument is a quiet NaN, and a quiet nan if either operand is a signaling NaN or both operands are quiet NaNs.

These definitions are mostly sensible for pairwise operation, but they have a fatal flaw if you attempt to extend them to more than two arguments or use them in reductions: they are not associative in the presence of signaling NaNs. Example:

minNum(minNum(1, .signalingNaN), 2) = minNum(.nan, 2) = 2
minNum(1, minNum(.signalingNaN, 2)) = minNum(1, .nan) = 1

FloatingPoint in Swift 3 ... 4.2
The FloatingPoint protocol binds IEEE 754; these operations are surfaced as the static functions minimum, maximum, minimumMagnitude and maximumMagnitude.

They are not surfaced as the min and max free functions defined on Comparable (which always returns the first argument if either is NaN), nor as the fmin and fmax free functions defined by the platform C module (which bind the C stdlib fmin and fmax functions).

IEEE 754 (201x)
Because of the flaw that I discuss above, the revision of IEEE 754 currently in preparation will remove the minNum, maxNum, minNumMag, and maxNumMag operations entirely. In their place, there are eight recommended—but not required—operations added to clause 9:

  • func minimum(_ x: T, _ y: T) -> T
  • func maximum(_ x: T, _ y: T) -> T
  • func minimumMagnitude(_ x: T, _ y: T) -> T
  • func maximumMagnitude(_ x: T, _ y: T) -> T
  • func minimumNumber(_ x: T, _ y: T) -> T
  • func maximumNumber(_ x: T, _ y: T) -> T
  • func minimumMagnitudeNumber(_ x: T, _ y: T) -> T
  • func maximumMagnitudeNumber(_ x: T, _ y: T) -> T

minimum and maximum return NaN if either argument is NaN, and the lesser/greater of the two arguments otherwise. The Magnitude operations compare magnitudes. The Number operations discard NaNs, preferring to return number arguments.

These new operations have the virtue of being associative, which makes them suitable for use in reductions. They are unfortunately not required; as recommended operations, they may change somewhat in the next revision of IEEE 754 (202x), so we should exercise some caution in adopting them.

(I'm going to talk only about minimum from here on out; everything also applies to maximum). For those keeping score at home, we have considered five different "minimum" operations at this point. The one bound to Comparable.min is not ideal because it isn't commutative in the presence of NaN. The one bound to FloatingPoint.minimum has been explicitly abandoned from IEEE 754, and is probably the worst of the bunch.

Swift 5 ...
I suggest the following (again, I am only discussing minimum; all of this applies equally to maximum):

  1. Add a customization point for binary min on Comparable that lets us override the behavior for FloatingPoint. Use this for the implementation of n-ary min, so that the behavior matches.
  2. Deprecate FloatingPoint.minimum, marking it renamed to FloatingPoint.minimumNumber, which matches the IEEE 754 recommended operation (the semantics of the two are identical except for signaling NaNs, which are effectively a bug in the current Swift minimum, so this is a very reasonable replacement).
  3. Deprecate the fmin free function. We don't need another name for this operation floating around to confuse things, and it's a holdover from the C stdlib.

The remaining questions after doing these three things are:

  1. Should we provide a binding for the new IEEE 754 minimum operation?
  2. What should the semantics of Comparable.min be on FloatingPoint?

The obvious thing to do is to have Comparable.min implement the new IEEE 754 minimum operation. This is pretty reasonable, because it satisfies most of the properties that we want for Comparable.min: it is associative, and it is commutative (up to representation when x == y). This would be a completely fine solution, I think.

There is one additional property, however, which is desirable for the min free function; that the sets {x, y} and {min(x,y), max(x,y)} are the same. This cannot be satisfied by either of the IEEE 754 recommended notions of minimum. I can think of at least one other option that we may want to consider: make NaNs a preconditionFailure when used in Comparable.min, and repurpose FloatingPoint.minimum to bind the IEEE 754 minimum operation.

This would leave us with three notions each of minimum and maximum; the two recommended IEEE operations, as static funcs on FloatingPoint, and a third definition which only allows values that are non-exceptional under Comparable. This may be a better solution, or it may be the pathway to a rabbit hole of ever-increasing complexity that we're better off ignoring.

5 Likes
2

[Note that I left the Magnitude operations out of my discussion about what to do about the situation; this is deliberate. They're much less-used, and should almost surely simply follow whatever we do for the normal minimum and maximum operations.]

3

My opinion is that if a min etc. customization point is added to Comparable, then the implementations for FloatingPoint types should preconditionFailure.

3 Likes
4

I think your proposed plan is the most reasonable, including preconditionFailure for comparing NaNs with a customized Comparable.min.

As for the new IEEE minimum, it may be best to keep the number of notions of “minimum” to a minimum and forego exposing that operation for the moment, especially in light of potential future changes in the standard.

1 Like
5

Thank you for this really good break down!
Can we just fix the bug in swift 5 and leave the name the same?

I do not like the idea of having a precondition for NaN. Doesn’t that just defeat the whole purpose of NaN?

6

I prefer NaN and anything is NaN throughout and therefore {1, NaN} != {min(1, NaN), max(1, NaN)}. With the “NaN and anything is NaN” rule there is no need to introduce the new IEEE comparisons.