3

I'm trying to understand the concept of meta-circular evaluator. According to Wikipedia

In computing, a meta-circular evaluator or meta-circular interpreter is an interpreter which defines each feature of the interpreted language using a similar facility of the interpreter's host language. For example, interpreting a lambda application may be implemented using function application.

In the context of Lisp, I think it means the interpreter implementation stores the program state in data structures familiar to those expressed by the syntax itself, i.e lists.

More generally, I would say the interpreter implementation uses the paradigm of the syntax to interpret the syntax. Also, it has nothing to do with the interpreter being implemented in the interpreted language (Lisp interpreter is typically written in C). Only the paradigm equivalency matters.

Let's consider Java Maxine Virtual Machine, the meta-circular JVM. Maxine JVM is written in Java. It's a JVM running inside a JVM. Again, the interpreter uses same paradigm as the interpreted language. Executable code expressed by Java objects is managed by executable code expressed by Java objects. Of course, the actual executable is byte code, but the abstract concept beyond it is what matters. Thus, I believe the Maxine may have been written in any language and still being considered as meta-circular, as long as the implementation matches OOP concepts and Java rules. Most obviously such language is Java itself. Yet here is one interesting conflict which I describe in the last paragraph, it really makes my head hurt!

This is how I understand what is meant by meta-circular evaluator in theory. But I don't really get the practical aspect. According to Wikipedia

In combination with an existing language implementation, meta-circular interpreters provide a baseline system from which to extend a language, either upwards by adding more features or downwards by compiling away features rather than interpreting them

What this actually means? How this comes or may be put into practice with Maxine Virtual Machine for example? How this is different from a function such as eval?

And if we go more philosophical, having two premises for meta-circular interpreter

  • The interpreter implementation language doesn't matter, paradigm equivalence does
  • At the execution level the concept of paradigm ceases to exists, everything being just bytes

What are the definitive boundaries of the meta-circularity? Where does this characteristic actually realizes? I'm probably way overthinking this, but I find it an interesting subject.

Tuomas Toivonen
  • 21,690
  • 47
  • 129
  • 225
  • I think you're missing the point here. If I write a complete or nearly complete interpreter for Java, in Java, then it qualifies. As for `eval`, from the wikipedia article you linked: "A self-interpreter displays a universal function for the language in question." – Jared Smith Apr 16 '18 at 17:15
  • Interesting question, but - can you please show your code? And tell us the exact problem you have? As it is now - your question is not a good fit for SO. – rsm Apr 16 '18 at 17:19
  • I'd like to politely disagree with Jared. My own take is that the magic of meta-circular evaluators blooms when the parse tree of the language is the same as the actual language. Only LISP family languages do this afaik. – Leonard Apr 16 '18 at 17:24
  • 4
    In Lisp a meta-circular interpreter is one that is written in Lisp itself. A Lisp interpreter written in C is not meta-circular. A Lisp interpreter executes Lisp source code, not byte code or similar. Generally it's more of a theoretical/pedagogical concept, since most practical Lisp interpreters are not meta-circular. Though one might use a Lisp compiler to create a Lisp interpreter. – Rainer Joswig Apr 16 '18 at 18:16
  • Consider two evaluators for a language x', written in some language x which is similar to x', and may be identical to it. In one of them function call in x' is implemented by function call in x, and so on. In the other, there is a compiler for x' which compiles to x86 machine code, and an emulator for the x86, written in x, runs this code, resulting in an evaluator for x. One of these is metacircular, the other isn't. –  Apr 16 '18 at 22:48

1 Answers1

1

Your Java-based analysis is off because

  • Java isn't the JVM.

  • Java is aped after Lisp. Lisps are compiled, to native code or a virtual machine similar to the JVM.

So, suppose a Lisp meta-circular interpreter is interpreting a function call. Sure, that function call is represented using the list syntax. The interpreter walks the list, evaluates the function and arguments (using itself recursively) and then performs the function call. How does it do that: by using apply on the function and list of arguments. That's supposedly what "meta-circular" means. The interpreter's programmer didn't have to write function application, but just borrowed it from the host language.

However, the interpreter isn't necessarily made of lists; it may be compiled Lisp code. It's not literally generating an (apply ...) form and handing it off to eval; it contains a compiled call to apply.

The meta-circular Lisp interpreter implicitly makes use of the host language in numerous ways. Firstly, it doesn't have its own reader; the host Lisp's reader is used and the interpreter is working on ready-made syntax. It doesn't have to reimplement symbol interning. If it needs to test whether a variable reference in the program matches a definition, it just uses the host's eq function to compare symbols.

"Meta-circular" is probably inspired by the idea that the interpreter can faithfully handle each one of the special forms of the host language, and so can implement it entirely. At that point it has gone "full circle": it can interpret its own implementation.

Meta-circular interpretation is used in education because it allows the evaluation model for a language to be expressed in the language itself. Well, not the evaluation mode; just an evaluation model, and usually a very inefficient one. For instance, it may offer a model of lexical environments which is an assoc list. (Whereas the compiled Lisp code that is running the interpreter doesn't use such a thing for its own lexical variables; it's actually putting variables into stack frames or closure vectors.)

Kaz
  • 55,781
  • 9
  • 100
  • 149