Comparison and Logical Operators or IEEE 754 Predicates

[damianmoz]

Currently, like most languages, Chapel implements the common predicates:

==  or .eq.
!=  or .ne.
>   or .gt.
<   or .lt.
>=  or .ge.
<=  or .le.

The first two never raise an exception if given an NaN.

The rest are implemented as calls to a routine or macro. This makes them hard to read.

We really need at least the following (none of which raise an IEEE exception). They have been recommended for the last 36 years but I have not seen them in any common language. It is about time that was rectified and Chapel can lead the way.

  ??  or unordered
  !?? or not unordered
  !>  or not greater than
  !>= or not greater than or equal to
  !<  or not less than
  !<= or not less than or equal to

I took the liberty of changing the conventional ? for unordered because Chapel already uses a question mark as an operator.

There is also

<>    or less or greater than but not equal to or unordered (raises an exception with an NaN in the mix)
!<>   or equal to or unordered but neither less or greater than (never raises an exception)

although I am being a bit liberal in my symbol for this last one as some people use that as an alternative to != or not equal to.
Also the first is too close to the swap operator for my liking. In this era of optimizing compilers, I fail to see why swapping needs its own operator and cannot be done as the 58 year old concept of using a tuple for the task

(x, y) = (y, x)

I agree that <=> is extremely concise and makes optimization easier to implement. That said, for a generic language:

swap(x, y)

is pretty tight and very clear and should work for objects of any type.

The reservation of the symbols is urgent before somebody else claims/hijacks them. Especially in this era of lock down the language. So the discussion needs to be had.

On the other hand, their implementation is not urgent. Note than many of those predicates in the second bunch are just a variant of one of the predicates in the first bunch, the difference being that they do not raise an IEEE 754 exception if given an NaN. I think that LLVM handles them several of them already. GCC also did, but that was caused by a bug which did not raise an exception when it was supposed to!

Comments please?

[bradcray]

Hi Damian —

Comments please?

• For those on the slow team like me, can you help me understand the difference between var result = !(a > b); and var result = (a !> b);?

• And similarly, what is a case where var result = (a <> b); and var result = (a != b); would give different results?

• The main cases in your table that give me pause are the ?? due to the other uses of ? in Chapel as you note. I think a double-? would be technically unambiguous, but still potentially confusing. For whatever reason, my head goes to things like <?> or >?<

• Do you have thoughts about how these features would or would not integrate with the notion of a spaceship operator (traditionally <=>, though in Chapel we've discussed using <==>).

I fail to see why swapping needs its own operator and cannot be done as the 58 year old concept of using a tuple for the task

I would say that it's because in cases where the naive assignment from x to y is expensive / O(n), I don't like requiring the user to hope that the compiler interprets the more complex tuple-based swap pattern as a swap rather than simply expressing the swap directly and knowing something reasonable will/can be done. Where a key case that we want to enable is the use of pointer swaps rather than O(n) deep copies to implement such expensive swaps when legal. You're right, though, that this could be expressed as swap(). In the early days of the language, we picked <=> because it felt more mnemonic and because we didn't yet have ref intents in the language. I seem to recall finding some sort of big CS award speech or paper that was advocating for a swap operator that made me feel enabled to do so (similar to your "Chapel can lead the way" comment above).

However, note that even if we retired <=> swap operator, I'm confident it would quickly get snapped up as a spaceship operator.

All that said, I don't find <> and <=> to be so close to one another as to have the existence of one preclude the other. That said, all of your three-character comparison operators do make me think that <=> will start more naturally being interpreted as the spaceship operator. Too bad we didn't use := as the assignment operator so that we could use :=: as the swap operator (that's meant to be tongue-in-cheek).

The reservation of the symbols is urgent before somebody else claims/hijacks them. Especially in this era of lock down the language.

I'd say that with the language being locked down, it's actually less likely that any of these will be gobbled up soon (and we can always add them later, as the goal is not to make breaking changes, not to stop making changes that improve things). The question as to whether adopting these would make <=> more confusing than it is today is the main thing that gives me slight pause w.r.t. stabilizing the language. But in any case, I'm also not opposed to discussing the whole thing further now, just mostly out of my area of expertise (if I have one).

They have been recommended for the last 36 years

In asking this, I'm not doubting your veracity, but can you refer us to a recommendation like this that we could use to bolster the proposal?

Thanks!

[damianmoz]

See attached background document. It answers some of your questions. I will address the others later.
Pred20211107.pdf

[damianmoz]

My customized version of the compiler allows me to use the assignment operation := instead of =. It works very well. I should see if :=: works for swapping.

[damianmoz]

In terms of the IEEE 754 comparison predicates

• C supports 12 of them, 6 symbolically, 6 with macros
• Chapel and Fortran support only 6 (symbolically)
• Kahan's 2002 paper recommends a subset of 14 symbolically, but it is not a perfectly orthogonal list
• My short paper suggests than same 14 symbolically but adds 2 more to ensure a perfectly orthogonal list

That said, I did need to change the ? predicate to ?? to avoid the clash with Chapel syntax.

I was not suggesting the work needs to be done now. But the symbols do need to be reserved.

And I am not suggesting anything that is not already covered by the IEEE 754 standard although Kahan's document does fix any ambiguity issues in the symbols that occur current standard. So I am not proposing new symbols or a new meaning to a symbol.

That said, a slight elaboration on my document would define the task and it could be offloaded to a student next year.

[damianmoz]

The latest iteration of those first 6 new predicates (or boolean operators) has a minor change to the second thereof:

  ??  or unordered
  !? or not unordered
  !>  or not greater than
  !>= or not greater than or equal to
  !<  or not less than
  !<= or not less than or equal to

Having these would make the implementation of the maxima and minima operations of #20390 simpler? That said, this issue is not urgent, but is ultimately needed. Just thought I would mention it.

[damianmoz]

The unordered and ordered predicates within the 2019 IEEE 754 standard (and the earlier 2008) are written in its Table 5.3 as

?     unordered
<=>   ordered

Chapel already uses both of these so they are out of the question.

At best, the closest approximation to the unordered concept, i.e. neither greater than, equal to, or less than, would be

!>=<

This notation is what Kahan used to use is some of his 1990s class notes, although by the millenium he had dropped this type of notation. And for me, not only it that too close to Chapel's swap operator for me but it is also too verbose at 4 characters long. And it already uses an exclamation mark so its negation is

>=<

which again is far too close to the swap operator (and is back to front anyway).

I would like to keep

??   unordered
!?    ordered

because that pair of quiet predicates is symmetric with the other quiet predicates ==/!=. By a quiet predicate, I mean one that does not raise an INVALID exception if either operand in the comparison is a quiet NaN. I assume a question mark cannot appear in Chapel outside of a parameter list. If a programmer can grasp the concept of a NaN, they can surely understand the difference between ? in a parameter list and ?? in a comparison predicate. Besides, the single '?' appears smack to the left or an identified in its other usage.

Also, there is the concept of a signalling equality predicate and its negation. That is a bit more challenging, so much so that the IEEE 754 standard has neither a symbolic or mneumonic form. We might discuss it further once we get the unordered/ordered quiet symbols bedded down.

[damianmoz]

The concept of the unordered/ordered quiet predicates in the 2019 (and 2008) IEEE 754 standard are

?    unordered
<=>  ordered

As Chapel uses both those already, that is never going to fly. Note that a quiet predicate (or comparison) is one which does not raise an INVALID exception in the presence of a quiet NaN.

The concept of the unordered predicate is that of the negation of any of greater than, equal to, or less than, or what could be written as

!>=<

This is exactly what Kahan had preferred in 1997 although by 2002 he had gone back to a single question mark for unordered, and a negated question mark for ordered. I do not like that 4 character symbol because it too verbose and too close to the Chapel swap operator. Also, its negation is then >=<, again too close to a Chapel swap operator.

Hence my preference for

??    unordered
!?      ordered

This choice means that I agree with Kahan on the second and I have achieved symmetry with the other quiet predicate, equal/unequal, i.e. ==/!=. If somebody can understand the concept of a NaN, and they know that a single question mark hard up against the start of an identifier can never appear outside of a parameter list, that won't be confused by a ?? in a predicate.

We still have to worry about the signalling equals predicate. But let's leave than for now.

[damianmoz]

Due to copyright, I cannot attach the IEEE 754 standards with the symbols. All of the symbols that I have proposed have at least 2 (or 3) decades of provenance. There is nothing new except for my use of the double question mark `??' which is necessary because Chapel is already using a single question mark. The attached Kahan papers from 1997 (IEEE754.PDF) and 2002 (Fclass.pdf) are more than adequate to explain the details of the predicates. The 2002 paper also details the mathematical heritage of most of those symbols including the single question mark. If you think it necessary, I will ask Kahan (through channels) if he has an earlier reference to these symbols.

IEEE754.PDF
Fclass.pdf

In working on #20390, I found myself needing the unordered predicates. It was interesting is how precisely (or imprecisely) CLANG and GCC optimize (or not) the use of == or != predicates when trying to identify NaN scenarios. The ?? and !? predicates should optimize far better.

[damianmoz]

Sorry @bradcray. I realized that I never replied succinctly to specific questions, despite my promises to do so.

Quoting Kahan but with my use of a double question mark ?? and a slight expansion:

Note that silent (or quiet) x !> y differs from signaling !(x > y) when either x or y can be NaN. However, x != y matches !(x == y) and similarly for !?, i.e. !(x ?? y) matches x !? y, since none of these ever signal.

The first question from @bradcray asked the difference between:

var resultS = !(a > b); and var resultQ = (a !> b);?

Extrapolating from Kahan, while resultS == resultQ, the former will raise the invalid floating point exception flag if either of the operands is a NaN. The latter will not. At the assembler level for say an x86-54, one scenario uses ucomisd and the other comisd.

The second (again altered) question from @bradcray asked the difference between:

var resultS = (a <> b);  and var resultQ = (a != b);

While resultS == resultQ, the first signals for either operand is a NaN, the second does not.

One of my tasks for the year is to make the Chapel compiler understand both x ?? y and x !? y and make them do the same as C's

unordered(x, y)
!unordered(x, y)

Can somebody point me at where I need to change the compiler please? No rush. Probably a job for April-June 2024. No rush.

[bradcray]

Can somebody point me at where I need to change the compiler please?

The "easy" part would be to add these new operators to the lexer and parser in frontend/lib/parsing/chpl.lex and chpl.ypp, following the example of (say) TLESSEQUAL in those files, then make parser and make compiler to rebuild the compiler with those changes. The harder (and mostly unknown to me) part would be what it would take to plumb those through the rest of the compiler such that you could define proc ??(...) { ... } and call it in module code. It may be that nothing more is required at all, but it's been long enough since I've tried such a thing that I'm just not sure.

And then the most challenging part would be to get consensus on introducing these new operators in order to merge the change to main. But that may or may not be of interest to you(?).

[damianmoz]

I looked at the "easy" part wnd was filled with dread. ...F......ar out!! The last time I messed with the compiler was nearly 10 years ago. It shows. Heaven help me with the "hard" part.

As for the challenging part, What I am suggesting is not new. The operation has been part of the IEEE 754 standard since its early days and has been part of the C library's implementation of that standard for decades, albeit via the far less concise mechanism of a routine called isunordered instead of the mathematical symbol. Syntactically it is not new either, using the symbol pair ??/!? instead of the ?/!? original proposal due to a clash with Chapel's use of a ?. They predate IEEE 754, well the single question mark and its negation do. It makes writing a standards compliant routine line max or min simpler and faster, and should do similar things for the performance of a reduction using those operators.

proc max(x : real(?w), y : real(w)) do return if x !? y then (if x > y then x else y) else x + y;

The predicate pair ??/~? in particular, greatly simplifies testing for the presence of a NaN.

Whether users or implementers actually care enough about IEEE 754 issues to result in its inclusion in main is another question. I am amazed at how many don't know much about it which is quite scary. But that is another problem.