Rust's big step function was to offer memory safety at compile time through the use of static analysis borrowed and grown out of prior efforts such as Cyclone, a research programming language formulated as a safe subset of C.
In other words, Rust has solved the halting problem since the static checking of array bounds is undecidable in the general case!
No one is making that claim.
For arrays, this problem is not computable at compile time, hence the sarcastic remark that, IF THE ABOVE DEFINITION IS TAKEN AT FACE VALUE, Rust must have solved the halting problem. Downvoters are so dumb here.
Why are you shouting? That's what twits do. You don't want to be a twit, do you? Read the site guidelines, emphasis is done with italicized text marked up with an * at the beginning and another * at the end.
But to respond to the topic at hand: Are you familiar with the distinction between sound (what Rust aims for) and complete analyses?
https://stackoverflow.com/questions/28389371/why-does-rust-c...
> Rust's big step function was to offer memory safety at compile time through the use of static analysis borrowed and grown out of prior efforts such as Cyclone, a research programming language formulated as a safe subset of C.
It is absolutely true that memory safety is offered at compile time in Rust which is a novel thing. You then pivoted this to start talking about bounds safety of arrays which is a strawman interpretation of what was written.
"Memory safety—the property that makes software devoid of weaknesses such as buffer overflows, double-frees, and similar issues—has been a popular topic in software communities over the past decade"
And the buffer overflows are not detected statically except for the cases when the compiler can prove them. And Rust proponents keep ignoring the topic of this subthread, which is memory safety by static analysis.
RefCell enforces memory safety too by doing the lifetime enforcement at runtime by using UnsafeCell to provide certain semantics. But the compiler ensures that the RefCell itself still has correct lifetimes and is used correctly, resulting in a compile time guarantee that the code that’s run is memory safe.
https://blog.adacore.com/memory-safety-in-rust
Notice that in-bounds indexing is included, same as in the definition from this submission that I quoted at you.
Firstly lets attack the direct claim. The reason you'd reduce to the halting problem is via Rice's theorem. But, Rice only matters if we want to allow exactly all the programs with the desired semantics. In practice what you do is either allow some incorrect programs too (like C++ does, that's what IFNDR is about, now some programs have no defined behaviour at all, but oh well, at least they compiled) or you reject some correct programs too (as Rust does). Now what we're doing is merely difficult rather than provably impossible, and people do difficult things all the time.
This is an important choice (and indeed there's a third option but it's silly, you could do both, rejecting some correct programs while allowing some incorrect ones, the worst of both worlds) but in neither case do we need to solve an impossible problem.
Now, a brief aside on what Rust is actually doing here, because it'll be useful in a moment. Rust's compiler does not need to perform a static bounds check on array index, what Rust's compiler needs to statically check is only that somebody wrote the runtime check. This satisfies the requirement.
But now back to laughing at you. While in Rust it's common to have fallible bounds checks at runtime (only their presence being tested at compile time) in WUFFS it's common for all the checks to be at compile time and so to have your code rejected if the tools can't see why your indexing is always in bounds.
When WUFFS sees you've written arr[k] it considers this as a claim that you've proved 0 <= k < arr.len() if it can't see how you've proved that then your code is wrong, you get an error. The result is that you're going to write a bunch of math when you write software, but the good news is that instead of going unread because nobody reviewing the code bothered reading the maths the machine read your math and it runs a proof checker, so if you were wrong it won't compile.
Edited: Fix off-by-one error
fn f(n : usize) -> usize {
if n == 0 {
10
} else if n % 32327 == 0 {
1
}
else {
f(n-1)
}
}
fn main() {
let a = [1,2,3,4,5];
let n = f(12312);
println!("{:?}", a[n]);
}An index OOB error? Here, it's important to remember the Rust panic is still memory safe. Perhaps you should read the article, or read up on what undefined behavior is?[0] Here, the Rust behavior is very well defined. It will either abort or unwind.[1]
If you prefer different behavior, there is the get method on slices.[2]
[0]: https://en.wikipedia.org/wiki/Undefined_behavior [1]: https://doc.rust-lang.org/reference/panic.html [2]: https://doc.rust-lang.org/std/primitive.slice.html#method.ge...
We understand you're saying it's not possible in the general case to assert that all memory accesses are in bounds. Instead of that, if you ensure all memory accesses are either in bounds or that they at least do not violate memory safety, you've achieved the requirement of "memory safety", regardless of runtime inputs.
Oh, I read it.
Rust, and for that matter, the person to whom you are replying, above, never claimed that Rust could statically check array bounds. You created that straw-man. Yes, Rust does use static analysis, as one important method to achieve memory safety, but Rust doesn't require static analysis in every instance for it to be Rust's big step function, or for Rust to achieve memory safety.
Yes, certain elements of memory safety can only be achieved at runtime. Fine? But using static analysis to achieve certain elements of memory safety at compile time is obviously better where possible, rather than only at runtime, such as re: Java or Fil-C?
Static analysis has a specific meaning, and rote insertion of bounds checking isn't it.
The equivalent of vector[i] in Rust is Vex::get_unchecked, which is marked as unsafe, not the default that people reach for normally.
I refuted that point by pointing out that the same process, if done manually in C++, would not be considered "static analysis that provides memory safety for array access".
C++ can have UB, compilable non-unsafe Rust can’t, that’s what static analysis of memory safety is.
Main point here is you don’t know (and refuse to learn) new knowledge.
A panic is not a violation of memory safety; if you wanted to violate memory safety you'd need to have caused that deref to succeed, and println to spit out the result.
EDIT: let me guess, did the panic message include "index out of bounds: the len is 5 but the index is 10"?
Pfft, the simply typed lambda calculus solved the halting problem back in 1940.