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?

Ornamental

JFYI, this is one of the issues that are discussed in the PLAI textbook (see www.plai.org). Reading that will probably work out better than reading wikipedia. – Battleax

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.

Ascension

the reason this is associated with Lisp is that McCarthy (you may have heard of him) gave a description of Lisp evaluation in Lisp. – Interception

While the original Lisp was defined in terms of itself on paper (before it was ever implemented, which is an interesting story in its own right), AotI / SICP have probably done more to directly popularize the idea and (in particular) the term, which is what the question is about. Also, I have in fact heard of him. Was that really necessary? – Ascension

say what you want, the term is associated with Lisp via McCarthy's famous paper. Nice that a Scheme paper and some books pick up the idea 17 years later. – Interception

Alan Kay says: '... that was the big revelation to me when I was in graduate school - when I finally understood that the half page of code on the bottom of page 13 of the Lisp 1.5 manual was Lisp in itself. These were "Maxwell's Equations of Software!" This is the whole world of programming in a few lines that I can put my hand over.' – Interception

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.

Pannell

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.

Ornamental

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.

Chimpanzee

This is no Meta-circular interpreter. It isn't even an interpreter, it is a prerprocessor. :) – Peristalsis

@Peristalsis That's a sample meta feature. What about exec(object[, globals[, locals]]) - This function supports dynamic execution of Python code. – Chimpanzee

exec and friends, while being meta-level behavior, do no make a meta-circular interpreter. You can make meta-circular interpreters in languages with no meta-level facilities whatsoever. The thing about meta-circularity is: an interpreter for Language A written in Lanugage A. Eg, Pascal in Pascal, or Basic in Basic, or Smalltalk in Smalltalk. Using exec just passes on to the host Python and does not pose a new implementation of Python. pypy is a meta-circular Python, you should look at it! – Peristalsis

@Peristalsis Thanks for clarifying. PyPy still has an executable and a JIT that feeds machine code to the CPU, so i don't see how that's completely different from exec, which is also Python that executes Python. – Chimpanzee

It is! Python using exec always needs a “host” python. PyPy doesn't, it's standalone. exec is a host (ie, Python) facility, and hence you don't have an interpreter at all. Python (the host python) is handling everything for you. In PyPy, everything (method calling, variable access, you name it…) is implemented. For meta-circularity you need an interpreter written in the language you are interpreting (or compiler…). The c2 wiki has a nice discussion. – Peristalsis

Machine code doesn't care about its heritage, and Python's exec can run Python's exec without defining the magic. Even that page itself has circular logic problems, but my code meets both authors' claims. – Chimpanzee

meta-circularity is about interpreters (or compilers). Your code is neither, hence not meta-circular. However, it is using meta-programming – Peristalsis

@Peristalsis 'Lisp written in Lisp implements "eval" by calling "eval".' - Your linked definition. – Chimpanzee

If you mean the discussion on the C2-Wiki, see at the bottom the Person has the same question. You should look at the Metacircular Evaluator, where it is nicely discussed: … – Peristalsis

In Lisp/Scheme it is not Lisp written in Lisp implementing "eval" by calling "eval", when the first eval is not the same as the second eval. The called eval is not to be confused with Python's exec; the eval is implemented by the meta-circular interpreter and not the one of the host language. – Peristalsis

c2 said not having to implement details is the boon of writing a language in itself. Feel free to answer with your own code. – Chimpanzee

c2 is more a discussion wiki than an informational one. And yes, “not the details” is one of the merits. But for an interpreter there must be something. You can't say “I made a CPU” and just delegate Assembly to the actual one. – Peristalsis

Yes you can! E.g. Metascala needs a host to host itself. – Chimpanzee

Yes, but they actually have a compiler/interpreter. The equivalent of your implementation would be to just pass-through the guest JVM bytecodes to the host JVM, which would not be metacircular. – Peristalsis

exec interprets, compiles, and executes Python; it's inefficient and illogical to duplicate that functionality. PyPy only did it to add functionality. I could call compile and mess with the bytecode itself, or parse everything 1:1 first, but that would only obfuscate the claim that a metacircular interpreter is an interpreter that can interpret itself. – Chimpanzee

I think we should continue our discussion elsewhere :). For example #pypy on Freenode, or wherever you want. – Peristalsis

@Peristalsis "Using exec just passes on to the host Python and does not pose a new implementation of Python". Neither does Lisp's metacircular evaluator (as described by McCarthy and others). It punts many tasks including parsing, environment capture and garbage collection to the host Lisp implementation. – Branca

While the Lisp metacircular evaluator delegates a lot of aspects to its host Lisp, it indeed does the actual interpretation. Using Python's exec here does not. – Peristalsis

I think the issue here might be macro expressibility (comment/links). I may be abusing the term, but I think you could call Python "circularly" macro expressible, bc w/ exec/eval a Python interpreter can be expressed in Python without global rewrite rules. IIUC, @Peristalsis is basically arguing that a metacircular interpreter should only rely on a subset of language features that would not be sufficient to macro express the language. – Spooky

I only included the macro bit because that's the only use case i see for self-interpretation. – Chimpanzee

This still does not alter the fact that a program is not an interpreter if it passes the execution to something like exec. It's a wrapper. – Peristalsis

It's a mistake to call something a MetaCircularEvaluator just because it's written in itself. – Chimpanzee