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?

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.

And that is the magic of MetaCircularEvaluators: 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?

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)?

Most ForthLanguage 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: 

  : 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 [.)

--SamuelFalvo?

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?

--DavidMcLean?

EditText of this page (last edited December 13, 2012) or FindPage with title or text search