While reading A.S. Tanenbaum's book "Structured Computer Organization", I had come to this paragraph. The text is about how interpretation of a program works.

The other technique is to write a program in L0 that takes programs in L1 as input data and carries them out by examining each instruction in turn and executing the equivalent sequence of L0 instructions directly. This technique does not require first generating a new program in L0. It is called interpretation and the program that carries it out is called an interpreter.ote

My question is; does this program have to be written in L0 Language, by means of lower level language? Can this program(interpreter) be written in L1 language and have its output to be L0 language?


I think the implication of your Tanenbaum quote is that there is no compiler for L1. In which case yes, the interpreter does have to be written in another language (how else would you run the interpreter?).[1] It doesn't have to be lower-level; you could write an interpreter for Haskell in ML, say, or vice-versa. You usually want to use a lower-level language, though, since interpretation is going to impose an order of magnitude speed (and size) overhead you need to win back in the speed of your interpreter for the language to be competitive.

In general, no. You can write an interpreter for any language L1 in L1, provided you also write a compiler for L1. Lisps are traditionally bootstrapped by: write an interpreter (a) for Lisp in some other language, then write a compiler (b) for Lisp in Lisp, executed by (a), then write an interpreter (c) for Lisp in Lisp, compiled by (b). Now you have a Lisp interpreter written in Lisp.

Having said that, a program that takes a program in L1 and produces a program in L0 is a compiler; it compiles to L0. All compilers compile to some other language[2] which in turn may be compiled some number of additional times, and then is interpreted either by hardware or by another program.

[1] Again, there are techniques for bootstrapping interpreters interpreted by themselves, but they all involve hand-written code in another language (or in the same language but compiled) and are a bit beyond this level.

[2] This is an over-simplification; optimization passes can be written as 'compilers' that compile to their source language and there are other uses for compilers that compile to the same language as the input. But for your purposes, think of a compiler as compiling to a different language than the source.


The output of an interpreter is not a program in any language. An interpreter executes the input program. Its output is the program's output. In contrast, a compiler produces a program in some assembly language, for an actual or a virtual computer (for example, Java compilers generate code for the Java virtual machine).

When writing interpreters, you don't want to use assembly language, since programs are harder to write in assembly language. Rather, you want either a higher-level language like Python or Ruby, or if you care about performance, a systems language like C or C++.

  • $\begingroup$ So if I understand it right, it is because it(as you wrote) executes instruction after instruction from L1 in L). If the interpreter was written in the same language(here in L1), there would be actually no need to have any interpreter. And I have another question I dont want to put into another section, since it is relevant to this. L1 and L0 langauges can't be that different. What does it mean? Thank you. $\endgroup$
    – Matti
    Sep 10 '13 at 17:50
  • 1
    $\begingroup$ Not necessarily, for example you could compile your L1-interpreter even if it is written in L1. This situation is not as ludicrous as would seem - perhaps your compiler only supports a subset of L1, while your interpreter supports L1 with some extensions. $\endgroup$ Sep 10 '13 at 17:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.