How can I detect Int overflow?
Alex Mentis
Task: write a function that uses folding to convert a String to an
Int.
Problem I'm having: given the String "314159265358979323846", the
function should report an error because the integer equivalent of this
string is outside the range of Int. If I run my code (below), it
overflows silently and outputs garbage. How can I check that the
calculation "place * 10 + digitToInt c" is within the bounds of Int
before outputting it and report an error otherwise?
I can make this function work by returning Integer instead of Int, but
I think that's missing the point of the exercise in the book.
Thanks,
Alex
Solution so far:
-- file: exercise04-2.1.hs
-- Write a function that converts a string of digits into an integer.
import Data.Char
import Data.List
asIntFold :: String -> Int
asIntFold "" = error "cannot convert string"
asIntFold ('-':str) = -(asIntFold(str))
asIntFold str = foldl' addPlace 0 str
where addPlace place c
| not (isDigit c) = error "cannot convert
string"
| otherwise = place * 10 + digitToInt c
Paul Rubin
> Task: write a function that uses folding to convert a String to an Int.
Int is evil. Use Integer instead of Int.
Mark T. B. Carroll
> Problem I'm having: given the String "314159265358979323846", the
> function should report an error because the integer equivalent of this
> string is outside the range of Int. If I run my code (below), it
> overflows silently and outputs garbage. How can I check that the
> calculation "place * 10 + digitToInt c" is within the bounds of Int
> before outputting it and report an error otherwise?
Int is Bounded, so you can use maxBound to check how high Ints get --
that should be enough of a clue? On my computer,
Prelude> maxBound :: Int
9223372036854775807
Prelude>
Somewhat alarmingly,
Prelude> signum (abs minBound :: Int)
-1
Prelude>
(-:
Mark
Howard Brazee
<no.e...@nospam.invalid> wrote:
>> Task: write a function that uses folding to convert a String to an Int.
>
>Int is evil. Use Integer instead of Int.
One thing I like about Haskell is that we have Integer. But most
languages I've used get by without it, preferring efficiency. Why is
Int evil?
--
"In no part of the constitution is more wisdom to be found,
than in the clause which confides the question of war or peace
to the legislature, and not to the executive department."
- James Madison
Paul Rubin
> One thing I like about Haskell is that we have Integer. But most
> languages I've used get by without it, preferring efficiency. Why is
> Int evil?
Because you can add two positive Ints and get a negative Int, for
example.
The efficiency hit of Integer doesn't have to be so large. The compiler
can use an Int-like representation most of the time (say, when advised
by a pragma), with an overflow check on arithmetic operations. Overflow
could either promote to a bignum representation or raise an exception,
either of which is preferable to silently giving the wrong answer.
Howard Brazee
<no.e...@nospam.invalid> wrote:
>Because you can add two positive Ints and get a negative Int, for
>example.
I'm still a Haskell beginner. How does this work, and why?
Paul Rubin
>>Because you can add two positive Ints and get a negative Int, for example.
> I'm still a Haskell beginner. How does this work, and why?
Same way as in C and other dangerous languages:
Prelude> let a = maxBound :: Int
Prelude> a
9223372036854775807
Prelude> a+5
-9223372036854775804
Alex Mentis
> Int is Bounded, so you can use maxBound to check how high Ints get --
> that should be enough of a clue?
Well, I saw maxBound, but the problem is I can't see how to compare
the value returned by maxBound to the result of a possibly overflowing
calculation because once the calculation is performed and silently
overflows it becomes, by the nature of overflow, a value within the
bounds of Int. For example, adding the guard
| (place * 10 + digitToInt c) > maxBound = error "cannot convert
string"
never gets executed because whenever (place * 10 + digitToInt c)
overflows, it returns a value between minBound and maxBound.
Alex Mentis
> Alex Mentis <asmen...@gmail.com> writes:
> > Task: write a function that uses folding to convert a String to an Int.
>
> Int is evil. Use Integer instead of Int.
Yes, I can make it work when I use Integer, of course, but again, I
don't think that's the goal of the exercise.
Hans Aberg
You might check the value
1 + maxBound :: Int
However, using using that idea is only correct if Int is implemented as
two's complement, and though that is the case today, not always in the
past. So if you want not relying on how Int is implemented, you need to
check overflow before it happens.
Patricia Shanahan
Why not do the intermediate steps in Integer, where the comparison to
the Int maxBound would work, and only convert the final result of a
non-overflowing calculation to Int?
Patricia
Howard Brazee
I figured it was sign overflow that somehow wasn't checked by the
compiler. But why? All of the compilers in languages I have used
do check.
At any rate, for most use we don't need to check, as Int is only
"evil", as you say with pretty large numbers.
Mark T. B. Carroll
> On Sep 4, 7:35 pm, "Mark T. B. Carroll" <m...@bcs.org> wrote:
>
>> Int is Bounded, so you can use maxBound to check how high Ints get --
>> that should be enough of a clue?
>
> Well, I saw maxBound, but the problem is I can't see how to compare
> the value returned by maxBound to the result of a possibly overflowing
> calculation because once the calculation is performed and silently
> overflows it becomes, by the nature of overflow, a value within the
> bounds of Int.
You don't add the next digit to the current sum, to compare, you instead
check something like if maxBound `div` 10 is larger than your current
digit place, I'd guess. Something like that.
Mark
Mark T. B. Carroll
> I figured it was sign overflow that somehow wasn't checked by the
> compiler. But why? All of the compilers in languages I have used
> do check.
Still, quite a few don't. Some don't even check array bounds. Sometimes
it's a compile-time option. For instance, having a quick go with Java
now -- a fairly high-level language -- I find it lets ints overflow
quite silently.
> At any rate, for most use we don't need to check, as Int is only
> "evil", as you say with pretty large numbers.
Indeed. Many languages guarantee ints are at least so-large, Haskell
included I think.
Mark
Paul Rubin
>> Prelude> a+5
>> -9223372036854775804
>
> I figured it was sign overflow that somehow wasn't checked by the
> compiler. But why? All of the compilers in languages I have used
> do check.
Off the top of my head I can't think of any compilers that check, except
for those that promote to bignum automatically.
> At any rate, for most use we don't need to check, as Int is only
> "evil", as you say with pretty large numbers.
Almost all numbers are pretty large in that sense. Int is only non-evil
if the compiler can statically verify that the values will always be
sufficiently small.
Dan Doel
> The efficiency hit of Integer doesn't have to be so large. The compiler
> can use an Int-like representation most of the time (say, when advised
> by a pragma), with an overflow check on arithmetic operations. Overflow
> could either promote to a bignum representation or raise an exception,
> either of which is preferable to silently giving the wrong answer.
Integers (in GHC) already use a machine integer representation when the
values are small enough, and only promote to a GMP arbitrary precision
integer on overflow.
The efficiency hit for Integer is doing all this, and the resulting
diminishment of optimizations.
If exception-on-overflow is preferable, there's the 'checked' library on
hackage that provides Data.Int/Word.Checked.
Antoine
The 'checked' package is not written for speed - it does the
assertions by performing all operations both in the requested type and
then in Integer to see if we've gone out of bounds of the base type.
Also, the checkes are not performed when compiling with optimizations.
It was originally intended to be a diagnostic - something you can swap
in to characterize your operations.
Antoine
Florian Weimer
> Howard Brazee <how...@brazee.net> writes:
>>> Prelude> a+5
>>> -9223372036854775804
>>
>> I figured it was sign overflow that somehow wasn't checked by the
>> compiler. But why? All of the compilers in languages I have used
>> do check.
>
> Off the top of my head I can't think of any compilers that check, except
> for those that promote to bignum automatically.
ML implementations generally check, e.g. in SML/NJ:
- valOf(Int.maxInt) + 1;;
uncaught exception Overflow [overflow]
raised at: <file stdIn>
Ada also requires overflow checking, and implementations adhere to
that.
berts...@gmail.com
> How can I check that the calculation "place * 10 + digitToInt c" is
> within the bounds of Int before outputting it and report an error otherwise?
I do a lot of work in C with combinatoric functions which can blow up quite easily. Often even if a closed form equation for the number of solutions or cases can be expressed, it can easily exceed any fixed-with integer representation. I use C to get the best bang-for-buck in terms of execution time, but there you don't have any ability to turn on a compile-time flag to check all arithmetic for overflow (unlike Swift or C# or more modern derivatives of C).
But there is a DIY solution if you don't mind working with a few algebraic inequalities of integer variables. You'll see that you can always unroll your expression to produce a safe arithmetic expression to show when overflow would (or would not) occur.
Given your expression, this could be done in two steps. First, I will assume that place>=0 is always true. Given that, the first goal is to make sure that place*10 <= maxBound::Int. So we need only to make sure that place <= maxBound::Int `div` 10 (where 'div' refers to the integer division operator). If place falls above that value, you have successfully detected the overflow in advance. Next, with the new value of place known to be safe, you merely need to make certain that digitToInt c <= maxBound::Int - place*10.
This could also be done in a single step: Since we know that 'digitToInt c' must fall in the range [0..9], a more efficient solution would be to simply make sure that the following expression holds True, and if place falls above this bound and the expression is False, the arithmetic overflow would have been detected in advance. This is simply the original inequality solved for place to find its maximum value:
place <= (maxBound::Int - digitToInt c) `div` 10
You also need to handle the case that negative numbers can go one value lower, since (abs minBound::Int) > (abs maxBound::Int), but with a bit of thought you can handle this via similar means.
While I find myself doing this quite routinely in C working in combinatorics where speed is paramount and you want to restrict the overflow checking to where you know it might occur (in a fully debugged program, that is), this isn't the best way to go in your case.
You have excellent language capabilities in Haskell like Integer or SafeInt types which you can use internally during conversion to prevent overflow and an incorrect result. Your code will also be far more readable than what I showed. However, whenever you find the need for speed and you're working in a language that doesn't offer alternatives easily (other than binding in multiprecision integer libraries), the algebraic approach is good to keep in your toolkit for when it is needed.