Interpretation

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

• The interpretation given to a representation -- for example, interpreting as a number something represented as a pattern of bits
• The action or process of executing a piece of software by a piece of software (as distinct from directly by the hardware of the computer).

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.

Interpreters

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

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

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

Last modified: Sun Oct 21 23:01:47 IST 2007