Self-interpreter
A self-interpreter is an interpreter written in the same language that it interprets. It may be metacircular.
Metacircular interpreters
An interpreter may be homoiconic, and it may use homoiconicity to represent its code as data. In this situation, the interpreter is called metacircular. In a metacircular interpreter, some interpreter operations are not implemented as interpreter behaviors, but by reusing behaviors of the host language. When an operation is not implemented, but passed through to the underlying host runtime, then the operation is absorbed by the interpreter. If instead the interpreter implements behaviors without reusing the host runtime, then the interpreter reifies the operation.
Non-metacircular interpreters can consider the question of whether to absorb or reify a particular behavior, too, but in a certain sense, non-homoiconic languages cannot absorb most behaviors.
Folklore
It used to be believed that self-interpreters only exist for languages that are sufficiently complex. Any Turing-complete language admits a self-interpreter. In contrast, legends claim that if a lambda calculus is strongly normalizing, then it cannot admit a self-interpreter. However, in [1], it is claimed that System Fω admits a self-interpreter.
It is, of course, trivial to design a language that is Turing-incomplete but capable of self-interpreting via adding a specific "self-interpreter" instruction, in the style of HQ9+. (That's InterpretMe)
Languages known for self-interpretation
- Prolog
- Subleq and other OISCs (multiple self-interpreters for it exist)
- brainfuck
- InterpretMe