Meta-Circular

A term describing an interpreter for a language L written in the same language L (or a subset thereof), said to be a meta-circular interpreter. More generally, any kind of metaprogram (implementation infrastructure or otherwise) written in a system S made to compute or reason about the meaning of programs written in system S is said to be meta-circular. Hence, you can have meta-circular compilers (what you do when bootstrapping a language implementation), meta-circular definitions of language extensions (see the CLOS MOP), meta-circular reasoning systems (NuPRL ACL2?), etc.

Simple Lisp dialects like Scheme are notable for allowing very nice and short meta-circular interpreters, and many Lisp books have tackled the exercise, to the point that it has been suggested that the proof of Gödel's theorem would have been easier if he had invented Lisp first.

The origin of the term is still unclear to us. (Question: who first used the term? Who popularized it?) It seems that the "circular" part is related to the interpreter or metaprogram being applicable to itself. Hence, you can run an instance of a meta-circular interpreter for L inside another instance, and so on, and get exponentially bigger and slower implementations of L (or possibly, implementations of dialects of L, each time with small variations or extensions).

Writing a meta-circular interpreter for a subset of one's favorite language (or at least, studying one) is a very common exercise to get familiar with the details of the semantics of the language, and the general techniques involved in implementing it. Such an exercise can help one understand a lot about parts of the language that one may otherwise appear to one as tricky or counter-intuitive, or worse, that one may misunderstand without even being conscious of it.

Besides the value in learning, meta-circular interpreters are useful for debugging programs or otherwise evaluating them in a controlled environment, for allowing dynamic evaluation despite the underlying implementation being a static compiler, for bootstrapping language features and extensions on top of an implementation of a subset of the language without those features, for experimenting with new language extensions or implementation techniques, for obtaining a compiler by applying a partial evaluator, for allowing a proof system to reason about the semantics of the full language, etc.

Here is one reference to the origin of the term: On Continuation-Passing Style

Metacircular interpreters, the term comes from Mc Carthy's implementation of Lisp in Lisp, are interpreters for CPS written of CPS. Metacircular interpreters are useful to understand the semantics of a language -- but they do not provide a full definition of that language nor a viable implementation. They are fun though."

If he is correct in his attribution it should be easy to verify as Mc Carthy's original Lisp book had a Lisp in Lisp.

This page is linked from: Methods of Reflection Topic