Recently I wrote
I wonder, why Haskell does not check/report the overflow for Int?
For the Haskell implementation, it is natural to have the Int
arithmetic cost much less (about 5 times) than Integer.
Therefore, for the applications like the polynomial arithmetics
(and many others) that represent a power product as
"newtype PP = PP [Integer] " or "newtype PP' = PP' [Int] "
it worths to preserve both PP and PP'.
PP' is considerably cheaper in running, and PP is generic.
Unfortunately, PP' is incorrect.
For example, x^(2^n) --> x^0, if 2^n > maxInt.
For the algebra, it would be better to
*break in such case with the overflow message*.
With this, the researcher runs the faster program and does not
risk to get the incorrect result.
...
--------------------------------------------------------------------
Dave Tweed <[EMAIL PROTECTED]> replies on 24 Oct 1997:
> I'm not sure that people who want to write `production systems' (i.e.,
> ones that will be run when the original author is no longer around to
> figure out what went wrong for bad input and how it can be fixed) would
> agree. Surely the best idea is to do something equivalent to the IEEE
> floating point standard which defines certain returned bit patterns to
> mean `over/underflow occurred', etc. The programmer can then handle this
> either
> in the simple way of calling error, or try to carry on in some suitable
> way. In a similar way there could be a tainted bit pattern for
> overflow, perhaps with testing functions built into the prelude. This
> would be even more useful since tainted bit-patterns in further
> calculations are defined to produce a tainted bit-pattern result, so
> overflow needn't be explicitly tested for each atomic operation.
Do you mean certain bit in the result number? Say, 3*maxInt
to produce a number with the lower (higher) bit 1 showing overflow?
If so then, for example, after the matrix inversion, which element
of result has to check for the overflow bit to verify the
correctness? And we cannot set the global flag, because it is
against functionality. Sorry if I mis-understood the idea.
With this, the researcher runs the faster program and does not
risk to get the incorrect result.
> That sounds close to trying to have it both ways: Int's are
> a (usefully large) approximation to Integers (or the mathematical
> integers) which can be implemented quickly precisely because they are
> bounded.
Because they are the machine words. Probably, the pair of machine
words would not do.
> The price you pay is that operations like +, *, etc become
> partial functions, and consequently your function definitions
> must take account of this.
Yes. But Int in Haskell does NOT lead to the partial functions on
Integer, it leads to *other functions*, the ones defined on the
residues modulo maxInt.
If the programmer has to express the polynomial product
f = let g = x^maxInt in g^10
s(he) expects deg(f) to be greater than maxInt. And Haskell will
make it less.
Here (^) is not a partial function, this is just another function,
different from what was aimed.
Therefore the program should represent the power product not with
Int
- if only the residue arithmetic for Int is standard -
but with some Int' that are like Int, only break by overflow. This
will lead to the partial functions.
As the equally efficient Int and Int' may hardly co-exist,
probably, it worths to stay with Int' only.
But I wonder: what with the language standard?
Suppose, many existing applications *rely* on that maxInt+1 == 0 ?
---------------------------------------------------------------------
Alastair Reid <[EMAIL PROTECTED]> replies on 24 Oct 1997:
> The argument has always been that you'll use Integer as the default.
> Once you have written and tested your program, you might choose to
> switch to using Int if you can convince yourself that you don't use
> integers above 2^29-1. How you do this is up to you.
>
> The tedious, but safe, way is to do all the proofs by hand.
Not only tedious. It is often a hard mathematical problem to prove
that the intermediate results keep within the given bound.
With Int' reporting overflow, it will turn *safe and not tedious*.
> The reckless way is to run your program on a few examples and check
> the answers against your original program.
The program is usually run to find the result initially unknown.
Suppose we have Int' instead that are like Int, only break by
overflow.
With Int', one could run first the function for the Int' data. In
the most cases, this will suffice. But if overflow, run it for
Integer.
> The middle ground is to define a new type which will perform runtime
> overflow checks. This approach requires two tricks:
> 1) You have to write range-checking versions of all the usual
> Int functions.
> 2) You have to provide instances for Eq, Ord, Num, etc so that you
> can continue to write things like "1 + 2 >= x" in you programs.
>
> The good news is that Mark Jones has already done all the work for
> you - the Number library distributed as part of Hugs does it all!
If you mean programming this in Haskell, then it will be slow.
And this should look rather like "(I' 1)+(I' 2) >= x".
And if one changes the numeric library for Int (written, probably,
in C) to do the range checking, and so on, then this Int is
different; what about the language standard?
I propose to add to the Haskell language the above type Int', with
the new "'" syntax.
For example:
23' + 3' == 26'
10'^9 + 1' == 1000 000 001'
(10'^9 + 1' :: Int ) == (mod (10^9+1) maxInt) :: Int
Though, I am not so sure ...
Then the designers implement Int' as you mention above.
And if the residue nature of Int is *not in Haskell standard*,
then Int might change its behaviour to the better one.
------------------
Sergey Mechveliani
[EMAIL PROTECTED]
