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.

And '''that''' 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:

	* PaulGraham, "The Roots of Lisp" - http://www.paulgraham.com/rootsoflisp.html
	* GuySteele and GeraldSussman, "TheArtOfTheInterpreter"
	* The book StructureAndInterpretationOfComputerPrograms contains a chapter dedicated to MetaCircularEvaluator''''''s ... although it gives a definition incompatible with the one given on this page.
	* The paper "A Simple Reflective Interpreter" (1992) by StanleyJefferson and DanielFriedman (see http://citeseer.nj.nec.com/jefferson92simple.html) contains an implementation of a minimal SchemeLanguage 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 ReflectiveTower.

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