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: A question about "monad laws"

Richard A. O'Keefe
On 12 Feb 2008, at 10:35 am, David Benbennick wrote:
> Some months ago I pointed out that Ratio Int (which is an Ord
> instance) doesn't satisfy this property.  I provided a patch to fix
> the problem, but my bug report was closed as wontfix:
> http://hackage.haskell.org/trac/ghc/ticket/1517.

I'm not happy about that response.
Basically, if the inputs to a mathematical operation are representable,
and the mathematically correct result is representable, I expect a  
system
to deliver it or die trying.  What the intermediate calculations get up
to is the implementor's problem, not the user's.  On the other hand, if
I knew in advance whether a particular + or * was going to overflow, I
probably wouldn't need the computer to actually do it.

But if I give the computer some numbers that are clearly representable
and just ask it to *sort* them, it had better d--- well get that RIGHT.

I am extremely grateful for this report, because now I know
"NEVER USE Ratio Int, it's too broken".

Sad aside:  back in the 70s I had my own Ratio Int written in Burroughs
Algol.  I was not smart enough to use double precision numbers for  
anything,
but because of one hardware feature, it didn't matter a lot.  That  
hardware
feature was that integer overflows were TRAPPED and REPORTED.  I have  
since
used precisely one C compiler on precisely one Unix system that took  
advantage
of the fact that the C standard (both C89 and C99) was very carefully  
written
to ALLOW TRAPPING of signed integer overflows.  (Contrary to  
mythology, C
only requires wrapping for unsigned integers.)  I found that a  
surprisingly
valuable debugging aid.

This all supports the general point, of course:  data types whose  
operations
are so implemented as to break sensible laws can and WILL land you in  
great
piles of fresh steaming hot fertiliser.

_______________________________________________
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"

Derek Elkins
In reply to this post by Stefan O'Rear
On Mon, 2008-02-11 at 13:34 -0800, Stefan O'Rear wrote:

> On Mon, Feb 11, 2008 at 01:59:09PM +0000, Neil Mitchell wrote:
> > Hi
> >
> > > > (x >>= f) >>= g == x >>= (\v -> f v >>= g)
> > >
> > > Or stated another way:
> > >
> > > (x >>= f) >>= g == x >>= (f >>= g)
> >
> > Which is totally wrong, woops.
> >
> > See this page for lots of details about the Monad Laws and quite a
> > nice explanation of where you use them:
> > http://www.haskell.org/haskellwiki/Monad_Laws
>
> 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

Indeed.  The monad laws are just that the Kleisli category is actually a
category.

_______________________________________________
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 Richard A. O'Keefe
Richard A. O'Keefe comments:

>   [floating point addition is not associative]]
>
> And this is an excellent example of why violating expected laws is BAD.
> The failure of floating point addition to be associative means that  there
> are umpteen ways of computing polynomials, for example, and doing it  
> different ways will give you different answers.  This is *not* a good
> way to write reliable software.

[Then we see the scalar product whose value *may* depend on the ev. order]

I wonder...
Would you say that *no* typical floating-point software is reliable?

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"

Uwe Hollerbach-2
In reply to this post by David Benbennick
Ratio Integer may possibly have the same trouble, or maybe something
related. I was messing around with various operators on Rationals and
found that positive and negative infinity don't compare right. Here's
a small program which shows this; if I'm doing something wrong, I'd
most appreciate it being pointed out to me. If I fire up ghci, import
Data.Ratio and GHC.Real, and then ask about the type of "infinity", it
tells me Rational, which as far as I can tell is Ratio Integer...? So
far I have only found these wrong results when I compare the two
infinities.

Uwe

> module Main where
> import Prelude
> import Data.Ratio
> import GHC.Real
>
> pinf = infinity
> ninf = -infinity
> zero = 0
>
> main =
>   do putStrLn ("pinf = " ++ (show pinf))
>      putStrLn ("ninf = " ++ (show ninf))
>      putStrLn ("zero = " ++ (show zero))
>      putStrLn ("min pinf zero =\t" ++ (show (min pinf zero)))
>      putStrLn ("min ninf zero =\t" ++ (show (min ninf zero)))
>      putStrLn ("min ninf pinf =\t" ++ (show (min ninf pinf)))
>      putStrLn ("min pinf ninf =\t" ++ (show (min pinf ninf)) ++ "\twrong")
>      putStrLn ("max pinf zero =\t" ++ (show (max pinf zero)))
>      putStrLn ("max ninf zero =\t" ++ (show (max ninf zero)))
>      putStrLn ("max ninf pinf =\t" ++ (show (max ninf pinf)))
>      putStrLn ("max pinf ninf =\t" ++ (show (max pinf ninf)) ++ "\twrong")
>      putStrLn ("(<) pinf zero =\t" ++ (show ((<) pinf zero)))
>      putStrLn ("(<) ninf zero =\t" ++ (show ((<) ninf zero)))
>      putStrLn ("(<) ninf pinf =\t" ++ (show ((<) ninf pinf)) ++ "\twrong")
>      putStrLn ("(<) pinf ninf =\t" ++ (show ((<) pinf ninf)))
>      putStrLn ("(>) pinf zero =\t" ++ (show ((>) pinf zero)))
>      putStrLn ("(>) ninf zero =\t" ++ (show ((>) ninf zero)))
>      putStrLn ("(>) ninf pinf =\t" ++ (show ((>) ninf pinf)))
>      putStrLn ("(>) pinf ninf =\t" ++ (show ((>) pinf ninf)) ++ "\twrong")
>      putStrLn ("(<=) pinf zero =\t" ++ (show ((<=) pinf zero)))
>      putStrLn ("(<=) ninf zero =\t" ++ (show ((<=) ninf zero)))
>      putStrLn ("(<=) ninf pinf =\t" ++ (show ((<=) ninf pinf)))
>      putStrLn ("(<=) pinf ninf =\t" ++ (show ((<=) pinf ninf)) ++ "\twrong")
>      putStrLn ("(>=) pinf zero =\t" ++ (show ((>=) pinf zero)))
>      putStrLn ("(>=) ninf zero =\t" ++ (show ((>=) ninf zero)))
>      putStrLn ("(>=) ninf pinf =\t" ++ (show ((>=) ninf pinf)))
>      putStrLn ("(>=) pinf ninf =\t" ++ (show ((>=) pinf ninf)) ++ "\twrong")
_______________________________________________
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"

David Benbennick
On Feb 11, 2008 10:18 PM, Uwe Hollerbach <[hidden email]> wrote:
> If I fire up ghci, import
> Data.Ratio and GHC.Real, and then ask about the type of "infinity", it
> tells me Rational, which as far as I can tell is Ratio Integer...?

Yes, Rational is Ratio Integer.  It might not be a good idea to import
GHC.Real, since it doesn't seem to be documented at
http://www.haskell.org/ghc/docs/latest/html/libraries/.  If you just
import Data.Ratio, and define

> pinf :: Integer
> pinf = 1 % 0

> ninf :: Integer
> ninf = (-1) % 0

Then things fail the way you expect (basically, Data.Ratio isn't
written to support infinity).  But it's really odd the way the
infinity from GHC.Real works.  Anyone have an explanation?

--
I'm doing Science and I'm still alive.
_______________________________________________
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"

Yitzchak Gale
In reply to this post by Richard A. O'Keefe
David Benbennick wrote:
>> Some months ago I pointed out that Ratio Int (which is an Ord
>> instance) doesn't satisfy this property.  I provided a patch to fix
>> the problem, but my bug report was closed as wontfix:
>> http://hackage.haskell.org/trac/ghc/ticket/1517.

Richard A. O'Keefe wrote:
> I'm not happy about that response...
> I am extremely grateful for this report, because now I know
> "NEVER USE Ratio Int, it's too broken".

Ian wrote, in the Trac ticket:
> Thanks for the patch, but I see a couple of problems:
> ...If you still think that this change should be made then
> I think that it should go through the library submissions process:
> http://www.haskell.org/haskellwiki/Library_submissions

The "wontfix" resolution does not mean that the patch
was rejected. It just means that there are reasons for
and against it, so GHC HQ is not unilaterally implementing
it without giving the community a chance to discuss the
issues. I think that is an admirable attitude.

If you feel that this issue is important, why not go
ahead and start the process to get it adopted?

Regards,
Yitz
_______________________________________________
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"

Yitzchak Gale
In reply to this post by jerzy.karczmarczuk
Jerzy Karczmarczuk wrote:
> Would you say that *no* typical floating-point software is reliable?

It depends on how you define "reliable".

Floating point intentionally trades accuracy for speed,
leaving it to the user to worry about round-off errors.
It is usually not too hard to get the probability of
failure somewhat low in practice, if you don't require
a proof.

It used to be true - and may still be - that the engineers
who implement floating point in the hardware of our
CPUs would never fly on commercial airliners. Would you?

Would you entrust your country's nuclear arsenal to an
automated system that depends on floating point arithmetic?

Regards,
Yitz
_______________________________________________
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"

Yitzchak Gale
In reply to this post by Ben Franksen
Ben Franksen wrote:
> ...and the Unimo paper[1] explains how to easily write a 'correct' ListT.
> BTW, Unimo is an extreme case of the monad laws holding only w.r.t.
> the 'right' equality, i.e. in the laws m == m' is to be understood as
>   observe_monad m == observe_monad m'
> (and even this '==' is of course /not/ the Eq class method but a semantic
> equality.)
> [1] http://web.cecs.pdx.edu/~cklin/papers/unimo-143.pdf

Are you sure? Maybe I am missing something, but I don't
see any claim that the Unimo ListT satisfies the laws any
more than the old mtl ListT. It looks to me like Unimo is
just an attempt to provide an easier way to create, use,
and understand monads, not a change in their semantics.

ListT-Done-Right could also be defined via the Unimo
framework, and then it would satisfy the monad laws.

Thanks,
Yitz
_______________________________________________
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 Yitzchak Gale
Yitzchak Gale writes:

> Jerzy Karczmarczuk wrote:
>> Would you say that *no* typical floating-point software is reliable?
>
> It depends on how you define "reliable".
>
> Floating point intentionally trades accuracy for speed,
...

> It used to be true - and may still be - that the engineers
> who implement floating point in the hardware of our
> CPUs would never fly on commercial airliners. Would you?
>
> Would you entrust your country's nuclear arsenal to an
> automated system that depends on floating point arithmetic?

1. This is not a possible "trade-off" or not. In scientific/engineering
  computation there is really no choice, since you have to compute
  logarithms, trigonometric functions, etc., and some inaccuracy is
  unavoidable. Of course, one may use intervals, and other extremely
  costly stuff, but if the stability of the algorithms is well controlled,
  and in normal case it is (especially if the basic arithmetics has some
  extra control bits to do the rounding), th issue is far from being
  mortal.

2. The story about engineering not flying commercial planes is largely
  anecdotical, and you know that. Repeating it here doesn't change much.

3. Nuclear arsenal is never really "entrusted to an automated system",
  because of reasons much beyond the fl.point inaccuracies.
  On the other hand, in all those software one has to deal with
  probabilities, and with imprecise experimental data, so even if for God
  knows which purpose everything used exact algebraic numbers, or
  controlled transcendental extensions, the input imprecision would kill
  all the sense of infinitely precise computations thereupon.

4. The non-reliability of engineering software has many more important
  reasons, sometimes incredibly stupid, such as the confusion between
  metric and English units in the Mars Climate Orbiter crash...
  The Ariane 5 crash was the result not of the floating-point computation
  but of the conversion to signed 16-bit numers (from a 64bit double).

5. Of course, in the original posting case, the underlying math/logic is
  discrete, and has no similar inaccuracies, so the two worlds should
  not be confounded... Here, if some laws get broken, it is the result of
  bad conventions, which usually can be easily avoided.

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: Re: A question about "monad laws"

Yitzchak Gale
I wrote:
>> Floating point intentionally trades accuracy for speed,

Jerzy Karczmarczuk wrote:
> 1. This is not a possible "trade-off" or not. In scientific/engineering
>   computation there is really no choice, since you have to compute
>   logarithms, trigonometric functions, etc., and some inaccuracy is
>   unavoidable. Of course, one may use intervals, and other extremely
>   costly stuff, but if the stability of the algorithms is well controlled,
>   and in normal case it is (especially if the basic arithmetics has some
>   extra control bits to do the rounding), th issue is far from being
>   mortal.

Agreed. That is what I meant by "trade-off". And I am not trying
to say at all that it is wrong to use it. Life is full of trade-offs.

>> It used to be true - and may still be - that the engineers
>> who implement floating point in the hardware of our
>> CPUs would never fly on commercial airliners. Would you?

> 2. The story about engineering not flying commercial planes is largely
>   anecdotical, and you know that. Repeating it here doesn't change much.

I heard it from someone who personally worked with one such team
of engineers about ten years ago.

>> Would you entrust your country's nuclear arsenal to an
>> automated system that depends on floating point arithmetic?

> 3. Nuclear arsenal is never really "entrusted to an automated system",
>   because of reasons much beyond the fl.point inaccuracies.

Yes, of course, no one is really that stupid. Are they?

>   On the other hand, in all those software one has to deal with
>   probabilities, and with imprecise experimental data, so even if for God
>   knows which purpose everything used exact algebraic numbers, or
>   controlled transcendental extensions, the input imprecision would kill
>   all the sense of infinitely precise computations thereupon.
> 4. The non-reliability of engineering software has many more important
>   reasons, sometimes incredibly stupid, such as the confusion between
>   metric and English units in the Mars Climate Orbiter crash...
>   The Ariane 5 crash was the result not of the floating-point computation
>   but of the conversion to signed 16-bit numers (from a 64bit double).

Yes, high reliability is very hard. There are many factors that
make it hard; floating point is undeniably one of them.
Again - that doesn't mean that floating point should not be used.
It is a powerful and important tool, as you say.

I was once part of a software project in which people's lives
might depend on there not being any bugs in my code.
It was an experience that changed my life forever,
and that is probably one of the factors that contributes
to my interest in Haskell.

Regards,
Yitz
_______________________________________________
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"

Jan-Willem Maessen
In reply to this post by David Benbennick

On Feb 12, 2008, at 1:50 AM, David Benbennick wrote:

> On Feb 11, 2008 10:18 PM, Uwe Hollerbach <[hidden email]>  
> wrote:
>> If I fire up ghci, import
>> Data.Ratio and GHC.Real, and then ask about the type of "infinity",  
>> it
>> tells me Rational, which as far as I can tell is Ratio Integer...?
>
> Yes, Rational is Ratio Integer.  It might not be a good idea to import
> GHC.Real, since it doesn't seem to be documented at
> http://www.haskell.org/ghc/docs/latest/html/libraries/.  If you just
> import Data.Ratio, and define
>
>> pinf :: Integer
>> pinf = 1 % 0
>
>> ninf :: Integer
>> ninf = (-1) % 0
>
> Then things fail the way you expect (basically, Data.Ratio isn't
> written to support infinity).  But it's really odd the way the
> infinity from GHC.Real works.  Anyone have an explanation?

An educated guess here: the value in GHC.Real is designed to permit  
fromRational to yield the appropriate high-precision floating value  
for infinity (exploiting IEEE arithmetic in a simple, easily-
understood way).  If I'm right, it probably wasn't intended to be used  
as a Rational at all, nor to be exploited by user code.

-Jan-Willem Maessen

_______________________________________________
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"

Heinrich Apfelmus
In reply to this post by Yitzchak Gale
Yitzchak Gale wrote:
> Ben Franksen wrote:
>> ...and the Unimo paper[1] explains how to easily write a 'correct' ListT.
>
> Are you sure? Maybe I am missing something, but I don't
> see any claim that the Unimo ListT satisfies the laws any
> more than the old mtl ListT.

> ListT-Done-Right could also be defined via the Unimo
> framework, and then it would satisfy the monad laws.

The list monad transformer implemented with Unimo (figure 13) is
different from  ListT m a = m [a]  (figure 11 for reference).

Note that I say "the list monad transformer".

I don't understand what's so special about "ListT m does not fulfill the
monad laws", it just shows that na├»vely using  m [a]  to implement the
list monad transformer is incorrect for general  m . In other words,
there is a big bug in  Control.Monad.List  and that's all there is to it.


Regards,
apfelmus

_______________________________________________
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"

Uwe Hollerbach-2
In reply to this post by Jan-Willem Maessen
On Feb 12, 2008 6:12 AM, Jan-Willem Maessen <[hidden email]> wrote:

On Feb 12, 2008, at 1:50 AM, David Benbennick wrote:

> On Feb 11, 2008 10:18 PM, Uwe Hollerbach <[hidden email]>
> wrote:
>> If I fire up ghci, import
>> Data.Ratio and GHC.Real, and then ask about the type of "infinity",
>> it
>> tells me Rational, which as far as I can tell is Ratio Integer...?
>
> Yes, Rational is Ratio Integer.  It might not be a good idea to import
> GHC.Real, since it doesn't seem to be documented at
> http://www.haskell.org/ghc/docs/latest/html/libraries/.  If you just
> import Data.Ratio, and define
>
>> pinf :: Integer
>> pinf = 1 % 0
>
>> ninf :: Integer
>> ninf = (-1) % 0
>
> Then things fail the way you expect (basically, Data.Ratio isn't
> written to support infinity).  But it's really odd the way the
> infinity from GHC.Real works.  Anyone have an explanation?

An educated guess here: the value in GHC.Real is designed to permit
fromRational to yield the appropriate high-precision floating value
for infinity (exploiting IEEE arithmetic in a simple, easily-
understood way).  If I'm right, it probably wasn't intended to be used
as a Rational at all, nor to be exploited by user code.

-Jan-Willem Maessen


Well... I dunno. Looking at the source to GHC.Real, I see

infinity, notANumber :: Rational
infinity   = 1 :% 0
notANumber = 0 :% 0
This is actually the reason I imported GHC.Real, because just plain % normalizes the rational number it creates, and that barfs very quickly when the denominator is 0. But the values themselves look perfectly reasonable... no?

Uwe

_______________________________________________
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"

Luke Palmer-2
2008/2/12 Uwe Hollerbach <[hidden email]>:

> Well... I dunno. Looking at the source to GHC.Real, I see
>
>  infinity, notANumber :: Rational
> infinity = 1 :% 0
> notANumber = 0 :% 0
>
>  This is actually the reason I imported GHC.Real, because just plain %
> normalizes the rational number it creates, and that barfs very quickly when
> the denominator is 0. But the values themselves look perfectly reasonable...
> no?

Ummm... I'm going to have to go with no.

In particular we can't have signed infinity represented like this and
maintain reasonable numeric laws:

  1/0 = 1/(-0) = (-1)/0

Rationals are defined not to have a zero denomiator, so I'll bet in
more than one place in Data.Ratio that assumption is made.

Luke
_______________________________________________
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 jerzy.karczmarczuk

On 12 Feb 2008, at 5:14 pm, [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
(b) "reliable" in each case needs to be defined with some care; it will
     almost never mean "gives answers accurate to machine precision for
     any legal input" and probably won't mean "gives sensible answers  
for
     any legal input" either.  With luck, it will mean "gives answers  
accurate
     to a specified tolerance for an input that differs from the  
input you
     actually provided by no more than a specified tolerance for inputs
     that are neither too big nor too small, a stated range".  (Note  
that
     the problem that gets almost solved may only be almost your  
problem.)
(c) practical advice is to use reputable packaged software whenever you
     possibly can rather than writing your own, and always check that  
the
     answers make physical sense before putting any trust with them;  
if (or
     should I say when) things go weird, seek the help of an expert.
(d) if you trust the output of a certain popular spreadsheet program, I
     have a bridge you might be interested in buying...

This is leaving aside all sorts of machine strangeness, like the student
whose neural net program started running hundreds of times slower than
he expected.  I advised him to replace
        s = 0;
        for (i = 0; i < n; i++) s += x[i]*x[i];
by
        s = 0;
        for (i = 0; i < n; i++)
            if (fabs(x[i]) > 1e-19)
                s += x[i]*x[i];
and the problem went away.  Dear reader: do you know why I expected this
problem, what it was, and why this is NOT a general solution?

_______________________________________________
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
Richard A. O'Keefe wrote:

>
> On 12 Feb 2008, at 5:14 pm, [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.

> This is leaving aside all sorts of machine strangeness, like the student
> whose neural net program started running hundreds of times slower than
> he expected.  I advised him to replace
>     s = 0;
>     for (i = 0; i < n; i++) s += x[i]*x[i];
> by
>     s = 0;
>     for (i = 0; i < n; i++)
>         if (fabs(x[i]) > 1e-19)
>         s += x[i]*x[i];
> and the problem went away.  Dear reader: do you know why I expected this
> problem, what it was, and why this is NOT a general solution?

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. As it were,
he seems to have applied what he though was an optimisation (using
floating point) without knowing anything about it. A professional
programmer would get (almost) no sympathy in such a situation.

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"

jerzy.karczmarczuk
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?

Then, the problem is not always pathological, in the sense of "exceptional
conditions". There are touchy points related to the stability of the
algorithms for the solution of differential equations. There are doubtful
random number generators in Monte-Carlo business. There are ill-conditioned
matrices and screwed-up iterative definitions. Algorithms work, work, and
ultimately explode or produce rubbish. The "laws" which get broken are
"almost" respected for a long time, and then we have the Bald Man (Sorites)
paradox...

RAO'K very wisely says that people should avoid reinventing wheels, and
they should use established packages, written by people who know.

The problem *here* is that we would like to have something fabulous in
Haskell - for example... And there aren't too many experts, who would
convert to the Functional Religion just for fun.
What is *much worse*, some potential users who could encourage building
such packages in the numerical domain, typically don't believe that FP
gives anything interesting. At least, this is the opinion of physicists
I spoke to recently.
Never mind. We shall dance over their cadavers, unless they dance over
ours. In both cases we shall be happy.

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: Re: A question about "monad laws"

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

On 14 Feb 2008, at 2:28 pm, Roman Leshchinskiy wrote:

> Richard A. O'Keefe wrote:
>> On 12 Feb 2008, at 5:14 pm, [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.

They obey a heck of a lot more of them.
Any combination of Ints using (+), (-), (*), and negate
is going to be congruent to the mathematically correct answer modulo  
2**n
for some n.  In particular, (+) is associative for Ints.

> It is not exceptionally hard to write reliable software using ints.

I did my BSc and MSc computing on a B6700, where the hardware *always*
notified you in case of an integer overflow.  In that case, it was
perfectly easy to write reliable software.  You just pretended that
the type 'INTEGER' in your program meant 'mathematical integer', and if
that got you into trouble, the machine was certain to tell you about it.

Using languages that do not check for integer overflow, even on hardware
(like, as it happens, both the different machines on my desk) that makes
it cheap to do so, I *have* had trouble with multiplying two positive  
integers
and getting a negative rules and also with a program that went into  
an infinite
loop because it happened to multiply two positive numbers and get  
another
positive number that was smaller than the one it started with.  
There's also
the problem dividing two negative integers can give you a negative  
result.
And one problem I definitely ran into was a Pascal 'for' loop with  
positive
bounds that ran forever.

When I contrast the amount of manual checking I have to do when  
writing C
(or, for that matter, Haskell) with the amount of manual checking I  
have to
do when using Smalltalk or SETL or Lisp, and when I remember how life  
was
*better* for me in this respect back in the 70s, well, it doesn't  
make me
happy.

This would be my top priority request for Haskell':
        require that the default Int type check for overflow on all
        operations where overflow is possible,
        provide Int32, Int64 for people who actually *want* wraparound.

I've been told that there was a day when there was serious trouble in  
the
US financial markets because the volume of trade exceeded the 32-bit  
signed
integer limit, and many programs started giving nonsense results.  
But the
Smalltalk programs just kept powering on...

> You just have to check for exceptional conditions.

Why should it be *MY* job to check for exceptional conditions?
That's the *MACHINE*'s job.  When you bought your computer, you paid
for hardware that will do this job for you!

> That's also the case for floating point.

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.

I have known a *commercial* program blithely invert a singular matrix
because of this kind of thing, on hardware where every kind of  
arithmetic
exception was reported.  There were no "exceptional conditions", the
answer was just 100% wrong.

> 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.
(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.
(c) x*x => 0 when x is small enough *is* fast on a lot of machines.

> As it were, he seems to have applied what he though was an  
> optimisation (using floating point) without knowing anything about  
> it. A professional programmer would get (almost) no sympathy in  
> such a situation.

You must be joking.  Almost everybody working with neural nets uses  
floating
point.  (One exception I came across was some people using special  
vector
processor hardware that didn't *have* floating point.  These days,  
you could
probably use a programmable GPU to good effect.)

For neural net calculations, you have to do lots of dot products.
When this example happened, machines were commonly 32 bit, not 64 bit.
So doing the calculations in integers would
  (a) have limited him to 16 bits for the coefficients,
      instead of double's 53.  This might just have been enough of a  
limit
      to prevent learning the kinds of things he wanted his net to  
learn.
      Actually, if you want to do a dot product on n-vectors, you need
      enough bits for n as well.  Suppose you have 100 inputs, then  
you'll
      need 7 bits for that, so you are limited to (31-7)/2 = 12 bits,  
which
      is dangerously low.  (doubles can do precise sums of up to 128  
products
      of coefficients with up to 23 bits).
  (b) integer multiplication was very slow on that machine.  On most  
modern
      machines, integer multiplication is quite slow compared with add,
      because architects look at C benchmarks and conclude that  
multiplication
      isn't important.  So programmers learn to do multiply-heavy  
calculations
      in floating point, so the benchmarks show less integer  
multiplication,
      so the architects let integer multiply get relatively slower,  
and ....
  (c) the sigmoid function *has* to be done in floating point  
arithmetic.
      In fact I *wanted* him to use integer operations so that he could
      exploit the new-at-the-time graphics instructions (think MMX),  
but the
      project foundered on this step.  He couldn't get a workable  
approximation
      of the sigmoid function using integers that didn't kill  
performance.
  (d) Much of the calculation needed for neural nets can be done  
using the
      Basic Linear Algebra Subroutines, which are available in seriously
      tuned form for most modern machines.  If a programmer *didn't* use
      these (floating-point-only) libraries, I would be asking why not.

If you are aware of any neural net software for general purpose  
hardware done
by programmers you consider competent that *doesn't* use floating  
point, I
would be interested to hear about it.

_______________________________________________
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:

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

> Then, the problem is not always pathological, in the sense of "exceptional
> conditions". There are touchy points related to the stability of the
> algorithms for the solution of differential equations. There are doubtful
> random number generators in Monte-Carlo business. There are ill-conditioned
> matrices and screwed-up iterative definitions. Algorithms work, work, and
> ultimately explode or produce rubbish. The "laws" which get broken are
> "almost" respected for a long time, and then we have the Bald Man (Sorites)
> paradox...
> RAO'K very wisely says that people should avoid reinventing wheels, and
> they should use established packages, written by people who know.

Yes, I completely agree with that (even though my original email
probably didn't sound as if I did). My point was that (a) most people
don't need floating point and (b) those who do need it should learn how
to use it.

> The problem *here* is that we would like to have something fabulous in
> Haskell - for example...

I think we mostly have it already.

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"

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

>
> On 14 Feb 2008, at 2:28 pm, Roman Leshchinskiy wrote:
>
>> Richard A. O'Keefe wrote:
>>> On 12 Feb 2008, at 5:14 pm, [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.
>
> They obey a heck of a lot more of them.
> Any combination of Ints using (+), (-), (*), and negate
> is going to be congruent to the mathematically correct answer modulo 2**n
> for some n.  In particular, (+) is associative for Ints.

Yes, but neither school nor, for the most part, university mathematics
teach us to expect modulo arithmetic. Good programmers learn about it at
some point in their carreer, though, and write their programs
accordingly. If they intend to use floating point, they should learn
about it, too.

I do agree that most programmers don't know how to use floats properly
and aren't even aware that they can be used improperly. But that's an
educational problem, not a problem with floating point.

> This would be my top priority request for Haskell':
>     require that the default Int type check for overflow on all
>     operations where overflow is possible,
>     provide Int32, Int64 for people who actually *want* wraparound.

I don't understand this. Why use a type which can overflow in the first
place? Why not use 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.
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. 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 have known a *commercial* program blithely invert a singular matrix
> because of this kind of thing, on hardware where every kind of arithmetic
> exception was reported.  There were no "exceptional conditions", the
> answer was just 100% wrong.

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.

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

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

> (c) x*x => 0 when x is small enough *is* fast on a lot of machines.

Only if underflow is masked (which it probably is by default). Although
I vaguely recall that denormals were/are slower on some architectures.

>> As it were, he seems to have applied what he though was an
>> optimisation (using floating point) without knowing anything about it.
>> A professional programmer would get (almost) no sympathy in such a
>> situation.
>
> You must be joking.  Almost everybody working with neural nets uses
> floating point.
>
> [...]
>
> If you are aware of any neural net software for general purpose hardware
> done
> by programmers you consider competent that *doesn't* use floating point, I
> would be interested to hear about it.

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. He had someone he could ask so hopefully, he'll know next time.

To be clear, I do not mean to imply that programmers who do not know
about floating point are incompetent. I'm only somewhat sceptical of
programmers who do not know about it but still write software that
relies on it.

Roman

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