> That's a bummer. It seems doable, but maybe it is too complex.
In general, eliminating runtime bounds checking is solving the halting problem.
let v = [1, 2, 3];
if halts(some_program) { v[1000] } else { v[0] }
Of course, this doesn't meant that it's impossible in a subset of cases, e.g. people are doing work on fast range analysis for LLVM, which would be able to remove some of the bounds checks sometimes: http://code.google.com/p/range-analysis/ (that analysis also applies to the arithmetic, and apparently only makes things single-digit percent slower (3% iirc).)
> In general, eliminating runtime bounds checking is solving the halting problem.
Your example does not convince me that this follows. In cases where the compiler cannot statically prove which branch will be taken, I would expect it to require that either path can be executed without error (so in your example compilation would fail). But you could use static range propagation to allow code like this (given in C++ syntax since I'm a Rust novice):
void f(int x[], unsigned int n) {
n = min(len(x), n);
for (int i = 0; i < n; i++) {
x[i];
}
}
Maybe not the greatest example since I would hope that Rust+LLVM would hoist its internal bounds-check to emit something very much like the above anyway. I guess intuitively I just hope that there's more that can be done when it comes to static bounds-checking.
Well, if you throw the halting problem at it then all of your static analysis goes away since you can use general recursion to write arbitrarily typed expressions. That's why things like Idris have termination checkers.
In general, eliminating runtime bounds checking is solving the halting problem.
Of course, this doesn't meant that it's impossible in a subset of cases, e.g. people are doing work on fast range analysis for LLVM, which would be able to remove some of the bounds checks sometimes: http://code.google.com/p/range-analysis/ (that analysis also applies to the arithmetic, and apparently only makes things single-digit percent slower (3% iirc).)