Lambda the Ultimate

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.

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

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 answers.com:

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.