Meta Circular Evaluator

An evaluator that is written in the same language that it evaluates is said to be metacircular if and only if doing so short-circuits the need to specify the precise semantics, because the key language constructs are implemented by themselves, exactly like looking up a word in a dictionary and finding that the definition uses the original word. That's the "metacircular" part.

How is that different from ordinary recursion?

It's circular recursion. There is no termination condition. It's a chicken-and-the-egg kind of thing. (There's actually a hidden termination condition: the bootstrapping process.)

A C compiler written in C is not a Meta Circular Evaluator, because the compiler must specify extremely detailed and precise semantics for each and every construct. The fact that the compiler is written in the target language does not help at all; the same algorithms could be translated into Pascal or Java or Ada or Cobol, and it would still be a perfectly good C compiler.

By contrast, a Meta Circular Interpreter for Lisp can't be translated into a non-Lisp language. That's right, cannot be -- at least, not in any simple one-to one fashion. Lisp written in Lisp implements "eval" by calling "eval". But there is no "eval" in many other languages (and if there is, it has different semantics), so instead a completely new language system would have to be written, one which gives a detailed algorithm for "eval" -- which was not necessary in the metacircular case.

And that is the magic of Meta Circular Evaluators: they reflect an underlying magic of the languages in which they are possible.

So it's a mistake to call something a Meta Circular Evaluator just because it's written in itself; that's not sufficient. Boot Strapping is a minor kind of magic, but metacircularity is a more major kind of magic. Which is why the C world talks about "bootstrapping a C compiler", not about "metacircular C compilers".

I'm not sure that you can have a metacircular compiler in any language. Metacircular evaluators are interpreters, right?

That is in fact my understanding (except that a system that behaves as an interpreter can be transparently implemented as a compiler), but after the wars on the Homoiconic Languages pages, it seems likely that this would be contested, so a persuasive argument would be in order, not just an assertion.

There are some excellent documents out there about the Meta Circular Evaluator, based on Lisp Language:

Paul Graham, "The Roots of Lisp" - www.paulgraham.com

The book Structure And Interpretation Of Computer Programs contains a chapter dedicated to Meta Circular Evaluators ... although it gives a definition incompatible with the one given on this page.

The paper "A Simple Reflective Interpreter" (1992) by Stanley Jefferson and Daniel Friedman (see citeseer.nj.nec.com ) contains an implementation of a minimal Scheme Language interpreter in Scheme such that every instance of the interpreter can be used to run another interpreter while providing access to the next higher level. Also see Reflective Tower.

To see the modern outgrowth of such things, web search "reflective towers", or see "A Tutorial on Behavioral Reflection and its Implementation" at www2.parc.com

Are there examples of Meta Circular Evaluator other than in the Lisp family (CL, Scheme)?

Most Forth Language implementations use a non-extensible interpreter and compiler, because of You Aint Gonna Need It. So, when it comes time to extend the interpreter and/or compiler in a way that simple colon definitions or immediate words cannot, most folks implement their own interpreter and compiler, suitable extended for their needs, but otherwise relying on the same basic tools that the existing interpreter and compiler use.

For example, here is a simple metacircular interpreter in arbitrary dialect Forth:

myInterpreter

begin 32 word find dup if execute else number then again ;

And here would be a compiler:

my-]

begin 32 word find dup if dup immediate? if execute else compile then else compile-number then again ;

A word such as [ would be an immediate word, which manipulates the return stack (or in ANSI-like dialects, would change the state of a variable imaginatively called STATE) to break out of the compiler loop, while a word like ] usually is the compiler itself. This preserves Forth's [ and ] semantics. Of course, you'll also need to re-implement : and :NONAME as well, but these are rather trivial.

For a concrete example, here's how to change the compiler so that all words prefixed by the back-tick are POSTPONEd:

\ not tested code; but it would look/feel a lot like this.

create macro-buffer 80 allot : create-postpone-macro S" POSTPONE " macro-buffer 1+ swap move ( embed the "POSTPONE " part into the buffer ) count dup -rot macro-buffer 10 + swap move ( embed the name of the word after POSTPONE ) 9 + macro-buffer c! ; ( and set the length of the whole string. )

word-starts-with-`?

dup 1+ c@ [char] ` = ;

new-]

state on begin 32 word find dup if dup 0< if execute ( it was an immediate word ) else compile ( it wasn't an immediate, so compile it instead ) else word-starts-with-`? if compute-postpone-macro macro-buffer count evaluate else number literal then then state @ 0= until ;

:

(:) new-] ; ( most Forth systems have a word like (:), that implements the core of :
without actually invoking the compiler )

]

new-] ; immediate ( note this word compiled with the "new" :-compiler! )

And that should be it. Yeah, it's a bit more complex than just creating a reader macro in Lisp, but hey, when the whole thing compiles to maybe 300 bytes or less on a 32-bit system, you could afford some 15 of these things in memory before you even hit the complexity of the reader itself, let alone the interpreter and compiler logic. :-)

(Not sure who changed the ] to [ characters. In Forth, [ is used to enter into interpreter mode from inside a definition. This allows compile-time pre-computed constants with zero run-time overhead, like this: : abc blah [ 2 4 * 5 6 * + ] literal blort ;. Hence, ] is the entry-point to the compiler, NOT [.)


I'm sure I'm misunderstanding the definition somewhere, because as far as I can tell any dynamic language would inherently be metacircular, since they basically all have some sort of eval instruction.

def python_interpreter(code): exec code

def ruby_interpreter code eval code end

How is this any different from implementing a Lisp interpeter using Lisp's eval?

See original on c2.com