Meta-circular evaluator

Edit links
From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Gregg-Irwin (talk | contribs) at 22:25, 14 August 2019 (Added Rebol and Red). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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

See also: History of compiler construction

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]

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.[9] 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

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:

Some languages with a meta-circular implementation via third parties:

See also

References

  1. ^ a b c d e Reynolds, John C. (August 1972). "Definitional Interpreters for Higher-Order Programming Languages" (PDF). Higher-Order and Symbolic Computation. 11 (4): 363–397. doi:10.1023/A:1010027404223. Retrieved 14 April 2017.
  2. ^ a b "The Metacircular Evaluator". Structure and Interpretation of Computer Programs. MIT.
  3. ^ 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
  4. ^ Knuth, Donald E.; Pardo, Luis Trabb (August 1976). The early development of programming languages. p. 36.
  5. ^ McCarthy, John (1961). "A Universal LISP Function" (PDF). Lisp 1.5 Programmer's Manual. p. 10.
  6. ^ Harvey, Brian. "Why Structure and Interpretation of Computer Programs matters". people.eecs.berkeley.edu. Retrieved 14 April 2017.
  7. ^ Braithwaite, Reginald (2006-11-22). "The significance of the meta-circular interpreter". Retrieved 2011-01-22.
  8. ^ Reynolds, John C. (1998). "Definitional Interpreters Revisited" (PDF). Higher-Order and Symbolic Computation. 11 (4): 356–7. doi:10.1023/A:1010075320153. Retrieved 14 April 2017.
  9. ^ Oriol, Manuel; Meyer, Bertrand (2009-06-29). Objects, Components, Models and Patterns: 47th International Conference, TOOLS EUROPE 2009, Zurich, Switzerland, June 29-July 3, 2009, Proceedings. Springer Science & Business Media. p. 330. ISBN 9783642025716. Retrieved 14 April 2017.
  10. ^ Meta-circular implementation of the Pico programming language

External links

Retrieved from "https://en.wikipedia.org/w/index.php?title=Meta-circular_evaluator&oldid=910852917"