The significance of the meta-circular interpreter

A self-interpreter is a “programming language interpreter written in the language it interprets.” A meta-circular interpreter is a special case of a self-interpreter that applies only to programs where the primary representation of the program is a primitive data type in the language itself (this property is called homoiconicity). Lisp is such a language because Lisp programs are lists of symbols and other lists. XSLT is such a language because XSLT programs are written in XML.

(If you have ever written an XSLT that transforms other XSLTs, then you immediately grasp the advantage of a meta-circular interpreter over an ‘ordinary’ self-interpreter: it is not just possible, but it is easy to write programs that write programs, because you don't have to fiddle with transforming each program into an abstract data structure (typically a tree) that can be manipulated by your program.)

This is interesting to both language theoreticians and hobbyists. But does it matter to those of us trying to get things done? What is the significance of meta-circular interpreters and self-interpreters?

The short answer is that if you are working on meta-programming, a self-interpreter makes all things not just possible, but practical. The lack of such an interpreter places a limit on how much you can accomplish using your implementation language.

Meta-programming

Let’s start our examination of the significance of self-interpreters with a review of meta-programming, or bottom-up programming. This is the practice of constructing a programming language tailored to your problem space. You get your language’s basics working by building it on top of a base, or implementation language, and then you build your solution in your solution language.

While meta-programming, you are working on two tiers either simultaneously or alternately: you work on expressing your solution in your solution language, and you work on the implementation (whether that be fun stuff like making it expressive or plumbing stuff like making it fast enough to be practical) in your implementation language.

An important and popular sub-domain of meta-programming is the practice of writing Domain-Specific Languages or DSLs. DSLs are solution languages tailored to resemble as closely as possible the human jargon of “domain experts.”

(Obie Fernandez has an excellent presentation on the rationale for and construction of DSLs.)

DSLs are commonly cited as useful in areas where programmers who are not domain experts collaborate with domain experts who are not programmer. In my own experience, DSLs are also valuable even when the programmers are themselves the domain experts. My rule of thumb for whether a DSL would be worthy of consideration is to ask how two programmers discussing the solution to a problem over an IM client would talk. If their language would closely resemble the natural constructs and idioms of their chosen implementation language, there is no need for a DSL.

This is not always the case. A very classic example is that of SQL. SQL is a DSL designed for programmers to express relational algebra rather than the imperative steps for performing queries and updates. Although complex cases are impenetrable to the journeyman, its general form closely follows the way even a non-technical person would express their thoughts about data that is stored in tables.

Another example of a successful DSL for programmers is the regular expression engine present in almost every language (whether baked in or as a commonly available library). Programmers do not discuss searching for text patterns in terms of backtracking and lookup tables and loops unless they are implementing a search library themselves.

Programmers talk about matching the string ‘Nokia’ followed by four digits, a forward slash, and two numbers separated by a period in the User-Agent Header. Regular expressions, while imperfect, match the way programmers think and talk about text matching much more closely than writing out the most efficient steps using strstr and for loops.

What about the meta-circular interpreter?

Meta-circular interpreters are nothing new. Lisp is most famous for its meta-circular interpreter. But do you know that one of the world’s most popular programming languages has the next best thing, a self-interpreter? The C programming language’s compiler is written in C. That’s interesting. But why is it significant?

Well, instead of heading up the ‘power continuum’ and talking about Lisp, let’s stay with C for a moment. If you’re a C programmer and you become very, very interested in building a better programming language, you have in your hands the tool to make changes as you see fit.

You might, for example, start with a pre-processor and implement the first version of your C++ language by mechanically translating a C++ program to C. Or you might bootstrap your C++ language by writing a compiler for C++ in C. Because you have in your hands all of the tools for going from source to running program, you can enhance and change its behaviour exactly as you please.

When a language is not implemented in itself, you have limitations on your ability to create new forms. One might argue that Lisp’s macros make it possible to build any other language paradigm on top of Lisp. This is partially correct, however macros alone are not a complete answer. Macros act to rewrite local sections of programs.

You cannot—to my knowledge—take a dialect of Lisp that does not support tail recursion and use macros to execute tail calls in constant space without rewriting every function using your macro. A similar argument holds for using macros to implement continuations. You must manually rewrite every function using your macros if you want to change the global behaviour of your program.

Manually blank every blank. This sounds an awful lot like something we can automate. Automatically transforming entire programs is the province of interpreters and compilers, isn’t it? If you wish to perform transformations that are global in scope, you want a custom interpreter. Of course, you can write one from scratch in your implementation language.

But… This sounds like we are headed towards the Turing Tar Pit. Isn’t it much easier to use the interpreter that’s built in? Implementation languages that provide an interpreter or compiler for themselves provide an industrial-strength, debugged platform for the construction of solution languages.

This is the other half of the power of Lisp: if you want to change deeper fundamental language features like whether you have a Lisp-1 or a Lisp-n, or whether all evaluation is lazy, or…, or…, or… you can, because Lisp interprets Lisp and Lisp compiles Lisp.

It is this reason that languages like Ruby, which is implemented mainly in C, provide less maximum power than languages like Smalltalk, which is implemented mainly in… Smalltalk. For example, there is talk—at this time—that continuations will be temporarily dropped from Ruby 1.9. If you have an application making heavy use of continuations, what is your upgrade path?

Of course, not everyone thinks they need all of a more powerful meta-programming implementation. You will have to decide for yourself whether a language without a meta-circular evaluator or self-interpreter offers other benefits that outweigh this significant feature.

Serving the self-interpreter to your canine companion

As Simen pointed out in a comment, Ruby does have a third-party project to interpret Ruby in Ruby called Rubinus. Assuming it graduates from its current status as an experimental work-in-progress, how is this different from having a self-interpreter baked into the language?

When a language is built on top of a self-interpreter, the language designers are forced to eat their own dog food.

Now it is not correct to say that Matz does not use Ruby. He does, and so he does eat his own dog food. And for the domains where he uses Ruby, he has optimized Ruby to be a useful tool. But since he doesn’t use Ruby to build Ruby, he does not have the same incentive to tune Ruby for the purpose of building languages.

An obvious example is Ruby’s performance. It is perfectly fine for building CRUD applications. However, it lacks really high performance when working with complex data structures in memory. This is the kind of thing that an interpreter or compiler has to do when parsing code or managing cactus stacks.

Imagine what would have happened had Matz become impatient waiting for Ruby to interpret itself when he was first building the language? I suggest that the implementation and language would both be tweaked to bring performance up an order of magnitude or more. Programmers are notoriously impatient with slow tools.

The implementation is not the only thing that improves when a language designer eats her own dog food by baking a self-interpreter into the language. The design of the language itself changes. Larry Wall has said that “Languages differ not so much in what they make possible, but in what they make easy.” When a designer builds their new language in itself, the language invariably makes building languages easy.

So I suggest that the presence of a self-interpreter baked right into the language, not bolted on as an after-thought forces a language to be useful for building solution languages.

(This is not a broad criticism of Ruby, or a suggestion that Ruby is not an excellent tool for building a wide variety of useful solution languages. I’m just trying to point out the salient distinction between baking a self-interpreter into a language from the beginning and bolting one on the side.)

But I’m a tool maven, not a language maven

Of course you are. So tell me, how does Eclipse do all of its magic with Java, a language lacking a self-interpreter?

The answer is here. The Eclipse team based Eclipse on VisualAge for Smalltalk. They were more than familiar with the benefits of having a self-interpreter, so they wrote most of one in themselves, in Java. Self-interpreters are also the basis for building advanced tools.

Labels: lispy, popular

  ¶ 6:23 PM