Lambda the Ultimate

Before trying to self-host a language; it is important that the language design itself be reasonably stable. Not perfect, mind you; but stable enough so that you won't be breaking yourself.

The decision to go and self-host (or when to do so) is complicated by several other factors. In the following discussion, the language being developed is known as L, and the bootstrapping language is B:

* The goodness of the tool-set. Even if L is far more expressive than B; chances are that B has a more mature tool-set available for it. Better libraries, robust compilers, IDEs, debuggers (please no "debuggers are for morons" rants), etc. None of these will exist for L until you (or someone) writes them. A good REPL will make a basic development environment, but using B's tools may be more productive.

* That said, if L is to become a useful language, at some point somebody will have to write the aforementioned tools; so doing so isn't at all wasted effort. The key question is not if, but when.

* If you are writing a HLL, chances are that at least part of the runtime infrastructure will need to be written in a systems' language such as C/C++. Java, for example, is not a suitable language for implementing a JVM.

* If you are writing a domain-specific language; you'd be better off not trying to self-host (unless the problem domain being addressed is compilers and such).

* When self-hosting, be wary of the hornets nest of paradoxes and infinite recursions that comes with self-hosting. Read Art of the Meta-Object Protocol, which discusses such issues in depth. Also read Ken Thompson's famous Turing Award lecture Reflections on Trusting Trust.

* Eating your own dog-food is a time-honored engineering principle; and there is a longstanding bias in the CS world that a (general purpose) programming language must be self-hosting in order to be worth anything. Many developers of high-level languages express a desire to free themselves from the "shackles" of low-level-language B, as if having a compiler written in B somehow limits the capability of L. It doesn't. The migration to self-hosting, if done at all, should be done for sound ease-of-development principles. (That said, starting a self-hosting implementation in L might be a good test case for L, so it has those advantages). Quite a few production-grade compilers and such are not written in the target language--GCC, for example, is written (mostly) in C despite supporting translation of numerous other languages. Don't let pride lead you to self-host prematurely.

* The transition to self-hosting should be incremental. A good technique is to replace one section at a time, until the whole implementation is self-hosting, possibly excluding the low-level bits that require C or some other systems language.

* Don't throw away the bootstrap compiler! (Or interpeter--see next point). The next user will need it to bring L up on his system.

* Regardless of self-hosting or not; write an interpreter first. Only when the language definition is stable, and the interpreter fully working, should you attempt to compile to assembly language and/or bytecode. The interpreter will give you a reference implementation to compare your compiler against.

* At all times: Don't bite off more than you can chew.

Scott has stated much more insightfully than I the issues associated with looking for a bootstrapping language B. I disagree with the grandparent that I should use what I know.

Note that I am avoiding saying anything specific about the language L, because it would only lead to people commenting on L, when for this discussion I am interested in comments on B. However imagine L is a descendent of popular recent scripting languages with a C flavour syntax, and you would have a good idea of L!

My premise is that there are better languages for B that I have no experience with, which would be more productive to use as a bootstrapping language (including time to learn the language.)

Is my premise correct?

For example, last week I started learning Visual Basic 6 to use for a project and it would be execrable to use as B (or for that matter virtually anything :-). Most other languages I know would be 10x more productive for me than VB. I believe that a more suitable language for B could be 10x more productive again. However my experience is in imperative and scripting languages, and I have no experience in the languages usually recommended for B. Lisp descendents are often cited for B, but I have yet to be convinced they would be resoundingly better than say Haskell or ocaml (I admit I know neither) for my needs.

would work fine.

Haskell might be the hardest to learn, if you aren't already familiar with it, because it's lazy evaluation is quite different from what programmers used to eager evaluation semantics might come to expect. I'm tempted to recommend ML over Common Lisp, if for no other reason than the existence of MLKit and similar tools. (What sort of typing system are you employing, BTW)?

The above assumes you are implementing a reference or prototype interpeter (and not too concerned with performance); until your language is up and running you ought not be in the business of cycle counting. Alternatively, both are good at implementing compilers (which is just rather complex symbolic processing). When it comes to higher-performance implementations, I would recommend first that you target an existing VM or abstract machine (JVM, ParrotCode, .NET) rather than re-inventing this particular wheel.

What of C++, Java, C, C#, etc? I wouldn't use plain C; as it has a primitive type system and is rather poor at symbolic manipulation compared to other languages. C++ is better (especially augmented with the numerous high-quality libraries from boost.org and others), but it's lack of garbage collection will be a problem for any interpeter. Some consider it's manifest typing a problem (others don't mind). You can get a GC for C++, but it's one thing that other languages don't make you worry about. Java and C# are often both used successfully for this sort of project (and make it easier to target the JVM and or .NET platforms respectively), but both are less "expressive" than ML. O'Caml (an object-oriented ML dialect) can be made rather fast if you like.

A lot also depends on your goals. Are you trying to get a system working as fast as possible, or is your goal more to learn something new? If the latter, you might be better off sticking with a familiar language. If the latter, consider acquiring a new language part of the learning experience.

Lisp beats Haskell/Ocaml only if L is parenthesized-prefix syntax. In that case, you avoid writing a lexer/parser, instead using the Lisp reader to transform program text into data structures your interpreter can understand. You can often implement the whole language as macros, cutting down significantly on developer time.

If you have a moderately-complicated syntax, you're probably better off with Ocaml. Between ocamllex, ocamlyacc, and caml4p, you've got a really good set of parsing tools, and then algebraic data types and pattern matching often help you destructure the syntax trees for interpretation/compilation. I know Lisp has similar tools, but I don't think they're as mature (does anyone in the Lisp world ever use syntax?) and then your type system isn't as rich once you've got the actual syntax tree. Then again, it's so easy to destructure lists (destructuring-bind anyone?) that perhaps you don't need it.

One interesting bootstrap possibility might be to use Lisp as B, create L as a prefix-syntaxed language, and then write a parser-generator in prefix-L that parses full-L. This way, you decouple the syntax from the compiler, so you automatically have the ability to create multiple syntaxes, and macros are a simple library away. I've thought some about implementing a language this way, but never got around to it.

there is a longstanding bias in the CS world that a (general purpose) programming language must be self-hosting in order to be worth anything

And there is the canonical reaction to this: “Has it been used for anything besides its own compiler?”

Fortunately self-hosting is academic to me at present!

On reflection, I now think the topic title should be something like "What are the most productive host languages to use for developing a new imperative language?"

I say "underspecified" or "if you abstract away from everything, then everybody is right."

Java, Javascript, Pyhton, Lua, Php, C++, D, Perl, Icon, Ruby, Nice, F#, Dylan, ML, OCaml... Think about this for a while: Lua in Haskell? Dylan in Python? Ocaml in Java? ML in Perl? I can give arguments and counterarguments for any combination. Each of the mentioned languages have/had their own specific requirements, they all have/had their own manner of getting there.

What do you mean with productive? I assume you want the shortest route to your goal.

Almost no requirements, no goal, therefor any well-known language fits.

Java, for example, is not a suitable language for implementing a JVM.

Really? What about Jikes? I'd also note that the most widely used Java compilers are written in Java.

This discussion makes me realize that my traditional understanding of the term "self-hosting" (is the compiler/interpreter written in its source language) is somewhat naive, considering both the compiler/interpreter and runtimes for a language may be implemented in any mixture of languages. I don't think I know of any strictly self-hosting implementations, considering even C compilers have parts of the runtime library implemented in assembly.