4 ms·

While I understand your position, none of this is new. I think this is one of the growing pains rust will have to survive. I once read a text about someone im

While I understand your position, none of this is new. I think this is one of the growing pains rust will have to survive. 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.

rightbyte 3y ago
> 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. 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?
- hyperman1 3y ago
  See the update at the end. The halting aspect comes from checking if a value is defined: when a return statement is executed, check that the expression being returned is filled in. In fact, it goes much wider, it has to check that every variable used has been defined and nothing final gets redefined. See for some interesting cases the examples at the start of https://docs.oracle.com/javase/specs/jls/se17/html/jls-16.html 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? } The famous Sufficiently Smart Compiler can decide the function always throws, and does not need a return statement. Let this_returns_true depend on deciding the halting problem, and there you are. Clearly, this level of analysis is out of reach for javac. The standard in this case just claims the then and else side can both be executed, so the return is required. If the else had a second throw, the compiler would not need the return.

rightbyte 3y ago

> 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. 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?

hyperman1 3y ago
See the update at the end. The halting aspect comes from checking if a value is defined: when a return statement is executed, check that the expression being returned is filled in. In fact, it goes much wider, it has to check that every variable used has been defined and nothing final gets redefined. See for some interesting cases the examples at the start of https://docs.oracle.com/javase/specs/jls/se17/html/jls-16.html 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? } The famous Sufficiently Smart Compiler can decide the function always throws, and does not need a return statement. Let this_returns_true depend on deciding the halting problem, and there you are. Clearly, this level of analysis is out of reach for javac. The standard in this case just claims the then and else side can both be executed, so the return is required. If the else had a second throw, the compiler would not need the return.