You too can write a compiler

2022-10-22 by Christian Kjær Larsen

A while ago I bought this domain with the plan of hosting a blog here. This is now happening, and this will be the first post in a series about a homemade compiler for a functional language.

I got inspired by reading Abdulaziz Ghuloums paper An Incremental Approach to Compiler Construction. The language we will be compiling is different (and will diverge over time) but some of the ideas are coming from there.

Topics that we will go through (not necessarily in order) if I don’t lose interest:

  • Language semantics and intepretation
  • Parsing
  • Naive code generation
  • Adding types
  • Tail call optimization
  • Heap allocation
  • Closures and lambdas
  • I/O
  • Garbage collection

The language

The first iteration of the language will be a simple first order functional programming language. A valid program that calculates 10 factorial is:

fun fact(n) =
    if n == 0
    then 1
    else n * fact(n - 1)

in fact(10)


The implementation will use Scala 3 for the compiler and Zig for the runtime. You can follow along on GitHub if you are interested.