Request for feedback: hobbyist post on "the significance of the meta-circular interpreter."

Hello Lambdans:

Under the influence of tryptophan, I published a blog post giving a hobbyist's perspective on The Significance of the Meta-Circular Interpreter.

My blog's audience are mainly comprised of other hobbyists and professional programmers who dream of escape from their BigCo humdrum. As you would expect, the post lacks academic rigour and some feedback on factual errors would improve it greatly. One early version conflated self-hosting, self-interpreting, and meta-circular evaluation. Thanks to an early comment, I was able to revise the content.

What are your thoughts on the significance of languages that contain a meta-circular evaluator, a self-interpreter, or that are self-hosting? How could this post be improved (either from the perspective of accuracy or of advocacy?)

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

The idea of defining a

The idea of defining a language via an interpreter is one of the oldest and most powerful ideas in computer science, and it's great to make that as easy as possible. The granddaddy reference to this is John Reynolds's paper Definitional Interpreters for Higher Order Programming Languages.

However, you've got to be careful with the idea of circularity. It's not really possible to genuinely define a language in itself, because what a program does depends on what the language it's written in does -- and an interpreter is a program just like anything else. As a concrete example, if you write a small lambda calculus interpreter in direct style, then your interpreter will be strict or lazy depending on if the underlying language is strict or lazy.

But giving programmatic access to the compiler or interpreter (ie, parser, typechecker, code generator) is a really good idea. I think the only reason it doesn't happen more frequently is because most language implementations really suck -- they aren't modular, and each pass isn't a library with a clean and narrow interface.

A fixed point

Given any interpreter for a language, if you use it to interpret the source code for the interpreter, you end up with another interpreter. If we hold the source code constant, we have a function mapping interpreters to interpreters and what we want are fixed points. You point out that there can be more than one fixed point, eg. strict and lazy interpreters. So an obvious question to ask is: how constrained are these fixed points? Can we find radically different but interesting and non-trivial fixed points?

This reminds me of biology. DNA supposedly specifies how organisms are built but the way DNA interpreted to build an organism is itself specified by the DNA. So DNA itself doesn't specify anything other than an equation with organisms forming fixed points.

Partial Evaluation

Looking at the post (though not in great detail) and I thought what you were getting at is essentially self applicable partial evaluation.

partial evaluation

Thanks, Daniel. I was trying to describe self-application and point out that while meta-programming is possible in any PL, it is easier in a self-hosting language.

runtime kernels

I did enjoy your blog post on meta circular evalutation. I didn't respond earlier because it gave me a really funny idea (and funny posts are not really desired style at LtU since it encourages further raucous behavior). I let the urge to be funny cool off, but I can gloss the joke later.

I liked your comments on suitability for implementing languages in some language L once L is meta circular itself, and hence friendly to language work (and perhaps performant as well, depending on the structure of whatever kernel is used). This deserves further exploration and comment by other folks. It's cleverly oriented toward practical versus theoretical notions, and we seldom hear high level practical ideas.

You asked for comment on improving your writeup. You might mention some Smalltalks implemented in themselves, like Squeak, have a boot-strapping C implementation at some point, which might continue life as part of an ongoing runtime. Performant high level languages typically have part of their implemention in C, or assembly, or C++ (there's no real reason to distinguish among these) for crucial bits. For example, Python primitives in C are a big part of good performance in Python.

In short, I think a language's runtime kernel (in C, or C++, or assember, etc) plays a big role that's usefully examined as a fun and practical design issue, having big consequences on design of (eg) meta circular languages.

Look at Python's C runtime for example. Good primitive writing style doesn't use any and all C code interchangeably. There's really a subset of C that's useful in Python primitives, since you must use Python's refcounting (and other management mechanisms) to get along nicely with other C code under Python.

I'm interested in runtimes that could be used to implement different languages. It would be cool to have a runtime kernel suitable for Smalltalk, Python, Ruby, Lisp, etc that allowed each other them to provide a meta circular implentation that also interoperated with each other at the runtime level, since they could have the same microcode semantics at the bottom (agreeing on memory management, for example).

Thinking about the properties of such a thing is fun. I see it as directly related to another thread here (C++ has indeed become too "expert friendly"), since it pertains to how you would write in C++ safely enough to be the kernel of a safe high level language. You'd want to constrain yourself to a subset of C++ with a specific library that's friendly toward the runtime of each languge implemented on that kernel.

Naturally a codename would be nice to discuss this mythical, prototypical runtime kernel that would let you bootstrap any other language of your fancy. But I thought of a funny one (which derailed my line of thought as I imagined dialogs among fictional characters, dressed in safari outfits, set in the 1930's in Africa, at an archeological dig where unscrupulous scoundrels plan to forge evidence on ancient programming languages from civilizations lost under the sea).

The name is motivated by emphasizing what you're not allowed to do if the kernel is not to interfere with semantics and behavior of a language you bootstrap on top. Consider part of the Hacker Slang entry for Mu at

According to various Discordians and Douglas Hofstadter the correct answer is usually mu, a Japanese word alleged to mean Your question cannot be answered because it depends on incorrect assumptions. Hackers tend to be sensitive to logical inadequacies in language, and many have adopted this suggestion with enthusiasm. The word mu is actually from Chinese, meaning nothing; it is used in mainstream Japanese in that sense. In Chinese it can also mean have not (as in I have not done it), or lack of, which may or may not be a definite, complete 'nothing').

(The long joke dialog about Mu involved a riff on an alternative meaning of the word; it's the apochryphal name of a lost civilization supposedly inspiring the legend of Atlantis. It was amusing to suppose they had programming languages there.)

Anyway, it's interesting to enumerate properties you'd like Mu to have as a runtime kernel for boot-strapping other languages. For example, it ought to directly support garbage collection (rules for using pointers that might move) and sphagetti stacks, and continuations at the bottom. If someone started a wiki devoted to nothing else except the design of Mu and variants thereof, I'd spend a lot of time there.


Yes, almost all performant languages have a kernel of some kind running in whatever systems language is friendly to the host OS.

Such a kernal could even be a VM like the JVM or CLR. I would personally consider a language "L" to be self-interpreting if all of its higher-level semantics are layered on top of the VM using L itself.

Or perhaps the VM runs Mu?

p.s. your humour is welcome in the comments of the original post. Please share!

Mu: the lost runtime

(This reply is an excuse to place a short explanation of Mu where I can reference it elsewhere.) Such a kernel could be JVM or CLR if they did in fact do everything done by current languages, such as full continuations with spaghetti stacks.

The term VM covers a lot of ground. Many folks lump an associated runtime together with the VM when a VM ought to be seen as a part of a runtime. VM can imply instruction set among other things, when runtime need not have one. Or a runtime might have multiple instruction sets and hence multiple VMs. So Mu might be any combination of VM and runtime that seems to win the armchair game described below.

For future reference: here's a tiny context-free Mu codename explanation. Pretend you want to bluesky a new spec for a VM or runtime aimed at one or several languages. Call this thought experiment Mu if your Mu ideas assume two goals: [1] Mu must work well for many languages (or better yet, all established languages). [2] Mu must avoid assumptions limiting use or efficiency in some language L you'd rather ignore for your convenience. (Name two programming languages; Mu must work for both: that's the design task, even if infeasible.)

Bonus: when you feel moved to humor, you can allude to the earlier invention of this Mu runtime by ancients in some lost civilization of Mu. (We're just struggling to recreate their works.) [cf]

Upside down programming

Just one little remark about this interesting topic. I made recently an experiment using a metaprogramming system I've written in Python implementing Python 2.5 syntax and semantics in Python 2.4 ( without using C code or touching the CPython runtime ). This can be considered as a some small attempt to reverse engineer or carving out a kernel language from a fully developed programming language - "upside down" programming.

During project development I've also made lots of experiences with language transformers that act on a language with syntax i.e. a non-homoiconic language with distinct styles of representation of the internal parse tree and source code. Unsurprisingly it turns out to be harder to define transformations correctly in that case due to the variety of different node types that fit together according to rules defined in the LL(1) grammar of the host language. One among other long term goals of this project is to soften the transformers while preserving their flexibility and universality for making this rather radical programming practice more usable for programmers of todays mainstream languages.