[3] The dissertation of Corrado Böhm[4] describes the design of a self-hosting compiler.
[5] Due to the difficulty of compiling higher-order functions, many languages were instead defined via interpreters, most prominently Lisp.
[1][6] The term itself was coined by John C. Reynolds,[1] and popularized through its use in the book Structure and Interpretation of Computer Programs.
Addressing these issues produces the more general notion of a "definitional interpreter".
In "Definitional Interpreters", Reynolds answered the question as to whether such a self-interpreter is well defined.
[12] 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.
[13] For call by name, these transformations map the self-interpreter to an early instance of the Krivine machine.
[17] 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.
[18][19] 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.
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
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.
[22] They are also useful for writing tools that are tightly integrated with the programming language, such as sophisticated debuggers.