4 ms·

> Mind proving? Which part? That interpreter must be implemented in a Turing-complete language? Well, it is pretty much a definition of a Turing completeness,

by sklogic 10y ago

> Mind proving? Which part? That interpreter must be implemented in a Turing-complete language? Well, it is pretty much a definition of a Turing completeness, it is provable by implementing an interpreter for a Turing machine, lambda calculus or any other equivalent system. Or you do not understand why compiler does not need a Turing complete language? Look at Compcert for example. A total language is more than enough. And even this is an overkill for a majority of compilers, which are nothing but a chain of trivial single-pass rewrites.

AnimalMuppet 10y ago
> Which part? Sorry, I should have clarified. I meant both. (Fortunately, you answered both...) Re your answer on the first part: I could have an interpreter for a non-Turing-complete language. An interpreter for that would not necessarily have to be Turing-complete, would it? Second point: Um, could you ELI5 what the difference between a total language and a Turing-complete language is?
- sklogic 10y ago
  > I could have an interpreter for a non-Turing-complete language Of course, but even this is pretty hard, much harder than compilation of an equivalent language. > the difference between a total language and a Turing-complete language is? For a total language you can always guarantee termination (which is impossible for a Turing complete one, see "halting problem"). In a total language recursive calls are only allowed for the arguments that are strict sub-structures of the caller arguments, which is perfectly ok for any imaginable AST or IR rewrite. Also, most of the compiler transforms don't even need this, they should rather be expressed declaratively, as non-iterative term rewriting systems.
  - AnimalMuppet 10y ago
    > > I could have an interpreter for a non-Turing-complete language > Of course, but even this is pretty hard, much harder than compilation of an equivalent language. Why? The compiler has to emit code. All the interpreter has to do is emit code and then execute the emitted code, which seems to me to be trivial. (Um, for some rather loose definition of "trivial". I am aware that there are issues of either 1) modifying the executable memory, 2) executing data memory, or 3) dynamically loading executable code. But I don't see that those justify "much harder". Am I missing something?) > For a total language you can always guarantee termination (which is impossible for a Turing complete one, see "halting problem"). I see. And, ideally, you'd like your compiler to always terminate. And you can't guarantee that for your interpreted language (unless the target language is total), because the program being interpreted could never terminate.
    - sklogic 10y ago
      If you defer the actual execution of the code to something else - another VM, a CPU directly, whatever, it is not an interpreter, it is just a compiler. Definitely not the kind of interpreters being discussed in this thread. If you have to implement this VM interpreter and all the runtime on your own, this is exactly where the hard part starts.
      - AnimalMuppet 10y ago
        So by "interpreter" you mean "sandboxing interpreter" or something like it? OK, I can buy that doing that is harder than just emitting code...
        sklogic 10y ago
        By interpreters here I mean this kind: https://news.ycombinator.com/item?id=11755303 https://news.ycombinator.com/item?id=11755303 I.e., an ad hoc AST-level interpretation, flat VM interpreters, tracing JITs, etc.

by sklogic 10y ago

AnimalMuppet 10y ago

> Which part? Sorry, I should have clarified. I meant both. (Fortunately, you answered both...) Re your answer on the first part: I could have an interpreter for a non-Turing-complete language. An interpreter for that would not necessarily have to be Turing-complete, would it? Second point: Um, could you ELI5 what the difference between a total language and a Turing-complete language is?

sklogic 10y ago
> I could have an interpreter for a non-Turing-complete language Of course, but even this is pretty hard, much harder than compilation of an equivalent language. > the difference between a total language and a Turing-complete language is? For a total language you can always guarantee termination (which is impossible for a Turing complete one, see "halting problem"). In a total language recursive calls are only allowed for the arguments that are strict sub-structures of the caller arguments, which is perfectly ok for any imaginable AST or IR rewrite. Also, most of the compiler transforms don't even need this, they should rather be expressed declaratively, as non-iterative term rewriting systems.
- AnimalMuppet 10y ago
  > > I could have an interpreter for a non-Turing-complete language > Of course, but even this is pretty hard, much harder than compilation of an equivalent language. Why? The compiler has to emit code. All the interpreter has to do is emit code and then execute the emitted code, which seems to me to be trivial. (Um, for some rather loose definition of "trivial". I am aware that there are issues of either 1) modifying the executable memory, 2) executing data memory, or 3) dynamically loading executable code. But I don't see that those justify "much harder". Am I missing something?) > For a total language you can always guarantee termination (which is impossible for a Turing complete one, see "halting problem"). I see. And, ideally, you'd like your compiler to always terminate. And you can't guarantee that for your interpreted language (unless the target language is total), because the program being interpreted could never terminate.
  - sklogic 10y ago
    If you defer the actual execution of the code to something else - another VM, a CPU directly, whatever, it is not an interpreter, it is just a compiler. Definitely not the kind of interpreters being discussed in this thread. If you have to implement this VM interpreter and all the runtime on your own, this is exactly where the hard part starts.
    - AnimalMuppet 10y ago
      So by "interpreter" you mean "sandboxing interpreter" or something like it? OK, I can buy that doing that is harder than just emitting code...
      - sklogic 10y ago
        By interpreters here I mean this kind: https://news.ycombinator.com/item?id=11755303 https://news.ycombinator.com/item?id=11755303 I.e., an ad hoc AST-level interpretation, flat VM interpreters, tracing JITs, etc.