Add Ord Laws to next Haskell Report

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
47 messages Options
123
Reply | Threaded
Open this post in threaded view
|

Re: Add Ord Laws to next Haskell Report

Merijn Verstraaten

> On 7 Feb 2019, at 22:41, David Feuer <[hidden email]> wrote:
>
> Even if Ord becomes lawful for floating point, there will still be massive problems reasoning about it because the Num instances can't support the ring laws, let alone the ordered ring laws. What should `compare NaN n` be?

Our goal is to make "compare NaN n" impossible to happen. You can only (try) to compare with NaN if you can *get* a NaN value. But IEEE-754 pretty clearly does *NOT* require computations that evaluate to NaN to be represented as values.

"Trap representations" (i.e., anything vaguely exception like) are an acceptable IEEE-754 compliant way of implementing NaN. All the major CPU platforms support trapping floating point exceptions, not many languages make use of this.

> If it's an exception, then the ordering is not total, you can't store NaN in a Set, etc.

I think this argument is without merit. Yes, it would mean you can't store NaN in a Set anymore (because you wouldn't even be able to have a NaN value...). But that's like complaining Int is broken because I can't store "(5 `div` 0)" in a Set. So far everyone seems perfectly ok with the exception raised by division by zero, so why not NaN?

> If it's LT or GT, then you get a total ordering, but a rather weird one. So yeah, you'd be able to store NaN in a Set and have an NaN key in a Map, but then as soon as you start looking at where these are coming from and where they're going, everything goes weird and you need type-specific code anyway.

If we accept value NaN's (as opposed to trapping NaNs) then we can't have Ord anyway, at least not without giving up on IEEE-754 compliance, as IEEE-754 demands "NaN" compares unequal with itself, which breaks any sort of ordering based function (even simple things like sort, as I painfully discovered in Python...)

Cheers,
Merijn

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

signature.asc (891 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Add Ord Laws to next Haskell Report

Carter Schonwald
additionally (for posterity), merjin pointed out to me that we do want x/0 to not be an exception when abs(x)!= 0, because  +/- infinity are perfectly valid and useful mathematical objects

On Thu, Feb 7, 2019 at 5:31 PM Merijn Verstraaten <[hidden email]> wrote:

> On 7 Feb 2019, at 22:41, David Feuer <[hidden email]> wrote:
>
> Even if Ord becomes lawful for floating point, there will still be massive problems reasoning about it because the Num instances can't support the ring laws, let alone the ordered ring laws. What should `compare NaN n` be?

Our goal is to make "compare NaN n" impossible to happen. You can only (try) to compare with NaN if you can *get* a NaN value. But IEEE-754 pretty clearly does *NOT* require computations that evaluate to NaN to be represented as values.

"Trap representations" (i.e., anything vaguely exception like) are an acceptable IEEE-754 compliant way of implementing NaN. All the major CPU platforms support trapping floating point exceptions, not many languages make use of this.

> If it's an exception, then the ordering is not total, you can't store NaN in a Set, etc.

I think this argument is without merit. Yes, it would mean you can't store NaN in a Set anymore (because you wouldn't even be able to have a NaN value...). But that's like complaining Int is broken because I can't store "(5 `div` 0)" in a Set. So far everyone seems perfectly ok with the exception raised by division by zero, so why not NaN?

> If it's LT or GT, then you get a total ordering, but a rather weird one. So yeah, you'd be able to store NaN in a Set and have an NaN key in a Map, but then as soon as you start looking at where these are coming from and where they're going, everything goes weird and you need type-specific code anyway.

If we accept value NaN's (as opposed to trapping NaNs) then we can't have Ord anyway, at least not without giving up on IEEE-754 compliance, as IEEE-754 demands "NaN" compares unequal with itself, which breaks any sort of ordering based function (even simple things like sort, as I painfully discovered in Python...)

Cheers,
Merijn

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add Ord Laws to next Haskell Report

George Wilson
I think we've gotten a bit off-track here. Certainly we have
disagreements about what should be done regarding floating-point
values in GHC over the longer term, but that shouldn't hold up the
report.
I would prefer to see the total order laws added as Daniel suggested,
while documenting that Float and Double have non-lawful instances due
to NaNs. If the handling of doubles is later improved we can simply
delete that line of documentation.

On Fri, 8 Feb 2019 at 08:34, Carter Schonwald
<[hidden email]> wrote:

>
> additionally (for posterity), merjin pointed out to me that we do want x/0 to not be an exception when abs(x)!= 0, because  +/- infinity are perfectly valid and useful mathematical objects
>
> On Thu, Feb 7, 2019 at 5:31 PM Merijn Verstraaten <[hidden email]> wrote:
>>
>>
>> > On 7 Feb 2019, at 22:41, David Feuer <[hidden email]> wrote:
>> >
>> > Even if Ord becomes lawful for floating point, there will still be massive problems reasoning about it because the Num instances can't support the ring laws, let alone the ordered ring laws. What should `compare NaN n` be?
>>
>> Our goal is to make "compare NaN n" impossible to happen. You can only (try) to compare with NaN if you can *get* a NaN value. But IEEE-754 pretty clearly does *NOT* require computations that evaluate to NaN to be represented as values.
>>
>> "Trap representations" (i.e., anything vaguely exception like) are an acceptable IEEE-754 compliant way of implementing NaN. All the major CPU platforms support trapping floating point exceptions, not many languages make use of this.
>>
>> > If it's an exception, then the ordering is not total, you can't store NaN in a Set, etc.
>>
>> I think this argument is without merit. Yes, it would mean you can't store NaN in a Set anymore (because you wouldn't even be able to have a NaN value...). But that's like complaining Int is broken because I can't store "(5 `div` 0)" in a Set. So far everyone seems perfectly ok with the exception raised by division by zero, so why not NaN?
>>
>> > If it's LT or GT, then you get a total ordering, but a rather weird one. So yeah, you'd be able to store NaN in a Set and have an NaN key in a Map, but then as soon as you start looking at where these are coming from and where they're going, everything goes weird and you need type-specific code anyway.
>>
>> If we accept value NaN's (as opposed to trapping NaNs) then we can't have Ord anyway, at least not without giving up on IEEE-754 compliance, as IEEE-754 demands "NaN" compares unequal with itself, which breaks any sort of ordering based function (even simple things like sort, as I painfully discovered in Python...)
>>
>> Cheers,
>> Merijn
>
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add Ord Laws to next Haskell Report

Carter Schonwald
true enough

Another cool thing that was pointed out to me, is that for NanFree Floats, the Projective reals (err, floats) with a single infinity become a new type over float/double (subject to how reals and floats) release. (thanks to Wren for that point )

On Thu, Feb 7, 2019 at 5:43 PM George Wilson <[hidden email]> wrote:
I think we've gotten a bit off-track here. Certainly we have
disagreements about what should be done regarding floating-point
values in GHC over the longer term, but that shouldn't hold up the
report.
I would prefer to see the total order laws added as Daniel suggested,
while documenting that Float and Double have non-lawful instances due
to NaNs. If the handling of doubles is later improved we can simply
delete that line of documentation.

On Fri, 8 Feb 2019 at 08:34, Carter Schonwald
<[hidden email]> wrote:
>
> additionally (for posterity), merjin pointed out to me that we do want x/0 to not be an exception when abs(x)!= 0, because  +/- infinity are perfectly valid and useful mathematical objects
>
> On Thu, Feb 7, 2019 at 5:31 PM Merijn Verstraaten <[hidden email]> wrote:
>>
>>
>> > On 7 Feb 2019, at 22:41, David Feuer <[hidden email]> wrote:
>> >
>> > Even if Ord becomes lawful for floating point, there will still be massive problems reasoning about it because the Num instances can't support the ring laws, let alone the ordered ring laws. What should `compare NaN n` be?
>>
>> Our goal is to make "compare NaN n" impossible to happen. You can only (try) to compare with NaN if you can *get* a NaN value. But IEEE-754 pretty clearly does *NOT* require computations that evaluate to NaN to be represented as values.
>>
>> "Trap representations" (i.e., anything vaguely exception like) are an acceptable IEEE-754 compliant way of implementing NaN. All the major CPU platforms support trapping floating point exceptions, not many languages make use of this.
>>
>> > If it's an exception, then the ordering is not total, you can't store NaN in a Set, etc.
>>
>> I think this argument is without merit. Yes, it would mean you can't store NaN in a Set anymore (because you wouldn't even be able to have a NaN value...). But that's like complaining Int is broken because I can't store "(5 `div` 0)" in a Set. So far everyone seems perfectly ok with the exception raised by division by zero, so why not NaN?
>>
>> > If it's LT or GT, then you get a total ordering, but a rather weird one. So yeah, you'd be able to store NaN in a Set and have an NaN key in a Map, but then as soon as you start looking at where these are coming from and where they're going, everything goes weird and you need type-specific code anyway.
>>
>> If we accept value NaN's (as opposed to trapping NaNs) then we can't have Ord anyway, at least not without giving up on IEEE-754 compliance, as IEEE-754 demands "NaN" compares unequal with itself, which breaks any sort of ordering based function (even simple things like sort, as I painfully discovered in Python...)
>>
>> Cheers,
>> Merijn
>
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add Ord Laws to next Haskell Report

Henning Thielemann
In reply to this post by Andrew Butterfield-2

On Thu, 7 Feb 2019, Andrew Butterfield wrote:

> Imagine trying to define the obvious partial ordering on sets - i.e.
> subset-or-equal using the Ord class. What should be the result, for
> Instance Ord (Set Int) of
>
> compare (fromList [1]) (fromList [2])    or  fromList [2] <= fromList [1] ?

Partial ordering means to me that the comparison function is partial.
I.e. fromList [2] <= fromList [1] would be "undefined".
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add Ord Laws to next Haskell Report

chessai .
In reply to this post by George Wilson
Yes, quite. This is only about clarifications to the report. All this other stuff seems mostly tangential, and should probably be another thread.

On Thu, Feb 7, 2019, 5:44 PM George Wilson <[hidden email] wrote:
I think we've gotten a bit off-track here. Certainly we have
disagreements about what should be done regarding floating-point
values in GHC over the longer term, but that shouldn't hold up the
report.
I would prefer to see the total order laws added as Daniel suggested,
while documenting that Float and Double have non-lawful instances due
to NaNs. If the handling of doubles is later improved we can simply
delete that line of documentation.

On Fri, 8 Feb 2019 at 08:34, Carter Schonwald
<[hidden email]> wrote:
>
> additionally (for posterity), merjin pointed out to me that we do want x/0 to not be an exception when abs(x)!= 0, because  +/- infinity are perfectly valid and useful mathematical objects
>
> On Thu, Feb 7, 2019 at 5:31 PM Merijn Verstraaten <[hidden email]> wrote:
>>
>>
>> > On 7 Feb 2019, at 22:41, David Feuer <[hidden email]> wrote:
>> >
>> > Even if Ord becomes lawful for floating point, there will still be massive problems reasoning about it because the Num instances can't support the ring laws, let alone the ordered ring laws. What should `compare NaN n` be?
>>
>> Our goal is to make "compare NaN n" impossible to happen. You can only (try) to compare with NaN if you can *get* a NaN value. But IEEE-754 pretty clearly does *NOT* require computations that evaluate to NaN to be represented as values.
>>
>> "Trap representations" (i.e., anything vaguely exception like) are an acceptable IEEE-754 compliant way of implementing NaN. All the major CPU platforms support trapping floating point exceptions, not many languages make use of this.
>>
>> > If it's an exception, then the ordering is not total, you can't store NaN in a Set, etc.
>>
>> I think this argument is without merit. Yes, it would mean you can't store NaN in a Set anymore (because you wouldn't even be able to have a NaN value...). But that's like complaining Int is broken because I can't store "(5 `div` 0)" in a Set. So far everyone seems perfectly ok with the exception raised by division by zero, so why not NaN?
>>
>> > If it's LT or GT, then you get a total ordering, but a rather weird one. So yeah, you'd be able to store NaN in a Set and have an NaN key in a Map, but then as soon as you start looking at where these are coming from and where they're going, everything goes weird and you need type-specific code anyway.
>>
>> If we accept value NaN's (as opposed to trapping NaNs) then we can't have Ord anyway, at least not without giving up on IEEE-754 compliance, as IEEE-754 demands "NaN" compares unequal with itself, which breaks any sort of ordering based function (even simple things like sort, as I painfully discovered in Python...)
>>
>> Cheers,
>> Merijn
>
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add Ord Laws to next Haskell Report

Oliver Charles-3
In reply to this post by Henning Thielemann
On Fri, 8 Feb 2019, 12:20 am Henning Thielemann, <[hidden email]> wrote:

On Thu, 7 Feb 2019, Andrew Butterfield wrote:

> Imagine trying to define the obvious partial ordering on sets - i.e.
> subset-or-equal using the Ord class. What should be the result, for
> Instance Ord (Set Int) of
>
> compare (fromList [1]) (fromList [2])    or  fromList [2] <= fromList [1] ?

Partial ordering means to me that the comparison function is partial.
I.e. fromList [2] <= fromList [1] would be "undefined".__________________

Oh heavens no! It's very useful to ask whether two elements are comparable, that's  a nightmare with this approach.
_____________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add Ord Laws to next Haskell Report

Henning Thielemann

On Fri, 8 Feb 2019, Oliver Charles wrote:

> On Fri, 8 Feb 2019, 12:20 am Henning Thielemann, <[hidden email]> wrote:
>
>       On Thu, 7 Feb 2019, Andrew Butterfield wrote:
>
>       > Imagine trying to define the obvious partial ordering on sets - i.e.
>       > subset-or-equal using the Ord class. What should be the result, for
>       > Instance Ord (Set Int) of
>       >
>       > compare (fromList [1]) (fromList [2])    or  fromList [2] <= fromList [1] ?
>
>       Partial ordering means to me that the comparison function is partial.
>       I.e. fromList [2] <= fromList [1] would be "undefined".__________________
>
>
> Oh heavens no! It's very useful to ask whether two elements are comparable, that's  a nightmare with this
> approach.
With the signature of 'compare' we can hardly do it better. That's why it
is certainly better to leave Ord for total orderings and define

class PartialOrd a where
    maybeCompare :: a -> a -> Maybe Ordering
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add Ord Laws to next Haskell Report

Sven Panne-2
In reply to this post by Merijn Verstraaten
Am Do., 7. Feb. 2019 um 23:31 Uhr schrieb Merijn Verstraaten <[hidden email]>:
Our goal is to make "compare NaN n" impossible to happen. [...]

Well, what is supposed to happen then when you *do* see a NaN, e.g. one produced from a foreign call? You *will* see NaNs in Haskell if you interact with other languages, most of them take a far less religious approach to floating points calculations.

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add Ord Laws to next Haskell Report

Oliver Charles-3
In reply to this post by Henning Thielemann
On Fri, 8 Feb 2019, 9:54 am Henning Thielemann, <[hidden email]> wrote:
With the signature of 'compare' we can hardly do it better. That's why it
is certainly better to leave Ord for total orderings and define

class PartialOrd a where
    maybeCompare :: a -> a -> Maybe Ordering

Yes, precisely. For a moment I thought you were suggesting we should use Ord for partial orders.

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add Ord Laws to next Haskell Report

Merijn Verstraaten
In reply to this post by Sven Panne-2


> On 8 Feb 2019, at 10:57, Sven Panne <[hidden email]> wrote:
>
> Am Do., 7. Feb. 2019 um 23:31 Uhr schrieb Merijn Verstraaten <[hidden email]>:
> Our goal is to make "compare NaN n" impossible to happen. [...]
>
> Well, what is supposed to happen then when you *do* see a NaN, e.g. one produced from a foreign call? You *will* see NaNs in Haskell if you interact with other languages, most of them take a far less religious approach to floating points calculations.

This is not true. As Carter pointed out we can setup the CPU to trap NaNs *even in foreign calls*. So, in theory we CAN rule this out safely. Doing this we can simply convert the trap into an exception at the FFI boundary.

Now, there are cases were this is problematic, so as said before we will probably need to allow people to optionally switch on 'value NaNs', because the foreign code isn't exception safe or for other reasons, but this is manageable. Via, for example having an annotation on foreign imports whether you want to trap or not.

In the scenario where someone switches to value NaNs, we are *still* not worse off than we are now. The things you suggest already happen *now*, so the only thing we're advocating is making it possible to have more sane behaviour in the future.

Any IEEE-754 compliant implementation of Double that doesn't use trapping NaN can, by definition, never ever be a sane implementation of Ord. As IEEE-754 *requires* "NaN /= NaN", so equality symmetry doesn't apply to NaNs and there is *no* safe way to sort/order data containing NaNs.

I've run into several nasty issues of trying to sort lists containing NaNs (not just Haskell, also Python and C) and it's *not* just the NaNs that are affected, entire subsequences end up getting sorted wrong based on the comparison with NaN and you end up with completely garbled and unsorted data.

In other words, there are only two ways to get sane behaviour from Double with regards to ordering:

1. Trapping NaN represenation
2. Deviate from IEEE-754 semantics

To me, option 2 is out of the question, it's the one consistent thing across language we have when it comes to floating point. I understand that *always* using trap representation isn't feasible, but allowing people to optionally switch to value NaNs leaves us no worse off than we are *right now*, and per above, there is literally no way to improve the situation wrt value NaNs without sacrificing IEEE-754 compliance.

Cheers,
Merijn

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

signature.asc (849 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Floats, the true ieee next generation Re: Add Ord Laws to next Haskell Report

Carter Schonwald
Thanks for eloquently summarizing , better than I would , what I thought I had laid out. 

Ieee floating point has fantastic hardware support .  May as well be the first real language to actually use it correctly. :)

On Fri, Feb 8, 2019 at 5:21 AM Merijn Verstraaten <[hidden email]> wrote:


> On 8 Feb 2019, at 10:57, Sven Panne <[hidden email]> wrote:
>
> Am Do., 7. Feb. 2019 um 23:31 Uhr schrieb Merijn Verstraaten <[hidden email]>:
> Our goal is to make "compare NaN n" impossible to happen. [...]
>
> Well, what is supposed to happen then when you *do* see a NaN, e.g. one produced from a foreign call? You *will* see NaNs in Haskell if you interact with other languages, most of them take a far less religious approach to floating points calculations.

This is not true. As Carter pointed out we can setup the CPU to trap NaNs *even in foreign calls*. So, in theory we CAN rule this out safely. Doing this we can simply convert the trap into an exception at the FFI boundary.

Now, there are cases were this is problematic, so as said before we will probably need to allow people to optionally switch on 'value NaNs', because the foreign code isn't exception safe or for other reasons, but this is manageable. Via, for example having an annotation on foreign imports whether you want to trap or not.

In the scenario where someone switches to value NaNs, we are *still* not worse off than we are now. The things you suggest already happen *now*, so the only thing we're advocating is making it possible to have more sane behaviour in the future.

Any IEEE-754 compliant implementation of Double that doesn't use trapping NaN can, by definition, never ever be a sane implementation of Ord. As IEEE-754 *requires* "NaN /= NaN", so equality symmetry doesn't apply to NaNs and there is *no* safe way to sort/order data containing NaNs.

I've run into several nasty issues of trying to sort lists containing NaNs (not just Haskell, also Python and C) and it's *not* just the NaNs that are affected, entire subsequences end up getting sorted wrong based on the comparison with NaN and you end up with completely garbled and unsorted data.

In other words, there are only two ways to get sane behaviour from Double with regards to ordering:

1. Trapping NaN represenation
2. Deviate from IEEE-754 semantics

To me, option 2 is out of the question, it's the one consistent thing across language we have when it comes to floating point. I understand that *always* using trap representation isn't feasible, but allowing people to optionally switch to value NaNs leaves us no worse off than we are *right now*, and per above, there is literally no way to improve the situation wrt value NaNs without sacrificing IEEE-754 compliance.

Cheers,
Merijn
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Floats, the true ieee next generation Re: Add Ord Laws to next Haskell Report

Lennart Augustsson
I would *hate* to lose quiet NaNs.  They can be very useful.  But I’d be fine having them as a separate type.

And while we’re at it, why not make Int overflow and underflow cause a trap as well?  With a different type if you want to wrap. 


On Fri, Feb 8, 2019 at 08:34 Carter Schonwald <[hidden email]> wrote:
Thanks for eloquently summarizing , better than I would , what I thought I had laid out. 

Ieee floating point has fantastic hardware support .  May as well be the first real language to actually use it correctly. :)

On Fri, Feb 8, 2019 at 5:21 AM Merijn Verstraaten <[hidden email]> wrote:


> On 8 Feb 2019, at 10:57, Sven Panne <[hidden email]> wrote:
>
> Am Do., 7. Feb. 2019 um 23:31 Uhr schrieb Merijn Verstraaten <[hidden email]>:
> Our goal is to make "compare NaN n" impossible to happen. [...]
>
> Well, what is supposed to happen then when you *do* see a NaN, e.g. one produced from a foreign call? You *will* see NaNs in Haskell if you interact with other languages, most of them take a far less religious approach to floating points calculations.

This is not true. As Carter pointed out we can setup the CPU to trap NaNs *even in foreign calls*. So, in theory we CAN rule this out safely. Doing this we can simply convert the trap into an exception at the FFI boundary.

Now, there are cases were this is problematic, so as said before we will probably need to allow people to optionally switch on 'value NaNs', because the foreign code isn't exception safe or for other reasons, but this is manageable. Via, for example having an annotation on foreign imports whether you want to trap or not.

In the scenario where someone switches to value NaNs, we are *still* not worse off than we are now. The things you suggest already happen *now*, so the only thing we're advocating is making it possible to have more sane behaviour in the future.

Any IEEE-754 compliant implementation of Double that doesn't use trapping NaN can, by definition, never ever be a sane implementation of Ord. As IEEE-754 *requires* "NaN /= NaN", so equality symmetry doesn't apply to NaNs and there is *no* safe way to sort/order data containing NaNs.

I've run into several nasty issues of trying to sort lists containing NaNs (not just Haskell, also Python and C) and it's *not* just the NaNs that are affected, entire subsequences end up getting sorted wrong based on the comparison with NaN and you end up with completely garbled and unsorted data.

In other words, there are only two ways to get sane behaviour from Double with regards to ordering:

1. Trapping NaN represenation
2. Deviate from IEEE-754 semantics

To me, option 2 is out of the question, it's the one consistent thing across language we have when it comes to floating point. I understand that *always* using trap representation isn't feasible, but allowing people to optionally switch to value NaNs leaves us no worse off than we are *right now*, and per above, there is literally no way to improve the situation wrt value NaNs without sacrificing IEEE-754 compliance.

Cheers,
Merijn
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Floats, the true ieee next generation Re: Add Ord Laws to next Haskell Report

David Feuer
No, no, no. Int and Word are *rings*, which let's us apply a ton of mathematical reasoning to their arithmetic. Trapping overflow would throw all that completely out the window. If you want to trap overflow, please use different types!

On Fri, Feb 8, 2019, 2:07 PM Lennart Augustsson <[hidden email] wrote:
I would *hate* to lose quiet NaNs.  They can be very useful.  But I’d be fine having them as a separate type.

And while we’re at it, why not make Int overflow and underflow cause a trap as well?  With a different type if you want to wrap. 


On Fri, Feb 8, 2019 at 08:34 Carter Schonwald <[hidden email]> wrote:
Thanks for eloquently summarizing , better than I would , what I thought I had laid out. 

Ieee floating point has fantastic hardware support .  May as well be the first real language to actually use it correctly. :)

On Fri, Feb 8, 2019 at 5:21 AM Merijn Verstraaten <[hidden email]> wrote:


> On 8 Feb 2019, at 10:57, Sven Panne <[hidden email]> wrote:
>
> Am Do., 7. Feb. 2019 um 23:31 Uhr schrieb Merijn Verstraaten <[hidden email]>:
> Our goal is to make "compare NaN n" impossible to happen. [...]
>
> Well, what is supposed to happen then when you *do* see a NaN, e.g. one produced from a foreign call? You *will* see NaNs in Haskell if you interact with other languages, most of them take a far less religious approach to floating points calculations.

This is not true. As Carter pointed out we can setup the CPU to trap NaNs *even in foreign calls*. So, in theory we CAN rule this out safely. Doing this we can simply convert the trap into an exception at the FFI boundary.

Now, there are cases were this is problematic, so as said before we will probably need to allow people to optionally switch on 'value NaNs', because the foreign code isn't exception safe or for other reasons, but this is manageable. Via, for example having an annotation on foreign imports whether you want to trap or not.

In the scenario where someone switches to value NaNs, we are *still* not worse off than we are now. The things you suggest already happen *now*, so the only thing we're advocating is making it possible to have more sane behaviour in the future.

Any IEEE-754 compliant implementation of Double that doesn't use trapping NaN can, by definition, never ever be a sane implementation of Ord. As IEEE-754 *requires* "NaN /= NaN", so equality symmetry doesn't apply to NaNs and there is *no* safe way to sort/order data containing NaNs.

I've run into several nasty issues of trying to sort lists containing NaNs (not just Haskell, also Python and C) and it's *not* just the NaNs that are affected, entire subsequences end up getting sorted wrong based on the comparison with NaN and you end up with completely garbled and unsorted data.

In other words, there are only two ways to get sane behaviour from Double with regards to ordering:

1. Trapping NaN represenation
2. Deviate from IEEE-754 semantics

To me, option 2 is out of the question, it's the one consistent thing across language we have when it comes to floating point. I understand that *always* using trap representation isn't feasible, but allowing people to optionally switch to value NaNs leaves us no worse off than we are *right now*, and per above, there is literally no way to improve the situation wrt value NaNs without sacrificing IEEE-754 compliance.

Cheers,
Merijn
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Floats, the true ieee next generation Re: Add Ord Laws to next Haskell Report

Carter Schonwald
In reply to this post by Lennart Augustsson
I absolutely agree. Before any user visible stuff happens the first step would be rts support for better managing floating point flags / rounding mode / trap bits. 

Could you list some contexts / examples where you want quiet or signaling nans respectively?  The more examples written down and shared the better! :)

On Fri, Feb 8, 2019 at 2:07 PM Lennart Augustsson <[hidden email]> wrote:
I would *hate* to lose quiet NaNs.  They can be very useful.  But I’d be fine having them as a separate type.

And while we’re at it, why not make Int overflow and underflow cause a trap as well?  With a different type if you want to wrap. 


On Fri, Feb 8, 2019 at 08:34 Carter Schonwald <[hidden email]> wrote:
Thanks for eloquently summarizing , better than I would , what I thought I had laid out. 

Ieee floating point has fantastic hardware support .  May as well be the first real language to actually use it correctly. :)

On Fri, Feb 8, 2019 at 5:21 AM Merijn Verstraaten <[hidden email]> wrote:


> On 8 Feb 2019, at 10:57, Sven Panne <[hidden email]> wrote:
>
> Am Do., 7. Feb. 2019 um 23:31 Uhr schrieb Merijn Verstraaten <[hidden email]>:
> Our goal is to make "compare NaN n" impossible to happen. [...]
>
> Well, what is supposed to happen then when you *do* see a NaN, e.g. one produced from a foreign call? You *will* see NaNs in Haskell if you interact with other languages, most of them take a far less religious approach to floating points calculations.

This is not true. As Carter pointed out we can setup the CPU to trap NaNs *even in foreign calls*. So, in theory we CAN rule this out safely. Doing this we can simply convert the trap into an exception at the FFI boundary.

Now, there are cases were this is problematic, so as said before we will probably need to allow people to optionally switch on 'value NaNs', because the foreign code isn't exception safe or for other reasons, but this is manageable. Via, for example having an annotation on foreign imports whether you want to trap or not.

In the scenario where someone switches to value NaNs, we are *still* not worse off than we are now. The things you suggest already happen *now*, so the only thing we're advocating is making it possible to have more sane behaviour in the future.

Any IEEE-754 compliant implementation of Double that doesn't use trapping NaN can, by definition, never ever be a sane implementation of Ord. As IEEE-754 *requires* "NaN /= NaN", so equality symmetry doesn't apply to NaNs and there is *no* safe way to sort/order data containing NaNs.

I've run into several nasty issues of trying to sort lists containing NaNs (not just Haskell, also Python and C) and it's *not* just the NaNs that are affected, entire subsequences end up getting sorted wrong based on the comparison with NaN and you end up with completely garbled and unsorted data.

In other words, there are only two ways to get sane behaviour from Double with regards to ordering:

1. Trapping NaN represenation
2. Deviate from IEEE-754 semantics

To me, option 2 is out of the question, it's the one consistent thing across language we have when it comes to floating point. I understand that *always* using trap representation isn't feasible, but allowing people to optionally switch to value NaNs leaves us no worse off than we are *right now*, and per above, there is literally no way to improve the situation wrt value NaNs without sacrificing IEEE-754 compliance.

Cheers,
Merijn
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Floats, the true ieee next generation Re: Add Ord Laws to next Haskell Report

Carter Schonwald
In reply to this post by David Feuer
I’m not sure if they currently have full ring structure , but  I do agree that trapping and non trapping int and word are useful. 

Simple example where all the finite signed ints work wrong today : 

There’s no proper additive inverse for minBound :: int 

Likewise , what’s our current definition of negate on finite word types?

On Fri, Feb 8, 2019 at 2:12 PM David Feuer <[hidden email]> wrote:
No, no, no. Int and Word are *rings*, which let's us apply a ton of mathematical reasoning to their arithmetic. Trapping overflow would throw all that completely out the window. If you want to trap overflow, please use different types!

On Fri, Feb 8, 2019, 2:07 PM Lennart Augustsson <[hidden email] wrote:
I would *hate* to lose quiet NaNs.  They can be very useful.  But I’d be fine having them as a separate type.

And while we’re at it, why not make Int overflow and underflow cause a trap as well?  With a different type if you want to wrap. 


On Fri, Feb 8, 2019 at 08:34 Carter Schonwald <[hidden email]> wrote:
Thanks for eloquently summarizing , better than I would , what I thought I had laid out. 

Ieee floating point has fantastic hardware support .  May as well be the first real language to actually use it correctly. :)

On Fri, Feb 8, 2019 at 5:21 AM Merijn Verstraaten <[hidden email]> wrote:


> On 8 Feb 2019, at 10:57, Sven Panne <[hidden email]> wrote:
>
> Am Do., 7. Feb. 2019 um 23:31 Uhr schrieb Merijn Verstraaten <[hidden email]>:
> Our goal is to make "compare NaN n" impossible to happen. [...]
>
> Well, what is supposed to happen then when you *do* see a NaN, e.g. one produced from a foreign call? You *will* see NaNs in Haskell if you interact with other languages, most of them take a far less religious approach to floating points calculations.

This is not true. As Carter pointed out we can setup the CPU to trap NaNs *even in foreign calls*. So, in theory we CAN rule this out safely. Doing this we can simply convert the trap into an exception at the FFI boundary.

Now, there are cases were this is problematic, so as said before we will probably need to allow people to optionally switch on 'value NaNs', because the foreign code isn't exception safe or for other reasons, but this is manageable. Via, for example having an annotation on foreign imports whether you want to trap or not.

In the scenario where someone switches to value NaNs, we are *still* not worse off than we are now. The things you suggest already happen *now*, so the only thing we're advocating is making it possible to have more sane behaviour in the future.

Any IEEE-754 compliant implementation of Double that doesn't use trapping NaN can, by definition, never ever be a sane implementation of Ord. As IEEE-754 *requires* "NaN /= NaN", so equality symmetry doesn't apply to NaNs and there is *no* safe way to sort/order data containing NaNs.

I've run into several nasty issues of trying to sort lists containing NaNs (not just Haskell, also Python and C) and it's *not* just the NaNs that are affected, entire subsequences end up getting sorted wrong based on the comparison with NaN and you end up with completely garbled and unsorted data.

In other words, there are only two ways to get sane behaviour from Double with regards to ordering:

1. Trapping NaN represenation
2. Deviate from IEEE-754 semantics

To me, option 2 is out of the question, it's the one consistent thing across language we have when it comes to floating point. I understand that *always* using trap representation isn't feasible, but allowing people to optionally switch to value NaNs leaves us no worse off than we are *right now*, and per above, there is literally no way to improve the situation wrt value NaNs without sacrificing IEEE-754 compliance.

Cheers,
Merijn
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Floats, the true ieee next generation Re: Add Ord Laws to next Haskell Report

Vanessa McHale

Most of the arguments for making them rings feel kind of pedantic, in any case. I can't think of a time I've ever used actual ring theory to reason about Ints/Words.

On 2/8/19 1:27 PM, Carter Schonwald wrote:
I’m not sure if they currently have full ring structure , but  I do agree that trapping and non trapping int and word are useful. 

Simple example where all the finite signed ints work wrong today : 

There’s no proper additive inverse for minBound :: int 

Likewise , what’s our current definition of negate on finite word types?

On Fri, Feb 8, 2019 at 2:12 PM David Feuer <[hidden email]> wrote:
No, no, no. Int and Word are *rings*, which let's us apply a ton of mathematical reasoning to their arithmetic. Trapping overflow would throw all that completely out the window. If you want to trap overflow, please use different types!

On Fri, Feb 8, 2019, 2:07 PM Lennart Augustsson <[hidden email] wrote:
I would *hate* to lose quiet NaNs.  They can be very useful.  But I’d be fine having them as a separate type.

And while we’re at it, why not make Int overflow and underflow cause a trap as well?  With a different type if you want to wrap. 


On Fri, Feb 8, 2019 at 08:34 Carter Schonwald <[hidden email]> wrote:
Thanks for eloquently summarizing , better than I would , what I thought I had laid out. 

Ieee floating point has fantastic hardware support .  May as well be the first real language to actually use it correctly. :)

On Fri, Feb 8, 2019 at 5:21 AM Merijn Verstraaten <[hidden email]> wrote:


> On 8 Feb 2019, at 10:57, Sven Panne <[hidden email]> wrote:
>
> Am Do., 7. Feb. 2019 um 23:31 Uhr schrieb Merijn Verstraaten <[hidden email]>:
> Our goal is to make "compare NaN n" impossible to happen. [...]
>
> Well, what is supposed to happen then when you *do* see a NaN, e.g. one produced from a foreign call? You *will* see NaNs in Haskell if you interact with other languages, most of them take a far less religious approach to floating points calculations.

This is not true. As Carter pointed out we can setup the CPU to trap NaNs *even in foreign calls*. So, in theory we CAN rule this out safely. Doing this we can simply convert the trap into an exception at the FFI boundary.

Now, there are cases were this is problematic, so as said before we will probably need to allow people to optionally switch on 'value NaNs', because the foreign code isn't exception safe or for other reasons, but this is manageable. Via, for example having an annotation on foreign imports whether you want to trap or not.

In the scenario where someone switches to value NaNs, we are *still* not worse off than we are now. The things you suggest already happen *now*, so the only thing we're advocating is making it possible to have more sane behaviour in the future.

Any IEEE-754 compliant implementation of Double that doesn't use trapping NaN can, by definition, never ever be a sane implementation of Ord. As IEEE-754 *requires* "NaN /= NaN", so equality symmetry doesn't apply to NaNs and there is *no* safe way to sort/order data containing NaNs.

I've run into several nasty issues of trying to sort lists containing NaNs (not just Haskell, also Python and C) and it's *not* just the NaNs that are affected, entire subsequences end up getting sorted wrong based on the comparison with NaN and you end up with completely garbled and unsorted data.

In other words, there are only two ways to get sane behaviour from Double with regards to ordering:

1. Trapping NaN represenation
2. Deviate from IEEE-754 semantics

To me, option 2 is out of the question, it's the one consistent thing across language we have when it comes to floating point. I understand that *always* using trap representation isn't feasible, but allowing people to optionally switch to value NaNs leaves us no worse off than we are *right now*, and per above, there is literally no way to improve the situation wrt value NaNs without sacrificing IEEE-754 compliance.

Cheers,
Merijn
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

signature.asc (499 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Floats, the true ieee next generation Re: Add Ord Laws to next Haskell Report

Jens Blanck
In reply to this post by Carter Schonwald
> minBound + minBound :: Int
0
> negate minBound == (minBound :: Int)
True
> 42 + negate 17 :: Word
25

Int and Word are currently rings. What proportion actually uses them as such would be interesting to know but I guess it is very small. I wouldn't dare to reason about Int and Word as rings as there is no guarantee on which ring they are. Int64 and Word64 and so on; yes, those can be reasoned about.

I'd be very happy to see a separate type for signalling integral types. Personally, I'd make them the default choice.

On Fri, 8 Feb 2019 at 19:27, Carter Schonwald <[hidden email]> wrote:
I’m not sure if they currently have full ring structure , but  I do agree that trapping and non trapping int and word are useful. 

Simple example where all the finite signed ints work wrong today : 

There’s no proper additive inverse for minBound :: int 

Likewise , what’s our current definition of negate on finite word types?

On Fri, Feb 8, 2019 at 2:12 PM David Feuer <[hidden email]> wrote:
No, no, no. Int and Word are *rings*, which let's us apply a ton of mathematical reasoning to their arithmetic. Trapping overflow would throw all that completely out the window. If you want to trap overflow, please use different types!

On Fri, Feb 8, 2019, 2:07 PM Lennart Augustsson <[hidden email] wrote:
I would *hate* to lose quiet NaNs.  They can be very useful.  But I’d be fine having them as a separate type.

And while we’re at it, why not make Int overflow and underflow cause a trap as well?  With a different type if you want to wrap. 


On Fri, Feb 8, 2019 at 08:34 Carter Schonwald <[hidden email]> wrote:
Thanks for eloquently summarizing , better than I would , what I thought I had laid out. 

Ieee floating point has fantastic hardware support .  May as well be the first real language to actually use it correctly. :)

On Fri, Feb 8, 2019 at 5:21 AM Merijn Verstraaten <[hidden email]> wrote:


> On 8 Feb 2019, at 10:57, Sven Panne <[hidden email]> wrote:
>
> Am Do., 7. Feb. 2019 um 23:31 Uhr schrieb Merijn Verstraaten <[hidden email]>:
> Our goal is to make "compare NaN n" impossible to happen. [...]
>
> Well, what is supposed to happen then when you *do* see a NaN, e.g. one produced from a foreign call? You *will* see NaNs in Haskell if you interact with other languages, most of them take a far less religious approach to floating points calculations.

This is not true. As Carter pointed out we can setup the CPU to trap NaNs *even in foreign calls*. So, in theory we CAN rule this out safely. Doing this we can simply convert the trap into an exception at the FFI boundary.

Now, there are cases were this is problematic, so as said before we will probably need to allow people to optionally switch on 'value NaNs', because the foreign code isn't exception safe or for other reasons, but this is manageable. Via, for example having an annotation on foreign imports whether you want to trap or not.

In the scenario where someone switches to value NaNs, we are *still* not worse off than we are now. The things you suggest already happen *now*, so the only thing we're advocating is making it possible to have more sane behaviour in the future.

Any IEEE-754 compliant implementation of Double that doesn't use trapping NaN can, by definition, never ever be a sane implementation of Ord. As IEEE-754 *requires* "NaN /= NaN", so equality symmetry doesn't apply to NaNs and there is *no* safe way to sort/order data containing NaNs.

I've run into several nasty issues of trying to sort lists containing NaNs (not just Haskell, also Python and C) and it's *not* just the NaNs that are affected, entire subsequences end up getting sorted wrong based on the comparison with NaN and you end up with completely garbled and unsorted data.

In other words, there are only two ways to get sane behaviour from Double with regards to ordering:

1. Trapping NaN represenation
2. Deviate from IEEE-754 semantics

To me, option 2 is out of the question, it's the one consistent thing across language we have when it comes to floating point. I understand that *always* using trap representation isn't feasible, but allowing people to optionally switch to value NaNs leaves us no worse off than we are *right now*, and per above, there is literally no way to improve the situation wrt value NaNs without sacrificing IEEE-754 compliance.

Cheers,
Merijn
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Floats, the true ieee next generation Re: Add Ord Laws to next Haskell Report

Carter Schonwald
No.  A ring can’t have 2x=0 for x not zero.  Thus int can’t  be 

And by ring I mean an algebraic structure where you have a multiplicative group that doesn’t generate zero from products of nonzero elements ... 

Phrased differently: Int doesn’t have a multiplicative group structure on the nonzero elements. That makes it a pretty nasty ring. Negate on minBound should be an overflow exception so you can have actual sane semantics.  This is an old dead horse with lots of blood written about it. 

https://ghc.haskell.org/trac/ghc/ticket/8695 has some related discussions 


On Fri, Feb 8, 2019 at 2:53 PM Jens Blanck <[hidden email]> wrote:
> minBound + minBound :: Int
0
> negate minBound == (minBound :: Int)
True
> 42 + negate 17 :: Word
25

Int and Word are currently rings. What proportion actually uses them as such would be interesting to know but I guess it is very small. I wouldn't dare to reason about Int and Word as rings as there is no guarantee on which ring they are. Int64 and Word64 and so on; yes, those can be reasoned about.

I'd be very happy to see a separate type for signalling integral types. Personally, I'd make them the default choice.

On Fri, 8 Feb 2019 at 19:27, Carter Schonwald <[hidden email]> wrote:
I’m not sure if they currently have full ring structure , but  I do agree that trapping and non trapping int and word are useful. 

Simple example where all the finite signed ints work wrong today : 

There’s no proper additive inverse for minBound :: int 

Likewise , what’s our current definition of negate on finite word types?

On Fri, Feb 8, 2019 at 2:12 PM David Feuer <[hidden email]> wrote:
No, no, no. Int and Word are *rings*, which let's us apply a ton of mathematical reasoning to their arithmetic. Trapping overflow would throw all that completely out the window. If you want to trap overflow, please use different types!

On Fri, Feb 8, 2019, 2:07 PM Lennart Augustsson <[hidden email] wrote:
I would *hate* to lose quiet NaNs.  They can be very useful.  But I’d be fine having them as a separate type.

And while we’re at it, why not make Int overflow and underflow cause a trap as well?  With a different type if you want to wrap. 


On Fri, Feb 8, 2019 at 08:34 Carter Schonwald <[hidden email]> wrote:
Thanks for eloquently summarizing , better than I would , what I thought I had laid out. 

Ieee floating point has fantastic hardware support .  May as well be the first real language to actually use it correctly. :)

On Fri, Feb 8, 2019 at 5:21 AM Merijn Verstraaten <[hidden email]> wrote:


> On 8 Feb 2019, at 10:57, Sven Panne <[hidden email]> wrote:
>
> Am Do., 7. Feb. 2019 um 23:31 Uhr schrieb Merijn Verstraaten <[hidden email]>:
> Our goal is to make "compare NaN n" impossible to happen. [...]
>
> Well, what is supposed to happen then when you *do* see a NaN, e.g. one produced from a foreign call? You *will* see NaNs in Haskell if you interact with other languages, most of them take a far less religious approach to floating points calculations.

This is not true. As Carter pointed out we can setup the CPU to trap NaNs *even in foreign calls*. So, in theory we CAN rule this out safely. Doing this we can simply convert the trap into an exception at the FFI boundary.

Now, there are cases were this is problematic, so as said before we will probably need to allow people to optionally switch on 'value NaNs', because the foreign code isn't exception safe or for other reasons, but this is manageable. Via, for example having an annotation on foreign imports whether you want to trap or not.

In the scenario where someone switches to value NaNs, we are *still* not worse off than we are now. The things you suggest already happen *now*, so the only thing we're advocating is making it possible to have more sane behaviour in the future.

Any IEEE-754 compliant implementation of Double that doesn't use trapping NaN can, by definition, never ever be a sane implementation of Ord. As IEEE-754 *requires* "NaN /= NaN", so equality symmetry doesn't apply to NaNs and there is *no* safe way to sort/order data containing NaNs.

I've run into several nasty issues of trying to sort lists containing NaNs (not just Haskell, also Python and C) and it's *not* just the NaNs that are affected, entire subsequences end up getting sorted wrong based on the comparison with NaN and you end up with completely garbled and unsorted data.

In other words, there are only two ways to get sane behaviour from Double with regards to ordering:

1. Trapping NaN represenation
2. Deviate from IEEE-754 semantics

To me, option 2 is out of the question, it's the one consistent thing across language we have when it comes to floating point. I understand that *always* using trap representation isn't feasible, but allowing people to optionally switch to value NaNs leaves us no worse off than we are *right now*, and per above, there is literally no way to improve the situation wrt value NaNs without sacrificing IEEE-754 compliance.

Cheers,
Merijn
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Floats, the true ieee next generation Re: Add Ord Laws to next Haskell Report

Carter Schonwald
I think the algebraic property we usually want for nice integer ish things is intergral domain. Which is a stronger property than ring. Pardon the confusion 

On Fri, Feb 8, 2019 at 3:03 PM Carter Schonwald <[hidden email]> wrote:
No.  A ring can’t have 2x=0 for x not zero.  Thus int can’t  be 

And by ring I mean an algebraic structure where you have a multiplicative group that doesn’t generate zero from products of nonzero elements ... 

Phrased differently: Int doesn’t have a multiplicative group structure on the nonzero elements. That makes it a pretty nasty ring. Negate on minBound should be an overflow exception so you can have actual sane semantics.  This is an old dead horse with lots of blood written about it. 

https://ghc.haskell.org/trac/ghc/ticket/8695 has some related discussions 


On Fri, Feb 8, 2019 at 2:53 PM Jens Blanck <[hidden email]> wrote:
> minBound + minBound :: Int
0
> negate minBound == (minBound :: Int)
True
> 42 + negate 17 :: Word
25

Int and Word are currently rings. What proportion actually uses them as such would be interesting to know but I guess it is very small. I wouldn't dare to reason about Int and Word as rings as there is no guarantee on which ring they are. Int64 and Word64 and so on; yes, those can be reasoned about.

I'd be very happy to see a separate type for signalling integral types. Personally, I'd make them the default choice.

On Fri, 8 Feb 2019 at 19:27, Carter Schonwald <[hidden email]> wrote:
I’m not sure if they currently have full ring structure , but  I do agree that trapping and non trapping int and word are useful. 

Simple example where all the finite signed ints work wrong today : 

There’s no proper additive inverse for minBound :: int 

Likewise , what’s our current definition of negate on finite word types?

On Fri, Feb 8, 2019 at 2:12 PM David Feuer <[hidden email]> wrote:
No, no, no. Int and Word are *rings*, which let's us apply a ton of mathematical reasoning to their arithmetic. Trapping overflow would throw all that completely out the window. If you want to trap overflow, please use different types!

On Fri, Feb 8, 2019, 2:07 PM Lennart Augustsson <[hidden email] wrote:
I would *hate* to lose quiet NaNs.  They can be very useful.  But I’d be fine having them as a separate type.

And while we’re at it, why not make Int overflow and underflow cause a trap as well?  With a different type if you want to wrap. 


On Fri, Feb 8, 2019 at 08:34 Carter Schonwald <[hidden email]> wrote:
Thanks for eloquently summarizing , better than I would , what I thought I had laid out. 

Ieee floating point has fantastic hardware support .  May as well be the first real language to actually use it correctly. :)

On Fri, Feb 8, 2019 at 5:21 AM Merijn Verstraaten <[hidden email]> wrote:


> On 8 Feb 2019, at 10:57, Sven Panne <[hidden email]> wrote:
>
> Am Do., 7. Feb. 2019 um 23:31 Uhr schrieb Merijn Verstraaten <[hidden email]>:
> Our goal is to make "compare NaN n" impossible to happen. [...]
>
> Well, what is supposed to happen then when you *do* see a NaN, e.g. one produced from a foreign call? You *will* see NaNs in Haskell if you interact with other languages, most of them take a far less religious approach to floating points calculations.

This is not true. As Carter pointed out we can setup the CPU to trap NaNs *even in foreign calls*. So, in theory we CAN rule this out safely. Doing this we can simply convert the trap into an exception at the FFI boundary.

Now, there are cases were this is problematic, so as said before we will probably need to allow people to optionally switch on 'value NaNs', because the foreign code isn't exception safe or for other reasons, but this is manageable. Via, for example having an annotation on foreign imports whether you want to trap or not.

In the scenario where someone switches to value NaNs, we are *still* not worse off than we are now. The things you suggest already happen *now*, so the only thing we're advocating is making it possible to have more sane behaviour in the future.

Any IEEE-754 compliant implementation of Double that doesn't use trapping NaN can, by definition, never ever be a sane implementation of Ord. As IEEE-754 *requires* "NaN /= NaN", so equality symmetry doesn't apply to NaNs and there is *no* safe way to sort/order data containing NaNs.

I've run into several nasty issues of trying to sort lists containing NaNs (not just Haskell, also Python and C) and it's *not* just the NaNs that are affected, entire subsequences end up getting sorted wrong based on the comparison with NaN and you end up with completely garbled and unsorted data.

In other words, there are only two ways to get sane behaviour from Double with regards to ordering:

1. Trapping NaN represenation
2. Deviate from IEEE-754 semantics

To me, option 2 is out of the question, it's the one consistent thing across language we have when it comes to floating point. I understand that *always* using trap representation isn't feasible, but allowing people to optionally switch to value NaNs leaves us no worse off than we are *right now*, and per above, there is literally no way to improve the situation wrt value NaNs without sacrificing IEEE-754 compliance.

Cheers,
Merijn
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
123