3-Lisp: an infinite tower of meta-circular performers

Accurate

3-lisp is a dialect of Lisp designed and implemented by Brian C. Smith as part of his PhD. thesis Procedural reflection in programming languages ​​(what this thesis calls "reflection" is now more commonly called "reification"). A 3-lisp program is conceptually executed by an interpreter written in 3-lisp which is itself executed by an interpreter written in 3-lisp and so on ad infinitum. This forms a (countably) infinite tower of meta-circular interpreters (v.i.). reflective lambda is a function that is executed one tower level above its caller. Reflective lambdas provide a very general language extension mechanism.

The code is here. Metacircular interpreters

An interpreter is a program that executes programs written in a programming language.

A meta-circular interpreter is an interpreter for a programming language written in this language. Metacircular interpreters can be used to clarify or define language semantics by reducing the full language to a sublanguage in which the interpreter is expressed. Historically, these definitional interpreters have become popular within the functional programming community, see classical definitional interpreters for higher-order programming languages. Some important techniques have been classified and studied within the framework of meta-circular interpretation, for example, the continuation passage style can be understood as a mechanism that makes meta-circular interpretation independent of the evaluation strategy: it allows a willing metalanguage to interpret a lazy object language and vice versa. As a by-product, a continuation pass-style interpreter is essentially a state machine and thus can be implemented in hardware, see The Scheme-79 chip. Similarly, the defunctionalization of higher-order function languages ​​provides them with first-order interpreters. But meta-circular interpreters also occur in imperative contexts, for example, the usual proof of the Böhm-Jacopini theorem (interestingly, it was Corrado Böhm who first introduced meta-circular interpreters in his thesis from 1954) for an Algol-like language a meta-circular interpreter expressed in a gotoless subset of the language, then specializes this interpreter for a particular program in the source language.

Given a language with a meta-circular interpreter, suppose the language is extended with a mechanism for trapping at the meta-level. For example, in a lisp-like language, this trap might be a new special form (reflect FORM) that directly executes (rather than interprets) FORM in the interpreter. Smith is primarily interested in reflexive powers (i.e., reification) achieved in this way, and it is clear that the meta-level trap provides a method of language extension very general: you can add new primitives, data types, flow control and sequencing operators, etc. But if you try to add reflection to an existing LISP meta-circular interpreter (e.g., see p. 13 of the LISP 1.5 Programmer's Handbook), you run into a problem: FORM cannot be run at the meta level, because at this level is not a form, but an S expression.

Meta-interpreting machine code

To understand the nature of the problem, consider a very simple case: object language is the machine language (or equivalently assembly language) of a processor. Suppose the machine code interpreter is wr...