1.2.1 What is a Compiler?🔗

All that and no mention of compilers. OK, so if we have a sense of what a programming language is now, what is a compiler? You’ve probably used several before but maybe never reflected too deeply on what exactly they were. Take a moment and think about what being a compiler means to you.

Compilers are a particular implementation strategy for realizing a programming language. At their heart, compilers employ a fundamental technique of computer science for solving problems, they perform a reduction. In order to compute the meaning of a program, a compiler translates that program into a program in a different language and then uses the realization of that language to compute the answer to the original program. This is in contrast to an interpreter which computes the meaning of a program directly.

There’s something lurking here that may be causing you some discomfort. Let’s say you have a compiler that translates programs in language A into programs in language B. How does that help you run your language A programs? Well you just run your language B program and what it computes will be the thing that the language A program computes (assuming the compiler performed a correct translation). But you may be asking yourself, how do you compute the language B program!? It’s not clear you’re any closer to the thing you want. Well, maybe you have a compiler from B to C. And D to E. Uh oh. OK, well maybe at some point you have an interpreter. Let’s say you have an interpreter for langauge E. After chaining all these compilers together, you have a thing you can run directly by feeding it the E interpreter and compute the result which is actually the result of the original A program. Pfew.

But wait... the program that interprets E programs, it has to be written in a language. Let’s say it was written in F. How do we run F programs? Maybe we compile to G, H, I, K. Maybe there’s an intpreter for K, written in L... Oh dear. We still have this seemingly endless regress because in order to compute programs in one langauge we have to know how to compute programs in another language: that other language is either the target language of some compiler or the implementation language of some interpreter. Where does this all bottom out?

One concrete answer to this question is: it bottoms out at the machine language of your computer and its CPU. Eventually we hit a point where there’s a compiler that translates from some language into machine code, or there’s an interpreter that’s written in machine code (or we can compile the interpreter into machine code, etc.). The machine code is just another programming language, but it’s a language that has an intrepreter implemented in hardware. It runs programs by physically carrying out the computation of the program, thus providing a foundation for building up our computational house of cards. Ultimately, all of the computations your computer is doing are carried out at the level of machine code intepreted by the CPU. So even though you may be running Java, Python, or Rust code, what’s actually happening is the CPU is running machine code. But here’s the magical thing: it doesn’t really matter. Once you know that you can run, say, Java code on your computer, you can view Java as the foundation if you want. If you wanted to develop a new programming language, you could write a compiler that targets Java or you could write an intepreter in Java. Your new language could run anywhere that Java can run (which is essentially anywhere). One of the great contributions of programming languages is that it allows us to build the world we want to live in and leave the old one behind. This is in fact why compilers were invented in the first place.

An important observation to make: programming languages exist independently of their implementations. Java is not ‘javac‘. C is not ‘gcc‘ (or ‘clang‘). Haskell is not ‘ghc‘. Compilers are a particular implementation strategy for realizing a programming language. Sometimes languages get conflated with their implementations. And sometimes we go further and conflate properties of the implementation with the language itself. This leads to people saying things like "Python is an interpreted language; C is a compiled language." Python is not an interpreted language, rather it’s most well-known implementation is an interpreter. Compilers for Python exist as do interpreters for C.

1.2.2 What will be do in this course?🔗

We are going to study how to implementat a programming language by making our own programming language. In particular, we are going to build a compiler for our language.

The language we are going to build is a modern, high-level general-purpose programming language. It will have features like:

• built-in datatypes including integers, boolean, characters, strings, vectors, lists, and user-defined structures

• first-class functions

• pattern matching

• memory safety

• proper tail calls

• automatic memory management

• file I/O

Our compiler is going to target x86-64 machine code, meaning that programs written in our high-level language can be run on any system capable of running x86-64 code, either natively in hardware, or through software simulation (e.g. Rosette on Apple Silicon Macs). x86-64 is one of the most ubiquitous instruction set architectures in use today. It’s also quite large, complicated, and old, with some design constraints that date back over 4 decades as it has evolved from its 16-bit precursor first released in 1978. The choice of x86-64 as the target of our compiler is largely an arbitrary one. We could easily have picked another instruction set architecture, like ARM64, or targeted an intermediate representation like LLVM IR. In choosing x86-64 we get a messy, "real", and bare-bones, low-level view of computation and moving to any of these other similar settings would be fairly easy to do. Alternatively, we could have targeted a higher-level language such as C or Rust, or even JavaScript or OCaml. The more high-level the language, the easier it will be to serve as a target for the compiler, especially when the target language’s semantics are close the source language’s. Doing so could certainly be interesting, but it would illuminate compilation only down to the level of abstractions of the target language. By going all the way down to machine code, we are able to understand the implementation of our high-level language features completely down to the actions of the CPU. There will be no more mystery.

In order to side-step getting bogged down in making design choices, we are going to implement (a subset of) an existing high-level langauge called Racket. Racket is a member of the Lisp family of langauges, a descendent of the Scheme programming language, and a close cousin of OCaml, which you’ve previously studied. This is largely an arbitrary choice. We could have picked any programming language to build a compiler for. In choosing Racket, we get a mature, well-designed language with a minimal, easy to parse semantics and a well-understood and clear semantics that has features representative of many modern high-level programming languages such as OCaml, Java, Python, JavaScript, Haskell, etc. If you can write a compiler for Racket, you are well-equiped to write a compiler for any of those or similar languages, or even to design your own new language.

We will us an incremental approach to study and build compilers, meaning we will start by specifying and implementing a very small subset of Racket. Once specified, implemented, and tested, we will enlarge the set of programs in the langauge, typically by adding some new langauge feature. Doing so necessitates revisiting the specification and implementation to handle this extended set of programs. And then we rinse and repeat, growing the language from something trivial into a fairly sophisticated language in which it’s possible to write interesting programs. Each iteration of the langauge will be a strict superset of the previous one, meaning that all programs in the previous language will continue to be programs in the next language. The first iteration has nothing more that integer literals and the final iteration contains a substantial subset of Racket.

In this course, we pay particular attention to the concept of a specification, which defines what it means for our compiler to be correct. We will use testing extensively to gain some evidence that our compiler is not incorrect. Our primary goal will be in writing a correct, maintainable compiler for a full-featured language. We will not concern ourselves too much with concerns of efficiency or optimization. First things first: we have to build something that works. After that, we can think about making it work faster.

We make extensive use of writing interpreters as our form of language specification. Interpreters, when written as clear, concise code in a high-level language, provide a precise distillation of the semantics of a programming language. They can also serve as a reference implementation, used to validate other implementations of the language.