Getting it right
Tim Bray has a good post up on binary search, but prefaces it with this:
Anyone who regards themselves as a serious programmer has internalized a lot of different ways of searching: hash tables, binary, and many different kinds of trees. I've used pretty well all of these seriously at some point, but for a decade or so, as far as can I recall I've used almost exclusively binary search, and I see no reason to change that. Herewith an essay for programmers, with fully-worked out examples in Java, on why. [Updated 39 months after publishing when I read with horror Josh Bloch’s exposé of a long-lurking bug. If we can’t get binary search right, what chance do we have with real software?]
As I said here, the code is fine. That type system you're using with Java? Not so much. Patrick Logan makes a related point here. The chances of getting software right will improve a whole heck of lot if we just stop using broken tools.
Comments
What does that have to do with type systems?
[Isaac Gouy] June 7, 2006 12:59:59.741
As I said here, the code is fine. That type system you're using with Java? ...
And as Greg Buchholz asked the first time - What does that have to do with type systems? Please explain.
Type System
[Ravi] June 7, 2006 13:14:27.614
Here's my complaint about this code's cause of potential failure.
If my type system gives me an integer type with upper and lower limits, I'd like it to throw an error when a computation exceeds the upper limit, not silently cycle thorugh to negative numbers. That is so ridiculously counter-intuitive I'm surprised more people have not objected to it.
The problem has everything to do with a type system that forces me to prematurely declare the type of variables but does not handle overflow and underflow gracefully.
[Isaac Gouy] June 7, 2006 19:07:51.980
Ravi does not handle overflow and underflow gracefully
Pretend for a moment that Java is a dynamic language, there are no type declarations and no compile-time type check. Integers would still underflow and overflow without raising an exception.
Pretend for a moment that you are using statically typed C# - integers still underflow and overflow without raising an exception. Now compile with the /checked option and underflow and overflow will raise an exception.
Just use Smalltalk
[ James Robertson] June 7, 2006 19:46:03.396
Comment by James Robertson
If you just use Smalltalk, you don't need to expend any thought on the problem at all.
[Daniel Berger] June 7, 2006 20:05:04.234
Isaac, agile languages typically auto-promote ints to large ints automatically. In Ruby, for example, Fixnums are automatically promoted to Bignums when the value exceeds 2**31 (assuming a 32-bit Ruby). So, your values *never* become unexpectedly negative. If your value exceeds a Bignum's maximum value, then an error is raised instead of wrapping.
[Isaac Gouy] June 7, 2006 23:54:21.271
I expect there's a real crisp definition for agile languages.
Daniel, agile languages typically don't provide ints.
They provide arbitrary precision integers - sometimes with a tagged representation for smaller values.
[Daniel Berger] June 8, 2006 0:02:13.845
Going pedantic on me now, eh Isaac? Why don't you do us all a favor and stop playing dumb.
say what you mean
[Isaac Gouy] June 8, 2006 19:54:12.682
Going pedantic on me now, eh Isaac?
Daniel, if you mean fixnmum say fixnum if you mean int say int.
There are language implementations that provide both arbitrary precision arithmetic as the default (with a tagged representation for small values) and machine integer formats.
Why don't you do us all a favor and stop playing dumb.
It would be smart to presume less about what others know or don't know.