Bootstrap Book

Learn how to Write a Compiler in 2000 Lines of Code

λ☶

This book explains the code of the λ☶ compiler to anyone who is interested in compiler architecture or functional language compilers. The code is roughly 2000 LOC in length, but it is very terse, so the explanation takes a while. The generated code is in the format of GNU Assembly for legibility. Binary targets are just as easy to write, but harder to read.

Chapter 1: S-Expressions

• The S-Expression Type Signature
• Why are S-Expressions Good
• How Do We Construct An S-Expression in Assembly
• What Common Functions Operate on S-Expressions

Chapter 2: Primitive Functions

• What Is a Function?
• What Do We Expect From a Function Inside the Compiler?
• System Calls
• The print-s Function
• The strlen Function
• The not Function
• The write-file Function
• The load-file Function

Chapter 3: Hello World

• Program Layout
• Processing Argv
• Heap Allocation of Atoms
• Heap Allocation of Cons Cells

Chapter 4: User-Defined Functions

• First-Order Functions
• Passing Multiple Arguments to a Function
• Higher-Order Functions

Chapter 5: Tokenization

• The Tokenizer Function
• Tokenization by Example

Chapter 6: Parsing

• The Abstract Syntax Tree
• The parse-program Function
• The parse-many-expressions Function
• The parse-one-expression Function
• The parse-lambda Function

Chapter 7: Type Checking

• Defining a Type Context
• Parsing a Type Definition
• Enumerating Inference Cases
• Infer Type of an Ascription
• Infer Type of a Literal
• Infer Type of a Variable
• Infer Type of an Application
• Infer Type of a Lambda

Chapter 8: Code Generation

• The Expression Datatype
• The compile-expr Function
• Codegen this Expressions
• Codegen local Expressions
• Codegen set Expressions
• Codegen match Expressions
• Codegen while Expressions
• Codegen if Expressions
• Codegen Function Application Expressions
• Codegen Literal Expressions
• Codegen argv Expressions
• Codegen Cons Expressions
• Codegen Nil Expressions
• Codegen Variable Expressions