Write a Compiler

Upcoming Course Dates:

December 16-20, 2024 (live-taught online). (Sold out)
January 27-31, 2025 (live-taught online). (New!)

Course Hours:

This is an immersion course.
9:30am-5:30pm US Central Time/Chicago

Cost:

$1500

Registration (no payment required now):

Instructor: David Beazley

Other Courses | FAQ

Overview

Shatter your brain by writing a compiler for a new programming language! Why? Because it's cool and you'll learn a lot.

Compilers is often considered a capstone course for computer science majors. There is a good reason for that--compilers are tools that programmers use daily regardless of the application domain. Moreover, a compiler touches nearly every topic of computer science ranging from the theoretical to the practical. Learning more about how they work makes you a better programmer. The process of writing a compiler is an exercise in managing software complexity. Compilers have a lot of moving parts, involve unusual tools, are difficult to test, and are challenging to debug. You'll learn a lot by writing a compiler. Plus, you'll be able to brag about it later.

Target Audience

This class is for more experienced programmers who'd like to take on a good challenge. Not many programmers actually get the opportunity to write a compiler unless they happen to take such a course as a CS undergraduate or they enroll in graduate school. Thus, if you're self-taught and curious about what writing a compiler is all about, this is the course for you.

"If you've seen any of David Beazley's fun and mind blowing talks, you can begin to imagine his week-long, intensive courses, held in his own Chicago office -- or "lair", as he calls it. It's even better than you think: starting with breakfast every day, David is a gracious host, a daredevil coder, and an inspiring teacher. I took his Compiler Course and I hope to attend more of his unique, hands-on workshops."

Instruction Format

This course is entirely project focused. The goal of the course is not just to learn how to write a compiler, but also how to approach the problem of writing a compiler. Part of the course involves group discussion about problem decomposition, coding techniques, design tradeoffs, testing, and other related topics. The rest of the time is spent working on individual coding.

Coding examples and the instructor solution are written in Python. However, the project involves no third-party libraries, esoteric Python-specific features, or Python-dependent tooling. As such, you're free to implement the project in any programming language that you wish. Writing a compiler can also be a challenging way to learn a new programming language should you be inclined to tackle the course on "hard mode."

Prerequisites

You might not think that you're ready to write a compiler, but if you've been coding for awhile and know the basics of data structures, it's something that you could probably tackle. No prior background in compilers is required although awareness of common programming language concepts (e.g., types, functions, classes, scoping rules, etc.) is strongly advised. Some knowledge of text manipulation, computer architecture (machine instructions, memory, etc.), and prior use of a compiled language is also recommended. Robert Nystrom's Crafting Interpreters book is also an excellent source of background information.

Syllabus

The course is structured around the goal of creating a small programming language called Wabbit. Wabbit is a small, statically typed, imperative language. You'll write a compiler that can take Wabbit code and compile it to a native executable program via LLVM. Recent versions of the course have also optionally targeted WebAssembly. The code produced by your compiler will have performance comparable to programs written in C.

The project involves the following core problems:

Data model. You need to figure out some way to represent a computer program, not as text, but as a proper data structure. Sometimes this is called an Abstract Syntax Tree (AST), but it's not necessarily directly tied to parsing.
Parsing. You need to parse programs by converting them from text to the data model. This involves tokenizing text and understanding grammars. We'll look a bit at how parsing algorithms work and you will write a recursive descent parser from scratch.
Program Transformation. Compilers often perform steps that transform a program into an equivalent program. For example, many advanced programming language features can be implemented using simpler features that already exist. Similarly, many compiler optimization techniques are based on program transforms.
Type checking. You'll write a simple static program analyzer that checks the source code for type errors and other semantic problems. Time permitting, we may also discuss a few advanced topics such as Algebraic Type Systems.

Code generation. You'll have your compiler generate code for LLVM and/or WebAssembly. Once you have this, you'll have programs that execute at native speed comparable to C programs. Time permitting, we'll discuss other possible code generation targets such as byte-code interpreters and virtual machines.
Native code generation. Tools such as LLVM still hide a lot of low-level details. We'll conclude by talking about some lower-level issues such as register allocation, activation frames, function calls, linkers, and other matters.

It's important to note that a major goal of the course is to build a stronger intuition for how all of the parts of a compiler actually work. Although there are a lot of existing frameworks and tools that can be used to assist in the creation of a "production grade" compiler, you will be creating a compiler from scratch from first principles.

Practical Takeaways

Although you are unlikely to write a compiler in your day-to-day work, this course touches on a wide variety of practical topics that are applicable elsewhere. These include:

Text manipulation and parsing skills. These can be applied to a variety of problems such as data munging, scraping, protocol implementation and more.

Complex data structure manipulation. Writing a compiler involves a vast array of data structures beyond your basic list or map. You'll build trees and directed graphs. You'll need to write code that navigates through those data structures--often using algorithms involving recursion. Managing the complexity is a challenge and you'll likely get ideas for how you might do it in other contexts (e.g., machine learning, networking, etc.).

Testing. A compiler is one of the most complicated programs you will ever write, consisting of many interlocking components that interact in non-trivial ways. Figuring out how to test it is a challenge. As such, you'll be exploring different facets of unit testing, integration testing, testing oracles, assertions, contracts and more.

Object Oriented Programming. One approach for managing the complexity in a compiler project is to utilize different object oriented programming techniques and design patterns. Although OO is not the main focus, there are many facets of the project where OO thinking might help. So, you can view it as an opportunity to practice.

Functional Programming. Another approach for managing complexity is to adopt ideas from functional programming. Compilers are a good match for recursive algorithms, pattern matching, combinators, and other techniques.
Programming Language Semantics. How does your favorite programming language actually work? No, I mean do you REALLY understand how it works? In order to write a compiler, you have to wrap your brain around a lot of important, often esoteric, usually subtle under-the-hood details. For example, the underlying type system, memory management, evaluation rules, call stacks, and more. After you're done writing a compiler, you'll never look at a programming language in the same way--you'll have a much greater awareness of everything.

Deeper Computing Knowledge. The next time you're at a party and two people are about to get into a heated fisticuffs battle over tail-call optimization, you'll be able to step in and break up an ugly scene. Why? Because you took compilers, that's why. You don't need to be a computer science major to take compilers, but when you're done, you might be mistaken for one.

Are You Nuts?

Writing a compiler in only 5 days? Is it even possible? To be sure, compilers is often regarded as one of the most difficult CS courses that one can take. If you take it at a University, you might get a professor who will drag you through the infamous Dragon Book, spend a lot of time doing mathematical proofs (e.g., deriving the LALR(1) parsing algorithm), and make the focus of the course on preparing graduate students for future research in programming languages. That can be a great class. I have taught that class. This is NOT that class.

Instead, this is a compilers course aimed at practioners. As such, the main focus is on coding and software development. Yes, you will learn about some important core concepts that underpin compilers. However, instead of doing mathematical proofs involving parsing theory, we'll focus on how you would actually go about implementing a parser and doing things such as writing unit tests for it.

To be sure, you will write a lot of code in this course. The course runs for more than 40 hours over five days. The final completed project consists of approximately 2000-3000 lines of code and is every bit as involved as the project you typically find in a college-level compilers course for computer science majors. Your final solution will probably have just as many bugs.

About the Instructor

This class is led by David Beazley. Although most known for his work in the Python community, Dave was formerly a tenure-track assistant professor in the Department of Computer Science at the University of Chicago where he taught a Compilers course along with a variety of other topics in systems and programming languages. In 2023 and 2024, he taught the Programming Language Design and Implementation course with Shriram Krishnamurthi at Brown University. Dave is also the creator of the PLY and SLY parsing tools for Python. He recently gave a PyCon talk about these tools. In a previous decade, he also created Swig, a C/C++ compiler for building scripting language extension modules. Mostly though, Dave just thinks that writing a compiler is cool.