Meta-circular evaluator: Difference between revisions

Edit links
From Wikipedia, the free encyclopedia
Browse history interactively
← Previous editNext edit →
Content deleted Content added
VisualWikitext
m →‎Examples: format only / capitalization
some references, second half still mostly unsourced
Line 1: Line 1:
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.<ref name=HOP>{{cite journal|last1=Reynolds|first1=John C.|title=Definitional Interpreters for Higher-Order Programming Languages|journal=Higher Order Symbolic Computation|date=August 1972|volume=11|issue=4|pages=363–397|doi=10.1023/A:1010027404223|url=http://www.cs.uml.edu/~giam/91.531/Textbooks/definterp.pdf|accessdate=14 April 2017}}</ref> Meta-circular evaluation is most prominent in the context of [[Lisp (programming language)|Lisp]].<ref name=HOP/> 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.<ref name=SICP/>
⚫
{{refimprove|date=September 2008}}
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.


== History ==
The first appearance of the idea is in the dissertation of [[Corrado Böhm]] (1951).<ref>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 {{cite book | last = Knuth | first = D. E. | title = Selected Papers on Computer Languages | publisher = Center for the Study of Language and Information | location = Stanford, CA | year = 2003}}</ref> The definition of [[Lisp (programming language)|Lisp]] 1.5 (1961) by [[John McCarthy (computer scientist)|John McCarthy]],<ref>Definition of EVALQUOTE in [http://www.softwarepreservation.org/projects/LISP/book/LISP%201.5%20Programmers%20Manual.pdf Lisp 1.5 Programmer's Manual]</ref> where the evaluation rules of Lisp are described as a Lisp program, had additional impact.
{{See also|History of compiler construction}}
The dissertation of [[Corrado Böhm]]<ref>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</ref> describes the design of a [[self-hosting]] compiler.
<ref>{{cite book|first1=Donald E.|last1=Knuth|author1-link=Donald Knuth|first2=Luis Trabb|last2=Pardo|title=The early development of programming languages|date=August 1976|url=https://archive.org/stream/bitsavers_stanfordcs562EarlyDevelPgmgLangAug76_5916830/STAN-CS-76-562_EarlyDevelPgmgLang_Aug76#page/n35/mode/2up|page=36}}</ref> Due to the difficulty of compiling [[higher-order function]]s, many languages were instead defined via interpreters, most prominently Lisp.<ref name=HOP/><ref>{{cite book|url=http://www.softwarepreservation.org/projects/LISP/book/LISP%201.5%20Programmers%20Manual.pdf|page=10|chapter=A Universal LISP Function|date=1961|author1-link=John McCarthy (computer scientist)|first1=John|last1=McCarthy|title=Lisp 1.5 Programmer's Manual}}</ref>. The term itself was coined by [[John C. Reynolds]],<ref name=HOP/> and popularized through its use in the book [[Structure and Interpretation of Computer Programs]].<ref name=SICP>{{cite book|title=Structure and Interpretation of Computer Programs|chapter=The Metacircular Evaluator|url=http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-26.html#%_sec_4.1|publisher=MIT}}</ref><ref>{{cite web|last1=Harvey|first1=Brian|title=Why Structure and Interpretation of Computer Programs matters|url=https://people.eecs.berkeley.edu/~bh/sicp.html|website=people.eecs.berkeley.edu|accessdate=14 April 2017}}</ref>


== Self-interpreters ==
{{Quotation|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|{{cite web | title = The significance of the meta-circular interpreter | url = http://weblog.raganwald.com/2006/11/significance-of-meta-circular_22.html | date = 2006-11-22 | accessdate = 2011-01-22}}}}


A self-interpreter is a meta-circular interpreter where the host language is also the language being interpreted.<ref>{{cite web | title = The significance of the meta-circular interpreter | url = http://weblog.raganwald.com/2006/11/significance-of-meta-circular_22.html | date = 2006-11-22 | first1=Reginald|last1=Braithwaite| accessdate = 2011-01-22}}}}</ref> A self-interpreter displays a [[utm theorem|universal function]] for the language in question, and can be helpful in learning certain aspects of the language.<ref>{{cite journal|last1=Reynolds|first1=John C.|title=Definitional Interpreters Revisited|journal=Higher Order Symbolic Computation|date=1998|volume=11|issue=4|pages=356-7|doi=10.1023/A:1010075320153|url=http://homepages.inf.ed.ac.uk/wadler/papers/papers-we-love/reynolds-definitional-interpreters-revisited.pdf|accessdate=14 April 2017}}</ref> 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".<ref name=HOP/>
Meta-circular evaluation is discussed at length in section 4.1, titled [http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-26.html#%_sec_4.1 The Metacircular Evaluator], of the
[[Massachusetts Institute of Technology|MIT]] university textbook ''[[Structure and Interpretation of Computer Programs|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==
== Uses ==


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.
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.<ref>{{cite book|last1=Oriol|first1=Manuel|last2=Meyer|first2=Bertrand|title=Objects, Components, Models and Patterns: 47th International Conference, TOOLS EUROPE 2009, Zurich, Switzerland, June 29-July 3, 2009, Proceedings|publisher=Springer Science & Business Media|isbn=9783642025716|page=330|url=https://books.google.com/books?id=6RAlcYFn1SAC&pg=PA330&lpg=PA330&dq=meta+circular&#v=onepage&q=meta%20circular&f=false|accessdate=14 April 2017|language=en}}</ref> 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==
==Examples==
<!-- NOTE TO FUTURE EDITORS: these are by no means complete or even particularly informed lists -->
<!-- NOTE TO FUTURE EDITORS: these are by no means complete or even particularly informed lists -->
⚫
{{Refimprove|section|date=September 2008}}
Many languages have one or more meta-circular implementations. Here below is a partial list.
Many languages have one or more meta-circular implementations. Here below is a partial list.


Revision as of 21:41, 14 April 2017

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

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

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