Comparable and FloatingPoint types

foo.sorted( treatingNanAs:-.infinity ) // Would place all NaNs at beginning, as though they were -infinity.
foo.containsNan() // Similar to .isNan() except applying to an array

These would help make it clear in the code that there is a possibility of the values being NaN.

The problem is that if floating point types conform to Comparable the generic sorted would still be available.

That’s right, you could still call sorted() on an array of floats. It’s just that if that array contained any NaNs, the operation would trap. This makes sense because NaN doesn’t have a natural order. In many cases, the trap will reveal a logic error. If you know the array you're sorting could have some NaNs in it, you use something like “foo.sorted( treatingNanAs:-.infinity )”. This has the advantage of making it clear in your code that NaN is a possibility and explicitly saying how you want NaN to be treated.

The idea behind trapping on comparisons with NaN is similar to trapping on interger overflow. The result of an integer overflow cannot be represented in the result type. Rather than quietly ignoring what may be an error in logic, Swift traps. The programmer either fixes the error or makes explicit how the situation is to be treated.

Likewise, a comparison with NaN cannot be represented in a boolean. Rather than quietly ignoring what may be an error in logic, Swift should trap. Then the programmer either fixes the error or makes explicit how the situation is to be treated.

But Equatable does not rely on &==, and Swift doesn't promise conformance to group axioms (although I might be wrong here ;-).
I somewhat agree with @Nevin that consistency itself is not a goal - but I can hardly think of any examples where breaking consistency has a positive effect.

Imho there is to much inconsistency in Swift, and especially Equatable has a bad track record here, as even the stdlib itself contains severe violations:

a == a is always true (Reflexivity)

(violated by FloatingPoint)

Equality implies substitutability

(violated by Set and Dictionary)

3 Likes

Equality implies substitutability in what Alex Stepanov calls “regular” operations. These operations are reverentially transparent with respect to the meaning of the value. Most members of types that have value semantics should be “regular”.

However, types that have value semantics are also allowed to have incidental members that reveal the underlying representation. Array.capacity is a good example. Order-revealing operations on Set and Dictionary are also good examples (order is strictly representational and is not guaranteed by the type). Unfortunately in the case of Set and Dictionary there are a lot of incidental members because they conform to Collection which is inherently an order-revealing protocol.

This issue is exacerbated by the fact that the Swift community has not adopted a clear definition of value semantics and is not in the habit of distinguishing “regular” operations from incidental members. Even the standard library does not make this crucial distinction in its documentation. If it did, at least it would be explicitly clear where substitutability is guaranteed and where it is not (and this would be communicated in a consistent fashion).

3 Likes

I am still pretty strongly in favor of introducing &==, etc... for IEEE floating point, but let's take a moment to do a thought experiment and explore another path...

Thought Experiment #1:

What if we were to remove Equatable and Comparable conformance from Float/Double, and make a new set of EquatableIEEE and ComparableIEEE (or whatever the names would be) protocols? Then we conditionally add in methods which require NaN to be taken into account like @tomkeith's foo.sorted(treatingNanAs: .infinity).

The upside is that the source breakage now has a fixit which fixes current bugs. The downside is that Numeric would probably no longer be compatible with Floating Point.

Thought Experiment #2:

What if we were to add a feature to Swift (assuming we don't already have it) that allowed a protocol to provide a tighter guarantee than a protocol it inherits from. That is:

Protocol A {
     func foo()->String?
}

Protocol B {
    override func foo()->String // Guaranteed not to be optional
    // Would also work for subclasses
}

Then we could add in a couple of new protocols to the hierarchy which allow failable ==, <, etc.... Then Equatable/Comparable would refine those to lose the optionals. Finally, we switch FloatingPoint to adhere to the weaker protocols, and it returns nil when comparing to Nan.

The upside is you can chain Nan here all the way up until the comparison... and only then does Swift make you deal with it (via the optional). I am sure @scanon can give many downsides that I am not considering...

Anyway, I am still in favor of using &==, etc... But I wanted to supply food for thought, in case it triggers an option which we may be missing in someone else...

1 Like

I have no strong opinions on the correct solution for this, but whatever the outcome, the documentation for Comparable should be updated with a big "note" box, stating i clear and plain English that the floating point types does not strictly conform to Comparable even if they declare that they do. In particular this does not hold:

Types with Comparable conformance implement the less-than operator ( < ) and the equal-to operator ( == ). These two operations impose a strict total order on the values of a type, in which exactly one of the following must be true for any two values a and b :

  • a == b
  • a < b
  • b < a

If you read on a little you will find:

Note
A conforming type may contain a subset of values which are treated as exceptional—that is, values that are outside the domain of meaningful arguments for the purposes of the Comparable protocol. For example, the special “not a number” value for floating-point types ( FloatingPoint.nan ) compares as neither less than, greater than, nor equal to any normal floating-point value. Exceptional values need not take part in the strict total order.

But there probably should be some mention of “exceptional values” closer to that section you mention.

1 Like

I don’t think it’s good to wave hands like this. When there are exceptional values there is not a strict total order at all. Was this exception created for any reason other than to justify the conformance of floating point types?

If we want a PartiallyComparable protocol to model partial orders we should introduce one. It would obviously not return Bool from the comparison methods.

4 Likes

I think the answer is pretty clearly “no”, but I was only addressing the documentation question for the current implementation.

I still think the solution in the original post here solves at least half the issue (i.e. the semantic issues with Comparable and Equatable). I understand that it doesn't solve the other half (i.e. comparisons on concrete types outside of the generic context) but I don't know if that is possible to solve in this timeframe, or if this problem is comparatively important because it doesn't really have the same semantic issues. So I still think I support the solution proposed in the thread, even with the understanding that it is a half measure and could introduce some inconsistencies and result in some Stack Overflow threads. If you can solve both halves at the same time instead then that would be great. e.g. I'm not opposed to shuffling the IEEE comparisons to a different operator spelling, personally, if it can be done in an acceptable way.

1 Like

Stepping back from the details, I am making two basic arguments here:

  1. We have been shipping this behavior for years, and this behavior is highly precedented in other languages. While this is not ideal behavior, it is well understood.

  2. Swift 5 branches very very soon now. Rushing in a fix for this which is unprecedented, untested, and unvetted seems unwise.

Rationale: This is a huge semantic change we're talking about here. I agree that the current situation is suboptimal (that is definitely not lost on me). This proposal is a semantic changes to swift, not a syntactic one: we have no good infrastructure to qualify the impact on the community or existing code (everything will continue to compile, just behave differently).

This particular fix is also far from obvious (see the many posts to this thread). I just see it as unwise to rush this. If it is important to fix, we can do it in a future release deliberately. I don't see why this proposal is critical to Swift 5, so if we should do this, lets take time to properly evaluate it and live with it for awhile to see if it feels good in practice.

-Chris

10 Likes

I agree. We need more time to evaluate solutions as well as room to consider source breaking changes.

It would be nice to hear some feedback from the core team on the idea of planning for source breaking releases (with large periods of stability in between) in order to avoid cementing unfortunate designs permanently in the language. The bar would still be high, just not as high as it is for most releases. Without a word of support from the core team people may be discouraged from investing time in exploring the solution space around issues like this one.

2 Likes

I’ve been thinking about this for some time today. It seems clear that the current capabilities of Swift provide no (fully) satisfying solution to address the inconsistency between the < operator on FloatingPoint types and the semantics that Equatable and Comparable expect.

Protocol conformances as they exist today generate confusion when a type can conform to a protocol in multiple ways and there isn’t an obvious choice. Moreover they don’t allow to express alternative conformances at all. The same argument came up a few weeks ago in Make Numeric Refine a new AdditiveArithmetic Protocol:

What if Swift had a notion of “named protocol conformances” that could be used to satisfy generic requirements only if referenced explicitly at the point of usage? Current protocol conformances, on the other hand, would become the “default” conformances to a protocol and would still be able to satisfy requirements implicitly.

FloatingPoint types would then be able to offer multiple protocol conformances to Comparable. For example, they could offer a total order that would fully respect Comparable semantics, a partial order that traps on NaNs, an order based on IEEE comparison, … Perhaps the first one would be the only one that really makes sense, but this model would still allow the others to exists. Importantly, users could add them retroactively with an extension if the standard library didn’t provide them.

I argue that in such a model FloatingPoint could offer no default conformance to Comparable at all. If you wanted to sort an array of Doubles, you would be forced to specify which order should be used and there would be no possible ambiguity with the outcome. This feels a bit drastic, but with the right ergonomics it should not increase complexity significantly while definitely improving clarity.

Is this a model that could reasonably be introduced in a future version of Swift? If yes, is there something in the language today that would prevent it from being implemented once the ABI is declared stable?

(This is the first time that I try to participate on Swift Evolution, so I could be missing something really obvious. I hope my contribution can be useful nonetheless)

2 Likes

I think the generally accepted terms are PartiallyEquatable/Comparable, or maybe just PartiallyOrderable. @scanon would know for sure.

Only if Numeric conforms to Equatable or Comparable (I don't remember off the top of my head). You can perform whatever math ops you want on .nans, it's just that the answer will always be .nan. Incidentally, the same isn't always the case for .infinity. Adding infinities of the same sign or subtracting infinities of the opposite sign both result in infinity. You can multiply infinity by anything other than 0 or .nan and the answer is just another infinity. And .infinity can be meaningfully compared to all* the other floating point values except .nan.

In any case, there isn't a backwards-compatible way to square this hole. Users of generic code expect a semantics out of ==, <, and > that IEEE floats simply can't provide. Even in non-generic (and non-Swift) code, the shear # of questions about floating point numbers on say, StackOverflow, indicates to me that programmers who aren't numerics experts are generally unaware of the potential corner cases in IEEE floating point code (or at least don't keep said corner cases in mind when coding). Getting rid of floats is a horrible idea because for their intended purpose, there's nothing better. It's just that their intended purpose isn't letting people, say, represent exactly 1/3, or keep track of the number of dollars they have down to the tenth of a cent, or any number of other things that involve basic 4th-grade math (which is far more complex to compute than more advanced math because you're expected to actually get the right answer, not just the "mostly right" approximation that an FPU, calculator, or engineer with a finite amount of time will give you).

* With the possible exception of itself, depending on whether you think that hardware should acknowledge that multiple infinities exist** or just leave it at some vague notion of "I'm sorry, Dave, I can't count that high". (Personally, I'd vote for doing the latter in hardware and letting some CAS library handle the former in software.)

** See "A Hierarchy of Infinities" (https://www.youtube.com/watch?v=i7c2qz7sO0I), or here's one of the wikipedia articles that talks about it: Aleph number - Wikipedia.

1 Like

I don't think anyone has suggested "getting rid of Floats". The main options on the table seem to be:

  1. Doing nothing

  2. Having operators &==, &<, etc... which use IEEE rules and having ==,<, etc... use Swift rules

  3. Adding an additional type which wraps Double or Decimal, and papers over some of the rough edges (at the loss of some efficiency in some cases). The original types would still be available...

1 Like

Ah, ok. I probably just misunderstood someone discussing #3.

Actually, the options proposed by @scanon here in this thread are:

  1. Changing the behavior of < and == on generic non-mathematical contexts.
  2. Adding alternative operators &< and &== with Swift’s semantics and doing nothing to < and ==.

Yes, it is correct that an alternative is to do nothing.

New types are far-future options, while changing the concrete behavior of < and == is not on the table for source compatibility reasons.

Could we please refrain from attempting to artificially restrict the solution space?

There is ongoing discussion in this thread about standardizing the behavior of < and ==, and introducing ampersand-prefixed versions to preserve the existing semantics. This option is clearly “on the table” by mote of being actively discussed.

Source compatibility is not a be-all end-all dictator nor an impassable barrier. Swift 5 will not be source-compatible with Swift 4, though the new compiler will likely include a mode which accepts the old language version. As evidence I present:

Furthermore, the original proposal from the original post in this thread is also silently source-breaking, as for example sort() and sort(by: <) would no longer do the same thing.

Now that we have firmly established that source compatibility is just one factor among many to consider when evaluating a proposal, and not an unassailable show-stopper, let us please return to the subject at hand so that the discussion may progress.

We are all trying to figure out what is best for Swift here, and a free exchange of ideas is essential to that goal.

6 Likes

The examples you give are largely of theoretically source-breaking changes, and indeed even those are taken very seriously. The scale at which changing < and == would be source breaking has no comparison in any of these examples, and @scanon has explicitly stated it’s a nonstarter.

So, yes, I would like to focus on this much more restricted solution space here in this thread as it was originally pitched. Can we instead agree to refrain from expanding it outward to the wide-ranging discussions that have already taken place multiple times in the past?

I’m explicitly interested in the topic of what we can do for Swift now within the next month or so, for version 5, which is my understanding of what this thread was launched to discuss. We simply cannot have every one of these discussions balloon to one questioning all of IEEE semantics if the goal is to make actual change.

1 Like

I didn't realize you controlled what we were allowed to talk about. Please stop trying to artificially shut down discussion.

From the responses here, it seems like changing the behavior of < and == has a lot of support. Whatever we decide to do (besides nothing) will break source compatibility...

1 Like

There's no need to be snarky about this. If anyone was "artifically shutting down discussion", it was Steve's very first post:

(emphasis mine)

I don't think it's wrong to try to expand an initial pitch, but in this case it means the thread has grown past the original discussion topic. I don't even think that's inherently wrong, but some people on the thread are still trying to discuss that, which means there are two different discussions going on and people are talking past each other. The two discussions aren't totally unrelated, because we've often said that we'd rather not take a language change if there's a better one we might be able to do in the future.

So I can't say I entirely agree with Xiaodi that the discussion of other options can't happen…but I do tend to agree that in practice changing < and == is, in fact, a non-starter.

3 Likes

I agree pretty strongly with Jordan, and want to clarify somewhat what I meant when I said "a non-starter".

Revisiting the Comparable protocol generally, or < and == on FloatingPoint more specifically is worth talking about in a "what if we take breaking changes sometime in the future" sense, but that's not compatible with the timeline or scales of Swift 5, and also not what this pitch is about.

This pitch is about trying to implement a narrow fix to fix bugs and unsafety in the behavior of core stdlib algorithms with FloatingPoint types in a Swift 5 timeline, in a way that does not paint us into any further semantic corners that we can possibly avoid. Obviously, the thread has gone off on a lot of tangents, most of which are worth talking about, but they are tangents to the pitch. Perhaps ideally some of these tangents would be forked into separate threads, but they're here.

We can all be a little bit more charitable in our interpretations of what others are arguing, too. Much of the pushback against more ambitious proposals here can be understood in the context of "not for Swift 5" or "that's an interesting idea, which could just as easily be built after this change as before, and in the meantime let's get a targeted bugfix done." Many of the more broadly scoped suggestions can be taken in the context of "that still doesn't completely fix the problem, so here's a suggestion of what we might do beyond that."

4 Likes