4 ms·
> 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 langua
by 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 agoIf 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 agoSo 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 agoBy 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.