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.^[1] Meta-circular evaluation is most prominent in the context of Lisp.^[1] 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.^[2]

History[]

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

Self-interpreters[]

A self-interpreter is a meta-circular interpreter where the host language is also the language being interpreted.^[7] A self-interpreter displays a universal function for the language in question, and can be helpful in learning certain aspects of the language.^[8] 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".^[1]

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.^[9] 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.^[10][11] 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 ${\displaystyle \pi \,\tau \to \tau }$ as self-interpreters, where ${\displaystyle \pi \,\tau }$ is the type of representations of ${\displaystyle \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_ω.^[12] 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 ${\displaystyle \pi \,\tau \to \pi \,\tau }$.^[13] 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.^[14] They are also useful for writing tools that are tightly integrated with the programming language, such as sophisticated debuggers.^{[citation needed]} 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.^{[citation needed]}

Examples[]

This section needs additional citations for verification. Please help by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources:  –  ·  ·  · scholar · JSTOR (September 2008) (Learn how and when to remove this template message)

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, 1997^[15]
    • , 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 or GraalVM's Espresso
• Scala via Metascala
• JavaScript via Narcissus or JS-Interpreter
• Oz via Glinda
• Python via PyPy
• Ruby via Rubinius
• Lua via

See also[]

• M-expression
• Homoiconicity
• Self-hosting compiler

References[]

External links[]

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