Meta-circular evaluator#Self-interpretation in total programming languages

{{See also|History of compiler construction}}

The dissertation of Corrado Böhm

{{cite journal

|last1=Böhm

|first1=Corrado

|title=Calculatrices digitales. Du déchiffrage des formules logico-mathématiques par la machine même dans la conception du programme

|date=1954

|journal=Ann. Mat. Pura Appl.

|volume=4

|issue=37

|pages=1–51|author1-link=Corrado Böhm

}}

describes the design of a self-hosting compiler.{{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}} Due to the difficulty of compiling higher-order functions, many languages were instead defined via interpreters, most prominently Lisp.{{cite book|chapter-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}} The term itself was coined by John C. Reynolds, and popularized through its use in the book Structure and Interpretation of Computer Programs.{{cite book

|publisher=MIT

|title=Structure and Interpretation of Computer Programs

|chapter=The Metacircular Evaluator

|chapter-url=https://mitp-content-server.mit.edu/books/content/sectbyfn/books_pres_0/6515/sicp.zip/full-text/book/book-Z-H-26.html#%_sec_4.1

|first1=Harold

|last1=Abelson

|author-link1=Harold Abelson

|first2=Gerald

|last2=Sussman

|author-link2=Gerald Jay Sussman

|first3=Julie

|last3=Sussman

|orig-date=First published 1984 (1st ed.)

|publication-date=1996

|access-date=2025-01-03

|url-status=live

|archive-url=https://web.archive.org/web/20240429234153/https://mitp-content-server.mit.edu/books/content/sectbyfn/books_pres_0/6515/sicp.zip/full-text/book/book-Z-H-26.html#%_sec_4.1

|archive-date=2024-04-29

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

A self-interpreter is a meta-circular interpreter where the host language is also the language being interpreted.{{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}} A self-interpreter displays a universal function for the language in question, and can be helpful in learning certain aspects of the language. 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".

This part is based on Section 3.2.4 of Danvy's thesis.{{cite thesis|title=An Analytical Approach to Programs as Data Objects|author=Danvy, Olivier|url=https://ebooks.au.dk/index.php/aul/catalog/book/214|year=2006|doi=10.7146/aul.214.152|isbn=9788775073948 }}

Here is the core of a self-evaluator for the $\backslash lambda$ calculus. The abstract syntax of the $\backslash lambda$ calculus is implemented as follows in OCaml, representing variables with their de Bruijn index, i.e., with their lexical offset (starting from 0):

type term = IND of int (* de Bruijn index *)

| ABS of term

| APP of term * term

The evaluator uses an environment:

type value = FUN of (value -> value)

let rec eval (t : term) (e : value list) : value =

match t with

IND n ->

List.nth e n

| ABS t' ->

FUN (fun v -> eval t' (v :: e))

| APP (t0, t1) ->

apply (eval t0 e) (eval t1 e)

and apply (FUN f : value) (a : value) =

f a

let main (t : term) : value =

eval t []

Values (of type value) conflate expressible values (the result of evaluating an expression in an environment) and denotable values (the values denoted by variables in the environment), a terminology that is due to Christopher Strachey.

{{cite tech report

|last1=Strachey

|first1=Christopher

|date=1967

|title=Fundamental Concepts in Programming Languages

|doi=10.1023/A:1010000313106}}

{{cite journal

|last1=Mosses

|first1=Peter D.

|date=2000

|title=A Foreword to 'Fundamental Concepts in Programming Languages'

|journal=Higher-Order and Symbolic Computation

|volume=13

|issue=1/2

|pages=7–9

|doi=10.1023/A:1010048229036|s2cid=39258759

|author1-link=Peter D. Mosses

}}

Environments are represented as lists of denotable values.

The core evaluator has three clauses:

• It maps a variable (represented with a de Bruijn index) into the value in the current environment at this index.
• It maps a syntactic function into a semantic function. (Applying a semantic function to an argument reduces to evaluating the body of the corresponding syntactic function in its lexical environment, extended with the argument.)
• It maps a syntactic application into a semantic application.

This evaluator is compositional in that

each of its recursive calls is made over a proper sub-part of the given

term. It is also higher order since the domain

of values is a function space.

In "Definitional Interpreters", Reynolds answered the question as to whether such a self-interpreter is well defined.

He answered in the negative because the evaluation strategy of the defined language (the source language) is determined by the evaluation strategy of the defining language (the meta-language).

If the meta-language follows call by value (as OCaml does), the source language follows call by value.

If the meta-language follows call by name (as Algol 60 does), the source language follows call by name.

And if the meta-language follows call by need (as Haskell does), the source language follows call by need.

In "Definitional Interpreters", Reynolds made a self-interpreter well defined by making it independent of the evaluation strategy of its defining language.

He fixed the evaluation strategy by transforming the self-interpreter into continuation-passing style, which is evaluation-strategy independent, as later captured in Gordon Plotkin's Independence Theorems.

{{cite journal

|last1=Plotkin

|first1=Gordon D.

|date=1975

|title=Call by name, call by value and the lambda-calculus

|journal=Theoretical Computer Science

|volume=1

|issue=2

|pages=125–159

|doi=10.1016/0304-3975(75)90017-1|author1-link=Gordon D. Plotkin

|doi-access=free

}}

Furthermore, because logical relations had yet to be discovered, Reynolds made the resulting continuation-passing evaluator first order by (1) closure-converting it and (2) defunctionalizing the continuation.

He pointed out the "machine-like quality" of the resulting interpreter, which is the origin of the CEK machine since Reynolds's CPS transformation was for call by value.

{{cite conference

|last1=Felleisen

|first1=Matthias

|author2-link=Daniel P. Friedman

|last2=Friedman

|first2=Daniel

|date=1986

|title=Control Operators, the SECD Machine, and the lambda-Calculus

|institution=Formal Description of Programming Concepts III, Elsevier Science Publishers B.V. (North-Holland)

|pages=193–217

|url=https://cs.indiana.edu/ftp/techreports/TR197.pdf|author1-link=Matthias Felleisen

}}

For call by name, these transformations map the self-interpreter to an early instance of the Krivine machine.

{{cite conference

|last1=Schmidt

|first1=David A.

|date=1980

|title=State transition machines for lambda calculus expressions

|chapter=State transition machines for lambda-calculus expressions

|series=Lecture Notes in Computer Science

|volume=94

|institution=Semantics-Directed Compiler Generation, LNCS 94

|pages=415–440

|doi=10.1007/3-540-10250-7_32|isbn=978-3-540-10250-2

|doi-access=free

}}

The SECD machine and many other abstract machines can be inter-derived this way.

{{cite conference

|last=Danvy

|first=Olivier

|date=2004

|title=A Rational Deconstruction of Landin's SECD Machine

|institution=Implementation and Application of Functional Languages, 16th International Workshop, IFL 2004, Revised Selected Papers, Lecture Notes in Computer Science 3474, Springer

|pages=52–71

|url=https://www.brics.dk/RS/03/33/BRICS-RS-03-33.pdf

|issn=0909-0878}}

{{cite journal

|last1=Ager

|first1=Mads Sig

|last2=Biernacki

|first2=Dariusz

|author3-link=Olivier Danvy

|last3=Danvy

|first3=Olivier

|last4=Midtgaard

|first4=Jan

|date=2003

|title=A Functional Correspondence between Evaluators and Abstract Machines

|journal=Brics Report Series

|volume=10

|issue=13

|institution=5th International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming (PPDP'03)

|pages=8–19

|doi=10.7146/brics.v10i13.21783|doi-access=free

}}

It is remarkable that the three most famous abstract machines for the $\backslash lambda$ calculus functionally correspond to the same self-interpreter.

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.{{cite book |last1=Riolo |first1=Rick |last2=Worzel |first2=William P. |last3=Kotanchek |first3=Mark |title=Genetic Programming Theory and Practice XII |date=4 June 2015 |publisher=Springer |isbn=978-3-319-16030-6|page=59 |url=https://books.google.com/books?id=rfDLCQAAQBAJ&pg=PA59 |access-date=8 September 2021 |language=en}} 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.Conor McBride (May 2003), [http://www.haskell.org/pipermail/haskell-cafe/2003-May/004343.html "on termination"] (posted to the Haskell-Cafe mailing list).Andrej Bauer (June 2014), [https://cstheory.stackexchange.com/q/24994 Answer to: A total language that only a Turing complete language can interpret] (posted to the Theoretical Computer Science StackExchange site) 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 $\backslash pi\backslash ,\backslash tau\; \backslash to\; \backslash tau$ as self-interpreters, where $\backslash pi\backslash ,\backslash tau$ is the type of representations of $\backslash tau$-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_ω.{{cite book |last1=Brown |first1=Matt |last2=Palsberg |first2=Jens |title=Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages |chapter=Breaking through the normalization barrier: A self-interpreter for f-omega |date=11 January 2016 |pages=5–17 |doi=10.1145/2837614.2837623 |isbn=9781450335492 |s2cid=14781370 |chapter-url=http://web.cs.ucla.edu/~palsberg/paper/popl16-full.pdf}}

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 $\backslash pi\backslash ,\backslash tau\; \backslash to\; \backslash pi\backslash ,\backslash tau$.{{cite book |last1=Brown |first1=Matt |last2=Palsberg |first2=Jens |title=Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages |chapter=Typed self-evaluation via intensional type functions |date=January 2017 |pages=415–428 |doi=10.1145/3009837.3009853|isbn=9781450346603 |doi-access=free }}

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.

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.{{cite book|last1=Oriol|first1=Manuel|author2-link=Bertrand Meyer |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&dq=meta+circular&pg=PA330|accessdate=14 April 2017|language=en|date=2009-06-29}} They are also useful for writing tools that are tightly integrated with the programming language, such as sophisticated debuggers.{{citation needed|date=April 2017}} 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|date=April 2017}}

{{More citations needed|section|date=September 2008}}

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:

• Lisp, 1958
• Scheme, 1975
• Pico, 1997[http://pico.vub.ac.be/mc/mccode/MCeval.html Meta-circular implementation of the Pico programming language]
• ActorScript, 2009?
• Clojure, 2007
• Forth, 1968
• PostScript, 1982
• Prolog, 1972
• TeX, based on virgin TeX, 1978
• Smalltalk, 1980
• Rebol, 1997
• Red, 2011
• Factor, 2003

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

• Java via Jikes RVM, Squawk, Maxine or [https://medium.com/graalvm/java-on-truffle-going-fully-metacircular-215531e3f840 GraalVM's Espresso]
• Scala via [https://github.com/lihaoyi/Metascala Metascala]
• JavaScript via [https://github.com/mozilla/narcissus Narcissus] or [https://github.com/NeilFraser/JS-Interpreter JS-Interpreter]
• Oz via Glinda
• Python via PyPy
• Ruby via Rubinius
• Lua via Metalua

• M-expression
• Homoiconicity
• Self-hosting compiler

{{reflist}}

• [http://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book.html Structure and Interpretation of Computer Programs (SICP)], online version of full book, accessed 2009-01-18.
• [https://github.com/lihaoyi/Metascala Metascala]

Category:Programming language implementation