Self-interpreter
|
|
A self-interpreter (frequently called meta-circular interpreter or meta-interpreter) is a programming language interpreter written in the language it interprets. An example would be a BASIC interpreter written in BASIC.
This may sound paradoxical; how can one implement a language in that language if it does't yet exist? However there is little mystery here. Languages are almost always "mocked up" in some other existing language and then later converted to a final form. In these cases the early mockups can be used to develop the source code to the language. Once the system is bootstrapped new versions of the language can be developed in the language itself.
A definition of a computer language is usually made in relation to an abstract machine (so-called operational semantics) or as a mathematical function (denotational semantics). A language can also be defined by an interpreter, whereby the semantics of the language in which the interpreter is defined is usually considered as given. The definition of a language by a self-interpreter is not well-founded (i.e., cannot be used to define a language), but a self-interpreter tells a reader a lot about the expressiveness and elegance of a language. It also enables the interpreter to interpret its own source code, the first step towards a reflective interpreter.
There are some languages that have a particularly nice and elegant self-interpreter, such as Lisp or Prolog. Much research on self-interpreters, in particular reflective interpreters, has been conducted in the context of the Scheme programming language, a dialect of Lisp. In general, however, any reasonably powerful (turing-complete) language allows the writing of its own interpreter.
The book Structure and Interpretation of Computer Programs presents a set of interesting examples of meta-circular interpretation for the Scheme programming language and variants thereof.
External links
- PaulGraham, "The Roots of Lisp" - http://www.paulgraham.com/rootsoflisp.html
- The book "Structure and Interpretation of Computer Programs" contains a chapter dedicated to self-interpreters (called Meta-Circular evaluators in this book) - http://mitpress.mit.edu/sicp/.
- The paper "A Simple Reflective Interpreter" (1992) by StanleyJefferson and DanielFriedman (see http://citeseer.nj.nec.com/jefferson92simple.html) contains an implementation of a minimal Scheme interpreter in Scheme such that every instance of the interpreter can be used to run another interpreter while providing access to the next higher level.
To see the modern outgrowth of such things, web search "reflective towers", or see "A Tutorial on Behavioral Reflection and its Implementation" at http://www2.parc.com/csl/groups/sda/projects/reflection96/docs/malenfant/ref96/ref96.html