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.

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

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

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.

> 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.

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.

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?

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.

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)").

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