A question about "monad laws"

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

Re: Re: A question about "monad laws"

Richard A. O'Keefe
On 14 Feb 2008, at 6:01 pm, Roman Leshchinskiy wrote:
> I don't understand this. Why use a type which can overflow in the  
> first place? Why not use Integer?

Why is this hard to understand?
Dijkstra's classic "A Discipline of Programming" distinguishes
several kinds of machine.  I'm quoting from memory here.

        A Sufficiently Large Machine is one which can run your program
        to completion giving correct answers all the way.

        An Insufficiently Large Machine is one which can't do that and
        silently goes crazy instead.

        A Hopefully Sufficiently Large Machine is one which *either*
        does what a Sufficiently Large Machine would have *or* reports
        that it couldn't.

The good thing about an SLM is that it always gives you right answers  
(assuming
your program is correct).  The bad thing is that you can't afford it.

The good thing about an ILM is that you can afford it.  The bad thing  
is that
you can't trust it.

The great thing about a HSLM is that you can both trust and afford it.

Presumably the reason for having Int in the language at all is speed.
As people have pointed out several times on this list to my knowledge,
Integer performance is not as good as Int performance, not hardly,
and it is silly to pay that price if I don't actually need it.

The thing about using SafeInt is that I should get the *same* space  
and speed
from SafeInt as I do from Int, or at the very least the same space  
and far
better speed than Integer, while at the same time EITHER the results  
are the
results I would have got using Integer *OR* the system promises to  
tell me
about it, so that I *know* there is a problem.

SafeInt is what you should use when you *THINK* your results should  
all fit
in a machine int but aren't perfectly sure.  (And this is nearly all  
the time.)

Int is what you should use when you don't give a damn what the  
results are as
long as you get them fast.  (But in that case, why not use C or  
assembler?)

>
>>> You just have to check for exceptional conditions.
>> Why should it be *MY* job to check for exceptional conditions?
>
> It shouldn't unless you use a type whose contract specifies that  
> it's your job to check for them. Which is the case for Int, Float  
> and Double.

Wrong.  You're confusing two things here.  One is Float and Double,
where we get in serious trouble WITHOUT ANY EXCEPTIONAL CONDITIONS IN  
SIGHT.
The other is Int overflow.  There may also be an equivocation on  
'checking'.
When was the last time you proved that a large program would not  
incur an
integer overflow?  When was the last time you proved that a library  
package
would not incur integer overflow provided it was called in accord  
with its
contract.  When was the last time you even *found* a sufficiently  
informative
contract in someone else's Haskell code?

The checking I am talking about is done by the hardware at machine  
speeds
and provides *certainty* that overflow did not occur.

> It's not the case for Integer and Rational.
>
>> If you think that, you do not understand floating point.
>> x+(y+z) == (x+y)+z fails even though there is nothing exceptional  
>> about
>> any of the operands or any of the results.
>
> For all practical purposes, the semantics of (==) is not well  
> defined for floating point numbers.

With respect to IEEE arithmetic, wrong.

> That's one of the first things I used to teach my students about  
> floats: *never* compare them for equality.

That's one of the warning signs I watch out for.  "Never compare  
floats for
equality" is a sure sign of someone who thinks they know about floats  
but don't.

> So in my view, your example doesn't fail, it's undefined. That  
> Haskell provides (==) for floats is unfortunate.

The operation is well defined and required by the IEEE standard.
>

> If they used (==) for floats, then they simply didn't know what  
> they were doing. The fact that a program is commercial doesn't mean  
> it's any good.

Er, we weren't talking about (==) for floats; I don't know where you  
got that.
I never said it was any good; quite the opposite.  My point is that  
bad software
escaped into the commercial market because floating point doesn't  
follow the
laws people expect it to.

>
>>> I guess it trapped on creating denormals. But again, presumably  
>>> the reason the student used doubles here was because he wanted  
>>> his program to be fast. Had he read just a little bit about  
>>> floating point, he would have known that it is *not* fast under  
>>> certain conditions.
>> Well, no.  Close, but no cigar.
>> (a) It wasn't denormals, it was underflow.
>
> "Creating denormals" and underflow are equivalent.

No they are not.  Underflow in this sense occurs when the result is too
small to be even a denormal.  (The IEEE exceptions Underflow and Inexact
are not the same.  Creating denormals is likely to trigger Inexact but
should not trigger Underflow.  I am talking only about a condition that
triggered Underflow.)

> Denormals are created as a result of underflow. A denormalised  
> number is smaller than any representable normal number. When the  
> result of an operation is too small to be represented by a normal  
> number, IEEE arithmetic will either trap or return a denormal,  
> depending on whether underflow is masked or not.

No, we're talking about a situation where returning a denormal is not  
an option
because there is no suitable denormal.  This is underflow.

>
>> (b) The fact underflow was handled by trapping to the operating  
>> system,
>>     which then completed the operating by writing a 0.0 to the  
>> appropriate
>>     register, is *NOT* a universal property of floating point, and  
>> is *NOT*
>>     a universal property of IEEE floating point.  It's a fact  
>> about that
>>     particular architecture, and I happened to have the manual and  
>> he didn't.
>
> IIRC, underflow is a standard IEEE exception.

Underflow is indeed a standard IEEE exception.  Like other standard IEEE
exceptions, it is *disabled by default*.  In this case, the hardware
delivered the exception *to the operating system*, but the operating
system did not deliver it to the *user code*.  It is the *combination*
of hardware and operating system that conforms to the IEEE standard  
(or not).
So we are talking about a situation where the only legal IEEE  
outcomes are
"return 0.0" or "raise the Underflow exception" and where raising an  
exception
*in the user code* wasn't allowed and didn't happen.

The hardware is allowed to trap to the operating system any time it  
feels
like, for any reason (like 'this model doesn't support the SQRTD  
instruction')
or none (hey, it's a Friday, I think I'll generate traps).

The knowledge I had, and the student lacked, was *not* knowledge  
about an
interface (the IEEE specification) but about an implementation.  
There's a
lot of Haskell code out there with no performance guides in the  
documentation...

> I'm not. But progammers I consider competent for this particular  
> task know how to use floating point. Your student didn't but that's  
> ok for a student.

Wrong.  He *did* know "how to use floating point", and his code would  
have
run at the expected speed on other hardware.  It gave pretty good  
answers.
What he didn't know was how one
particular machine struck the balance between hardware and software.

I wonder just how many programmers these days think Double.(*) is  
_always_
a cheap hardware instruction?

Returning to our theme:  the programmer expectation here is "a simple  
cost
model."  Violating that expectation led to a program with a huge  
unexpected
cost problem.  In the same way, violating other programmer  
expectations is
likely to lead to unexpected correctness problems.




_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Re: A question about "monad laws"

Bugzilla from jed@59a2.org
In reply to this post by Roman Leshchinskiy
On 14 Feb 2008, [hidden email] wrote:

>
> [hidden email] wrote:
> > Trialog:
> > Roman Leshchinskiy writes:
> >> Richard A. O'Keefe wrote:
> >
> >>> [hidden email] wrote:
> >>>> Would you say that *no* typical floating-point software is reliable?
> >>>
> >>> With lots of hedging and clutching of protective amulets around the
> >>> word "reliable", of course not.  What I *am* saying is that
> >>> (a) it's exceptionally HARD to make reliable because although the operations
> >>>  are well defined and arguably reasonable they do NOT obey the laws that
> >>>     school and university mathematics teach us to expect them to obey
> >>
> >> Ints do not obey those laws, either. It is not exceptionally hard to write
> >> reliable software using ints. You just have to check for exceptional
> >> conditions. That's also the case for floating point.
> >> That said, I suspect that 90% of programs that use float and double would be
> >> much better off using something else. The only reason to use floating point
> >> is performance.
> >
> > I have a bit different perspective...
> > First, when I see the advice "use something else", I always ask "what",
> > and I get an answer very, very rarely... Well? What do you propose?
>
> For Haskell, Rational seems like a good choice. The fact that the standard
> requires defaulting to Double is quite unfortunate and inconsistent, IMO; the
> default should be Rational. Float and Double shouldn't even be in scope without
> an explicit import. There really is no good reason to use them unless you are
> writing a binding to existing libraries or really need the performance.
Until you need to evaluate a transcendental function.  Floating point
numbers are remarkably well-behaved in the following sense.

  Fundamental Axiom of Floating Point Arithmetic (Trefethen & Bau, 1997)
    For all x,y in F, there exists e with |e| <= e_machine such that
        x <*> y = (x * y) (1 + e)
    where F is the set of real numbers in a particular floating point
    representation, <*> represents any hardware arithmetic operation
    and * is the corresponding exact operation.

This is satisfied by nearly all floating point implementations, with
somewhat stronger conditions for IEEE.  It is easily extended to complex
arithmetic, perhaps after scaling e_machine by a small factor.  This
single axiom is sufficient for all stability (with regard to rounding
error) results of numerical algorithms.  Double precision has 15
significant digits.  It is a very rare physical quantity that can be
measured to 10 significant digits and this is unlikely to change in the
next 100 years.  It is a rare algorithm for which floating point
arithmetic is a problem.  Occasionally we must make decisions, such as
choosing which way to project during Householder QR, so that rounding
error is not a problem.  Unfortunately, Gaussian Elimination is an
important (only because it happens to be fast) algorithm which suffers
From rounding error.  Since there are well conditioned matrices for
which Gaussian Elimination fails spectacularly despite pivoting, many
people believe that rounding error is a major part of numerical
analysis.  This is absolutely not the case; it is less than 10% of the
field.

Of course, if you are not trying to represent arbitrary real numbers,
using floating point may be a mistake.  Converting between integer or
rational representations and floating point requires careful attention.
As long as you stay in floating point, it is almost never a problem.
Remember that it is not possible to implement exact real arithmetic so
that equality is decidable.  We should take this as a sign that equality
for floating point arithmetic is dangerous to rely upon.

Floating point is extremely useful and I think it would be a mistake to
remove it from the Prelude.  One thing I would like to see is the Enum
instances removed.

Jed

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

attachment0 (202 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Re: A question about "monad laws"

Roman Leshchinskiy
In reply to this post by Richard A. O'Keefe
Richard A. O'Keefe wrote:

> On 14 Feb 2008, at 6:01 pm, Roman Leshchinskiy wrote:
>> I don't understand this. Why use a type which can overflow in the
>> first place? Why not use Integer?
>
> [...]
>
> Presumably the reason for having Int in the language at all is speed.
> As people have pointed out several times on this list to my knowledge,
> Integer performance is not as good as Int performance, not hardly,
> and it is silly to pay that price if I don't actually need it.

Do I understand correctly that you advocate using overflowing ints (even
if they signal overflow) even if Integers are fast enough for a
particular program? I strongly disagree with this. It's premature
optimisation of the worst kind - trading correctness for unneeded
performance.

> SafeInt is what you should use when you *THINK* your results should all fit
> in a machine int but aren't perfectly sure.  (And this is nearly all the
> time.)

Again, I strongly disagree. You should use Integer unless your program
is too slow and profiling shows that Integer is the culprit. If and only
if that is the case should you think about alternatives. That said, I
doubt that your SafeInt would be significantly faster than Integer.

>>>> You just have to check for exceptional conditions.
>>> Why should it be *MY* job to check for exceptional conditions?
>>
>> It shouldn't unless you use a type whose contract specifies that it's
>> your job to check for them. Which is the case for Int, Float and Double.
>
> Wrong.  You're confusing two things here.  One is Float and Double,
> where we get in serious trouble WITHOUT ANY EXCEPTIONAL CONDITIONS IN
> SIGHT.  The other is Int overflow.

I'm not sure what I'm confusing here, my comment referred specifically
to exceptional conditions which floats provide plenty of. As to getting
in trouble, I don't need floats for that, I manage to do it perfectly
well with any data type including (). Seriously, though, I think we
agree that using floating point numbers correctly isn't trivial, people
who do that should know what they are doing and should best use existing
libraries. I just don't see how floats are special in this regard.

> The checking I am talking about is done by the hardware at machine speeds
> and provides *certainty* that overflow did not occur.

So you advocate using different hardware?

>>> If you think that, you do not understand floating point.
>>> x+(y+z) == (x+y)+z fails even though there is nothing exceptional about
>>> any of the operands or any of the results.
>>
>> For all practical purposes, the semantics of (==) is not well defined
>> for floating point numbers.
>
> With respect to IEEE arithmetic, wrong.

Yes, IEEE does define an operation which is (wrongly, IMO) called
"equality". It's not a particularly useful operation (and it is not
equality), but it does have a defined semantics. However, the semantics
of (==) on floats isn't really defined in Haskell or C, for that matter,
even if you know that the hardware is strictly IEEE conformant.

In general, floating point numbers do not really have a useful notion of
equality. They are approximations, after all, and independently derived
approximations can only be usefully tested for approximate equality. And
yes, x+(y+z) is approximately equal to (x+y)+z for floats. How
approximate depends on the particular values, of course.

>> That's one of the first things I used to teach my students about
>> floats: *never* compare them for equality.
>
> That's one of the warning signs I watch out for.  "Never compare floats for
> equality" is a sure sign of someone who thinks they know about floats
> but don't.

Hmm. Personally, I've never seen an algorithm where comparing for exact
equality was algorithmically necessary. Sometimes (rarely) it is
acceptable but necessary? Do you know of one? On the other hand, there
are a lot of cases where comparing for exact equality is algorithmically
wrong.

As an aside, you might want to try googling for "Never compare floats
for equality". I'm positive some of those people *do* know about floats.

>> "Creating denormals" and underflow are equivalent.
>
> No they are not.  Underflow in this sense occurs when the result is too
> small to be even a denormal.

I'm fairly sure that IEEE underflow occurs when the result cannot be
represented by a *normal* number but I don't have a copy of the
standard. Anyway, it's not important for this discussion, I guess.

> Underflow is indeed a standard IEEE exception.  Like other standard IEEE
> exceptions, it is *disabled by default*.  In this case, the hardware
> delivered the exception *to the operating system*, but the operating
> system did not deliver it to the *user code*.  It is the *combination*
> of hardware and operating system that conforms to the IEEE standard (or
> not).
> So we are talking about a situation where the only legal IEEE outcomes are
> "return 0.0" or "raise the Underflow exception" and where raising an
> exception
> *in the user code* wasn't allowed and didn't happen.

Now I'm curious. I would have guessed that it was an Alpha but that
would behave differently (it would trap on underflow, but only in strict
IEEE mode and only because it actually implemented flush to zero instead
of gradual underflow).

>> I'm not. But progammers I consider competent for this particular task
>> know how to use floating point. Your student didn't but that's ok for
>> a student.
>
> Wrong.  He *did* know "how to use floating point", and his code would have
> run at the expected speed on other hardware.  It gave pretty good answers.

Wrt speed - not necessarily. For instance, x86 is really bad when it
comes to denormals. Have a look at

   http://www.cygnus-software.com/papers/x86andinfinity.html

for instance. So while he knew how to get good results with floating
point, he didn't know how to get good performance. Which, as you say, is
not part of the IEEE standard but which you still have to know if you
use floats.

Roman


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Re: A question about "monad laws"

ajb@spamcop.net
G'day all.

Richard A. O'Keefe wrote:

>> That's one of the warning signs I watch out for.  "Never compare floats for
>> equality" is a sure sign of someone who thinks they know about  
>> floats but don't.

Quoting Roman Leshchinskiy <[hidden email]>:

> Hmm. Personally, I've never seen an algorithm where comparing for exact
> equality was algorithmically necessary.

One trick I've occasionally used is to avoid the need for a discriminated
union of floating point and integer types by just using a floating point
number.

If you ignore bitwise operations and division/remainder, any integer
operation that doesn't cause overflow on 32-bit integers will work just
the same if you use IEEE-754 64-bit floating point numbers instead.
That includes equality.  Moreover, you even get a few more significant
bits of precision.

In these days of fast 64 and 128 bit words, it might not be entirely
moral, but it works.

Cheers,
Andrew Bromage
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: A question about "monad laws"

jerzy.karczmarczuk
In reply to this post by Bugzilla from jed@59a2.org
Jed Brown comments the answer of -

 -- Roman Leshchinskiy who answers my question concerning the replacement
of floating-point numbers:

>> > First, when I see the advice "use something else", I always ask "what",
>> > and I get an answer very, very rarely... Well? What do you propose?

>> For Haskell, Rational seems like a good choice. The fact that the
>> standard requires defaulting to Double is quite unfortunate and
>> inconsistent, IMO; the default should be Rational. Float and Double
>> shouldn't even be in scope without an explicit import. There really
>> is no good reason to use them unless you are
>> writing a binding to existing libraries or really need the performance.

Here Jed Brown says:

> Until you need to evaluate a transcendental function.
...
It would be killing, wouldn't it?...

I would say more. It is known that in randomly taken, usual formulae in
physics, engineering, etc., if you start with rationals, *typically* the
GCD between numerator and denominator will be small, the reductions of
fractions are not very effective. Your rationals explode very fast!
If after some reasonable number of operations you get rationals whose
num/den have millions of digits, the program becomes *completely useless*,
this is not "just" the questions of performance.

Richard O'Keefe said that people speculate about floating-point numbers
without knowing them. Well, nobody is perfect...
I am a bit disturbed by people, who speculate without ever *needing*
fl.p's, and who haven't thus the sensibility. For them this is a kind of
game. Well, it isn't.

R.L. says:

> For all practical purposes, the semantics of (==) is not well defined
> for floating point numbers. That's one of the first things I used to
> teach my students about floats: *never* compare them for equality.
> So in my view, your example doesn't fail, it's undefined.
> That Haskell provides (==) for floats is unfortunate.

I disagree, on practical basis. Floating-point numbers are very well
defined, we know how the mantissa is represented. If the numbers are
normalized, as they should, plenty of low-level iterative algorithms
may use the equality - after some operation - to check that the machine-
precision convergence has been obtained. On the contrary, the verification
that the absolute value between two terms is less than some threshold,
may be arbitrary or dubious.

Jerzy Karczmarczuk


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: A question about "monad laws"

Wilhelm B. Kloke
In reply to this post by ajb@spamcop.net
[hidden email] <[hidden email]> schrieb:

> G'day all.
>
> Richard A. O'Keefe wrote:
>
>> Hmm. Personally, I've never seen an algorithm where comparing for exact
>> equality was algorithmically necessary.
>
> One trick I've occasionally used is to avoid the need for a discriminated
> union of floating point and integer types by just using a floating point
> number.

IMHO it is a perfectly good idea to use the FP processor for integer
computations. You can use the Inexact Trap as Overflow Exception,
a service you don't get from i386 (and most other) hardware for int
operations. Of course your integers are limited to 24bit+sign in
single precision and 54bit+sign in double. In i387 extended precision
you get 64bit+sign.

I would consider a good idea if ghc would provide language support to
this sort of integers.
--
Dipl.-Math. Wilhelm Bernhard Kloke
Institut fuer Arbeitsphysiologie an der Universitaet Dortmund
Ardeystrasse 67, D-44139 Dortmund, Tel. 0231-1084-257
PGP: http://vestein.arb-phys.uni-dortmund.de/~wb/mypublic.key

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Re: A question about "monad laws"

Roman Leshchinskiy
In reply to this post by jerzy.karczmarczuk
[hidden email] wrote:

> Jed Brown comments the answer of -
> -- Roman Leshchinskiy who answers my question concerning the replacement
> of floating-point numbers:
>>> > First, when I see the advice "use something else", I always ask
>>> "what",
>>> > and I get an answer very, very rarely... Well? What do you propose?
>
>>> For Haskell, Rational seems like a good choice. The fact that the
>>> standard requires defaulting to Double is quite unfortunate and
>>> inconsistent, IMO; the default should be Rational. Float and Double
>>> shouldn't even be in scope without an explicit import. There really
>>> is no good reason to use them unless you are
>>> writing a binding to existing libraries or really need the performance.
>
> Here Jed Brown says:
>> Until you need to evaluate a transcendental function.
> ...
> It would be killing, wouldn't it?...

Yes, it would. I was talking about average programs, though, which (I
suspect) don't do numerics and really only need fractions. If you do
numerics, by all means use a data type that supports numerics well. But
even here, and especially in a functional language, IEEE floating point
usually isn't the best choice unless you really need the performance.

You seem to be after a type that can be used to represent non-integer
numbers in next to all problem domains. I don't think such a type
exists. So, as usual, one has to choose a data structure suited to the
problem at hand. IMO, standard floating point is not a good choice for
most problem domains so Float and Double shouldn't be used by default.
Whether Rational is a good default is certainly debatable.

>> For all practical purposes, the semantics of (==) is not well defined
>> for floating point numbers. That's one of the first things I used to
>> teach my students about floats: *never* compare them for equality. So
>> in my view, your example doesn't fail, it's undefined. That Haskell
>> provides (==) for floats is unfortunate.
>
> I disagree, on practical basis. Floating-point numbers are very well
> defined, we know how the mantissa is represented. If the numbers are
> normalized, as they should, plenty of low-level iterative algorithms
> may use the equality - after some operation - to check that the machine-
> precision convergence has been obtained.

If you are absolutely sure that for every possible precision and for
every sequence of operations that compilers will generate from your code
your algorithm will actually converge to a particular binary
representation and not flip-flop on the last bit of the mantissa, for
instance, and if you do not care about the actual precision of your
algorithm (i.e., you want as much as possible of it) then yes, you might
get away with using exact equality. Of course, you'll have to protect
that part of your code by a sufficient number of warnings since you are
using a highly unsafe operation in a very carefully controlled context.
I'm not sure the trouble is really worth it. Anyway, in my view, such an
unsafe operation shouldn't be in scope by default and definitely
shouldn't be called (==). It's really quite like unsafePerformIO.

> On the contrary, the verification that the absolute value between two
> terms is less than some threshold, may be arbitrary or dubious.

Only if you use an inappropriate theshold. Choosing thresholds and
precision is an important part of numeric programming and should be done
with great care.

Roman

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: A question about "monad laws"

Aaron Denney
In reply to this post by Roman Leshchinskiy
On 2008-02-14, Roman Leshchinskiy <[hidden email]> wrote:

> Richard A. O'Keefe wrote:
>> Presumably the reason for having Int in the language at all is speed.
>> As people have pointed out several times on this list to my knowledge,
>> Integer performance is not as good as Int performance, not hardly,
>> and it is silly to pay that price if I don't actually need it.
>
> Do I understand correctly that you advocate using overflowing ints (even
> if they signal overflow) even if Integers are fast enough for a
> particular program? I strongly disagree with this. It's premature
> optimisation of the worst kind - trading correctness for unneeded
> performance.

"Fast enough" is not absolute.  It's not trading correctness, it's
trading /completion/.  And if you expect everything to fit in
[-2^31..2^31-1] or [0..2^32-1], finding out it doesn't might be valuable
information about your problem domain.  For "exploratory" coding, speed
and knowing when something breaks can be more important than knowing
that all possible corner case are covered, even ones you don't expect to
hit.

>> SafeInt is what you should use when you *THINK* your results should all fit
>> in a machine int but aren't perfectly sure.  (And this is nearly all the
>> time.)
>
> Again, I strongly disagree. You should use Integer unless your program
> is too slow and profiling shows that Integer is the culprit. If and only
> if that is the case should you think about alternatives. That said, I
> doubt that your SafeInt would be significantly faster than Integer.

Why?  GMP is pretty good, but it's not going to be anywhere near
hardware speeds.

>> The checking I am talking about is done by the hardware at machine speeds
>> and provides *certainty* that overflow did not occur.
>
> So you advocate using different hardware?

At a minimum, any usable hardware sets flags on overflow.
Testing on those is pretty cheap.  Much cheaper than calling a GMP
routine to compare with 2^32, for instance.

--
Aaron Denney
-><-

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: A question about "monad laws"

Ben Franksen
In reply to this post by Wilhelm B. Kloke
Wilhelm B. Kloke wrote:

> [hidden email] <[hidden email]> schrieb:
>> G'day all.
>>
>> Richard A. O'Keefe wrote:
>>
>>> Hmm. Personally, I've never seen an algorithm where comparing for exact
>>> equality was algorithmically necessary.
>>
>> One trick I've occasionally used is to avoid the need for a discriminated
>> union of floating point and integer types by just using a floating point
>> number.
>
> IMHO it is a perfectly good idea to use the FP processor for integer
> computations. You can use the Inexact Trap as Overflow Exception,
> a service you don't get from i386 (and most other) hardware for int
> operations. Of course your integers are limited to 24bit+sign in
> single precision and 54bit+sign in double. In i387 extended precision
> you get 64bit+sign.
>
> I would consider a good idea if ghc would provide language support to
> this sort of integers.

No need, you can do that for yourself:

{-# LANGUAGE GeneralizedNewtypeDeriving #-}
newtype DInt = DInt Double deriving (Eq, Ord, Enum, Num)

instance Show DInt where show (DInt x) = show (truncate x :: Integer)


You can even make it H98 by defining the instances manually...

Cheers
Ben

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Re: A question about "monad laws"

Thorkil Naur
In reply to this post by Richard A. O'Keefe
Hello,

On a tangent, probably:

On Thursday 14 February 2008 10:24, Roman Leshchinskiy wrote:
> ...
> Hmm. Personally, I've never seen an algorithm where comparing for exact  
> equality was algorithmically necessary. Sometimes (rarely) it is
> acceptable but necessary? Do you know of one?

Finding the "machine epsilon", perhaps, that is, the smallest (floating point,
surely) number for which 1.0+machine_eps==1.0 would be a candidate?

> ...

Best regards
Thorkil
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Re: A question about "monad laws"

Roman Leshchinskiy
In reply to this post by Aaron Denney
Aaron Denney wrote:

> On 2008-02-14, Roman Leshchinskiy <[hidden email]> wrote:
>> Richard A. O'Keefe wrote:
>
>>> SafeInt is what you should use when you *THINK* your results should all fit
>>> in a machine int but aren't perfectly sure.  (And this is nearly all the
>>> time.)
>> Again, I strongly disagree. You should use Integer unless your program
>> is too slow and profiling shows that Integer is the culprit. If and only
>> if that is the case should you think about alternatives. That said, I
>> doubt that your SafeInt would be significantly faster than Integer.
>
> Why?  GMP is pretty good, but it's not going to be anywhere near
> hardware speeds.

This how Integer is defined in the libraries:

data Integer
    = S# Int# -- small integers
    | J# Int# ByteArray# -- large integers

As long as the Int# doesn't overflow, you don't call any GMP routines.

Roman

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Re: A question about "monad laws"

ajb@spamcop.net
In reply to this post by Thorkil Naur
G'day all.

Quoting Thorkil Naur <[hidden email]>:

> Finding the "machine epsilon", perhaps, that is, the smallest  
> (floating point,
> surely) number for which 1.0+machine_eps==1.0 would be a candidate?

The machine epsilon is the smallest relative separation between two
adjacent normalised floating point numbers.  (The largest is the
machine epsilon multiplied by the radix, more or less.)

So as I understand it, if you're thinking relative error, this test:

     (fabs(x1-x2) < machine_eps * fabs(x1))

should be true if and only if x1 == x2, assuming that x1 and x2 are
nonzero and normalised.

I've always had the impression that using the machine epsilon for
pseudo-equality testing is fairly useless, especially if you can work
out a meaningful problem-specific tolerance.

What seems to be more useful is using the machine epsilon to compute an
estimate of how much relative error your algorithm accumulates.  I've
seen this in a lot of Serious Numeric Code(tm), and I've done it myself
(probably inexpertly) a few times.

I haven't tried this, but I imagine that a computed relative error
estimate could be useful for assisting your approximate-equality
tests under some circumstances.  Richard might know of some
circumstances where this sort of thing would be useful.

Cheers,
Andrew Bromage
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Re: A question about "monad laws"

Richard A. O'Keefe
In reply to this post by Roman Leshchinskiy

On 14 Feb 2008, at 10:24 pm, Roman Leshchinskiy wrote:
> Do I understand correctly that you advocate using overflowing ints  
> (even if they signal overflow) even if Integers are fast enough for  
> a particular program?

No you most certainly do NOT.  There is no way to soundly, and I  
would have
thought no way to plausibly, infer that from anything I wrote.
>

> Again, I strongly disagree. You should use Integer unless your  
> program is too slow and profiling shows that Integer is the  
> culprit. If and only if that is the case should you think about  
> alternatives. That said, I doubt that your SafeInt would be  
> significantly faster than Integer.

SafeInt should be as fast as Int, or very nearly.
The representation of SafeInt is identical to the representation of Int,
so the space overheads are definitely lower.
>> The checking I am talking about is done by the hardware at machine  
>> speeds
>> and provides *certainty* that overflow did not occur.
>
> So you advocate using different hardware?

Again, this is the opposite of what I wrote.
On my desk there are a Pentium machine and an UltraSPARC and a G4.
They *all* support cheap integer overflow checks.
I am saying that we should use the hardware we have already paid for!

> It's not a particularly useful operation (and it is not equality),  
> but it does have a defined semantics. However, the semantics of  
> (==) on floats isn't really defined in Haskell or C, for that  
> matter, even if you know that the hardware is strictly IEEE  
> conformant.

The semantics of == on floats in C99 is, under certain circumstances,  
and on the
machines I use with the compilers I use, defined to be those of the  
IEEE (or,
as the C99 standard puts it, IEC) operation.
>
> In general, floating point numbers do not really have a useful  
> notion of equality. They are approximations.

The *numbers* are not approximations, the *operations* are approximate.
In particular, floating point +, -, *, <, ==, abs, sign, and other  
related
operations (but not /) are *exact* on integral values, if the results  
fit.
AWK programs would be in terrible trouble if this were not so
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Re: A question about "monad laws"

Richard A. O'Keefe
In reply to this post by Wilhelm B. Kloke
On 15 Feb 2008, at 2:03 am, Wilhelm B. Kloke wrote:
IMHO it is a perfectly good idea to use the FP processor for integer
> computations. You can use the Inexact Trap as Overflow Exception,
> a service you don't get from i386 (and most other) hardware for int
> operations.

A neat idea.  However, the i386 has the INTO instruction, the SPARC  
family
has the TRAPV instruction, and other processors have analogues.  Some  
machines
have two sets of add/subtract instructions, one trapping, one not.



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: A question about "monad laws"

Wilhelm B. Kloke
In reply to this post by Ben Franksen
Ben Franksen <[hidden email]> schrieb:

> Wilhelm B. Kloke wrote:
>> [hidden email] <[hidden email]> schrieb:
>>>
>> I would consider a good idea if ghc would provide language support to
>> this sort of integers.
>
> No need, you can do that for yourself:
>
> {-# LANGUAGE GeneralizedNewtypeDeriving #-}
> newtype DInt = DInt Double deriving (Eq, Ord, Enum, Num)
>
> instance Show DInt where show (DInt x) = show (truncate x :: Integer)

Probably you missed the point I wanted to make. This works only properly,
if you can catch the Inexact Trap which indicates the overflow. The problem
whith normal Ints is that the hardware does not support overflow detection.
You get silent wrong results if you use an Int type which maps to
C int, but not if it maps to C float or double with Inexact trap enabled.
Therefore you need add runtime checks to be sure that you notice
a possible overflow condition.
--
Dipl.-Math. Wilhelm Bernhard Kloke
Institut fuer Arbeitsphysiologie an der Universitaet Dortmund
Ardeystrasse 67, D-44139 Dortmund, Tel. 0231-1084-257
PGP: http://vestein.arb-phys.uni-dortmund.de/~wb/mypublic.key

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: A question about "monad laws"

Ben Franksen
Wilhelm B. Kloke wrote:

> Ben Franksen <[hidden email]> schrieb:
>> Wilhelm B. Kloke wrote:
>>> [hidden email] <[hidden email]> schrieb:
>>>>
>>> I would consider a good idea if ghc would provide language support to
>>> this sort of integers.
>>
>> No need, you can do that for yourself:
>>
>> {-# LANGUAGE GeneralizedNewtypeDeriving #-}
>> newtype DInt = DInt Double deriving (Eq, Ord, Enum, Num)
>>
>> instance Show DInt where show (DInt x) = show (truncate x :: Integer)
>
> Probably you missed the point I wanted to make.

Obviously ;)

> This works only properly,
> if you can catch the Inexact Trap which indicates the overflow. The
> problem whith normal Ints is that the hardware does not support overflow
> detection. You get silent wrong results if you use an Int type which maps
> to C int, but not if it maps to C float or double with Inexact trap
> enabled. Therefore you need add runtime checks to be sure that you notice
> a possible overflow condition.

I agree completely.

Cheers
Ben

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: A question about "monad laws"

askyle
In reply to this post by Stefan O'Rear
>  My favorite presentation of the monad laws is associativity of Kliesli
>  composition:
>  (a1 >=> a2) x = a1 x >>= a2   -- predefined in 6.8 control.monad
>  -- The laws
>  return >=> a    = a
>  a >=> return    = a
>  a >=> (b >=> c) = (a >=> b) >=> c

If you use this presentation you also need the following law:
(a . b) >=> c  = (a >=> c) . b
that is, compatibility with ordinary function composition. I like to call this "naturality", since it's instrumental in proving return and bind to be natural transformations.

The law looks less alien if we use a flipped version of (>=>):
(<=<) = flip (>=>)
{- Monad Laws in terms of (<=<) -}
return <=< f  =  f <=< return  =  f          -- Identity
f <=< (g <=< h)  =  (f <=< g) <=< h     -- Associativity
f <=< (g . h)  = (f <=< g) . h                -- Naturality

(which happens to be my favorite presentation of the laws, followed by the derivations that lead to the 'do' notation, which lead to various 'ah' moments from unsuspecting FP-challenged friends)
Reply | Threaded
Open this post in threaded view
|

Re: Re: A question about "monad laws"

askyle
In reply to this post by Richard A. O'Keefe
I'm not sure whether this is the right branch of the thread for this post.
Maybe it belongs to a different thread altogether.
But here goes:

Maybe most of our gripes with floating point arithmetic (besides broken implementations) is that we expect it to behave like Real arithmetic, and when it doesn't, we whine that it's unreliable, ill-defined, etc etc etc.

If we consider FP as a mathematical entity of its own (e.g as defined in IEEE 754), we see that it has a well-defined, reliable behaviour which happens to emulate the behaviour of the real numbers within some margins. The accuracy of this emulation can be analyzed in a rigorous manner, see http://www.validlab.com/goldberg/paper.pdf

So if floating point (==) doesn't correspond with numeric equality, it's not FP's fault, but ours for expecting it to do! By the way, IEEE754 does define another comparison operator which corresponds to our notion of 'equality'. FP (==) is just a partial equivalence relation which makes more sense than mathematical equality in an FP context. Of course, if an implementation doesn't guarantee that 'x == x' yields true whenever x is not a NaN, then the implementation is broken.

An earlier post said that "Haskell is not math" (or something like it). I beg to differ -- one of its selling points, after all, is supposed to be the ability to perform equational reasoning. We work hard to give well-defined semantics to our expressions. We rely on types to tell us which properties to expect of which values, and which manipulations are valid.

But then Haskell goes and fools us (just like most other languages do) into thinking FP arithmetic is something that it's not: the behaviour of operations depends on an unseen environment (e.g. rounding mode), the order of evaluation matters, evaluation can fail... not at all what we'd call purely functional!

So if FP arithmetic is not purely functional, what do we do? If we could do Haskell all over again, I'd propose a different approach to FP arithmetic (and for stuff like Int, for that matter), which I'm actually surprised not to see discussed more often since it's after all the usual Haskell approach to things which are not purely functional. The original topic of this thread should already have hinted at it. ;)
Reply | Threaded
Open this post in threaded view
|

Re: A question about "monad laws"

ajb@spamcop.net
In reply to this post by askyle
G'day all.

Quoting askyle <[hidden email]>:

> If you use this presentation you also need the following law:
> (a . b) >=> c  = (a >=> c) . b
>
> that is, compatibility with ordinary function composition. I like to call
> this "naturality", since it's instrumental in proving return and bind to be
> natural transformations.

Define:

     f >=> g = \x -> f x >>= g
     fmap f xs = xs >>= return . f

Then:

   fmap f . return
= (expand fmap)
   \x -> (return x >>= return . f)
= (defn. of >=>)
   \x -> (return >=> return . f) x
= (left identity)
   \x -> (return . f) x
=
   return . f

Therefore return is natural.

Bind (or, equivalently, join) is left as an exercise.

Cheers,
Andrew Bromage
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: A question about "monad laws"

Wolfgang Jeltsch-2
In reply to this post by askyle
Am Mittwoch, 12. März 2008 00:53 schrieb askyle:
> […]

> So if floating point (==) doesn't correspond with numeric equality, it's
> not FP's fault, but ours for expecting it to do!

No, I think, it’s the Prelude’s fault to define (==) as “floating point
equality”.  We should us a different identifier like floatingPointEq.  (==)
is expected to be an equivalence relation.  (I think I already said this.)

> […]

Best wishes,
Wolfgang
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
1234