7 ms·

The way I would sum up interpreters and compilers, trying to put it as concisely as possible: Step 1. Write a program that reads the input program into a data

The way I would sum up interpreters and compilers, trying to put it as concisely as possible: Step 1. Write a program that reads the input program into a data structure that exactly represents the language. You just wrote a parser. Step 2. Write a program that operates on the data structure from (1) to execute the program. You just wrote an interpreter. Step 3 (Optional): Write a program that converts the data structure from (1) into a different data structure that you can interpret more efficiently. You just wrote an optimizer. Step 4 (Optional): Keep iterating on (3) until the output of your optimizer is machine code. You just wrote a compiler. Not saying the above obviates the need for a book like this one (at all), I just had never thought of it in quite this way and wanted to write it down. :)

Arnavion 10y ago
Nit: The output does not have to be machine code to be considered a compiler.
- nickpsecurity 10y ago
  It can even be source code: source-to-source compiler.
  - cestith 10y ago
    That's technically true. Those are also known as translators, although they are technically no different from compilers. Something that compiles to an executable format for your environment is most likely to be actually called a compiler. Some "interpreters" are actually compiling to opcodes for a virtual machine then running on the virtual machine.
- clusmore 10y ago
  Yes, it took me a while to "realise" (or perhaps "accept") this as well. What is machine code? Code that a machine can execute natively? What if I built a machine that had primitive instructions for JavaScript? Then JavaScript would be machine code, and an X->JavaScript "transpiler" could be considered a "compiler". Now what if before building such a machine, I wanted to simulate one? I could write a "virtual" machine, which is really just a program that acts like a physical machine with native JavaScript instructions. Also known as a JavaScript interpreter.
  - briansteffens 10y ago
    Yeah, plus even when you get down to machine code, those instructions can be implemented as microcode in the CPU. Then you have things like the lisp machines. Or V8 compiling bits of javascript to machine code while it "interprets". What exactly defines a compiler gets pretty fuzzy.
  - cestith 10y ago
    You could write something that compiles down to JavaScript opcodes then run them in your JavaScript virtual machine. This is actually pretty similar to what Perl5 does. You wouldn't have to do that to have an interpreter, though. So your implementation of your "interpreter" fuzzes the line moreso because it indeed technically contains a compiler.
- taneq 10y ago
  What, then, is the difference between a compiler and an interpreter? Just that the compiler saves its output rather than executing it?
  - yoz-y 10y ago
    For me, the compiler takes input program in language A and spits out the same program in language B. An interpreter goes (more or less) line by line and executes what it reads. In theory, compilation is reversible, execution is not.
    - nv-vn 10y ago
      Minor nit-pick: an interpreter need not work line-by-line, but rather (more commonly?) AST-node-by-AST-node. This isn't necessarily true for BASIC interpreters or something resembling assembly, but in general the code is represented as a tree of parsed values by the time the interpreter starts running your code.
  - Patient0 10y ago
    I would define it as: when a compiler operates on its own source code, the resultant compiled compiler executes as fast as the original. When an interpreter evaluates its own source code, the resultant interpreted interpreter is an order of magnitude slower. This definition allows for things like "just in time" compilation, and rules out silly tricks like bundling an interpreter and some source code into an executable image.
    - taneq 10y ago
      So compilation is idempotent? That's pithy, I like it.
    - SixSigma 10y ago
      Until you get to the Forth family
      - bogomipz 10y ago
- haberman 10y ago
  I think in everyday usage, the most common thing that distinguishes the two is that a compiler saves its output in some standard format that some other piece of software is expected to understand. So for example, something like Babel for JS is considered a compiler, because its output is JavaScript, which is a standardized language. On the other hand, Python is not usually considered a compiler, even though it writes .pyc files to disk, because its output is bytecode that only Python itself is expected to understand. Even this is a little bit grey though, because we would say that Python contains a bytecode compiler as one of its components, but I don't think that most people would say that the Python binary is a compiler.
  - bretthoerner 10y ago
    > Python is not usually considered a compiler, even though it writes .pyc files to disk, because its output is bytecode that only Python itself is expected to understand. I'd disagree, simply because this is exactly what javac does too.
    - z92 10y ago
      But javac doesn't run it. It's run by "java". Therefore javac is called the compiler. If things were such that "java" runs all .java files and creates those .class files as bytecode cache, then java won't have been called a compiler. And similarly, if python had two different programs, one to create *.pyc files and the other runs it, the former one would have been called a python compiler.
    - haberman 10y ago
      Java bytecode is standardized. So any JVM implementing the spec should be able to interpret the output of javac: http://docs.oracle.com/javase/specs/jvms/se7/html/jvms-6.html#jvms-6.2 http://docs.oracle.com/javase/specs/jvms/se7/html/jvms-6.htm... Python bytecode on the other hand is not standardized: its bytecode is considered an implementation detail of CPython and can vary from version to version. Your example reinforces my point.
  - dismantlethesun 10y ago
theoh 10y ago
There's a lot of mystique and prestige around the idea of compilers. It doesn't help that parsing is a fairly untidy, complex process. You're definitely right in trying to present the overall functions in a much, much simpler way. My personal recommendation in this field is nanopass compiler architecture. It's a more manageable approach to the task of implementing a compiler, through the use of lots of incremental passes rather than a few heroic ones. http://andykeep.com/pubs/np-preprint.pdf http://andykeep.com/pubs/np-preprint.pdf NB "When a paper on the first nanopass framework was accepted for ICFP 2004, however, the program committee required the authors to refocus the paper on education because they did not believe the nanopass methodology was suitable for commercial compilers. They were principally concerned with the compile-time overhead of repeated traversals. This concern was impossible to refute at the time because the prototype infrastructure and implementation were not mature enough to put to the test."
- philiplu 10y ago
  Interesting. My first compiler experience, 40 years ago, could reasonably be considered nanopass. This was the IBM Fortran IV compiler on an 11/30 clone. IIRC, the code to compile was kept in the minuscule memory, while dozens of passes were pulled in from disk to move slowly from source to machine code. As a bonus, you could usually gauge how far you'd progressed by watching the pattern of the blinkenlights.
benibela 10y ago
>Step 2. Write a program that operates on the data structure from (1) to execute the program. You just wrote an interpreter. I did just that. The data structure matches the language exactly. It is also slow. The plan was to benchmark it and optimize the slowest parts, but they turn out to be all equally slow. It is better to skip this step and directly create some byte-code or something. Probably less work than changing it later
- haberman 10y ago
  Definitely. This wasn't meant to be an actual guide as much as a way of concisely explaining the terms. You'll almost always want byte-code of some kind if you want good performance.

Arnavion 10y ago

Nit: The output does not have to be machine code to be considered a compiler.

nickpsecurity 10y ago
It can even be source code: source-to-source compiler.
- cestith 10y ago
  That's technically true. Those are also known as translators, although they are technically no different from compilers. Something that compiles to an executable format for your environment is most likely to be actually called a compiler. Some "interpreters" are actually compiling to opcodes for a virtual machine then running on the virtual machine.
clusmore 10y ago
Yes, it took me a while to "realise" (or perhaps "accept") this as well. What is machine code? Code that a machine can execute natively? What if I built a machine that had primitive instructions for JavaScript? Then JavaScript would be machine code, and an X->JavaScript "transpiler" could be considered a "compiler". Now what if before building such a machine, I wanted to simulate one? I could write a "virtual" machine, which is really just a program that acts like a physical machine with native JavaScript instructions. Also known as a JavaScript interpreter.
- briansteffens 10y ago
  Yeah, plus even when you get down to machine code, those instructions can be implemented as microcode in the CPU. Then you have things like the lisp machines. Or V8 compiling bits of javascript to machine code while it "interprets". What exactly defines a compiler gets pretty fuzzy.
- cestith 10y ago
  You could write something that compiles down to JavaScript opcodes then run them in your JavaScript virtual machine. This is actually pretty similar to what Perl5 does. You wouldn't have to do that to have an interpreter, though. So your implementation of your "interpreter" fuzzes the line moreso because it indeed technically contains a compiler.
taneq 10y ago
What, then, is the difference between a compiler and an interpreter? Just that the compiler saves its output rather than executing it?
- yoz-y 10y ago
  For me, the compiler takes input program in language A and spits out the same program in language B. An interpreter goes (more or less) line by line and executes what it reads. In theory, compilation is reversible, execution is not.
  - nv-vn 10y ago
    Minor nit-pick: an interpreter need not work line-by-line, but rather (more commonly?) AST-node-by-AST-node. This isn't necessarily true for BASIC interpreters or something resembling assembly, but in general the code is represented as a tree of parsed values by the time the interpreter starts running your code.
- Patient0 10y ago
  I would define it as: when a compiler operates on its own source code, the resultant compiled compiler executes as fast as the original. When an interpreter evaluates its own source code, the resultant interpreted interpreter is an order of magnitude slower. This definition allows for things like "just in time" compilation, and rules out silly tricks like bundling an interpreter and some source code into an executable image.
  - taneq 10y ago
    So compilation is idempotent? That's pithy, I like it.
  - SixSigma 10y ago
    Until you get to the Forth family
    - bogomipz 10y ago
haberman 10y ago
I think in everyday usage, the most common thing that distinguishes the two is that a compiler saves its output in some standard format that some other piece of software is expected to understand. So for example, something like Babel for JS is considered a compiler, because its output is JavaScript, which is a standardized language. On the other hand, Python is not usually considered a compiler, even though it writes .pyc files to disk, because its output is bytecode that only Python itself is expected to understand. Even this is a little bit grey though, because we would say that Python contains a bytecode compiler as one of its components, but I don't think that most people would say that the Python binary is a compiler.
- bretthoerner 10y ago
  > Python is not usually considered a compiler, even though it writes .pyc files to disk, because its output is bytecode that only Python itself is expected to understand. I'd disagree, simply because this is exactly what javac does too.
  - z92 10y ago
    But javac doesn't run it. It's run by "java". Therefore javac is called the compiler. If things were such that "java" runs all .java files and creates those .class files as bytecode cache, then java won't have been called a compiler. And similarly, if python had two different programs, one to create *.pyc files and the other runs it, the former one would have been called a python compiler.
  - haberman 10y ago
    Java bytecode is standardized. So any JVM implementing the spec should be able to interpret the output of javac: http://docs.oracle.com/javase/specs/jvms/se7/html/jvms-6.html#jvms-6.2 http://docs.oracle.com/javase/specs/jvms/se7/html/jvms-6.htm... Python bytecode on the other hand is not standardized: its bytecode is considered an implementation detail of CPython and can vary from version to version. Your example reinforces my point.
- dismantlethesun 10y ago

theoh 10y ago

There's a lot of mystique and prestige around the idea of compilers. It doesn't help that parsing is a fairly untidy, complex process. You're definitely right in trying to present the overall functions in a much, much simpler way. My personal recommendation in this field is nanopass compiler architecture. It's a more manageable approach to the task of implementing a compiler, through the use of lots of incremental passes rather than a few heroic ones. http://andykeep.com/pubs/np-preprint.pdf http://andykeep.com/pubs/np-preprint.pdf NB "When a paper on the first nanopass framework was accepted for ICFP 2004, however, the program committee required the authors to refocus the paper on education because they did not believe the nanopass methodology was suitable for commercial compilers. They were principally concerned with the compile-time overhead of repeated traversals. This concern was impossible to refute at the time because the prototype infrastructure and implementation were not mature enough to put to the test."

philiplu 10y ago
Interesting. My first compiler experience, 40 years ago, could reasonably be considered nanopass. This was the IBM Fortran IV compiler on an 11/30 clone. IIRC, the code to compile was kept in the minuscule memory, while dozens of passes were pulled in from disk to move slowly from source to machine code. As a bonus, you could usually gauge how far you'd progressed by watching the pattern of the blinkenlights.

benibela 10y ago

>Step 2. Write a program that operates on the data structure from (1) to execute the program. You just wrote an interpreter. I did just that. The data structure matches the language exactly. It is also slow. The plan was to benchmark it and optimize the slowest parts, but they turn out to be all equally slow. It is better to skip this step and directly create some byte-code or something. Probably less work than changing it later

haberman 10y ago
Definitely. This wasn't meant to be an actual guide as much as a way of concisely explaining the terms. You'll almost always want byte-code of some kind if you want good performance.