Meta-circular evaluator

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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

Self-interpretation in total programming languages[edit]

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 as self-interpreters, where is the type of representations of -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 .[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[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.[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[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 and Symbolic Computation. 11 (4): 363–397. doi:10.1023/A:1010027404223. S2CID 43352033. Archived from the original (PDF) on 9 August 2017. 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. S2CID 34126862. Retrieved 14 April 2017.
  9. ^ Riolo, Rick; Worzel, William P.; Kotanchek, Mark (4 June 2015). Genetic Programming Theory and Practice XII. Springer. p. 59. ISBN 978-3-319-16030-6. Retrieved 8 September 2021.
  10. ^ Conor McBride (May 2003), "on termination" (posted to the Haskell-Cafe mailing list).
  11. ^ Andrej Bauer (June 2014), Answer to: A total language that only a Turing complete language can interpret (posted to the Theoretical Computer Science StackExchange site)
  12. ^ Brown, Matt; Palsberg, Jens (11 January 2016). "Breaking through the normalization barrier: a self-interpreter for f-omega" (PDF). Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages: 5–17. doi:10.1145/2837614.2837623. ISBN 9781450335492. S2CID 14781370.
  13. ^ Brown, Matt; Palsberg, Jens (January 2017). "Typed self-evaluation via intensional type functions". Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages: 415–428. doi:10.1145/3009837.3009853. ISBN 9781450346603.
  14. ^ 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.
  15. ^ Meta-circular implementation of the Pico programming language

External links[edit]