Building a Lisp Compiler: An Incremental Approach
In this blog post, we will embark on a journey to build a Lisp compiler. This series is based on Abdulaziz Ghuloum’s paper “An Incremental Approach to Compiler Construction” with some modifications. Our goal is to understand the process of compiler construction and gain insights into machine architecture.
Now, you might be wondering why we chose Lisp as the language for our compiler. The answer lies in its simplicity and compactness. Lisp can be represented in just a few lines of code, making it an ideal candidate for this project. Additionally, many interpreter implementations of Lisp are under 200 lines, so we can expect our compiler to be more substantial.
Before we dive into the details, let’s address some common questions. Why compile directly to x86-64? Well, x86-64 is a widely used instruction set architecture, and by compiling directly to it, we can gain a deeper understanding of machine architecture and explore different encoding possibilities. As for why we chose C as the implementation language, it allows us to avoid copying code directly from the paper and forces us to write our own implementation, which enhances the learning experience.
In terms of generating assembly code, we have decided not to use text assembly. Instead, we aim to generate x86-64 instructions directly. This approach has a few advantages. Firstly, it simplifies the testing process, as we can have an in-process unit test suite that compiles Lisp programs and executes them on-the-fly. Secondly, it allows us to delve into the intricacies of machine architecture and understand how instructions are encoded in different scenarios.
Throughout this series, we will be adding new features to the compiler in each installment. These features could range from new Lisp functionality to compiler optimizations and refactoring. Each post will build upon the code and concepts discussed in previous posts, so it is recommended to read the series in order to fully grasp the material.
Our plan for this series is as follows:
- Implementing a Lisp interpreter
- Building a Lisp compiler
- Adding support for variables and functions
- Implementing control flow constructs
- Optimizing the compiler
- Adding optional features from the original paper
- Exploring additional optional features
As you can see, this is quite an extensive plan, and there may be some steps that are not explicitly mentioned here. However, we will try to cover as much ground as possible, even if it means taking some shortcuts along the way. Rest assured, even if we don’t finish this series, you can still refer to Ghuloum’s paper for further learning.
In the next installment, we will start with the smallest program and gradually build upon it. Along the way, we will encounter challenges, make mistakes, and learn from them in “real” time. So, stay tuned for the exciting journey ahead!
If you have any questions, comments, or suggestions, please feel free to post them on our sr.ht elist. It’s a public inbox where we can discuss and receive patches. We are always open to feedback and collaboration.
Before we conclude, here are some additional links that you may find useful or interesting while following along with this series:
- [Link 1]
- [Link 2]
- [Link 3]
We hope you are as excited as we are to embark on this journey of building a Lisp compiler. Let’s dive in and explore the fascinating world of compiler construction!
Compiling a Lisp (2020)