4 ms·

Sorry for the shameless plug, but about a year ago I started a series of articles on how to write a simple interpreter called "Let's Build A Simple Interpreter.

by rspivak 10y ago

Sorry for the shameless plug, but about a year ago I started a series of articles on how to write a simple interpreter called "Let's Build A Simple Interpreter." Take a look, it might be something that you may like: Part 1: https://ruslanspivak.com/lsbasi-part1/ https://ruslanspivak.com/lsbasi-part1/ ... Part 9: https://ruslanspivak.com/lsbasi-part9/ https://ruslanspivak.com/lsbasi-part9/

sklogic 10y ago
Interpreters are inherently very complex, far more complicated than compilers. It is a bit harsh to start learning this subject with an interpreter.
- striking 10y ago
  I'd say interpreters are less complex than compilers. Even compiling down to byte code and interpreting that isn't as difficult as writing something that actually outputs optimized code that runs on bare metal. There are some very complex interpreters out there, but they have different goals than simple interpreters or optimizing compilers (see: Erlang, LuaJIT, Ruby, etc.)
  - sklogic 10y ago
    > something that actually outputs optimized code 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.
- SomeCallMeTim 10y ago
  Sorry, but no. 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.
  - sklogic 10y ago
    > Sorry, but no. 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".
    - AnimalMuppet 10y ago
      > You can write a compiler in a non-Turing-complete language. This is impossible for an interpreter. Mind proving?
      - 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?

by rspivak 10y ago

sklogic 10y ago

Interpreters are inherently very complex, far more complicated than compilers. It is a bit harsh to start learning this subject with an interpreter.

striking 10y ago
I'd say interpreters are less complex than compilers. Even compiling down to byte code and interpreting that isn't as difficult as writing something that actually outputs optimized code that runs on bare metal. There are some very complex interpreters out there, but they have different goals than simple interpreters or optimizing compilers (see: Erlang, LuaJIT, Ruby, etc.)
- sklogic 10y ago
  > something that actually outputs optimized code 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.
SomeCallMeTim 10y ago
Sorry, but no. 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.
- sklogic 10y ago
  > Sorry, but no. 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".
  - AnimalMuppet 10y ago
    > You can write a compiler in a non-Turing-complete language. This is impossible for an interpreter. Mind proving?
    - 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?