4 ms·

I don't think this can end well. Rust have too many underspecified behavior, and the only source of truth is the official implementation. Everybody know the t

I don't think this can end well. 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

sanxiyn 4y ago
I note that Rust already has been reimplemented (mrustc), mostly by one person.
- j16sdiz 4y ago
  mrustc assume all rust code is valid and skips all those heuristics checks. gccrs on the other hand, aims to be a full implementation with all those checkers.
  - 3836293648 4y ago
    Gccrs does not aim to be a full implementation. They're aiming to be a good enough implementation that they can steal the last parts (the borrow checker) from rustc. More specifically they're aiming to steal the next gen borrow checker, not the current one
jmillikin 4y ago
GCC is first and foremost a compiler for GNU C, which is a set of unspecified extensions to C, which is a language that achieved near-universal adoption despite decades of competing mutually-incompatible implementations. 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.
- Vogtinator 4y ago
  You forgot the </sarcasm> tag. Or are you actually serious with your comment? GCC supports various "flavors" of C, including fully standard compliant versions. GNU extensions are all documented.
  - jmillikin 4y ago
    GCC by default runs in GNU C mode, which accepts constructs that are not valid in any version of ISO C. Its extensions are not part of the language spec, and the only way to discover their behavior is by reference to implementation-specific documentation/code. 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.
- anthk 4y ago
  Check GCC-ADA and Spark.
  - deleted 4y ago
    [deleted]
samus 4y ago
NP-completeness is not a problem at all. Compilers already solve multiple NP-complete problems in the course of compilation after all, for example register allocation. They require heuristics to be solved in a reasonable time, but the upside is that there is no gold standard since there are pathological cases for any heuristic. Presumably, a representative set of crates from the ecosystem will be chosen to find performance issues. 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.
- loicd 4y ago
  > Compilers already solve multiple NP-complete problems in the course of compilation after all, for example register allocation. 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.
  - samus 4y ago
    A less precise borrow checker can usually still be satisfied by adding workarounds, at the cost of performance of course. Adding redundant reference counting or increasing the lifetime of data and the duration of critical regions make the program slower. In this sense, improving the borrow checker is analogous to adding new analyses and optimizations passes to a compiler.
    - loicd 4y ago
      OK, I suppose I have to dig deeper into Rust to determine whether I really disagree with that, or maybe this is too vague. The question is: who applies your workarounds? If this is always the compiler, then I agree, but if the programmer has to do any work, then your analogy fails.
leni536 4y ago
The way it can end well is that the spec gets more and more precise due to the combined efforts of independent frontend implementers.
CJefferson 4y ago
C++'s type system is turing complete, and there seem to be plenty of successful independant implementations of that -- although they do often disagree on how many programs are executed.
hyperman1 4y ago
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 4y 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 4y 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.
efficax 4y ago
but that's exactly why multiple implementations are a good idea, because it will help encourage further specification and standardization of the unspecified and heuristic behaviors.

sanxiyn 4y ago

I note that Rust already has been reimplemented (mrustc), mostly by one person.

j16sdiz 4y ago
mrustc assume all rust code is valid and skips all those heuristics checks. gccrs on the other hand, aims to be a full implementation with all those checkers.
- 3836293648 4y ago
  Gccrs does not aim to be a full implementation. They're aiming to be a good enough implementation that they can steal the last parts (the borrow checker) from rustc. More specifically they're aiming to steal the next gen borrow checker, not the current one

jmillikin 4y ago

GCC is first and foremost a compiler for GNU C, which is a set of unspecified extensions to C, which is a language that achieved near-universal adoption despite decades of competing mutually-incompatible implementations. 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.

Vogtinator 4y ago
You forgot the </sarcasm> tag. Or are you actually serious with your comment? GCC supports various "flavors" of C, including fully standard compliant versions. GNU extensions are all documented.
- jmillikin 4y ago
  GCC by default runs in GNU C mode, which accepts constructs that are not valid in any version of ISO C. Its extensions are not part of the language spec, and the only way to discover their behavior is by reference to implementation-specific documentation/code. 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.
anthk 4y ago
Check GCC-ADA and Spark.
- deleted 4y ago
  [deleted]

samus 4y ago

NP-completeness is not a problem at all. Compilers already solve multiple NP-complete problems in the course of compilation after all, for example register allocation. They require heuristics to be solved in a reasonable time, but the upside is that there is no gold standard since there are pathological cases for any heuristic. Presumably, a representative set of crates from the ecosystem will be chosen to find performance issues. 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.

loicd 4y ago
> Compilers already solve multiple NP-complete problems in the course of compilation after all, for example register allocation. 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.
- samus 4y ago
  A less precise borrow checker can usually still be satisfied by adding workarounds, at the cost of performance of course. Adding redundant reference counting or increasing the lifetime of data and the duration of critical regions make the program slower. In this sense, improving the borrow checker is analogous to adding new analyses and optimizations passes to a compiler.
  - loicd 4y ago
    OK, I suppose I have to dig deeper into Rust to determine whether I really disagree with that, or maybe this is too vague. The question is: who applies your workarounds? If this is always the compiler, then I agree, but if the programmer has to do any work, then your analogy fails.

leni536 4y ago

The way it can end well is that the spec gets more and more precise due to the combined efforts of independent frontend implementers.

CJefferson 4y ago

C++'s type system is turing complete, and there seem to be plenty of successful independant implementations of that -- although they do often disagree on how many programs are executed.

hyperman1 4y ago

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 4y 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 4y 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.

efficax 4y ago

but that's exactly why multiple implementations are a good idea, because it will help encourage further specification and standardization of the unspecified and heuristic behaviors.