Lambda the Ultimate

Abdulaziz Ghuloum (Indiana University), An Incremental Approach to Compiler Construction

Compilers are perceived to be magical artifacts, carefully crafted by the wizards, and unfathomable by the mere mortals. Books on compilers are better described as wizard-talk: written by and for a clique of all-knowing practitioners. Real-life compilers are too complex to serve as an educational tool. And the gap between real-life compilers and the educational toy compilers is too wide. The novice compiler writer stands puzzled facing an impenetrable barrier, “better write an interpreter instead.”

The goal of this paper is to break that barrier. We show that building a compiler can be as easy as building an interpreter.

This paper from the Scheme workshop presents an extended tutorial showing how to implement a compiler from Scheme to x86 assembly language. The compiler is written in Scheme, obviously (something that may confuse students, I might add, so beware).

An important aspect of the presentation of the material is that the compiler is built incrementally, and the product of each step is a working compiler for a growing subset of the language. This is similar to the EOPL approach. In contrast many compiler textbooks and courses follow a different route, in which each phase is dedicated to building a different part of the compiler (i.e., lexer, parser etc.), and thus the student only sees how the parts interconnect, and gets the satisfaction of seeing the compiler work, at the very end of the process.

Supporting material can be found here.