Mario’s comment really is brilliant. Theo’s is something I’ve thought about for ages but never got that crisply. Edit both posts together and submit to programming or splash essays?

Great distinction between compiler and interpreter! But I think you were abusing big O notation too much for my taste. I think the following definition gives the same results:

Given a program X and compiler/interpreter Y. If there exists such input for X which doesn't influence an output of Y then Y is a compiler, otherwise it is an interpreter.

The problem here is to define what is an output of an interpreter... like all possible states during an evaluation of X maybe.

Meh. So if I write a shell script that compiles your program and then runs it, my script will now be an interpreter?

I think that saying O(0) for an interpreter is kind of missing that an interpreter also has O(n) processing, eg replacing all the 1-char variable names with k-char variable names increases the interpreter's lexing time by k. And since both compiler and interpreter have O(f(n)) runtime, I don't think O() by itself captures the distinction here.

Also, compilers often have optimizations that are polynomial on size of input.

It seems to me that "compiling" is basically a special case of partial evaluators. You do some processing up front to get some speedup at runtime. And it isn't limited to constant factor speedup, since compilers are allowed to reduce O(n^2) code to O(1) runtime.

What seems to me a useful distinction is: "compiling" transforms a representation of a program into a different representation of a program. "interpreting" takes a representation of a program and produces actions/results.

Pretty much any program execution today is some mix of compiling and interpreting. Even running a "binary" can have a compilation step within the CPU to microcode.

Just, some ways of executing a program put more work into compiling before interpreting. And some types of compiling emit their output, rather than feeding it directly into an interpreter.

So, pragmatically, cpython is an "interpreter" because it reads source code and produces behavior, rather than a different representation of the source code. javac is a "compiler" because it transforms source code into another representation, which can then be read by the jvm interpreter.

Internally, jvm can have separate compilation and interpretation steps, but from a user's point of view, there's no way of getting a snapshot of its compilation output, so it's not usefully a compiler in that sense, even if it does use compiler techniques.

cpython can emit .pyc files, so it is a compiler in that sense, but it's still also an interpreter, and mostly used as an interpreter.

golang is just a compiler, it doesn't do any interpreting. The interpreting is done by the target architecture.

Felix beat me to the punch. Really Etaniel in the previous entry already did, ahead of everyone else, but he expressed it somewhat obliquely and only outlined the compiler side of it. Mario’s comment was an excellently observed corollary, but the fact that compilers run in time proportional to the size of the input program isn’t definitive, it just follows from the fact that a compiler takes a program as input and produces another program as its output. Likewise for an interpreter, it follows from the fact that an interpreter produces its input program’s output as its output. The fundamental definitions of a compiler and interpreter are those, that they take a program as input but a compiler produces another program as output and an interpreter produces the program’s output as its output. And as Felix said, in practice almost all programs we think of as interpreters contain a compiler stage, because the original language is almost never a convenient form of the program to interpret… but now I’m just repeating his comment.