Meta-circular evaluator

In computing, a meta-circular evaluator (MCE) or meta-circular interpreter (MCI) is an interpreter which defines each feature of the interpreted language using a similar facility of the interpreter's host language. For example, interpreting a lambda application may be implemented using function application. Meta-circular evaluation is most prominent in the context of Lisp. A self-interpreter is a meta-circular interpreter where the interpreted language is nearly identical to the host language; the two terms are often used synonymously.

History

The dissertation of Corrado Böhm describes the design of a self-hosting compiler.
Due to the difficulty of compiling higher-order functions, many languages were instead defined via interpreters, most prominently Lisp. The term itself was coined by John C. Reynolds, and popularized through its use in the book '' Structure and Interpretation of Computer Programs''.

Self-interpreters

A self-interpreter is a meta-circular interpreter where the host language is also the language being interpreted. A self-interpreter displays a universal function for the language in question, and can be helpful in learning certain aspects of the language. A self-interpreter will provide a circular, vacuous definition of most language constructs and thus provides little insight into the interpreted language's semantics, for example evaluation strategy. Addressing these issues produces the more general notion of a "definitional interpreter".

Self-interpretation in total programming languages

Total functional programming languages that are strongly normalizing cannot be Turing complete, otherwise one could solve the halting problem by seeing if the program type-checks. That means that there are computable functions that cannot be defined in the total language. In particular it is impossible to define a self-interpreter in a total programming language, for example in any of the typed lambda calculi such as the simply typed lambda calculus, Jean-Yves Girard's System F, or Thierry Coquand's calculus of constructions. Here, by "self-interpreter" we mean a program that takes a source term representation in some plain format (such as a string of characters) and returns a representation of the corresponding normalized term. This impossibility result does not hold for other definitions of "self-interpreter".
For example, some authors have referred to functions of type $\pi\,\tau \to \tau$ as self-interpreters, where $\pi\,\tau$ is the type of representations of $\tau$-typed terms. To avoid confusion, we will refer to these functions as ''self-recognizers''.
Brown and Palsberg showed that self-recognizers could be defined in several strongly-normalizing languages, including System F and System F_ω.
This turned out to be possible because the types of encoded terms being reflected in the types of their representations prevents constructing a diagonal argument.
In their paper, Brown and Palsberg claim to disprove the "conventional wisdom" that self-interpretation is impossible (and they refer to Wikipedia as an example of the conventional wisdom), but what they actually disprove is the impossibility of self-recognizers, a distinct concept. In their follow-up work, they switch to the more specific "self-recognizer" terminology used here, notably distinguishing these from "self-evaluators", of type $\pi\,\tau \to \pi\,\tau$.
They also recognize that implementing self-evaluation seems harder than self-recognition, and leave the implementation of the former in a strongly-normalizing language as an open problem.

Uses

In combination with an existing language implementation, meta-circular interpreters provide a baseline system from which to extend a language, either upwards by adding more features or downwards by compiling away features rather than interpreting them. They are also useful for writing tools that are tightly integrated with the programming language, such as sophisticated debuggers. A language designed with a meta-circular implementation in mind is often more suited for building languages in general, even ones completely different from the host language.

Examples

Many languages have one or more meta-circular implementations. Here below is a partial list.

Some languages with a meta-circular implementation designed from the bottom up, in grouped chronological order:
* Lisp, 1958
** Scheme, 1975
*** Pico, 1997Meta-circular implementation of the Pico programming language
/ref>
*** ActorScript, 2009?
** Clojure, 2007
* Forth, 1968
** PostScript, 1982
* Prolog, 1972
* TeX, based on virgin TeX, 1978
* Smalltalk, 1980
* Rebol, 1997
** Red, 2011
* Factor, 2003

Some languages with a meta-circular implementation via third parties:
* Java via Jikes RVM, Squawk, Maxine o
GraalVM's Espresso
* Scala vi
Metascala
* JavaScript via Narcissus o
JS-Interpreter
* Oz via Glinda
* Python via PyPy
* Ruby via Rubinius
* Lua via Metalua

See also

* M-expression
* Homoiconicity
* Self-hosting compiler

References

{{reflist

External links

Structure and Interpretation of Computer Programs (SICP)
online version of full book, accessed 2009-01-18.

Metascala

Programming language implementation