Meta-circular evaluator

In computing, a meta-circular evaluator is a special case of a self-interpreter in which the existing facilities of the parent interpreter are directly applied to the source code being interpreted, without any need for additional implementation. Meta-circular evaluation is most common in the context of homoiconic languages.

The first appearance of the idea is in the dissertation of Corrado Böhm (1951).^[1] The definition of Lisp 1.5 (1961) by John McCarthy,^[2] where the evaluation rules of Lisp are described as a Lisp program, had additional impact.

The difference between self-interpreters and meta-circular interpreters is that the latter restate language features in terms of the features themselves, instead of actually implementing them. (Circular definitions, in other words; hence the name). They depend on their host environment to give the features meaning.

— Reginald Braithwaite, "The significance of the meta-circular interpreter". 2006-11-22. Retrieved 2011-01-22.

Meta-circular evaluation is discussed at length in section 4.1, titled The Metacircular Evaluator, of the MIT university textbook Structure and Interpretation of Computer Programs (SICP). The core idea they present is two functions:

• Eval which takes as arguments an expression and an environment (bindings for variables) and produces either a primitive or a procedure and a list of arguments
• Apply which takes as arguments a procedure and a list of arguments to which the procedure should be applied and produces an expression and an environment

The two functions then call each other in circular fashion to fully evaluate a program.

Ramifications

Meta-circular implementations are suited to extending the language they are written in. 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 implementation.

Languages with a meta-circular implementation designed from the bottom up, in grouped chronological order:

• Lisp, 1958
  • Scheme, 1975
    • Pico, 1997^[3]
    • ActorScript, 2009?
  • Clojure, 2007
• Forth, 1968
  • PostScript, 1982
• Prolog, 1972
• TeX, based on virgin TeX, 1978
• Smalltalk, 1980
• Factor, 2003

Languages with a meta-circular implementation via third parties:

• Java via Jikes RVM, Squawk or Maxine
• Scala via Metascala
• JavaScript via Narcissus or JS-Interpreter
• Oz via Glinda
• Python via PyPy
• Ruby via Rubinius
• Lua via Metalua

See also

• M-expression
• Self-hosting compiler

References

1. C. Böhm, Calculatrices digitales. Du déchiffrage des formules logico-mathématiques par la machine même dans la conception du programme, Ann. Mat. Pura Appl. (4) 37 (1954) 1-51; see also the discussion of Böhm's contribution in D. Knuth, L.T. Pardo, The early development of programming languages, reprinted in Knuth, D. E. (2003). Selected Papers on Computer Languages. Stanford, CA: Center for the Study of Language and Information.
2. Definition of EVALQUOTE in Lisp 1.5 Programmer's Manual
3. Meta-circular implementation of the Pico programming language

External links

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