Crafting compilers

Horace Guy published on
3 min, 525 words

Categories: programming

TL; DR: My own code is on github.

An attempt at crafting interpreters #

Due to the warm reviews, I tried first to read Crafting Interpreters and went though the first chapters, but I was quickly underwhelmed. Indeed I found the following:

  • The language of the first part is Java, which I am not proficient in. I still managed to roughly translate the scanning part to python, but I am not familiar with Java so it adds a barrier for me.
  • The imperative, stateful style is hard to wrap one's head around.
  • In order to have a working interpreter you have to go through the entire first part.
  • I want to learn assembly, and this book doesn't have any.

All in all, after the Scanning part I was unsatisfied and looked for something else.

Compiler Construction #

So I pivoted and instead I went with University of California San Diego's Compiler Construction course (codename CSE 131) of fall 2019, taught by Joe Gibbs Politz. Incidentally, he is also part of the Pyret language crew.

It checks almost all of my (digital) boxes:

  • The code is in OCaml, which I know a bit
  • It goes all the way to Assembly
  • References the classic Modern compiler implementation in ML by Andrew W. Appel (also known as the Tiger book), which is on my to-do list after this course
  • The approach is incremental: at the end of each assignment, I have a fully functional compiler !

The only minor drawback is that I am more interested in ARM than x86_64, because from what I've read x86 is messier than ARM.

I find it rewarding since now, after the first assignment, I have an end-to-end compiler for a calculator with variable. Of course, this is not a full-fledged language but I'm going to incrementally add features.

I just wish it were a book because I prefer this format to video lectures.

Modern OCaml #

The course leverages basic features of the OCaml programming language and relies on makefiles for the build system. I tried to follow the style but unfortunately I didn't get satisfactory intellisense in vscode without dune, the newish OCaml build system. So I converted everything to use dune.
Also, for unit test the old OUnit is used, so I changed to leverage the more user-friendly and colorful Alcotest.

terminal output from Alcotest
Look at this colorful and explicit output !

Project structure #

The structure is the following:

~/dev/cse131/pa1 main*
 tree -C
├── bin
   ├── dune
   ├── main.c
├── dune-project
├── input
   ├── 42.ana
   ├── addnums.ana
   ├── letdup.ana
   ├── letdup_valid.ana
   ├── letlet.ana
   └── sub1.ana
├── lib
   ├── dune
├── Makefile
├── output
├── pa1.opam
└── test
    ├── dune

5 directories, 23 files

My own code is on github.

Wrap-up #

[edit: January 14 2024]

I stopped after the second assignment because the lectures started to get hairy and I got the feeling that everything wasn't recorded. And also because of other constraints (life). Still, the mini-compiler should be functional.

All-in-all, I enjoyed working on this project.