IEEE NaN and Trichotomy

[jra@gensym.com (Jim Allard)]

Being somewhat of a late-comer to the discussion I don't know if this has been
addressed before, but I wanted to address my surprise at the explicit rejection
of IEEE NaN comparison behavior in Dylan.

On pages 75 and 147 there are mentions that floats follow IEEE conventions
except within comparisons, where the IEEE behavior would harm trichotomy and
therefore cannot be used.  No alternate behavior is described.  Though I do not
know what within the language depends on trichotomy and so cannot know the
fallout of this suggestion, I would urge the Dylan designers to revisit this
issue and consider adopting a fully compliant IEEE float behavior.

I also have a suggestion (which may be completely wrong) that partial orderings
could be handled if the possibility is allowed of users optionally writing more
binaryX comparitor methods, which would be used by comparitors other than = and
< when available, but still falling back to the two required comparitors when
the optional ones weren`t supplied.

My concerns about dropping IEEE NaN comparisons maninly have to do with
implementation speed issues made difficult by this choice.  Other concerns for
me would be getting Dylan users to understand a non-compliant behavior and
Dylan missing out on industrial standards and practices that tie-in with the
IEEE standard.

If Dylan programs do not use the IEEE behavior, then implementors of Dylan
compilers will have to figure out how to implement behavior other than what is
built-in to the math processors they are presented with.  Controlling
generation of NaNs within a program is one approach, though a difficult one.
The IEEE standard allows implementations to choose between generating NaN
results on overflows or to raise a SIGFPE exception.  Many vendor's processors
have switches that allow the programmer to choose between behaviors.  So one
choice a Dylan implementor could make is to always raise SIGFPE on NaN
generation, turning that into a Dylan exception, making NaNs not be valid
floats within a Dylan program, and so NaNs are not an issue within the
comparison operations.  However, issues surrounding the use of these switches
can be difficult.  On the IBM Risc System 6000 for example, setting the switch
that causes SIGFPE on overflow harms performance, since the process using this
switch must be run in serial mode, eliminating the low level parallelism of the
machine.  Another problem with this approach is that users could return NaNs
from foreign code.  Finally, this approach contradicts the general movement I
seem to be seeing amongst vendors of new architectures towards allowing NaN
generation as the default behavior.

Another approach is to go ahead and allow NaNs to be generated within the
arithmetic, to explicitly detect NaNs within comparison operation
implemenations, and then do whatever behavior Dylan eventually defines for NaN
comparison.  I would guess this is what the Dylan designers expected to occur.
This might be done when comparing A and B by emitting instructions to check the
following:

  (and (not (< a b)) (not (< b a)))

This works since IEEE says that comparisons involving NaN always return false.
The problem with this approach is that all floating point comparisons must use
variants of this check before running.  This would be a required floating point
performance deficiency within Dylan, which would give ammunition to those who
fight high-level languages as fat and slow.

A final approach is to not specially handle NaNs, let binary< and binary=
operations return #f, and therefore allow a NaN to be seen as greater than
other float values.  Given the intent of NaN within IEEE floats, this would be
a very odd choice.

As for my other concerns, I think it is difficult enough to get programmers
used to one set of choices around the complex issue of NaN handling.  To have
Dylan introduce another set of choices raises the learning curve for new
programmers.

Within my work I run into a lot of process control engineers.  They have told
me that NaNs are used in some process control systems to represent values from
sensors that are known to not be currently providing accurate values, and that
they commonly implement the logic on these values to be fail-safe, given IEEE
behavior on comparisons with NaN.  So, for example, safety checks are done such
that when readings on a valve position come back as NaN, then safety checks
will fail, since the safety predicates are written to always return true when
safe.  This individual also said that there were ISA standards for use of NaN
where sensors failed, though I haven't been able to confirm that.  I would
expect that many such practices have emerged around IEEE floats in different
industries, and non-standard IEEE behavior in Dylan would alienate those
industries.

The desire to use only two comparitors, binary= and binary<, as the basis of
all ordering within Dylan comparisons seems to be the motivation for trichotomy
requirements.  However, this would imply to me that implementations may not
make use of specific, optimized operations for comparitors like <=, but would
force both binary< and binary= to be used, which introduces another potential
performance loss.  Partially ordered sets are explicitly excluded from the
Dylan comparitor protocol, given trichotomy.

A suggestion for partially ordered comparisons is to provide generic functions
for binary>, binary>=, and binary<=, to allow users to optionally provide
methods for these generic functions along with the required binary= and binary<
methods (required assuming they want ordering), and to change the definitions
of the >, >=, and <= methods so that they will call the optional binary
ordering methods in preference to binary< and binary= when possible.  The
documentation for these binary comparitor generic functions could suggest that
for partial orderings that the binary comparitors return #f when the comparison
is inconclusive.  This is needed for stable sorts, and would follow the IEEE
float convention of returning false for inconclusive comparisons.

Note that this suggestion would depend upon an introspective function I've not
yet seen defined, which would determine if there is a method defined for a
particular set of arguments to a generic function.  To get compile-time method
selection for inlining of comparitors, a version that could determine if a
method is defined given given the types of the arguments to a generic function
would also be required.

Any thoughts or interest on this?

Jim

-------------------------------------------------------------------------------
Jim Allard                                        jra@gensym.com
Manager of Languages, Interpreters, & Compilers   (617) 547-2500
Gensym Corporation
125 CambridgePark Drive
Cambridge, MA  02140
-------------------------------------------------------------------------------