"Vladimir Panteleev" <vladimir thecybershadow.net> writes:

double[] arr = [1, 2, 3, double.nan, 1, 2];
assert(arr.isSorted);
arr.sort();

This code will fail with an assert error, but not the one on the 
second line. Rather, it will fail inside std.range, when sort 
calls assumeSorted, which checks elements in an order different 
than sort and isSorted.

Here's a case where the odd way NaN interacts with generic code 
messes things up in an ugly way.

This is concerning. It's very easy to overlook this while writing 
an application, and it can become a hidden vulnerability.

We can't fix the operators... but, perhaps, we could define a 
safe default comparison predicate (e.g. std.algorithm.less) for 
use with sorting and related tasks? Aside from bitwise 
comparison, is it even possible to efficiently compare 
floating-point values in a way suitable for sorting?

"qznc" <qznc web.de> writes:

On Tuesday, 12 November 2013 at 04:41:56 UTC, Vladimir Panteleev 
wrote:
 double[] arr = [1, 2, 3, double.nan, 1, 2];
 assert(arr.isSorted);
 arr.sort();

 This code will fail with an assert error, but not the one on 
 the second line. Rather, it will fail inside std.range, when 
 sort calls assumeSorted, which checks elements in an order 
 different than sort and isSorted.

 Here's a case where the odd way NaN interacts with generic code 
 messes things up in an ugly way.

 This is concerning. It's very easy to overlook this while 
 writing an application, and it can become a hidden 
 vulnerability.

 We can't fix the operators... but, perhaps, we could define a 
 safe default comparison predicate (e.g. std.algorithm.less) for 
 use with sorting and related tasks? Aside from bitwise 
 comparison, is it even possible to efficiently compare 
 floating-point values in a way suitable for sorting?

You cannot sort NaNs. A comparison with NaN must always evaluate 
to false.

One could change isSorted to check for false instead of true, so 
it would accept NaN. That would probably break too much code, 
though.

   arr[n] < arr[n+1]  => !(arr[n+1] < arr[n])

Apparently, isSorted contains an antisymmetry check, which is not 
triggered, because it relies on true results.

"tn" <no email.com> writes:

On Tuesday, 12 November 2013 at 07:33:57 UTC, qznc wrote:
 On Tuesday, 12 November 2013 at 04:41:56 UTC, Vladimir 
 Panteleev wrote:
 double[] arr = [1, 2, 3, double.nan, 1, 2];
 assert(arr.isSorted);
 arr.sort();

 This code will fail with an assert error, but not the one on 
 the second line. Rather, it will fail inside std.range, when 
 sort calls assumeSorted, which checks elements in an order 
 different than sort and isSorted.

 Here's a case where the odd way NaN interacts with generic 
 code messes things up in an ugly way.

 This is concerning. It's very easy to overlook this while 
 writing an application, and it can become a hidden 
 vulnerability.

 We can't fix the operators... but, perhaps, we could define a 
 safe default comparison predicate (e.g. std.algorithm.less) 
 for use with sorting and related tasks? Aside from bitwise 
 comparison, is it even possible to efficiently compare 
 floating-point values in a way suitable for sorting?

 You cannot sort NaNs. A comparison with NaN must always 
 evaluate to false.

 One could change isSorted to check for false instead of true, 
 so it would accept NaN. That would probably break too much 
 code, though.

   arr[n] < arr[n+1]  => !(arr[n+1] < arr[n])

But that is exactly what it does.

https://github.com/D-Programming-Language/phobos/blob/8372da44f66f20c67b69b4b8fb39233ce42d493c/std/algorithm.d#L10021

And that is the reason the second line "assert(arr.isSorted);" 
passes, while it should fail as the array is clearly not sorted. 
Instead modifying

   !(arr[n+1] < arr[n])  =>  arr[n] <= arr[n+1]

would make the function work correctly (return false if the range 
contains nans), but then the template parameter "less" should be 
replaced by "lessOrEqual". An alternative would be to check for 
nans explicitly.

"tn" <no email.com> writes:

On Tuesday, 12 November 2013 at 08:54:35 UTC, tn wrote:
 On Tuesday, 12 November 2013 at 07:33:57 UTC, qznc wrote:
 On Tuesday, 12 November 2013 at 04:41:56 UTC, Vladimir 
 Panteleev wrote:
 double[] arr = [1, 2, 3, double.nan, 1, 2];
 assert(arr.isSorted);
 arr.sort();

 This code will fail with an assert error, but not the one on 
 the second line. Rather, it will fail inside std.range, when 
 sort calls assumeSorted, which checks elements in an order 
 different than sort and isSorted.

 Here's a case where the odd way NaN interacts with generic 
 code messes things up in an ugly way.

 This is concerning. It's very easy to overlook this while 
 writing an application, and it can become a hidden 
 vulnerability.

 We can't fix the operators... but, perhaps, we could define a 
 safe default comparison predicate (e.g. std.algorithm.less) 
 for use with sorting and related tasks? Aside from bitwise 
 comparison, is it even possible to efficiently compare 
 floating-point values in a way suitable for sorting?

 You cannot sort NaNs. A comparison with NaN must always 
 evaluate to false.

 One could change isSorted to check for false instead of true, 
 so it would accept NaN. That would probably break too much 
 code, though.

  arr[n] < arr[n+1]  => !(arr[n+1] < arr[n])

 But that is exactly what it does.

 https://github.com/D-Programming-Language/phobos/blob/8372da44f66f20c67b69b4b8fb39233ce42d493c/std/algorithm.d#L10021

 And that is the reason the second line "assert(arr.isSorted);" 
 passes, while it should fail as the array is clearly not 
 sorted. Instead modifying

   !(arr[n+1] < arr[n])  =>  arr[n] <= arr[n+1]

 would make the function work correctly (return false if the 
 range contains nans), but then the template parameter "less" 
 should be replaced by "lessOrEqual". An alternative would be to 
 check for nans explicitly.

Actually, you could also use "!>=" instead of "<" so that the 
compasison would become:

   !(arr[n+1] !>= arr[n])

This is also correct for floating point numbers. However, it 
might be problematic for user defined types that also implement 
something similar to nan (eg. bigfloat). I could not find any 
documentation on how the unordered comparison operators (<>, 
!<>=, !<=, !<, !>=, !>, !<>) translate into opCmp calls.

Walter Bright <newshound2 digitalmars.com> writes:

On 11/12/2013 1:33 AM, tn wrote:
 I could not find any documentation on how the unordered
 comparison operators (<>, !<>=, !<=, !<, !>=, !>, !<>) translate into opCmp
calls.

That's because they just don't translate to opCmp calls. At one point I was 
going to set up an opExtendedCmp or something like that for those operators,
but 
then we went ahead and deprecated those operators, rendering the idea moot.

"tn" <no email.com> writes:

On Tuesday, 12 November 2013 at 09:40:52 UTC, Walter Bright wrote:
 On 11/12/2013 1:33 AM, tn wrote:
 I could not find any documentation on how the unordered
 comparison operators (<>, !<>=, !<=, !<, !>=, !>, !<>) 
 translate into opCmp calls.

 That's because they just don't translate to opCmp calls.

Well, they seem to translate to something, because this works as 
expected:

   struct S {
       private double v;
       auto opCmp(S rhs) { return v - rhs.v; }
   }

   S v1 = S(1);
   S v2 = S(2);
   S vn = S(double.nan);
   assert((v2 < v1) == false);
   assert((v1 < v2) == true);
   assert((v1 < v1) == false);
   assert((v1 < vn) == false);
   assert((v2 !>= v1) == false);
   assert((v1 !>= v2) == true);
   assert((v1 !>= v1) == false);
   assert((v1 !>= vn) == true);


 but then we went ahead and deprecated those operators

Maybe the spec then needs to be updated:

http://dlang.org/expression.html#RelExpression
http://dlang.org/expression.html#floating_point_comparisons

Jonathan M Davis <jmdavisProg gmx.com> writes:

On Tuesday, November 12, 2013 10:33:26 tn wrote:
  I could not find any
 documentation on how the unordered comparison operators (<>,
 !<>=, !<=, !<, !>=, !>, !<>) translate into opCmp calls.

As I understand it, they only work with the built-in floating point types and 
are supposed to be deprecated. So, writing new code which uses them - 
particularly generic code - wouldn't make sense.

- Jonathan M Davis

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 11/12/13 12:54 AM, tn wrote:
 On Tuesday, 12 November 2013 at 07:33:57 UTC, qznc wrote:
 On Tuesday, 12 November 2013 at 04:41:56 UTC, Vladimir Panteleev wrote:
 double[] arr = [1, 2, 3, double.nan, 1, 2];
 assert(arr.isSorted);
 arr.sort();

 This code will fail with an assert error, but not the one on the
 second line. Rather, it will fail inside std.range, when sort calls
 assumeSorted, which checks elements in an order different than sort
 and isSorted.

 Here's a case where the odd way NaN interacts with generic code
 messes things up in an ugly way.

 This is concerning. It's very easy to overlook this while writing an
 application, and it can become a hidden vulnerability.

 We can't fix the operators... but, perhaps, we could define a safe
 default comparison predicate (e.g. std.algorithm.less) for use with
 sorting and related tasks? Aside from bitwise comparison, is it even
 possible to efficiently compare floating-point values in a way
 suitable for sorting?

 You cannot sort NaNs. A comparison with NaN must always evaluate to
 false.

 One could change isSorted to check for false instead of true, so it
 would accept NaN. That would probably break too much code, though.

   arr[n] < arr[n+1]  => !(arr[n+1] < arr[n])

 But that is exactly what it does.

 https://github.com/D-Programming-Language/phobos/blob/8372da44f66f20c67b69b4b8fb39233ce42d493c/std/algorithm.d#L10021


 And that is the reason the second line "assert(arr.isSorted);" passes,
 while it should fail as the array is clearly not sorted. Instead modifying

    !(arr[n+1] < arr[n])  =>  arr[n] <= arr[n+1]

 would make the function work correctly (return false if the range
 contains nans), but then the template parameter "less" should be
 replaced by "lessOrEqual". An alternative would be to check for nans
 explicitly.

I think NaNs are singular unordered values that make invalid inputs for 
either sort or isSorted. We should simply add an assert to isSorted.

Andrei

"Vladimir Panteleev" <vladimir thecybershadow.net> writes:

On Tuesday, 12 November 2013 at 15:56:25 UTC, Andrei Alexandrescu 
wrote:
 I think NaNs are singular unordered values that make invalid 
 inputs for either sort or isSorted. We should simply add an 
 assert to isSorted.

Considering their effect on the program state, NaNs can be seen 
as invalid input, and asserts are not suitable for input 
validation.

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 11/12/13 8:05 AM, Vladimir Panteleev wrote:
 On Tuesday, 12 November 2013 at 15:56:25 UTC, Andrei Alexandrescu wrote:
 I think NaNs are singular unordered values that make invalid inputs
 for either sort or isSorted. We should simply add an assert to isSorted.

 Considering their effect on the program state, NaNs can be seen as
 invalid input, and asserts are not suitable for input validation.

I should know, since I dedicated a chapter to the topic in TDPL :o). 
It's all a matter of boundaries, i.e. what you consider "input" and what 
you consider "precondition". When user code reads floating point data 
off of disk, they should do real validation. For isSorted we could say 
that the output is only defined for inputs that are comparable. Or 
indeed we could specify that isSorted throws if unordered data is 
presented, and verify everything at runtime, at a cost in efficiency. 
It's a judgment call, not a cut and dried decision. In this case I think 
assert is the better call.

Andrei

"tn" <no email.com> writes:

On Tuesday, 12 November 2013 at 15:56:25 UTC, Andrei Alexandrescu 
wrote:
 On 11/12/13 12:54 AM, tn wrote:
 ...
 An alternative would be to check for nans explicitly.

 I think NaNs are singular unordered values that make invalid 
 inputs for either sort or isSorted. We should simply add an 
 assert to isSorted.

But sort and isSorted both allow user to provide a custom "less" 
function. What if the user needs NaNs and, for example, wants to 
sort them before all the other values? Then he calls 
"arr.sort!((a,b) => a < b || (isnan(a) && !isnan(b)))" and the 
code asserts?

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 11/12/13 10:31 AM, tn wrote:
 On Tuesday, 12 November 2013 at 15:56:25 UTC, Andrei Alexandrescu wrote:
 On 11/12/13 12:54 AM, tn wrote:
 ...
 An alternative would be to check for nans explicitly.

 I think NaNs are singular unordered values that make invalid inputs
 for either sort or isSorted. We should simply add an assert to isSorted.

 But sort and isSorted both allow user to provide a custom "less"
 function. What if the user needs NaNs and, for example, wants to sort
 them before all the other values? Then he calls "arr.sort!((a,b) => a <
 b || (isnan(a) && !isnan(b)))" and the code asserts?

I think this is a misunderstanding. I never advocated inserting 
specialized asserts for floating-point numbers. http://goo.gl/3dGGkf 
takes care of that the right way - by making sure that the less 
predicate is sensible for the kind of work isSorted and sort do. That is 
regardless of the nature of the objects being sorted.

Andrei

Jonathan M Davis <jmdavisProg gmx.com> writes:

On Tuesday, November 12, 2013 05:41:55 Vladimir Panteleev wrote:
 double[] arr = [1, 2, 3, double.nan, 1, 2];
 assert(arr.isSorted);
 arr.sort();
 
 This code will fail with an assert error, but not the one on the
 second line. Rather, it will fail inside std.range, when sort
 calls assumeSorted, which checks elements in an order different
 than sort and isSorted.
 
 Here's a case where the odd way NaN interacts with generic code
 messes things up in an ugly way.
 
 This is concerning. It's very easy to overlook this while writing
 an application, and it can become a hidden vulnerability.
 
 We can't fix the operators... but, perhaps, we could define a
 safe default comparison predicate (e.g. std.algorithm.less) for
 use with sorting and related tasks? Aside from bitwise
 comparison, is it even possible to efficiently compare
 floating-point values in a way suitable for sorting?

The check could be special-cased for floating point values so that it takes NaN 
into account, but NaN pretty much screws with everything. Once it's there, 
pretty much anything involving math or comparisons is going to go bad. So, you 
could argue that it's a bug in the program if sort is passed a NaN and that 
the assertion in sort is therefore perfectly valid. You can't really sort 
anything with NaN in it anyway.

- Jonathan M Davis

"Vladimir Panteleev" <vladimir thecybershadow.net> writes:

On Tuesday, 12 November 2013 at 08:10:16 UTC, Jonathan M Davis 
wrote:
 On Tuesday, November 12, 2013 05:41:55 Vladimir Panteleev wrote:
 double[] arr = [1, 2, 3, double.nan, 1, 2];
 assert(arr.isSorted);
 arr.sort();
 
 This code will fail with an assert error, but not the one on 
 the
 second line. Rather, it will fail inside std.range, when sort
 calls assumeSorted, which checks elements in an order different
 than sort and isSorted.
 
 Here's a case where the odd way NaN interacts with generic code
 messes things up in an ugly way.
 
 This is concerning. It's very easy to overlook this while 
 writing
 an application, and it can become a hidden vulnerability.
 
 We can't fix the operators... but, perhaps, we could define a
 safe default comparison predicate (e.g. std.algorithm.less) for
 use with sorting and related tasks? Aside from bitwise
 comparison, is it even possible to efficiently compare
 floating-point values in a way suitable for sorting?

 The check could be special-cased for floating point values so 
 that it takes NaN
 into account, but NaN pretty much screws with everything. Once 
 it's there,
 pretty much anything involving math or comparisons is going to 
 go bad. So, you
 could argue that it's a bug in the program if sort is passed a 
 NaN and that
 the assertion in sort is therefore perfectly valid. You can't 
 really sort
 anything with NaN in it anyway.

Here is the problem:

1) NaN values are accepted as input almost anywhere where doubles 
are. std.conv recognizes the string "nan" and converts it to 
double.nan,
2) It is unreasonable to expect every D user out there dealing 
with floating point numbers to be forced to check every source of 
floating point values in their program against NaNs.
3) If the program is compiled in debug mode, it will crash 
quasi-randomly, since the assumeSorted assert does not check 
every pair.

For these reasons, this problem can become a sort of time bomb in 
their application: even with 100% test coverage, one NaN in the 
wrong place inputted by a malicious end user can cause a 
situation the program's authors have not foreseen.

It can be argued that it is a flaw in the language in that it 
allowed such a situation to arise in the first place.

P.S. Please enable RFC 2646 (format=flowed) support in your email 
client. It is emitting unreflowable text, which causes jagged 
quotes as seen above.

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 11/12/13 8:00 AM, Vladimir Panteleev wrote:
 1) NaN values are accepted as input almost anywhere where doubles are.
 std.conv recognizes the string "nan" and converts it to double.nan,

They are still singular values. Code has no business comparing them 
unwittingly.

 2) It is unreasonable to expect every D user out there dealing with
 floating point numbers to be forced to check every source of floating
 point values in their program against NaNs.

I find that perfectly reasonable. How do you mean that?

 3) If the program is compiled in debug mode, it will crash
 quasi-randomly, since the assumeSorted assert does not check every pair.

It should always crash. As I said: insert an assert in assumeSorted and 
be done with it.

 For these reasons, this problem can become a sort of time bomb in their
 application: even with 100% test coverage, one NaN in the wrong place
 inputted by a malicious end user can cause a situation the program's
 authors have not foreseen.

 It can be argued that it is a flaw in the language in that it allowed
 such a situation to arise in the first place.

The language allows NaN floating point number with the semantics of IEEE 
754. We hardly have any leeway in the matter unless we want to irate a 
lot of people for no good reason.

I don't understand your entire point here. I agree with something like 
"NaNs are a nuisance." We need to fix the corresponding bugs in 
assumeSorted, isSorted etc. by inserting sanity checks such as:

if (a[i] < a[i + 1]) { assert(!(a[i + 1] < a[i])); ... }
else { assert(a[i + 1] >= a[i]); ... }

etc.


Andrei

"Vladimir Panteleev" <vladimir thecybershadow.net> writes:

On Tuesday, 12 November 2013 at 16:48:01 UTC, Andrei Alexandrescu 
wrote:
 On 11/12/13 8:00 AM, Vladimir Panteleev wrote:
 1) NaN values are accepted as input almost anywhere where 
 doubles are.
 std.conv recognizes the string "nan" and converts it to 
 double.nan,

 They are still singular values. Code has no business comparing 
 them unwittingly.

 2) It is unreasonable to expect every D user out there dealing 
 with
 floating point numbers to be forced to check every source of 
 floating
 point values in their program against NaNs.

 I find that perfectly reasonable. How do you mean that?

Both of the above hinge on the relative obscurity of NaNs and the 
problems they could cause. People who are not specifically 
familiar with NaNs and how they interact with other 
floating-point values will treat floating-point values as "just 
numbers", and expect them to compare and sort in the same way as 
integers.

 The language allows NaN floating point number with the 
 semantics of IEEE 754. We hardly have any leeway in the matter 
 unless we want to irate a lot of people for no good reason.

 It's a judgment call, not a cut and dried decision.

Agreed - however, I think there might be more than one way to 
deal with this.

1) As above, introduce a "less" function which guarantees 
transitivity for basic types, and use it in examples throughout.

2) Improve documentation and visibility of this problem. For 
example, add this to the documentation of sort:

"The predicate must be transitive (`a<b && b<c` implies `a<c`) in 
order for `sort` to behave properly - otherwise, the program may 
fail on certain inputs (but not others) when not compiled in 
release mode. Note that `a<b` is not transitive for floating 
points, because the expression will always be `false` when either 
`a` or `b` is `NaN`."

 We should simply add an assert to isSorted.

How would this be implemented, anyway? I stumbled upon this 
problem with this code:

enum sortPred = q{a.hits > b.hits || (a.hits == b.hits && a.value 
< b.value)};
all.sort!sortPred();

(I know about multiSort, but it currently seems to be buggy - I 
do have a test case, but it has a few million entries and I need 
to reduce it.)

 if (a[i] < a[i + 1]) { assert(!(a[i + 1] < a[i])); ... }
 else { assert(a[i + 1] >= a[i]); ... }

Sort et al don't know how to check "a>=b"... and they can't use 
"a<b" either, because !(a<b) && !(b<a) implies a==b.

"Bigsandwich" <bigsandwich gmail.com> writes:

 Both of the above hinge on the relative obscurity of NaNs and 
 the problems they could cause. People who are not specifically 
 familiar with NaNs and how they interact with other 
 floating-point values will treat floating-point values as "just 
 numbers", and expect them to compare and sort in the same way 
 as integers.

Please, please, please just no.  As someone who works with 
floating point daily, you cannot idiot proof it like this.  They 
will never behave like "just numbers" and you can't make them.

Even leaving out NAN, you have issues with precision, accumulated 
error, denormals, equality comparison, and on and on.

If you don't know what you are doing with them, then you just 
shouldn't be touching them.  Unicode has similar issues.

Walter Bright <newshound2 digitalmars.com> writes:

On 11/12/2013 10:25 AM, Bigsandwich wrote:
 Please, please, please just no.  As someone who works with floating point
daily,
 you cannot idiot proof it like this.  They will never behave like "just
numbers"
 and you can't make them.

 Even leaving out NAN, you have issues with precision, accumulated error,
 denormals, equality comparison, and on and on.

 If you don't know what you are doing with them, then you just shouldn't be
 touching them.  Unicode has similar issues.

I think it's apropos to reference this famous document:

"What Every Computer Scientist Should Know About Floating-Point Arithmetic"

http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html

I know, I know, RTFM, but one cannot ignore this stuff and write professional 
quality fp code, nor is it practical to have the language ignore it for you.

Walter Bright <newshound2 digitalmars.com> writes:

On 11/12/2013 9:59 AM, Vladimir Panteleev wrote:
 Both of the above hinge on the relative obscurity of NaNs and the problems they
 could cause. People who are not specifically familiar with NaNs and how they
 interact with other floating-point values will treat floating-point values as
 "just numbers", and expect them to compare and sort in the same way as
integers.

NaNs are valid values for floating point numbers. Trying to pretend they don't 
exist is a doomed strategy for programmers. I regard this as analogous to the 
regular proposals to hide the fact that char[] are sequences of unicode code 
points, attempts to pretend that integers don't overflow, etc.

Floating point math has some strange characteristics (NaNs are only one such), 
and anyone writing a non-toy fp app needs to learn that stuff. There's no other
way.

"Vladimir Panteleev" <vladimir thecybershadow.net> writes:

On Tuesday, 12 November 2013 at 18:31:40 UTC, Walter Bright wrote:
 NaNs are valid values for floating point numbers. Trying to 
 pretend they don't exist is a doomed strategy for programmers. 
 I regard this as analogous to the regular proposals to hide the 
 fact that char[] are sequences of unicode code points, attempts 
 to pretend that integers don't overflow, etc.

 Floating point math has some strange characteristics (NaNs are 
 only one such), and anyone writing a non-toy fp app needs to 
 learn that stuff. There's no other way.

On Tuesday, 12 November 2013 at 18:25:10 UTC, Bigsandwich wrote:
 Please, please, please just no.  As someone who works with 
 floating point daily, you cannot idiot proof it like this.  
 They will never behave like "just numbers" and you can't make 
 them.

 Even leaving out NAN, you have issues with precision, 
 accumulated error, denormals, equality comparison, and on and 
 on.

That doesn't change the reality that not everyone is aware of 
these issues, and that even people who are aware of them may 
overlook something somewhere. We can't pretend that there is no 
problem just because it's something you "have to know" and "have 
to be careful about" - if we can improve the situation without 
making a compromise elsewhere, then it must be done.

I don't see this stance as any different than shouting "RTFM!!!" 
at anyone who makes a mistake which, in theory, could be avoided 
by studying, memorization and careful application of the 
appropriate documentation located ... somewhere. This approach 
does not work - even if that user has learned his lesson the hard 
way, more new users will make the same mistake. Instead, you must 
actually make the problem less likely to manifest - improve your 
documentation, or improve the design of your system such that 
such errors will be less likely to occur.

This particular situation affects only one specific property of 
floating-point numbers, so other properties are not relevant to 
this discussion. Personally, I've been taught about 
floating-point precision issues back in school, but I've only 
learned about NaNs while learning D. Call me an unlearned idiot 
if that makes you feel better, but it is rather likely that there 
will be more users making the same mistake in the future if the 
situation is not addressed.

Furthermore, the problem is aggravated by that it is hidden by 
generic code. This thread isn't a complaint that "the line `if 
(a<b)` in my program behaves in a funny way" - there are no 
explicit floating-point comparisons in the example in the 
original post. We are calling sort, a function in the standard 
library, with its default predicate, as specified in the standard 
library, using a built-in type, which is part of the language, 
and it fails its own assertion on certain input. This is a 
problem!

I have suggested possible improvements earlier in this thread, so 
I'd like to ask you to comment on those rather than hand-waving 
the problem away.

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 11/12/13 11:06 AM, Vladimir Panteleev wrote:
 That doesn't change the reality that not everyone is aware of these
 issues, and that even people who are aware of them may overlook
 something somewhere. We can't pretend that there is no problem just
 because it's something you "have to know" and "have to be careful about"
 - if we can improve the situation without making a compromise elsewhere,
 then it must be done.

I agree. I'll just add that people who plan to get work done with 
floating point will inevitably stumble upon NaN. There's no two ways 
about it.

 I don't see this stance as any different than shouting "RTFM!!!" at
 anyone who makes a mistake which, in theory, could be avoided by
 studying, memorization and careful application of the appropriate
 documentation located ... somewhere. This approach does not work - even
 if that user has learned his lesson the hard way, more new users will
 make the same mistake. Instead, you must actually make the problem less
 likely to manifest - improve your documentation, or improve the design
 of your system such that such errors will be less likely to occur.

I agree here, too. Again, I'll add that "improving the documentation" 
helps little unless RTFM is at work :o).

 This particular situation affects only one specific property of
 floating-point numbers, so other properties are not relevant to this
 discussion. Personally, I've been taught about floating-point precision
 issues back in school, but I've only learned about NaNs while learning
 D. Call me an unlearned idiot if that makes you feel better, but it is
 rather likely that there will be more users making the same mistake in
 the future if the situation is not addressed.

You're young. I guarantee you were to hit NaN whether or not D had 
anything to do with it.

 Furthermore, the problem is aggravated by that it is hidden by generic
 code. This thread isn't a complaint that "the line `if (a<b)` in my
 program behaves in a funny way" - there are no explicit floating-point
 comparisons in the example in the original post. We are calling sort, a
 function in the standard library, with its default predicate, as
 specified in the standard library, using a built-in type, which is part
 of the language, and it fails its own assertion on certain input. This
 is a problem!

Yes.

 I have suggested possible improvements earlier in this thread, so I'd
 like to ask you to comment on those rather than hand-waving the problem
 away.

I think your solutions are not good. I also think my solution in 
http://goo.gl/3dGGkf is good. (I know it sounds awful, but I hope you'll 
appreciate the brevity :o).) The solution I propose explains exactly how 
NaN messes up the ordering comparison operator, in a way that doesn't 
make the tests refer to NaN or floating point numbers in particular.


Andrei

Walter Bright <newshound2 digitalmars.com> writes:

On 11/12/2013 12:24 PM, Andrei Alexandrescu wrote:
 You're young. I guarantee you were to hit NaN whether or not D had anything to
 do with it.

I want to add that NaN has been a reality on x86 machines since about 1983. C 
(and C++) compilers for decades have utterly ignored its existence - but that 
didn't make it go away. It just meant that things like the fp functions in the 
Standard library exhibited undefined behavior with NaNs, which is far worse
than 
at least having sensible documented behavior.

The C compilers I wrote (and C++) always made an effort to handle NaN correctly 
(and overflows, underflows, and subnormals), and I often felt that I was the 
only one who cared about it :-)

What D does is simply recognize that NaNs are an inevitable characteristic of 
the floating point hardware, and deal with them in the most straightforward 
manner practical. Deciding and documenting what .sort should do with NaNs is 
part of that. Trying to pretend that NaNs aren't a fact of life with IEEE 
floating point hardware is not going to work.

Note:



and how the behavior with NaN arguments is all carefully documented.

"Vladimir Panteleev" <vladimir thecybershadow.net> writes:

On Tuesday, 12 November 2013 at 20:24:11 UTC, Andrei Alexandrescu 
wrote:
 Again, I'll add that "improving the documentation" helps little 
 unless RTFM is at work :o).

The distinction between good and bad documentation in this 
context is whether the respective information is discoverable. 
That is, don't make users ask "How should I have known that?". A 
warning on the documentation of std.algorithm.sort is good, but 
an article on floating-points merely included together with the 
documentation, and not referenced from anywhere, isn't.

 I think your solutions are not good. I also think my solution 
 in http://goo.gl/3dGGkf is good. (I know it sounds awful, but I 
 hope you'll appreciate the brevity :o).)

Brevity appreciated :D

"tn" <no email.com> writes:

On Tuesday, 12 November 2013 at 17:59:37 UTC, Vladimir Panteleev 
wrote:
 1) As above, introduce a "less" function which guarantees 
 transitivity for basic types, and use it in examples throughout.

 2) Improve documentation and visibility of this problem. For 
 example, add this to the documentation of sort:

 "The predicate must be transitive (`a<b && b<c` implies `a<c`) 
 in order for `sort` to behave properly - otherwise, the program 
 may fail on certain inputs (but not others) when not compiled 
 in release mode. Note that `a<b` is not transitive for floating 
 points, because the expression will always be `false` when 
 either `a` or `b` is `NaN`."

But 'a<b' is transitive for floating points. The transitivity 
condition (`a<b && b<c` implies `a<c`) says nothing about the 
cases where a and b (or b and c) are incomparable. Transitivity 
is not the problem

 Sort et al don't know how to check "a>=b"... and they can't use 
 "a<b" either, because !(a<b) && !(b<a) implies a==b.

This is the problem, that is, the fact that with '<' you can't 
tell the difference between equal values and incomparable values 
(one or both are NaNs). On the other hand, with '<=' you can. See:

  (a<b) && !(b<a)  -->  a<b
!(a<b) &&  (b<a)  -->  b<a
  (a<b) &&  (b<a)  -->  (not possible)
!(a<b) && !(b<a)  -->  a==b OR incomparable

but

  (a<=b) && !(b<=a)  -->  a<b
!(a<=b) &&  (b<=a)  -->  b<a
  (a<=b) &&  (b<=a)  -->  a==b
!(a<=b) && !(b<=a)  -->  incomparable

Thus, the correct solution would be to modify the functions to 
take "lessOrEqual" as a template parameter instead of "less".

If "less" is kept, then we need another template argument to 
separate equality and incomparability (something like 
"equals(a,b)", or "incomparable(a,b)").

"Vladimir Panteleev" <vladimir thecybershadow.net> writes:

On Tuesday, 12 November 2013 at 19:26:12 UTC, tn wrote:
 But 'a<b' is transitive for floating points. The transitivity 
 condition (`a<b && b<c` implies `a<c`) says nothing about the 
 cases where a and b (or b and c) are incomparable. Transitivity 
 is not the problem

Whoops, you're right. I meant transitivity of the negated 
expression: !(a>b) && !(b>c) implies !(a>c). This fails for [3, 
NaN, 1].

 Sort et al don't know how to check "a>=b"... and they can't 
 use "a<b" either, because !(a<b) && !(b<a) implies a==b.

 This is the problem, that is, the fact that with '<' you can't 
 tell the difference between equal values and incomparable 
 values (one or both are NaNs). On the other hand, with '<=' you 
 can. See:

  (a<b) && !(b<a)  -->  a<b
 !(a<b) &&  (b<a)  -->  b<a
  (a<b) &&  (b<a)  -->  (not possible)
 !(a<b) && !(b<a)  -->  a==b OR incomparable

 but

  (a<=b) && !(b<=a)  -->  a<b
 !(a<=b) &&  (b<=a)  -->  b<a
  (a<=b) &&  (b<=a)  -->  a==b
 !(a<=b) && !(b<=a)  -->  incomparable

 Thus, the correct solution would be to modify the functions to 
 take "lessOrEqual" as a template parameter instead of "less".

Too late for that now... just like it's too late to change IEEE 
comparison logic.

 If "less" is kept, then we need another template argument to 
 separate equality and incomparability (something like 
 "equals(a,b)", or "incomparable(a,b)").

Is this to allow generic partial ordering (rather than to fix 
sorting NaNs specifically)? I remember seeing a thread about 
partial ordering and opCmp:
http://forum.dlang.org/post/dpfbtu$1ocf$1 digitaldaemon.com

"tn" <no email.com> writes:

On Tuesday, 12 November 2013 at 19:39:19 UTC, Vladimir Panteleev 
wrote:
 On Tuesday, 12 November 2013 at 19:26:12 UTC, tn wrote:
 Thus, the correct solution would be to modify the functions to 
 take "lessOrEqual" as a template parameter instead of "less".

 Too late for that now... just like it's too late to change IEEE 
 comparison logic.

Yes, I was expecting this. :)

 If "less" is kept, then we need another template argument to 
 separate equality and incomparability (something like 
 "equals(a,b)", or "incomparable(a,b)").

 Is this to allow generic partial ordering (rather than to fix 
 sorting NaNs specifically)? I remember seeing a thread about 
 partial ordering and opCmp:
 http://forum.dlang.org/post/dpfbtu$1ocf$1 digitaldaemon.com

I had generic partial orderings in my mind too, but I think it is 
also needed for user defined floating point types such as 
bigfloat. (Unless "isnan" function is defined for the bigfloat 
type too and detected automatically.)

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 11/12/13 9:59 AM, Vladimir Panteleev wrote:
 On Tuesday, 12 November 2013 at 16:48:01 UTC, Andrei Alexandrescu wrote:
 On 11/12/13 8:00 AM, Vladimir Panteleev wrote:
 1) NaN values are accepted as input almost anywhere where doubles are.
 std.conv recognizes the string "nan" and converts it to double.nan,

 They are still singular values. Code has no business comparing them
 unwittingly.

 2) It is unreasonable to expect every D user out there dealing with
 floating point numbers to be forced to check every source of floating
 point values in their program against NaNs.

 I find that perfectly reasonable. How do you mean that?

 Both of the above hinge on the relative obscurity of NaNs and the
 problems they could cause. People who are not specifically familiar with
 NaNs and how they interact with other floating-point values will treat
 floating-point values as "just numbers", and expect them to compare and
 sort in the same way as integers.

I think that's their problem, not ours.

 The language allows NaN floating point number with the semantics of
 IEEE 754. We hardly have any leeway in the matter unless we want to
 irate a lot of people for no good reason.

 It's a judgment call, not a cut and dried decision.

 Agreed - however, I think there might be more than one way to deal with
 this.

 1) As above, introduce a "less" function which guarantees transitivity
 for basic types, and use it in examples throughout.

This is a bit much.

 2) Improve documentation and visibility of this problem. For example,
 add this to the documentation of sort:

 "The predicate must be transitive (`a<b && b<c` implies `a<c`) in order
 for `sort` to behave properly - otherwise, the program may fail on
 certain inputs (but not others) when not compiled in release mode. Note
 that `a<b` is not transitive for floating points, because the expression
 will always be `false` when either `a` or `b` is `NaN`."

Great idea, just file an enh request or just write the pull request.

 We should simply add an assert to isSorted.

 How would this be implemented, anyway? I stumbled upon this problem with
 this code:

 enum sortPred = q{a.hits > b.hits || (a.hits == b.hits && a.value <
 b.value)};
 all.sort!sortPred();

 (I know about multiSort, but it currently seems to be buggy - I do have
 a test case, but it has a few million entries and I need to reduce it.)

 if (a[i] < a[i + 1]) { assert(!(a[i + 1] < a[i])); ... }
 else { assert(a[i + 1] >= a[i]); ... }

 Sort et al don't know how to check "a>=b"... and they can't use "a<b"
 either, because !(a<b) && !(b<a) implies a==b.

It really implies "a and b are in the same equivalence class". Building 
on that notion, we can figure what's wrong with NaNs and how to assert 
against their failings.

Consider we define equiv(a, b) as (a, b) => !less(a, b) && !less(b, a).

If at least one of the numbers is NaN, all comparisons return false. 
That puts NaN in the same equivalence class with all numbers, including 
numbers that are deemed in distinct equivalence classes. That's where 
NaNs mess things up, and that's what we need to assert. Consider three 
numbers a, b, and c. Then the following must pass:

assert((equiv(a, b) && equiv(b, c)) <= equiv(a, c));

("<=" on Booleans is actually implication.)

That test will fail with NaNs and should be part of isSorted, sort etc.

We should also check such as:

assert(!less(a, a));
assert(less(a, b) <= !less(b, a));

These should be checked in sort only; isSorted does not need these.


Andrei

"Vladimir Panteleev" <vladimir thecybershadow.net> writes:

On Tuesday, 12 November 2013 at 20:03:37 UTC, Andrei Alexandrescu 
wrote:
 Both of the above hinge on the relative obscurity of NaNs and 
 the
 problems they could cause. People who are not specifically 
 familiar with
 NaNs and how they interact with other floating-point values 
 will treat
 floating-point values as "just numbers", and expect them to 
 compare and
 sort in the same way as integers.

 I think that's their problem, not ours.

(I partially disagree here - see my reply to Walter.)

 Sort et al don't know how to check "a>=b"... and they can't 
 use "a<b"
 either, because !(a<b) && !(b<a) implies a==b.

 It really implies "a and b are in the same equivalence class". 
 Building on that notion, we can figure what's wrong with NaNs 
 and how to assert against their failings.

 Consider we define equiv(a, b) as (a, b) => !less(a, b) && 
 !less(b, a).

 If at least one of the numbers is NaN, all comparisons return 
 false. That puts NaN in the same equivalence class with all 
 numbers, including numbers that are deemed in distinct 
 equivalence classes. That's where NaNs mess things up, and 
 that's what we need to assert. Consider three numbers a, b, and 
 c. Then the following must pass:

 assert((equiv(a, b) && equiv(b, c)) <= equiv(a, c));

OK, we're on the same page so far (although you've presented the 
problem more eloquently).

 ("<=" on Booleans is actually implication.)

(Cool!)

 That test will fail with NaNs and should be part of isSorted, 
 sort etc.

OK, but which a, b and c will be checked? Taking all adjacent 
triples will not work with two adjacent NaNs.

 We should also check such as:

 assert(!less(a, a));
 assert(less(a, b) <= !less(b, a));

Again, for which a/b?

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 11/12/13 12:45 PM, Vladimir Panteleev wrote:
 assert((equiv(a, b) && equiv(b, c)) <= equiv(a, c));

 OK, we're on the same page so far (although you've presented the problem
 more eloquently).

 ("<=" on Booleans is actually implication.)

 (Cool!)

(... the disadvantage being b is evaluated even if a is false. 
Shouldn't; false implies everything.)

 That test will fail with NaNs and should be part of isSorted, sort etc.

 OK, but which a, b and c will be checked? Taking all adjacent triples
 will not work with two adjacent NaNs.

We can make that work if we insert the tests at the end of a run of 
equivalent values. That would still miss other cases though in isSorted 
(I think sort() can actually be much more thorough there). The point 
here is that we should work together on an innovative solution. Getting 
bogged in the "there's a problem with the language here" mindset 
prevents the forming of good ideas.

 We should also check such as:

 assert(!less(a, a));
 assert(less(a, b) <= !less(b, a));

 Again, for which a/b?

In the isSorted case, for all adjacent values inspected. For sort, 
assertions can be added after each less() that does work.


Andrei

"Vladimir Panteleev" <vladimir thecybershadow.net> writes:

On Tuesday, 12 November 2013 at 21:15:39 UTC, Andrei Alexandrescu 
wrote:
 We can make that work if we insert the tests at the end of a 
 run of equivalent values.

I've thought about this as well, but then there are cases like...

[4, 5, NaN, 3, NaN, 5, 6]

"5, NaN, 3, NaN, 5" is a run of equivalent values as long as 
neighboring pairs are concerned.

 The point here is that we should work together on an innovative 
 solution. Getting bogged in the "there's a problem with the 
 language here" mindset prevents the forming of good ideas.

Agreed.

"monarch_dodra" <monarchdodra gmail.com> writes:

On Tuesday, 12 November 2013 at 22:17:10 UTC, Vladimir Panteleev
wrote:
 On Tuesday, 12 November 2013 at 21:15:39 UTC, Andrei 
 Alexandrescu wrote:
 We can make that work if we insert the tests at the end of a 
 run of equivalent values.

 I've thought about this as well, but then there are cases 
 like...

 [4, 5, NaN, 3, NaN, 5, 6]

 "5, NaN, 3, NaN, 5" is a run of equivalent values as long as 
 neighboring pairs are concerned.

 The point here is that we should work together on an 
 innovative solution. Getting bogged in the "there's a problem 
 with the language here" mindset prevents the forming of good 
 ideas.

 Agreed.

I may be late to the party, but I think it might be a bit unfair
for sort to be able to reliably "catch" this issue.

Heck, if you call *sort* with NaN, how should it even behave?
Error? Exception?

With AssumeSorted, I think it should throw an Error, if it can
*reliably* do so.

--------

That said, we may have been looking at this problem the wrong
way. Instead of trying to verify the comparison inside the sort,
why not do the check in the comparator itself? It is the
comparator that should "know" how to deal with NaN: Either it
considers it bigger/smaller than everything, and sorts
accordingly, or doesn't know how to deal with it, and throws an
Error/Exception, depending on the users' wishes.

We could make sort/assumeSorted default comparator simply assert
on NaN: This should be able to keep the handling of the NaN
relatively customizable, and cheap in release, without having to
hack into sort/assumeSorted, to do some weird bidirectional
checks.

This keeps the default fast and safe, and if users want more
speed/customization, they can do whatever the heck they like.

My 0.02$

"tn" <no email.com> writes:

On Tuesday, 12 November 2013 at 20:03:37 UTC, Andrei Alexandrescu 
wrote:
 Consider we define equiv(a, b) as (a, b) => !less(a, b) && 
 !less(b, a).

 If at least one of the numbers is NaN, all comparisons return 
 false. That puts NaN in the same equivalence class with all 
 numbers, including numbers that are deemed in distinct 
 equivalence classes. That's where NaNs mess things up, and 
 that's what we need to assert. Consider three numbers a, b, and 
 c. Then the following must pass:

 assert((equiv(a, b) && equiv(b, c)) <= equiv(a, c));

 ("<=" on Booleans is actually implication.)

Shouldn't the implication be to the other direction? Then it 
becomes

assert((equiv(a, b) && equiv(b, c)) => equiv(a, c));

 That test will fail with NaNs and should be part of isSorted, 
 sort etc.

But it requires that the input contains at least three elements. 
And it has to test a lot of possible triples (a,b,c), which I 
think requires at least O(n^2) time. And it does not fail 
consistently whenever the input contains at least one NaN 
(consider an input that contains only NaNs).

 We should also check such as:

 assert(!less(a, a));
 assert(less(a, b) <= !less(b, a));

 These should be checked in sort only; isSorted does not need 
 these.

The latter fails also if a==b. (Unless the direction of the 
implication is again wrong.)

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 11/12/13 1:03 PM, tn wrote:
 On Tuesday, 12 November 2013 at 20:03:37 UTC, Andrei Alexandrescu wrote:
 Consider we define equiv(a, b) as (a, b) => !less(a, b) && !less(b, a).

 If at least one of the numbers is NaN, all comparisons return false.
 That puts NaN in the same equivalence class with all numbers,
 including numbers that are deemed in distinct equivalence classes.
 That's where NaNs mess things up, and that's what we need to assert.
 Consider three numbers a, b, and c. Then the following must pass:

 assert((equiv(a, b) && equiv(b, c)) <= equiv(a, c));

 ("<=" on Booleans is actually implication.)

 Shouldn't the implication be to the other direction? Then it becomes

 assert((equiv(a, b) && equiv(b, c)) => equiv(a, c));

It is in the other direction, but the latter doesn't compile :o). Again, 
it just turns out "a <= b" has the meaning of "a implies b". It's not a 
particularly intuitive way to express it.

 That test will fail with NaNs and should be part of isSorted, sort etc.

 But it requires that the input contains at least three elements. And it
 has to test a lot of possible triples (a,b,c), which I think requires at
 least O(n^2) time. And it does not fail consistently whenever the input
 contains at least one NaN (consider an input that contains only NaNs).

I agree. Ideas?

 We should also check such as:

 assert(!less(a, a));
 assert(less(a, b) <= !less(b, a));

 These should be checked in sort only; isSorted does not need these.

 The latter fails also if a==b. (Unless the direction of the implication
 is again wrong.)

Try it!


Andrei

"tn" <no email.com> writes:

On Tuesday, 12 November 2013 at 21:07:48 UTC, Andrei Alexandrescu 
wrote:
 On 11/12/13 1:03 PM, tn wrote:
 On Tuesday, 12 November 2013 at 20:03:37 UTC, Andrei 
 Alexandrescu wrote:
 Consider we define equiv(a, b) as (a, b) => !less(a, b) && 
 !less(b, a).

 If at least one of the numbers is NaN, all comparisons return 
 false.
 That puts NaN in the same equivalence class with all numbers,
 including numbers that are deemed in distinct equivalence 
 classes.
 That's where NaNs mess things up, and that's what we need to 
 assert.
 Consider three numbers a, b, and c. Then the following must 
 pass:

 assert((equiv(a, b) && equiv(b, c)) <= equiv(a, c));

 ("<=" on Booleans is actually implication.)

 Shouldn't the implication be to the other direction? Then it 
 becomes

 assert((equiv(a, b) && equiv(b, c)) => equiv(a, c));

 It is in the other direction, but the latter doesn't compile 
 :o). Again, it just turns out "a <= b" has the meaning of "a 
 implies b". It's not a particularly intuitive way to express it.

 That test will fail with NaNs and should be part of isSorted, 
 sort etc.

 But it requires that the input contains at least three 
 elements. And it
 has to test a lot of possible triples (a,b,c), which I think 
 requires at
 least O(n^2) time. And it does not fail consistently whenever 
 the input
 contains at least one NaN (consider an input that contains 
 only NaNs).

 I agree. Ideas?

If you want the isSorted function to always fail if the input 
contains NaNs, then I have no other ideas than what I have 
already mentioned. It is just not possible by using only "<" 
comparison. Something more is needed.

The other way would be to define isSorted to return true if and 
only if the _comparable_ elements in the input are sorted (thus 
ignoring possible NaNs in between). This is actually 
implementable with only "<" comparison, but probably requires 
O(n^2) time in the worst case.

"Vladimir Panteleev" <vladimir thecybershadow.net> writes:

On Tuesday, 12 November 2013 at 21:03:03 UTC, tn wrote:
 assert((equiv(a, b) && equiv(b, c)) <= equiv(a, c));

 ("<=" on Booleans is actually implication.)

 Shouldn't the implication be to the other direction? Then it 
 becomes

 assert((equiv(a, b) && equiv(b, c)) => equiv(a, c));

<= as in ≤ (less or equal), not ⇐ (reverse implies). <= can be 
used on booleans as "implies" due to the way it treats booleans 
as integers (true as 1, false as 0).

"tn" <no email.com> writes:

On Tuesday, 12 November 2013 at 21:09:34 UTC, Vladimir Panteleev 
wrote:
 On Tuesday, 12 November 2013 at 21:03:03 UTC, tn wrote:
 assert((equiv(a, b) && equiv(b, c)) <= equiv(a, c));

 ("<=" on Booleans is actually implication.)

 Shouldn't the implication be to the other direction? Then it 
 becomes

 assert((equiv(a, b) && equiv(b, c)) => equiv(a, c));

 <= as in ≤ (less or equal), not ⇐ (reverse implies). <= can be 
 used on booleans as "implies" due to the way it treats booleans 
 as integers (true as 1, false as 0).

Thanks for the explanation. I thought it was pseudocode. That is 
a horribly confusing trick.

"Vladimir Panteleev" <vladimir thecybershadow.net> writes:

On Tuesday, 12 November 2013 at 20:03:37 UTC, Andrei Alexandrescu 
wrote:
 2) Improve documentation and visibility of this problem. For 
 example,
 add this to the documentation of sort:

 "The predicate must be transitive (`a<b && b<c` implies `a<c`) 
 in order
 for `sort` to behave properly - otherwise, the program may 
 fail on
 certain inputs (but not others) when not compiled in release 
 mode. Note
 that `a<b` is not transitive for floating points, because the 
 expression
 will always be `false` when either `a` or `b` is `NaN`."

 Great idea, just file an enh request or just write the pull 
 request.

https://github.com/D-Programming-Language/phobos/pull/1691