Rust have too many underspecified behavior, and the only source of truth is the official implementation.
Everybody know the type system in rust is NP-complete. The compiler use different heuristics and hints to do a best effort solution. I can't imagine how this can be reimplemented
I once read a text about someone implementing C++ before it was standardized. Whenever something wasn't clear, he tried it on CFront. CFront would generally crash. That's a lot worse than rust today, and there are a lot of C++ compilers nevertheless.
For the NP-complete problem, here is how Java solved this: The compiler has to validate that every function's execution ends with a valid return statement. This is literally the halting problem, impossible for the compiler to solve.
As a way out of this conundrum, the java standard dictates the algorithm. It is conservative, so it rejects some valid programs. But it is part of the standard, so if one java compiler accepts a program, you know all the other ones will too. So all java compilers make the same mistakes, as required by the java standard. A compiler is simply not allowed to implement a better algorithm.
While it is a huge effort, gccrs will probably succeed, and help clarify the rust standard in the process. Real risks are more long term: gcc java slowly petered out. For rust, things seem better, as gccrs has a stable funding source.
Update: Java's problem/algorithm is not (only) the return statement. It is the requirement that every variable is defined before being used. You find it as 'definite assignement' in the compiler standard.
It is not the halting problem though. The compiler does not have to prove the return is ever reached. Just that the instruction pointer does not fall off the end of the function. Just check the branch targets one by one?
See for some interesting cases the examples at the start of https://docs.oracle.com/javase/specs/jls/se17/html/jls-16.ht...
Update: come to think of it, it probably is the halting problem simply for returning:
int somefunc(){
if(this_returns_true()){
throw Something();
}else{
// No throw here
}
// Do I need return 1 here?
}
C++ templates are Turing-complete, and GCC implements them just fine.
The idea that Rust requires a formal specification (outside very rare situations, like aeronautic firmware) is silly.
GCC supports various "flavors" of C, including fully standard compliant versions.
GNU extensions are all documented.
That is also the situation Rust currently is in. There is no Rust spec, only a reference manual for rustc.
People who complain about unspecified behavior in Rust (or, equally, about Rust's lack of a language spec) are not satisfied with mere documentation. They want something like the Java language specification and conformance test suite.
The underspecified part should not be a deal breaker, even though it's certainly a difficulty. But it will also be an opportunity to spot suboptimal implementation choices in rustc. Exposing these will improve the language as a whole.
The NP-complete problem is optimal register allocation (through graph coloring). Register allocation in itself is not NP-complete. You can always use a suboptimal but fast algorithm because optimizations are optional. On the other hand, type checking is not optional, so having to solve a NP-complete problem for that would indeed be problematic.
In the PR dug out by a sibling commenter, the improvement to the compiler was indeed to apply the workaround that the programmer had to do. I believe that the churn of new heuristics is going to become smaller, as presumably most of the low-hanging fruits have been harvested by now.
Not necessarily. There are plenty of NP-complete problems that can be solved optimally fast enough to be useful for the instances that actually come up in real world applications.
For example the Traveling Salesman Problem (TSP) is NP-complete, but there are exact solvers that run in reasonable time for instances of a few hundred vertices. That's fine if you are say a delivery company trying to plan the day's itinerary for one of your delivery trucks.
but... we don't want same sourcecode compile with one compiler implementation, but not the other... right?
When I say "under-specified", I meant something like this:
https://github.com/rust-lang/rust/pull/105300/
quote> I claim it's more correct as well because it fixes #104639.
There is no spec. Just a bunch of implementation-defined behavior. Without a spec, this would be a forever catching up game. It is not easy to come up with a spec -- the implement is filled with heuristics because the intrinsic NP-completeness.
It's not ideal, but I can live with it so long as when I write a program which compiles it has the desired behaviour. That's the problem in C++ and to a lesser extent C which ultimately falls out of this same constraint. In C++ it's easy to write programs which compiler A and compiler B will both compile but they have different results and neither of them is wrong. I have no use for this whatsoever.
If some Rust compilers say my program is unacceptable, and others build it correctly, obviously that's not brilliant news but I can choose whether to fix the program to be acceptable to more compilers, or not worry - the results at least are correct.
Implementations accepting different sets of inputs is certainly annoying, but acceptable as long as they are erring on the side of caution. We definitely don't want code to compile which is actually not type-safe. At a quick glance, the PR can be understood as automating a workaround that programmers had to do by themselves before.
> This PR (similarly, and building on top of #104765) allows RPITs and async fns to untangle their lifetime bounds to figure out the set of lifetimes that actually get caputed instead of falling back to a larger one or even 'static. For most cases it was was already possible for users to manually reorder their lifetimes to make their code compile, this PR just makes that automatic, as the order of generic params and bounds should not matter.
gccrs on the other hand, aims to be a full implementation with all those checkers.
More specifically they're aiming to steal the next gen borrow checker, not the current one