There are some very complex interpreters out there, but they have different goals than simple interpreters or optimizing compilers (see: Erlang, LuaJIT, Ruby, etc.)
Optimisations might be difficult (some of them, not all). Yet, a straightforward compilation is trivial, far simpler than the simplest of possible interpreters.
And an unoptimised compiler is by far more simple than even an unoptimised interpreter.
Writing an interpreter is strictly a subset of writing a compiler. Instead of spitting out machine instructions, you can use your source language to execute actions directly.
Mind proving?
> Writing an interpreter is strictly a subset of writing a compiler.
What?!?
You can write a compiler in a non-Turing-complete language. This is impossible for an interpreter. So, how is it a "strict subset" now?
Also, interpreters must provide much more functionality than compilers. Compilers simply rewrite the code from one representation into another. Interpreters must take care about the runtime, about the operational semantics. It's much harder than a simple rewriting.
> Instead of spitting out machine instructions, you can use your source language to execute actions directly.
And the latter is many times more complicated than "spitting out machine instructions".
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.
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?
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.
> 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.
My impression comes from when I took a comparative programming languages class and we developed a Pascal interpreter.
I then took compiler design and over the course of two quarters implemented a compiler. Note I said "over TWO quarters." It took twice the time to create the compiler than the interpreter. A simple interpreter absolutely can be easier to write than a simple compiler.
That's what I'm talking about: The minimal requirements for writing an interpreter using a high level language (we used C++ -- this was 1988, so C++ before templates were a part of the language) are less complex than the minimal requirements for writing a compiler using a high level language (also C++, though with the addition of YACC and LEX).
The interpreter has to include a VM state, sure. But that state can be implemented in the state of the language you're using. I've written simple interpreters a half dozen times now -- very simple ones that I needed to run animations in games, or to script AI opponents, or to script UI layout and trigger UI interactions. The interpreted language was frequently barely Turing Complete, but I guarantee you that writing a compiler that spits out machine (or even assembly) code is much harder.
Among other things, you can rely on the host language itself to handle recursion. You can also create a "map" of global variables and, when the interpreter says to set a value, pull it out of the map.
I'm overgeneralizing for brevity, but I hope you see what I'm saying. Writing an interpreter for a simple language that maps well into the host language can actually be trivial -- the host language itself can provide much of the implementation.
Writing a compiler doesn't allow such shortcuts. You must code to the target machine architecture, not an arbitrarily complex (but well-mapped to the language) architecture stored in high level data structures. You must do all the hard work of reducing high level statements down to a sequence of low-level instructions.
If you're talking about writing an interpreter that spits out VM instructions (where it's basically performing a compile-to-vm), then sure, you're right: In that case you're writing a compiler and a VM and calling it an interpreter. Any real interpreter today would likely work this way, if only to be able to take advantage of LLVM -- and if you can use that, you can write your interpreter at exactly the same level of complexity as writing a compiler. The tasks would be equivalent.
If you're talking a transpiler that takes one high level language and spits out another high level language (thinking Babel, TypeScript, CoffeeScript, or even the early C++-to-C conversion tools), then sure, that would be even simpler than writing an interpreter.
If your task is just to write an interpreter, and the source and destinations languages are similar enough, then you can use shortcuts writing the interpreter (similar to writing the transpiler) that you just can't use writing a full compiler.