``Interpretation'' in Computer Science can have two meanings:

Although these two are distinct meanings, they are connected, because for a piece of software to interpret another, the software being interpreted must be represented in a way that the interpreter can use.


[Program and interpreter]
Program and interpreter

An interpreter is, of course, software itself, and so could be either executed directly by the computer's hardware (a compiled interpreter, or possibly one written directly in machine code), or by another interpreter. For purposes of describing software, the latter is more useful.

[Program and interpreter and interpreter's interpreter]
Program and interpreter
and interpreter's interpreter

However, if that is more useful, might it then be useful for the interpreter, itself, to be interpreted?

Metacircular interpreters

[Program and tower of interpreters]
Program and tower of interpreters

It is possible to envisage an infinite tower of such interpreters; of course, an infinite number of these would run infinitely slowly. This is little practical use in such a form; however, it is a useful model for the definition of programming languages: we define an interpreter in the language that it interprets.

To do this, we need a language in which programs in that language can be represented as data structures within that language. A classic example of such a language is Lisp.

Reflective interpreters

An interpreter is reflective if it provides primitive operators that pass the interpreter's state (such as the stack of the program it is interpreting) to the interpreted program, and to take data from the program and make into part of the program or its state.

Tower-reflective interpreters

An interpreter is tower-reflective if it passes back to the interpreted program a value which includes the interpreter itself, and the interpreter of that interpreter, and so on.

Defining a simple interpreter

The examples here will be given in Lisp; I have written a short introduction to Lisp for such purposes.

The examples will get re-written some time. I don't now like the way I wrote them long ago.

John C. G. Sturdy
[John's home] Last modified: Sun Oct 21 23:01:47 IST 2007