What is the exact definition of a Metacircular Interpreter?

Question

Is it legal to call a C compiler written in C or a PHP interpreter written in PHP metacircular? Is this definition valid only for languages of a specific type, like Lisp? In short, what are the conditions that an interpreter should satisfy for being called Metacircular?

Answer 1

A metacircular interpreter is an interpreter written in a (possibly more basic) implementation of the same language. This is usually done to experiment with adding new features to a language, or creating a different dialect.

The reason this process is associated with Lisp is because of the highly lucid paper "The Art of the Interpreter", which shows several metacircular interpreters based on Scheme. (The paper is the kernel for the book SICP, and its fourth chapter works through others that create e.g. a lazily-evaluated Scheme.)

This is also vastly easier to do in a "homoiconic" language (a language whose code can be manipulated as data at runtime), such as Lisp, Prolog, and Forth.

As to your direct question - the C compiler wouldn't be an interpreter at all. A compiler written in its own language is 'self-hosting', which is a similar property, but more related to bootstrapping. A PHP interpreter in PHP probably wouldn't count, since you would likely be re-implementing a nontrivial amount of the language in the process. The major benefit of a conventional metacircular interpreter is that doing so isn't necessary - you can plug in the existing parser, garbage collection (if any), etc., and just write a top-level evaluator with different semantics. In Scheme or Prolog, it's often less than a page of code.

Answer 2

Here is a definition from the wikipedia page for metacircular:

A meta-circular evaluator is a special case of a self-interpreter in which the existing facilities of the parent interpreter are directly applied to the source code being interpreted, without any need for additional implementation.

So the answer is no in both cases:

• A C compiler is not an interpreter (evaluator). It translates a program from one form to another without executing it.
• A (hypothetical) PHP interpreter written in PHP would be a self interpreter, but not necessarily metacircular.

Answer 3

To complement the above answers: http://www.c2.com/cgi/wiki?MetaCircularEvaluator

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.

Answer 4

As i understand it, a metacircular interpreter is an interpreter that can interpret itself.

A compiler only translates code, and doesn't execute it.

Any Turing-complete language is mathematically able to emulate any logical computation, so here's an example using Python. Instead of using CPython to translate this code to CPU instructions and execute it, you could also use PyPy. The latter is bootstrapped, so fulfills some arbitrary criterion that some people use to define a metacircular interpreter.

"""
Metacircular Python interpreter with macro feature.
By Cees Timmerman, 14aug13.
"""

import re

def meta_python_exec(code):
    # Optional meta feature.
    re_macros = re.compile("^#define (\S+) ([^\r\n]+)", re.MULTILINE)
    macros = re_macros.findall(code)
    code = re_macros.sub("", code)
    for m in macros:
        code = code.replace(m[0], m[1])

    # Run the code.
    exec(code)

if __name__ == "__main__":
    #code = open("metacircular_overflow.py", "r").read()  # Causes a stack overflow in Python 3.2.3, but simply raises "RuntimeError: maximum recursion depth exceeded while calling a Python object" in Python 2.7.3.
    code = "#define 1 2\r\nprint(1 + 1)"
    meta_python_exec(code)

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.