Building a Compiler in Five Projects

Are you interested in creating a compiler, understanding how functional languages work, or gaining practical experience with x86-64 assembly? If so, I invite you to explore the projects from my CIS531 class, a master’s course on compiler design. This course assumes prior programming knowledge, some familiarity with C, and an understanding of assembly language.

Although the projects are implemented in Racket, a functional programming language, learning Racket is straightforward thanks to my YouTube tutorials, making it accessible even for beginners. The course closely follows Prof. Jeremy Siek’s book, “Essentials of Compilation,” which I recommend purchasing support the author. Both the book and supplementary materials like slides and videos are available online.

The course guides students through building a compiler with features such as variables, assignment, arithmetic, input/output, boolean logic, branching, heap-allocated vectors, mutation, loops, functions, lambdas, and closures. This combination offers insight into both imperative and functional programming paradigms and their interaction.

The project sequence consists of five increasingly complex tasks:

1. Warm-up: Stack interpreter (skip if experienced with Racket).

2. Arithmetic: Compile straightforward arithmetic expressions with variables to x86-64 assembly.

3. Branching: Add boolean logic, comparisons, and decision-making structures.

4. Loops & Vectors: Support heap-allocated vectors, mutation, and loops.

5. Functions & Lambdas: Enable first-class functions, closures, and recursion.

The projects prioritize reaching a highly expressive and fun language quickly, sacrificing some features like type safety, garbage collection, and extensive built-in functions. The code does not incorporate register allocation, relying on simple translation to assembly, which can be extended.

Achieving a complete, production-ready compiler requires further steps such as ensuring memory safety with dynamic type tagging, adding more built-in features, and implementing register allocation. These enhancements would bring the compiler closer to real-world usability, and from there, additional language features and optimizations could be integrated.

In conclusion, these five projects offer a foundational understanding of compiler construction, balancing complexity with educational value, and providing a stepping stone toward more advanced compiler design.

—

Frequently Asked Questions (FAQ)

Q: What programming language are the projects implemented in?
A: The projects are built using Racket, a functional programming language.

Q: Do I need prior experience with Racket?
A: Not necessarily; tutorials are available to learn Racket quickly.

Q: What is the main goal of these projects?
A: To develop an increasingly complex compiler for a simple language, culminating in support for functions and recursion.

Q: Are memory safety and garbage collection included?
A: No, the current projects do not include these features; they focus on translation and basic implementation.

Q: Can these projects lead to a fully production-ready compiler?
A: Yes, with additional work on safety, built-in functions, and register allocation, they can evolve into more sophisticated compilers.