Building Lisps

Some Lisp-related, and just compiler-related papers and things I've been digging up and enjoying all over again...

Expansion-Passing Style: A General Macro Mechanism

A simple way to implement macros (no hygiene, thank you). Moreover compared to a basic defmacro, this approach allows many more kinds of transformations, e.g. currying, call-by-name, call-by-need, macrolet, stepping inspector, etc. Without getting into anything else about compilation, you can plop this thing right on top of your current Lisp and create all kinds of new Lisps and tools.

Rabbit: A Compiler for Scheme

The original Scheme compiler where Steele put all the basic elements together for writing modern compilers for any language.

The 90-minute Scheme-to-C Compiler

This one's fairly recent and has not received enough attention. This is a concise, Cliff Notes, summary of Rabbit, for all intents. Amazingly it is a working Scheme-to-C compiler, of course without optimizations, the full numeric tower, data structures, etc.

Realistic Compilation by Program Transformation

A thesis that came out of the Rabbit, Orbit, SML/NJ, etc. school. Explains why most compilers should not be *-to-C but *-to-Lambda. The cheapest way to do this today: *-to-Gambit-to-C. Takes transformation to an extreme: ultimately the source-to-source transformations restrict the names in the program to those that can be directly mapped onto the machine registers, etc. But the representation is still essentially executable source code, e.g. Scheme code.

ORBIT: An Optimizing Compiler for Scheme (pdf)

See also the T Project. If you've made it this far you are interested in compilers, language implementations, and Lisp. Orbit is Rabbit, but way out there.

I'm not a compiler guru. I've had the courses in school, built some simple Scheme-ish systems, implemented "little languages" dragon-style for employers who had no appetite for Lisp, etc. I just love these papers listed above, among others to be listed some other time.