Back in 2013, I took a compiler course in Carnegie Mellon. It was a difficult course, but one that taught me a lot about perseverance and systems engineering. In the time I spent writing that compiler, I gained a lot of respect for type theory and the power it provides in writing correct code.
Once the course was over, I made a small pledge. I would rewrite that compiler, this time in Haskell, but build it correctly with all of the new type modeling tricks I had learned. I wanted to know how much these techniques really helped. I thought it would take me another year to rewrite it. After all, I had built the original in 4 months. That was wrong. Horribly wrong.
It’s been 5 years since that time and I’ve spent 3 working in the industry and I’ve learned a whole lot since those days hacking away at university. Throughout this entire time, I’ve spent bursts working on this compiler. I’m about half way done with the initial write, and I realized that there’s some interesting value in recording some of the lessons I’ve come across.
Of note, a lot of what I’m experiencing so far has to do with being clever in Haskell and the extent to which it allows me to model and encode constraints into my data types. Soon, I’ll also be looking at improving compiler performance and correctness.
The interface for the compiler is simple: I have to produce x86_64 assembly code from a C0 source file. Obviously a toy language, but good enough to get some idea of how this will go. I must be able to run “make” from the compiler directory, and run tests on a suite of 1000 source files compiled by the previous classes. Goal at the end of the day is to make all the tests run green.
Finally, there’s an odd set of constraints I’ve placed on myself for writing this project:
- Write idiomatic Haskell.
- If you can model constraints into the data representation, do it.
- Future proof the compiler. When choosing an implementation, ignore complexity and only consider effectiveness when deciding how to implement the feature.
- No unit tests until you’ve completed an initial run of the compiler.
- Once that initial run is complete, write exhaustive tests and rerun.
This is obviously not super scientific, but I want to record my experience of each of these stages to the best of my ability. This is essentially the only project in which I’ve written Haskell and hopefully, it’s one that provides people without a theory background a window into why people like me find Haskell and other languages with novel/powerful type systems useful.