Bentley Overflow Bug

Joshua Bloch, whose departure can’t have been good for Sun, reports that most divide-and-conquer algorithms—including the binary search in Jon Bentley’s excellent Programming Pearls—are broken because of integer overflow bugs (via Tim Bray):

We programmers need all the help we can get, and we should never assume otherwise. Careful design is great. Testing is great. Formal methods are great. Code reviews are great. Static analysis is great. But none of these things alone are sufficient to eliminate bugs: They will always be with us. A bug can exist for half a century despite our best efforts to exterminate it. We must program carefully, defensively, and remain ever vigilant.

Good advice, but since all of the above failed in some of the simplest and most widely distributed code ever written, what hope do we have? Well, when static analysis is useless and humans can’t be trusted, it sounds like a job for the language. As the example illustrates, Java already does this with array bounds checking, and plenty of languages (even some compiled ones) automatically promote integers to avoid overflow problems.