Meta-circular evaluator

From Wikipedia, the free encyclopedia
  (Redirected from Metacircular Interpreter)
Jump to: navigation, search

In computing, a meta-circular evaluator or meta-circular interpreter 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[edit]

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[edit]

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[edit]

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[edit]

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[edit]

References[edit]

  1. ^ a b c d e Reynolds, John C. (August 1972). "Definitional Interpreters for Higher-Order Programming Languages" (PDF). Higher Order 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". Lisp 1.5 Programmer's Manual (PDF). 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 Symbolic Computation. 11 (4): 356–7. doi:10.1023/A:1010075320153. Retrieved 14 April 2017. 
  9. ^ Oriol, Manuel; Meyer, Bertrand. 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[edit]