"I was shocked to learn that the binary search program that Bentley proved correct and subsequently tested in Chapter 5 of Programming Pearls contains a bug."
That's from Joshua Bloch's discovery in 2006 that Java's binary search implementation was broken: http://googleresearch.blogspot.com.es/2006/06/extra-extra-re...
Arguably addition (or any operation) that overflows with signed integers ought to cause some kind of SignedIntegerOverflow exception. If you want to do modulo mathematics in the set of [0, 2^n) then you should explictly use unsigned integers, which are defined to work that way.
So you could have "integer, range [a-b), exception on overflow" or "integer, 32-bit, unsigned, wrap" or "integer, 8-bit, signed, saturates" (the latter is useful in codecs and often available in assembly).
Don't remember how it handled overflow.
Yes, ranges work. They (and ordinary integers) throw exceptions on overflow:
type NonoverflowingByte is integer range 0..255;
type OverflowingByte is mod 256;
For saturating arithmetic, there doesn't seem to be built-in language support. (There isn't even a standard library package. That seems to be a bit of an omission. Isn't saturating arithmetic common in the kind of real-time environment where Ada is used?)
Ada so totally deserves to be better known.
I do wonder why it isn't. It's probably handicapped by its history: once people have written off a language they'll never look at it again, despite improvements to fix the very problems they fled.
As an Ada advocate, what does it do badly? String processing? Networking?
String processing is both really nice and a pain. Built-in strings are fixed size, but the `array<>` magic means you do string processing using functional style without needing to explicitly size anything. The string libraries are a bit of a mess, with `Wide_String` and `Wide_Wide_String`, because they made the same mistake as Java and Windows about UCS-2 vs Unicode.
The standard library is mostly really cool, but it makes the same mistake C++ does in that entries in collections are always initialised by copying, so you can't have collections of non-copyable objects. I forget the details but I think the last time I tried to do collections of pointers I couldn't make it work properly.
Ada's generics are awesome. Nested functions that work properly are awesome. The compilation time is awesome. Access semantics that prevent you leaking pointers to inner stack frames are awesome. in-out parameters are awesome (they mostly replace pointers). Being unable to pass a nested function to a procedure as a callback parameter is less awesome; the access semantics forbid it.
To my mind, though, the biggest showstopper in Ada is a technically fairly trivial thing: it's case insensitive. This means that any programmer used to case sensitive languages, which is basically any programmer, will have to drastically revamp their coding style to work with Ada, because none of the usual conventions about separating locals from globals by capitalisation work any more. It also makes Ada code look ugly to the untrained eye. It's hard to convert people when the first thing they say when looking at code is 'ugh'.
Cool breakdown. This isn't true anymore in C++11 with move semantics.
Also the expression functions only being in module specifications is probably due to their source code being needed to inline them.
def sum(a, b) when is_integer(a) and is_integer(b) do
a + b
end
def sum(a, b) when is_list(a) and is_list(b) do
a ++ b
end
def sum(a, b) when is_binary(a) and is_binary(b) do
a <> b
end
sum 1, 2
#=> 3
sum [1], [2]
#=> [1,2]
sum "a", "b"
#=> "ab"Are there any restriction on what the code in the guards can do?
But the guard code are just macros, so... ;)
But I do believe that Erlang underneath does have actual limits.
We can only work with the tools and techniques we've discovered so far. Later, we find situations or results that show our tools or techniques aren't correct or aren't good enough and we improve them to cover the new situations.
It would manifest itself with 32-bit integer indexes and with arrays of greater than 2^30 elements. So phooey. You can't even fit that many array elements into a 32-bit address space. And if you're in a 64-bit address space, you should be using 64-bit indexes.
Whine: way back in the 1960s, the IBM S/360 threw a fixed-point overflow exception (okay, to be pedantic, they called it a "program interruption", but it's the same idea) when you did that. Sadly, the Fortran compiler of the day masked it. And this same philosophy has carried over to today. About 99 times out of 100, fixed point overflow is bad, why is it being masked off?
Would this mean that Bentley's proof was in fact incorrect (i.e. not a valid proof at all) or that it simply didn't consider integer overflow for fixed size ints?
I wonder to what extent the implementation (i.e. the size of the integer type used) should affect the proof that an algorithm is correct?
Inside a formal system it's relatively easy to understand what's going on; the real difficulties are at the boundaries: how do we build a formal model of a real system, and how do we translate formal results back to the original system? It's a lot like programming: manipulating data is easy, the problems are getting the right data and interpreting what the output means.
In this case, the model didn't capture overflow; so the proof is valid for that model, but it's not a useful model for Java's ints.