> 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.
If you have to implement this VM interpreter and all the runtime on your own, this is exactly where the hard part starts.
I.e., an ad hoc AST-level interpretation, flat VM interpreters, tracing JITs, etc.
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.