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 MetaCircularEvaluator
, 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 MetaCircularInterpreter
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.
is the magic of MetaCircularEvaluator
s: they reflect an underlying magic of the languages in which they are possible.
So it's a mistake to call something a MetaCircularEvaluator
just because it's written in itself; that's not sufficient. BootStrapping
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 HomoiconicLanguages 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 MetaCircularEvaluator
, based on LispLanguage
To see the modern outgrowth of such things, web search "reflective towers", or see "A Tutorial on Behavioral Reflection and its Implementation" at http://www2.parc.com/csl/groups/sda/projects/reflection96/docs/malenfant/ref96/ref96.html
Are there examples of MetaCircularEvaluator other than in the Lisp family (CL, Scheme)?
implementations use a non-extensible interpreter and compiler, because of YouAintGonnaNeedIt
. 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:
begin 32 word find dup if execute else number then again ;
And here would be a compiler:
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
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. )
dup 1+ c@ [char] ` = ;
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 )
if compute-postpone-macro macro-buffer count evaluate
else number literal
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 ruby_interpreter code
How is this any different from implementing a Lisp interpeter using Lisp's eval?