Returning to Compilers, as a Student

I've wanted to understand compilers more deeply for a long time. I began exploring them in the early 2000s, and I still find the basic idea remarkable: a program can take code written for people to read and translate it into instructions a machine can execute. It has to understand enough of what we wrote to preserve its meaning through that translation. There is a great deal of computer science in that seemingly ordinary act of building a program.

That is where my interest comes from. After about twenty-five years in software, I still approach this subject as a student of computer science. There are ideas I recognise, others I need to revisit, and many implementation details I would like to understand properly. Using compilers regularly has only given me more questions about them.

I've now managed to set aside some time to study and write. These posts will mostly be notes for myself, with a small implementation to check the explanations against. Writing them publicly takes a little courage, but I hope the process will help me be more careful about what I think I understand.

Back to the books

The Dragon Book was part of my early reading, along with other compiler texts I worked through carefully. I would like to return to that material with the questions I have now.

Its proper title is Compilers: Principles, Techniques, and Tools. The first edition was by Alfred Aho, Ravi Sethi, and Jeffrey Ullman; Monica Lam joined the authors for the second edition. My own interest began before that later edition appeared. There are other books I want beside it as I work: Andrew Appel's Modern Compiler Implementation, with its C, Java, and ML editions, and Keith Cooper and Linda Torczon's Engineering a Compiler.

They give me different ways to approach the same subject. I'd be pleased if the implementation helps me read them with a little more understanding.

This time I want to pause at the details that are easy to acknowledge on a page. A parser produces a tree, certainly. But what should I put in that tree so the next phase can use it? Which source locations should survive? Where should an error be reported? I find those questions easier to work through when there is a function to write and a test that can disagree with me.

Following the languages

My own reading began around C and Java, but following their ideas soon takes us in several directions. C makes the relationship with memory and machine operations fairly visible. Smalltalk explored an object-centred programming environment; C++ brought object-oriented facilities into a language with C roots and systems-programming concerns. Java made a virtual machine a familiar part of everyday development: source could become bytecode, with the JVM responsible for executing it on a particular machine.

That is a rough path through the ideas, not a claim that one language neatly replaced the previous one. Their histories overlap, and each still raises worthwhile implementation questions. Even the phrase "compile the program" can refer to different stopping points along that path.

Python and Ruby brought another part of the picture into focus for me. We often call them interpreted languages. Broadly, interpretation means that another program carries out the operations described by our code, rather than the processor directly executing a native translation of that whole program. It does not mean that the implementation has no compiler. CPython, for example, compiles source to bytecode, which its virtual machine executes. CRuby also has compiled instruction sequences.

An implementation can combine these techniques, including compiling frequently executed code to native instructions while the program runs. That is just-in-time compilation. The more I read about such systems, the less useful a strict "compiled language versus interpreted language" division seems. It is worth asking what a particular implementation does, and when it does it.

More recently, TypeScript and Rust have kept my attention. TypeScript adds static checking around JavaScript while leaving JavaScript's runtime model in place. Rust takes a different approach to systems programming, making ownership and borrowing part of what the compiler checks. Both bring me back to an old question: how much can we establish about a program before it runs?

Rust is receiving a good deal of attention, and that helped draw me towards it for this exercise. What holds my interest is the work its compiler does. I would like to understand more of how it combines native code generation with those checks, even though our small implementation will cover only the basic compiler phases.

A small project to learn from

We'll write a compiler in Rust for a very small subset of Rust itself. I'll call that subset MicroRust. Rust is the language; rustc is its compiler. Keeping that distinction clear matters here, since we will be using Rust to build a separate compiler of our own.

Choosing an existing syntax gives us a useful reference. Our example programs can compile with rustc from the beginning. As MicroRust develops, we can compare what it accepts and what its programs produce. When the results differ, we have a specific question to investigate.

The implementation will stay small enough that I can follow a value through it. That means leaving out much of what makes Rust interesting as a systems language, including ownership and borrowing. I still think there is plenty to learn from getting ordinary integer expressions and function calls through every phase. Once those parts are concrete, I should be better prepared to read about the analyses we have left out.

I would also like to keep the code alongside the prose, so a reader can run the examples and change them. Some snippets will show a small part of the compiler; others will be programs it accepts or deliberately rejects. I'll distinguish those cases. An example that fails for the intended reason can teach us something, but it should not leave someone wondering whether they copied it incorrectly.

In the first implementation chapter, we'll settle the scope and choose the program to carry through the series. For now, I am glad to have made time for a subject I have wanted to study more closely for years. Writing a little code alongside the reading seems a reasonable place to begin.