Find the Bug
Here’s a pretty tricky bug I hunted down yesterday, with the help of oerjan on #haskell. If you weren’t there to see, it’s a lot of fun. Here’s the code:
foo n = product [24 - n .. 23] `div` product [1 .. n] bar n = length (takeWhile ((< 1000000) . foo) [1 .. n]) baz n = if bar n == n then n else bar n
And here’s the result:
cdsmith@devtools:~/haskell/projects$ ghci Strange.hs GHCi, version 6.7.20070703: http://www.haskell.org/ghc/ :? for help [1 of 1] Compiling Main ( Strange.hs, interpreted ) Ok, modules loaded: Main. *Main> bar 10 9 *Main> baz 10 10
The question: Why does bar 10 evaluate to something different from baz 10? By looking at the definition of baz, you might convince yourself that baz and bar do the same thing. Apparently not.
Scroll down for the answer.
The problem is numeric overflow. The standard library length function has a result type of Int. The intermediate result in foo is too large to fit in the data type Int. The bar function has type forall a. Integral a => a -> Int. When calling bar directly, this isn’t a problem because the argument defaults to type Integer and foo is evaluated entirely in arbitrary precision numbers. However, when baz is evaluated, there is a comparison bar n == n, so the result of bar must have the same type as its argument. The result is known to be Int because the return type of bar is not polymorphic. So the argument n must also be of type Int. Then foo's inferred type is Int -> Int, which causes the overflow.
All clear now?
If one wanted to take a lesson from this, it would be one of the following:
- Be careful with types.
- General purpose functions like
lengthshouldn’t use dangerous types likeInt. Intshould be made less dangerous by throwing an exception on overflow.
Let’s take a poll: which lesson do you draw from it? Post in the comments.
When ghci responds with simply ’10’ it hasn’t really given you a full answer as it hasn’t told you the type of the result. Seems to me it ought to also print out the type.
I’m always wary of letting the compiler infer numeric types for me, since (as you found) it can screw around with the semantics. You may not be the sort to put type annotations on every top-level declaration, but I think this code is a great argument for doing so — at the very least it forces you to think about what you want, and at best the type checker will often catch this sort of thing for you. Adding type annotations to the above code, one quickly runs into type errors — unless you make everything Int -> Int, which should (hopefully) give pause when doing something with (e.g.) large products.
Also see Data.List.genericLength.
The mistake was made in the Haskell 1.0 to 1.1 changes. The length function used to have the type genericLength does.
I strongly claim that there is no need to change the ‘length’ function. To get a ‘length’ result that would overflow Int you would need to fully traverse a list (i.e. the Haskell singly linked list) with more than 2 billion elements.
Essentially no one should be applying ‘length’ to such a long list, and there is ‘genericLength’ that covers this (and all other Integral) cases for the few people who do it.
The problem here is that ‘foo’ computes something up to 23! which is much bigger than Int’s 2^31. And he did not specify ‘Integer’ and he did not change the ‘default (Int,Integer)’ behavior (note that he is also using the interactive GHCI system). If I want to use numbers and not worry about defaulting then I put ‘default ()’ in the file.
As for an overflow checking Int, you could make a newtype that checked overflow. You could even make a type
data CheckedInt = I Int | Overflow | Underflow | DivideByZero | ….
and use it instead.
Hmm. If there’s one thing this example makes clear, it’s that the implications of defining length with type ([a] -> Int) go far beyond the range of values that will ever be returned by length. They also have to do with what you might want to do with the result of length, and the types of the other values in those computations. The simple fact that Int will never overflow its specified range is not enough to establish that Int is the correct type.
I’m sure there were reasons for the choice not to do length = genericLength; but they will have to do with performance. Absent the desire for performance optimizations, I have a hard time seeing why Int would be considered the “right” choice for length, as compared to (Integral a) => a. Ah well, everyone makes trade-offs.
No one’s yet taken up my favorite answer, which is that there’s something wrong with the Int type. The combination of (a) not defining the size of Int, and (b) permitting wrap-on-overflow basically means that the behavior of Int is undefined in certain cases. Unchecked overflow for types like Int32 and Word32 would be quite justifiable; but IMO unchecked overflow for Int is just plain wrong.
Well, here are the lessons I took from it:Like, whoa! Type inference can actually cause bugs? Dude. I thought it was meant to prevent them…
Maybe one should start by using an algorithm that’s less likely to overflow :-)
I’m generally not in favour of arithmetic throwing exceptions, but that’s largely down to my time spent doing scientific numeric stuff, where exceptions were a major pain. And Int has no equivalent of Infinity, so maybe that’s the least bad option.