In Compiled and Interpreted Languages: Two Ways of Saying Tomato, I showed how any language can be implemented as an interpreter or a compiler. However, I was deliberately vague when defining how one might distinguish an “interpreter” from a “compiler”, in no small part because I couldn’t think of a crisp definition of the two terms. Although I wasn’t quite as vague as “I know it when I see it”, I was uncomfortably close.
It was thus with great interest that I read a comment on the post from a good friend, and language implementation veteran, Mario Wolczko. In a sense, Mario gave two ways of distinguishing compilers from interpreters, but I’m going to quote the one that made my jaw drop:
How to distinguish between a compiler and an interpreter? One way is to look at the time it takes. A compiler should run in time roughly proportional to the size of the source, whereas the runtime of an interpreter is determined by how much work the source program has to do for a given input. For example, suppose the source program reads a number and then has a loop whose trip count is this number. The time it takes to compile this program will be independent of the number, in contrast to the time it takes to interpret the program.
This is, in my opinion, a brilliant way of distinguishing interpreters from compilers.
In case his definition doesn’t click with you, let me try a minor variation (ab)using Big O notation. For a program P, we can consider the running time of a compiler to be O(n) where n is the size of the source code (e.g. lines of code [1]). In contrast, the running time of an interpreter is O(f(m)) where m is a concrete input [2] to the program and f() an evaluation function. O(n) grows linearly with n but O(f(m)) may have a non-linear relationship with m.
There are a couple of things I like about this definition. First, it makes clear that compilers run in ignorance of concrete inputs (there is no m in the Big O notation for a compiler above). Second, it makes clear that the running time of an interpreter relates to a specific concrete input, not the size of the program being interpreted, nor to every possible concrete input. If you’re used to compilers and interpreters, both facts are “obvious”, but I’ve never seen them defined so crisply before.
How does this style of definition work for the grey zone in between traditional compilers and interpreters? Some readers may have heard of partial evaluation, which takes a program, a concrete input, and partially compiles the program relative to that input. At first glance, that might sound like it has the same complexity as an interpreter, even though it feels like it should be more like a compiler.
Fortunately, I think a simple expansion of Mario’s definition shows the difference clearly: we just need to give separate Big O notations for the compile-time and run-time phases of different language implementation approaches:
| Compile-time | Run-time | |
|---|---|---|
| Compiler | O(n) | O(f(m)) |
| Interpreter | O(0) | O(f(m)) |
| Partial evaluator | O(g(m)) | O(f(m) - g(m)) |
g() is the partial evaluation function. The reason for separating f() and g() is that, in general, we can’t fully evaluate a program at compile-time (hence the “partial” part of “partial evaluation”). In other words, the compile-time evaluation is bounded such that g(m) ≤ f(m) [3]; the work done by the partial evaluator at compile-time is subtracted from the run-time. As this shows, a compiler has to do some work at compile-time, whereas an interpreter has to do none [4], and a partial evaluator has to do a lot of work.
Bringing it back to some of the examples from Compiled and Interpreted Languages: Two Ways of Saying Tomato, how might we classify, say, CPython?
| Compile-time | Run-time | |
|---|---|---|
| Compiler | O(n) | O(f(m)) |
| Interpreter | O(0) | O(f(m)) |
| Partial evaluator | O(g(m)) | O(f(m) - g(m)) |
| CPython | O(n) | O(f(m)) |
Since CPython has a compiler in, it’s O(n) at compile-time, but also O(f(m)) at run-time — the same time complexities as, say, clang or gcc! This isn’t quite as surprising as it may first seem. A compiler transforms a program to machine code which is directly executed by a CPU; a language implementation such as CPython contains a compiler which transforms a program to opcodes which are then executed by an evaluator. Roughly speaking, we would expect an evaluator to be a constant factor slower than CPU execution, and Big O notation deliberately removes such constant factors.
Now we can have a go at the various BF implementations from Compiled and Interpreted Languages: Two Ways of Saying Tomato:
| Compile-time | Run-time | |
|---|---|---|
| Compiler | O(n) | O(f(m)) |
| Interpreter | O(0) | O(f(m)) |
| Partial evaluator | O(g(m)) | O(f(m) - g(m)) |
| CPython | O(n) | O(f(m)) |
| 1: base | O(0) | O(f(m)) |
| 2: + bracket caching | O(n) | O(f(m)) |
| 3: + opcodes | O(n) | O(f(m)) |
| 4: + opcode bracket caching | O(n) | O(f(m)) |
| 5: + Add(n) | O(n) | O(f(m)) |
| 6: + Sub(n) / Left(n) / Right(n) | O(n) | O(f(m)) |
| 7: + Zero | O(n) | O(f(m)) |
| 8: reorganised | O(n) | O(f(m)) |
In the original blog post I said:
This raises an interesting question: when would you say our BF implementations moved from interpreted to compiled? I find it hard to pinpoint the transition definitively. The first BF implementation is definitely interpreted; and by the fifth I’d say it’s definitely compiled; but I’m not sure which of the intermediate stages can be stated as the definitive transition point. Rather, the intermediate stages get increasingly hard to classify with certainty.
Using our new definitions has forced me to be clear that even the second BF interpreter has “compiler” Big O notation!
Thanks again to Mario for giving me a definition that’s made my thoughts more concrete. If you’re interested in language implementation, please be sure to look at the Virtual Machines and Managed Runtimes course he gave, and which is freely available online — it’s a wonderful resource!
Acknowledgements: thanks to Mario Wolczko for comments.
Footnotes
This definition would also work for a number of other reasonable metrics, for example, the number of functions.
This definition would also work for a number of other reasonable metrics, for example, the number of functions.
To keep things simple I’m implicitly assuming that m is an integer.
To keep things simple I’m implicitly assuming that m is an integer.
Another way of looking at this would be to say that m is split into two parts: mstatic and mdynamic. Then the compile-time would be f(mstatic) and the run-time would be f(mdynamic).
Another way of looking at this would be to say that m is split into two parts: mstatic and mdynamic. Then the compile-time would be f(mstatic) and the run-time would be f(mdynamic).
There is a long-standing debate as to whether O(0) is equivalent to O(1) or not, since O(1) stands for any constant, which includes zero. If you feel more comfortable with an interpreter being defined as O(1), please feel free to make that substitution in your head for the rest of this post.
There is a long-standing debate as to whether O(0) is equivalent to O(1) or not, since O(1) stands for any constant, which includes zero. If you feel more comfortable with an interpreter being defined as O(1), please feel free to make that substitution in your head for the rest of this post.