raganwald
Wednesday, November 22, 2006
  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: ,

 

Comments on “The significance of the meta-circular interpreter:
Well, as a Lisper, I am really bored by those pop languages called Ruby and Python reinventing the Lisp wheel and making a lot of noise around that.
 
Do you Lispers really think that constantly making smart-ass comments about the allegedly superiority of Lisp makes you more liked?

I wouldn't use Lisp just because of the arrogance of it's community - even if the language would be able to hold the promises of it's followers (which it can't).
 
piss of jerk....
 
"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?"

Ruby now has Rubinius, which is written in Ruby, and it has continuations.
 
Heh, I feel like I am trying to be friends with two people who have gone through a bitter break-up!

How do I let you know I like you, Mr. Lisp as well as you, Ms Ruby, even though you seem to be quite upset with each other?

How do invite you both to my weblog party, but somehow keep one of you in the kitchen and the other in the living room so that you can each have a good time without going at it hammer and tongs?
 
Now about reinvention... I agree it is not productive to reinvent something. See Greenspun's Tenth Rule, which I quote loudly and often.

Developing ideas in ignorance of the body of knowledge we have already accumulated always seems to lead to half-measures and concepts with unpalatable limitations.

Without bringing Python and Ruby into it, I wonder if, on the other hand, there is value in reinterpreting the principles first implemented in Lisp?

For example, it seems to me that languages like Haskell and ML attempt to take ideas first articulated in Lisp and "turn the dial to eleven," elevating them to first-class themes.

What do you think? Do you see a distinction between reinvention and reinterpretation?
 
pjdelport has pointed out an interesting distinction:

The article confuses meta-circular interpreters somewhat with ones that are just self-hosting.

Things like C compilers written in C are not meta-circular[1]: they implement language features directly in terms of lower-level primitives.

By contrast, meta-circular interpreters restate language features in terms of the features themselves, instead of actually implementing them. (Circular definitions, in other words; hence the name). They depend on their host environment to give the features meaning.

[1] OK, this is almost completely true: minor things like string escape sequences are sometimes defined meta-circularly (as discussed in Ken Thompson's classic Reflections on Trusting Trust.

 
I learned Lisp young enough that "Lisp is implemented in itself!" didn't seem so shocking.

The great insight for me was reading TAOMOP and learning that CLOS was implemented in CLOS. That fried my brain a little bit, but in retrospect it probably shouldn't have.
 




<< Home
Reg Braithwaite


Recent Writing
Homoiconic Technical Writing / raganwald.posterous.com

Books
What I‘ve Learned From Failure / Kestrels, Quirky Birds, and Hopeless Egocentricity

Share
rewrite_rails / andand / unfold.rb / string_to_proc.rb / dsl_and_let.rb / comprehension.rb / lazy_lists.rb

Beauty
IS-STRICTLY-EQUIVALENT-TO-A / Spaghetti-Western Coding / Golf is a good program spoiled / Programming conventions as signals / Not all functions should be object methods

The Not So Big Software Design / Writing programs for people to read / Why Why Functional Programming Matters Matters / But Y would I want to do a thing like this?

Work
The single most important thing you must do to improve your programming career / The Naïve Approach to Hiring People / No Disrespect / Take control of your interview / Three tips for getting a job through a recruiter / My favourite interview question

Management
Exception Handling in Software Development / What if powerful languages and idioms only work for small teams? / Bricks / Which theory fits the evidence? / Still failing, still learning / What I’ve learned from failure

Notation
The unary ampersand in Ruby / (1..100).inject(&:+) / The challenge of teaching yourself a programming language / The significance of the meta-circular interpreter / Block-Structured Javascript / Haskell, Ruby and Infinity / Closures and Higher-Order Functions

Opinion
Why Apple is more expensive than Amazon / Why we are the biggest obstacles to our own growth / Is software the documentation of business process mistakes? / We have lost control of the apparatus / What I’ve Learned From Sales I, II, III

Whimsey
The Narcissism of Small Code Differences / Billy Martin’s Technique for Managing his Manager / Three stories about The Tao / Programming Language Stories / Why You Need a Degree to Work For BigCo

History
06/04 / 07/04 / 08/04 / 09/04 / 10/04 / 11/04 / 12/04 / 01/05 / 02/05 / 03/05 / 04/05 / 06/05 / 07/05 / 08/05 / 09/05 / 10/05 / 11/05 / 01/06 / 02/06 / 03/06 / 04/06 / 05/06 / 06/06 / 07/06 / 08/06 / 09/06 / 10/06 / 11/06 / 12/06 / 01/07 / 02/07 / 03/07 / 04/07 / 05/07 / 06/07 / 07/07 / 08/07 / 09/07 / 10/07 / 11/07 / 12/07 / 01/08 / 02/08 / 03/08 / 04/08 / 05/08 / 06/08 / 07/08 /