summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--Compiler in a Day/00-overview.page40
-rw-r--r--Compiler in a Day/01-ciadlang.page289
-rw-r--r--Compiler in a Day/02-ast.page237
-rw-r--r--Compiler in a Day/03-frame-layout.page169
-rw-r--r--Compiler in a Day/04-abi.page136
-rw-r--r--Compiler in a Day/05-codegen.page136
-rwxr-xr-xCompiler in a Day/run.sh8
7 files changed, 1015 insertions, 0 deletions
diff --git a/Compiler in a Day/00-overview.page b/Compiler in a Day/00-overview.page
new file mode 100644
index 0000000..778c5c1
--- /dev/null
+++ b/Compiler in a Day/00-overview.page
@@ -0,0 +1,40 @@
++++
+title = "Overview — Compiler In A Day"
+next = "01-ciadlang.md"
++++
+
+# Compiler In A Day
+
+This is intended to be a walkthrough of a complete compiler for a simple language that can be read and understood in a single day.
+
+In order to achieve this, we're going to be cutting a lot of corners, mostly around code generation.
+The assembly we'll be producing will run correctly, but it will be very inefficient.
+
+Our compiler will accept a file written in our programming language and output x86_64 assembly, which can be assembled and linked by [GNU Binutils], intended to be run on Linux.
+
+It should also run on the [Windows Subsystem for Linux] or on FreeBSD with its [Linux ABI support].
+
+We'll also have a small runtime, written in C, and using [the Boehm-Demers-Weiser garbage collector].
+
+The source code we'll show for the compiler is in Ruby, but nothing Ruby-specific will be used.
+In fact, a previous version of this compiler was written in C11.
+
+Our compiler will have four parts.
+They are, in the order they get run:
+
+- [Lexing][Lexical analysis]: the process of breaking up the strings of source code into lexical units known as "tokens." This simplifies parsing.
+- [Parsing]: the process of building a tree representing the program from the tokens.
+- Frame layout: the process of assigning slots in each function's [stack frame] to its local variables.
+- Code generation: the process of generating actual assembly code from the program.
+
+TODO: pictures!
+
+Before we can start looking at these steps, however, we should look at the language we'll be compiling.
+
+[GNU Binutils]: https://www.gnu.org/software/binutils/
+[Lexical analysis]: https://en.wikipedia.org/wiki/Lexical_analysis
+[Linux ABI support]: https://man.freebsd.org/cgi/man.cgi?query=linux&sektion=4&format=html
+[Parsing]: https://en.wikipedia.org/wiki/Parsing
+[stack frame]: https://en.wikipedia.org/wiki/Call_stack#Structure
+[the Boehm-Demers-Weiser garbage collector]: https://en.wikipedia.org/wiki/Boehm_garbage_collector
+[Windows Subsystem for Linux]: https://learn.microsoft.com/en-us/windows/wsl/
diff --git a/Compiler in a Day/01-ciadlang.page b/Compiler in a Day/01-ciadlang.page
new file mode 100644
index 0000000..7abba8b
--- /dev/null
+++ b/Compiler in a Day/01-ciadlang.page
@@ -0,0 +1,289 @@
++++
+title = "The Ciad language — Compiler In A Day"
+prev = "00-overview.md"
+next = "02-ast.md"
++++
+
+# The Ciad language
+
+Before we start looking at the compiler, we should see and understand the language we'll be compiling.
+This language is named Ciad (pronounced like "key-add"), which is an acronym for the name of this series.
+
+This article will be a bit dry; it's mostly describing what is, rather than *why* it is.
+Some design decisions will be expounded on later, when their benefits are reaped.
+
+Other design decisions take more time to explain; some of these will get their own articles.
+
+One choice about this article that's worth discussing up front — the description of the language is done both in natural language, and in an appropriate formalism.
+
+The main benefit of the latter is precision — with a good formal description, we can avoid needing to argue about what the compiler "should" do, or a program "should" mean; instead, we can consult the formalism.
+
+A secondary benefit (that we won't exploit in this series) is the wide variety of tools and techniques that can give us "nice things" from formal descriptions of a programming language.
+
+In theory, a full formal description of the syntax and semantics of a programming language can be used to "mechanically" generate a complete working compiler for the language.
+
+In practice, almost every language has at least one "weird thing" that breaks the ability to do this.
+Still, sticking to having a good formal description makes it easier to take advantage of programming language theory, even if we do have to do some "fixing up" to handle weird things in our language.
+
+## Syntax
+
+The formalism we'll be using to describe Ciad's syntax is [EBNF], a notation used for describing [context-free grammars].
+
+TODO: Should I say more about CFGs?
+
+TODO: I should definitely mention tokens.
+
+The syntax of a programming language is typically described in two parts, with the lexical syntax described separately from the rest.
+
+This is because it's typically simpler to discuss things like comments and whitespace once, and then state a rule like "comment and whitespace tokens are ignored during parsing," rather than noting that a comment or whitespace token could appear at any point in the actual grammar.
+
+This also fits with the separation between lexing and parsing; typically, a lexer can use simpler algorithms than a parser.
+
+### Lexical Grammar
+
+There are eight categories of tokens in Ciad's lexical syntax:
+
+- Identifiers, like `foo` and `main`. Identifiers are used for the names of variables and functions.
+
+- Keywords, like `if` and `while`. We recognize these separately from identifiers so that users can't do things like create a function named `while`, which may be confusing to other people and hard to parse.
+
+- Integer and string literals, like `34` and `"Hello, world!"`. We need to recognize these in order for them to be present in the syntax!
+
+- Punctuation, like `=` and `++`. These get recognized in a manner similar to that of keywords.
+
+- Comments and whitespace, like `// TODO: speed up this loop` and line feeds. As mentioned above, recognizing them in this separate lexing step helps simplify the syntactic grammar, since they can be ignored here.
+
+- End of file. We have a special token to indicate that the end of the file has been reached. This isn't "really" part of the syntax, but it'll help us when we get around to implementing it.
+
+```ebnf
+token = identifier | keyword | integer literal
+ | string literal | punctuation | comment
+ | whitespace | ? end of file ?;
+```
+
+Identifiers are a letter or underscore, followed by zero or more letters, underscores, or digits, except for keywords.
+
+```ebnf
+identifier = identifier or keyword - keyword;
+identifier or keyword = identifier start character,
+ {identifier body character};
+identifier start character = letter | "_";
+identifier body character = letter | "_" | digit;
+
+letter = "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H"
+ | "I" | "J" | "K" | "L" | "M" | "N" | "O" | "P"
+ | "Q" | "R" | "S" | "T" | "U" | "V" | "W" | "X"
+ | "Y" | "Z"
+ | "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h"
+ | "i" | "j" | "k" | "l" | "m" | "n" | "o" | "p"
+ | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x"
+ | "y" | "z";
+digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7"
+ | "8" | "9";
+```
+
+The words `else`, `fun`, `if`, `return`, `var`, and `while` are all keywords.
+
+```ebnf
+keyword = "else" | "fun" | "if" | "return" | "var"
+ | "while";
+```
+
+An integer literal is one or more digits optionally preceded by a `-` character.
+
+```ebnf
+integer literal = ["-"], digit, {digit};
+```
+
+A string literal is zero or more string chunks surrounded by two `"` characters.
+A string chunk can either be escaped or unescaped.
+An escaped string chunk starts with a `\` character, and is then followed by one of `f`, `n`, `r`, `t`, `\`, `"`, or `x` and two hexadecimal digits.
+An unescaped string chunk is one or more [ASCII printable characters] other than `\` and `"`.
+
+```ebnf
+string literal = '"', {string chunk}, '"';
+string chunk = escaped string chunk
+ | unescaped string chunk;
+
+escaped string chunk = "\", escape sequence;
+escape sequence = "f" | "n" | "r" | "t" | "\" | '"'
+ | "x", hex digit, hex digit;
+hex digit = "A" | "B" | "C" | "D" | "E" | "F"
+ | "a" | "b" | "c" | "d" | "e" | "f" | digit;
+
+unescaped string chunk = unescaped character,
+ {unescaped character};
+unescaped character = printable character - ('"' | "\");
+
+printable character = digit | letter | " " | "!" | '"'
+ | "#" | "$" | "%" | "&" | "'" | "("
+ | ")" | "*" | "+" | "," | "-" | "."
+ | "/" | ":" | ";" | "<" | "=" | ">"
+ | "?" | "@" | "[" | "\" | "]" | "^"
+ | "_" | "`" | "{" | "|" | "}" | "~";
+```
+
+The following sequences of characters are punctuation: `(`, `)`, `[`, `]`, `{`, `}`, `,`, `=`, `==`, `-`, `+`, `++`, `;`.
+
+Multi-character sequences are preferred to two single-character ones; this rule is often called "[maximal munch]" (and applies everywhere else in the lexical grammar, too).
+
+```ebnf
+punctuation = "(" | ")" | "[" | "]" | "{" | "}" | ","
+ | "=" | "-" | "+" | ";" | "==" | "++";
+```
+
+Comments are `//` followed by zero or more ASCII printable characters or horizontal tabs and terminated by a carriage return, line feed, or the end of the file.
+
+```ebnf
+comment = "//", comment character, comment end of line;
+comment character = printable character
+ | ? horizontal tab character ?;
+comment end of line = ? carriage return character ?
+ | ? line feed character ?
+ | ? end of file ?;
+```
+
+Whitespace tokens are one or more carriage returns, form feeds, horizontal tabs, line feeds, and space characters.
+
+```ebnf
+whitespace = whitespace character,
+ {whitespace character};
+whitespace character = ? carriage return character ?
+ | ? form feed character ?
+ | ? horizontal tab character ?
+ | ? line feed character ?
+ | " ";
+```
+
+### Syntactic Grammar
+
+The syntactic grammar of Ciad is specified using the nonterminals and terminals from the lexical grammar.
+
+Recall that any comment or whitespace tokens that are encountered are ignored, so the syntactic grammar should be read as if there were a `{comment | whitespace}` before any other nonterminal or terminal from the lexical grammar.
+
+A Ciad program is a series of declarations, which may be variable declarations or function declarations.
+
+```ebnf
+program = {declaration}, ? end of file ?;
+declaration = variable declaration | function declaration;
+```
+
+#### Declaration Syntax
+
+A variable declaration is the `var` keyword, followed by an identifier (the variable name) and a semicolon.
+
+```ebnf
+variable declaration = "var", identifier, ";";
+```
+
+A function declaration is the `fun` keyword, followed by an identifier (the function name), a comma-separated (and optionally comma-terminated) list of identifiers surrounded by parentheses (the function arguments), and a block (the function body).
+
+A block is zero or more statements surrounded by curly braces.
+
+```ebnf
+function declaration = "fun", identifier,
+ "(", [function arguments], ")",
+ block;
+function arguments = identifier, {",", identifier}, [","];
+block = "{", {statement}, "}";
+```
+
+#### Statement Syntax
+
+There are five kinds of statements: assignment statements, expression statements, if statements, return statements, and while statements.
+Additionally, variable declarations can be used as statements.
+
+```ebnf
+statement = assignment statement | expression statement
+ | if statement | return statement
+ | while statement | variable declaration;
+```
+
+An assignment statement is an expression followed by an equals sign, another expression, and a semicolon.
+
+An expression statement is an expression followed by a semicolon.
+
+A return statement is the `return` keyword, followed by an expression and a semicolon.
+
+```ebnf
+assignment statement = expression, "=", expression, ";";
+expression statement = expression, ";";
+return statement = "return", expression, ";";
+```
+
+A while statement is the `while` keyword followed by an expression, then zero or more statements surrounded by curly braces (the body).
+
+```ebnf
+while statement = "while", expression, block;
+```
+
+An if statement is the `if` keyword followed by an expression and a block, and optionally by the `else` keyword and another block.
+
+```ebnf
+if statement = "if", expression, block, ["else", block];
+```
+
+#### Expression Syntax
+
+Unambiguously describing expressions is somewhat tricky.
+
+For instance, consider the expression `1 - 2 - 3`.
+Is this the same expression as `(1 - 2) - 3`, or as `1 - (2 - 3)`?
+
+The ordinary rules of order of operations tell us that it's the former, but we need to specify how they work for operations that don't exist in ordinary math.
+For example, should the expression `x ++ y[3]` be the same as `(x ++ y)[3]` or the same as `x ++ (y[3])`?
+
+TODO: Should I explain precedence and associativity?
+Probably, since approximately every programming language spec uses them... or I could leave them until an after-the-code-works chapter.
+
+To help keep our description unambiguous, we describe two subcategories of expressions, atomic expressions and suffixed expressions.
+
+Atomic expressions are those expressions that don't contain operators that aren't enclosed within delimiters.
+This includes integer and string literals, variables, parenthesized expressions, and array literals.
+
+Array literals are comma-separated (and optionally comma-terminated) lists of expressions surrounded by curly braces.
+
+```ebnf
+atomic expression = integer literal | string literal
+ | identifier
+ | "(", expression, ")"
+ | "{", [expression list], "}";
+expression list = expression, {",", expression}, [","];
+```
+
+Suffixed expressions are atomic expressions followed by zero or more suffix operators.
+
+These are the call operator (a parenthesized list of comma-separated and optionally comma-terminated expressions) and the index operator (an expression surrounded by square brackets).
+
+```ebnf
+suffixed expression = atomic expression,
+ {expression suffix};
+expression suffix = call operator | index operator;
+call operator = "(", [expression list], ")";
+index operator = "[", expression, "]";
+```
+
+Finally, an expression is a sequence of one or more suffixed expressions separated by infix operators, which are `+`, `-`, `++`, and `==`.
+
+These operators have equal precedence and associate to the left; that is, `1 - 2 == 3 + 4` is the same as `(((1 - 2) == 3) - 4)`.
+While this isn't what most people are used to, it's easier to implement!
+
+```ebnf
+expression = suffixed expression
+ | expression, infix operator,
+ suffixed expression;
+```
+
+## Semantics
+
+TODO: lol, which formalism...
+
+---
+
+Unlike many (most?) other compiler tutorials, we *won't* be starting with parsing.
+Instead, we'll start with how we represent the program after it's been parsed.
+
+[ASCII printable characters]: https://en.wikipedia.org/wiki/ASCII#Printable_characters
+[context-free grammars]: https://en.wikipedia.org/wiki/Context-free_grammar
+[EBNF]: https://en.wikipedia.org/wiki/Extended_Backus%E2%80%93Naur_form
+[maximal munch]: https://en.wikipedia.org/wiki/Maximal_munch
diff --git a/Compiler in a Day/02-ast.page b/Compiler in a Day/02-ast.page
new file mode 100644
index 0000000..a130533
--- /dev/null
+++ b/Compiler in a Day/02-ast.page
@@ -0,0 +1,237 @@
++++
+title = "The Abstract Syntax Tree — Compiler In A Day"
+prev = "01-ciadlang.md"
+next = "03-frame-layout.md"
++++
+
+# The Abstract Syntax Tree
+
+Most programming languages' syntax can be described with a tree structure.
+An expression like `m.a * m.d - m.b * m.c` could be represented as:
+
+```
+ ╭────────── - ──────────╮
+ ╭──── * ────╮ ╭──── * ────╮
+ ╭─ . ─╮ ╭─ . ─╮ ╭─ . ─╮ ╭─ . ─╮
+var field var field var field var field
+ │ │ │ │ │ │ │ │
+"m" "a" "m" "d" "m" "b" "m" "c"
+```
+
+Such a tree is called an *abstract syntax tree*, or AST.
+
+TODO: Move the CST material to the "what to do better" section?
+
+In our compiler, the parser directly produces the AST.
+In some compilers, there's an intermediate tree called the *concrete syntax tree*, or CST.
+
+The CST is a tree that exactly corresponds to the input program, with every token present as a child.
+
+```
+ ╭────────────── binop ──────────────╮
+ ╭───── binop ─────╮ │ ╭───── binop ─────╮
+ ╭─ dot ─╮ │ ╭─ dot ─╮ │ ╭─ dot ─╮ │ ╭─ dot ─╮
+var │ field │ var │ field │ var │ field │ var │ field
+ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
+"m" "." "a" "*" "m" "." "d" "-" "m" "." "b" "*" "m" "." "c"
+```
+
+This tree is called the *concrete syntax tree*, or CST.
+It gets simplified to produce the AST.
+
+TODO: A better example, one where there's actual meaningful simplification?
+
+Typically, this is done so that type-checking and other error checks can be performed with as much information about the source code present as possible.
+
+In a simple compiler like ours, though, we don't lose much quality of error reporting checking for errors on the AST instead.
+
+Now, it's finally time to see some of the code in our compiler!
+
+To start with, we'll just define the structure of the tree as Ruby classes.
+
+Recall from [the syntactic grammar](./01-ciadlang.md#syntactic-grammar) that a program is a sequence of declarations.
+
+```ruby
+class Program
+ def initialize(decls)
+ @decls = decls
+ end
+end
+```
+
+Declarations either declare a function or a variable.
+Both have a name, but a function also has a list of arguments and a block of statements that comprise its body.
+
+```ruby
+class DeclFun
+ def initialize(name, args, body)
+ @name, @args, @body = name, args, body
+ end
+end
+
+class DeclVar
+ def initialize(name)
+ @name = name
+ end
+end
+```
+
+We'll also define a helper class for arguments.
+For now, this will just wrap the name of an argument, but later, it'll come in handy.
+
+```ruby
+class Arg
+ def initialize(name)
+ @name = name
+ end
+end
+```
+
+There are four kinds of statements: assignment statements, if statements, return statements, and while statements.
+These follow what's in the grammar.
+
+Remember, though, that expressions and variable declarations can also show up as statements!
+
+In a statically typed language, we would probably define `StmtExpr` and `StmtDeclVar` classes to handle them.
+However, we don't need to in Ruby, since it's dynamically typed!
+
+TODO: okay, I feel like I ought to justify this better...
+But the justification involves the visitors we're going to introduce later.
+
+```ruby
+class StmtAssign
+ def initialize(lhs, rhs)
+ @lhs, @rhs = lhs, rhs
+ end
+end
+
+class StmtIf
+ attr_reader :then_stmts
+ attr_reader :else_stmts
+ def initialize(cond, then_stmts, else_stmts)
+ @cond = cond
+ @then_stmts = then_stmts
+ @else_stmts = else_stmts
+ end
+end
+
+class StmtReturn
+ def initialize(expr)
+ @expr = expr
+ end
+end
+
+class StmtWhile
+ attr_reader :body_stmts
+ def initialize(cond, body_stmts)
+ @cond, @body_stmts = cond, body_stmts
+ end
+end
+```
+
+Finally, we have the classes for expressions.
+There are 10 of these, that are exactly like what we've seen so far.
+
+```ruby
+class ExprAppend # lhs ++ rhs
+ def initialize(lhs, rhs)
+ @lhs, @rhs = lhs, rhs
+ end
+end
+
+class ExprArrayIndex # array[index]
+ def initialize(array, index)
+ @array, @index = array, index
+ end
+end
+
+class ExprArrayLit # { exprs... }
+ def initialize(exprs)
+ @exprs = exprs
+ end
+end
+
+class ExprCall # func(args...)
+ def initialize(func, args)
+ @func, @args = func, args
+ end
+end
+
+class ExprEquals # lhs == rhs
+ def initialize(lhs, rhs)
+ @lhs, @rhs = lhs, rhs
+ end
+end
+
+class ExprIntLit
+ def initialize(value)
+ @value = value
+ end
+end
+
+class ExprMinus # lhs - rhs
+ def initialize(lhs, rhs)
+ @lhs, @rhs = lhs, rhs
+ end
+end
+
+class ExprPlus # lhs + rhs
+ def initialize(lhs, rhs)
+ @lhs, @rhs = lhs, rhs
+ end
+end
+
+class ExprStringLit
+ def initialize(value)
+ @value = value
+ end
+end
+
+class ExprVariable
+ def initialize(name)
+ @name = name
+ end
+end
+```
+
+Now that we have all these classes, we can build ASTs corresponding to programs.
+
+Let's look at a simple program and determine what its AST should look like.
+
+```ciad
+var x;
+
+fun main(args) {
+ x = length(args);
+ print({x, args});
+}
+```
+
+Because our AST is so simple, it corresponds pretty directly to the program.
+
+TODO: Is there more to say here?
+
+```ruby
+example = Program.new([
+ # var x;
+ DeclVar.new("x"),
+ # fun main(args) { ... }
+ DeclFun.new("main", [Arg.new("args")], [
+ # x = length(args);
+ StmtAssign.new(
+ ExprVariable.new("x"),
+ ExprCall.new("length", [ExprVariable.new("args")])),
+ # print({x, args});
+ ExprCall.new("print", [
+ ExprArrayLit.new([
+ ExprVariable.new("x"),
+ ExprVariable.new("args"),
+ ])
+ ]),
+ ]),
+])
+```
+
+Now that we have our AST, we'll need to process it.
+
+In the next post, we'll start the first "real step" of compiling: laying out stack frames.
diff --git a/Compiler in a Day/03-frame-layout.page b/Compiler in a Day/03-frame-layout.page
new file mode 100644
index 0000000..2f53308
--- /dev/null
+++ b/Compiler in a Day/03-frame-layout.page
@@ -0,0 +1,169 @@
++++
+title = "Frame Layout — Compiler In A Day"
+prev = "02-ast.md"
+next = "04-abi.md"
++++
+
+# Frame Layout
+
+When programs execute, their local variables' values are typically stored into a data structure called the *call stack*, or commonly just *the stack*.
+
+This is a stack data structure whose entries are called *stack frames*.
+These contain all the information that a function might need to save while calling another one.
+
+For example, consider the following program.
+
+```ciad
+fun f(x) {
+ var y;
+ var z;
+
+ y = x + 3;
+ z = g(x - 1);
+ return y - z;
+}
+
+fun g() {
+ if x == 0 {
+ return 42;
+ } else {
+ return f(x - 1);
+ }
+}
+
+fun main(args) {
+ return f(2);
+}
+```
+
+When `f` calls `g`, we need to store the value of `y` somewhere, so that it can be used again after `g` returns.
+We also need to store what function `f` should return to once it finishes, and we store that on the stack as well.
+
+In general, most languages structure their stacks as something like:
+
+```
+╭───────────────────────────────╮ <-- "bottom of the stack"
+│ address main should return to │ (highest address
+├───────────────────────────────┤ on most current
+│ saved frame pointer │ CPU architectures)
+├───────────────────────────────┤
+│ │
+│ saved local variables of main │
+│ │
+┝━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┥
+│ address f should return to │
+├───────────────────────────────┤
+│ saved frame pointer │
+├───────────────────────────────┤
+│ │
+│ saved local variables of f │
+│ │
+┝━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┥
+│ address g should return to │
+├───────────────────────────────┤
+│ saved frame pointer │ frame pointer
+├───────────────────────────────┤ <--------- when running g
+│ │
+│ local variables of g │ stack pointer
+│ │ when running g, aka
+╰───────────────────────────────╯ <----- "top of the stack"
+```
+
+The stack then "grows down" as functions are called.
+When a function returns, it removes its frame from the stack, shrinking it.
+
+The stack is kept track of with the *stack pointer*, which points to the top of the stack, i.e. the address at the _end_ of the current stack frame.
+
+In some programs, there's also a *frame pointer*.
+This points to the address at the start of local variables of the current stack frame.
+
+With a smarter compiler than we're building in this series, the frame pointer isn't necessary.
+However, it can still be useful for a debugger and some kinds of runtime introspection.
+
+In our compiler, we'll need to have a pass that computes how much storage the local variables of each function will take up in the stack frame.
+
+Once we know this, we can compute the address of any local variable as an offset from the frame pointer.
+
+Alright, let's get started with the code!
+
+The first thing we'll need to do is to extend `Arg` and `DeclVar` with the ability to store a slot index.
+This the offset of the variable from the frame pointer.
+
+```ruby
+class Arg
+ # ...
+
+ attr_accessor :slot
+end
+
+class DeclVar
+ # ...
+
+ attr_accessor :slot
+end
+```
+
+Then, we can add the method to perform the pass to the `Program` class.
+
+Computing frame layouts doesn't require any sort of information that's shared between functions, so we can just tell each function declaration to compute it independently.
+
+```ruby
+class Program
+ # ...
+
+ def compute_frame_layouts
+ @decls.each do |decl|
+ case decl
+ in DeclFun
+ decl.compute_frame_layout
+ in DeclVar
+ # Ignore it; variables don't have any kind of frame
+ # to be laid out.
+ end
+ end
+ end
+end
+```
+
+Once we're processing the function, we start with storing a counter for the number of local variables we have in the declaration.
+
+We define a helper function (`assign_slot_to`) to be called on every `Arg` and `DeclVar` in the function as well.
+
+```ruby
+class DeclFun
+ # ...
+
+ def compute_frame_layout
+ @locals_count = 0
+ def assign_slot_to(var)
+ var.slot = @locals_count
+ @locals_count += 1
+ end
+
+ @args.each { |arg| assign_slot_to arg }
+
+ def traverse_stmt(stmt)
+ case stmt
+ in DeclVar
+ assign_slot_to stmt
+
+ in StmtIf
+ stmt.then_stmts.each { |stmt| traverse_stmt stmt }
+ stmt.else_stmts.each { |stmt| traverse_stmt stmt }
+ in StmtWhile
+ stmt.body_stmts.each { |stmt| traverse_stmt stmt }
+
+ else
+ # Do nothing; nothing else needs to get a slot nor
+ # contains anything that needs to get a slot.
+ end
+ end
+
+ @body.each { |stmt| traverse_stmt stmt }
+ end
+end
+```
+
+Once this has finished running, every `DeclStmt` will have an `@locals_count`, and every `Arg` and non-global `DeclVar` will have an `@slot`.
+
+Before we can start generating code, though, we should look at some details of exactly what code we'll be generating.
diff --git a/Compiler in a Day/04-abi.page b/Compiler in a Day/04-abi.page
new file mode 100644
index 0000000..ec96b40
--- /dev/null
+++ b/Compiler in a Day/04-abi.page
@@ -0,0 +1,136 @@
++++
+title = "The ABI — Compiler In A Day"
+prev = "03-frame-layout.md"
+next = "05-codegen.md"
++++
+
+# The ABI
+
+We're ready to start making the final decisions about the machine code we're going to produce.
+
+To reiterate, we're _not_ aiming to produce efficient machine code for now.
+We're just aiming to get the simplest thing that works.
+
+The important things to decide are:
+
+- How different registers are allowed to be used.
+- The way we pass arguments to and receive arguments from functions.
+- How the various data types in our language are represented.
+
+These questions (and more related ones we won't touch on) are called the *application binary interface*, or ABI.
+
+Usually, a platform has an ABI already defined and documented for the C programming language.
+This C ABI serves as the "lowest common denominator" for other languages' ABIs.
+
+Even though you can make your compiler follow whatever ABI you want, it simplifies calling into other languages (and letting them call your code) if it roughly follows the C ABI.
+
+Although we aren't providing features for users to interoperate with any other code they want, we still need to call into our runtime.
+Since our runtime will be written in C, we want to make this as painless as possible.
+
+We're producing code to run on Linux on x86_64 CPUs, so the most relevant C ABI document is the [AMD64 Architecture Processor Supplement of the System V ABI].
+
+We can copy its choices about how registers can be used, and how arguments get passed to and return values get returned from functions:
+
+| Registers | Saved by | Notes |
+| -------------------------- | -------- | --------------------- |
+| rdi, rsi, rdx, rcx, r8, r9 | Caller | Function arguments |
+| rax | Caller | Function return value |
+| r10, r11 | Caller | |
+| rbp | Callee | Frame pointer |
+| rsp | Callee | Stack pointer |
+| rbx, r12, r13, r14, r15 | Callee | |
+
+When a register is caller-saved, that means that the functions we generate are allowed to freely modify them.
+However, so is any function we call, so we can't rely on values in them staying unchanged.
+
+Conversely, a callee-saved register must be restored to its original value before we return, but we can rely on functions we call doing the same.
+
+Next, we need to figure out how we're going to represent values.
+We have three types of values: integers, strings, and arrays.
+
+Since we're implementing a dynamically typed language, any variable needs to be able to store values of any of these types.
+
+We also want values to fit in a single (64-bit) register, for simplicity and performance.
+
+Finally, we want values that contain memory addresses to be represented by those addresses, so that the garbage collector we're using can recognize them as pointers.
+
+The easiest thing to do is to simply represent all three as pointers to structures in the heap that have information about the type stored in them.
+
+For example, the array `{42, "foo"}` might be represented as the pointer `0x08001230`, pointing to data like:
+
+```
+╭────────────╮
+│ 0x08001230 │ HEAP
+╰────────────╯
+ │ │ ... │
+ ╰─> ├────────────┤
+ type tag │ ARRAY │
+ data pointer │ 0x08001250 │───╮
+ length │ 2 │ │
+ capacity │ 4 │ │
+ ├────────────┤ <─╯
+ │ 0x08001270 │─────╮
+ │ 0x08001280 │───╮ │
+ │ 0 │ │ │
+ │ 0 │ │ │
+ ├────────────┤ <───╯
+ type tag │ INTEGER │ │
+ value │ 42 │ │
+ ├────────────┤ <─╯
+ type tag │ STRING │
+ data pointer │ 0x080012a0 │───╮
+ length │ 2 │ │
+ capacity │ 8 │ │
+ ├────────────┤ <─╯
+ │ "foo", ... │
+ ├────────────┤
+ │ ... │
+```
+
+We know that `0x08001230` points to an array, since when we dereference it, we get the `ARRAY` constant.
+
+It doesn't really matter what values the `INTEGER`, `ARRAY`, and `STRING` constants have.
+For simplicity, let's make them:
+
+| Constant | Value |
+| --------- | ----- |
+| `INTEGER` | 0 |
+| `ARRAY` | 1 |
+| `STRING` | 2 |
+
+So, putting it all together, let's imagine the equivalent of this simple function in C:
+
+```
+fun f(arr, x) {
+ return arr[x] + x;
+}
+```
+
+It might look something like:
+
+```c
+enum type_tag { INTEGER, ARRAY, STRING };
+struct array { struct value** data_ptr; size_t len, cap; };
+struct string { char* data_ptr; size_t len, cap; };
+struct value {
+ enum type_tag tag;
+ union {
+ int64_t integer;
+ struct array array;
+ struct string string;
+ };
+};
+
+struct value* f(struct value* arr, struct value* x) {
+ assert(arr->tag == ARRAY);
+ assert( x->tag == INTEGER);
+ assert(x->integer < arr->array.len);
+ struct value* arr_x = arr->array.data_ptr[x->integer];
+
+ assert(arr_x->tag == INTEGER);
+ assert( x->tag == INTEGER);
+ return make_int(arr_x->integer + x->integer);
+}
+```
+
+[AMD64 Architecture Processor Supplement of the System V ABI]: https://gitlab.com/x86-psABIs/x86-64-ABI
diff --git a/Compiler in a Day/05-codegen.page b/Compiler in a Day/05-codegen.page
new file mode 100644
index 0000000..2d21d75
--- /dev/null
+++ b/Compiler in a Day/05-codegen.page
@@ -0,0 +1,136 @@
++++
+title = "Code Generation — Compiler In A Day"
+prev = "04-abi.md"
+next = "05-codegen.md"
++++
+
+# Code Generation
+
+We're ready to start producing machine code!
+
+To reiterate, we're _not_ aiming to produce efficient machine code for now.
+We're just aiming to get the simplest thing that works.
+
+Before we actually dive into generating code, there's a bit more to decide.
+The important things to decide are:
+
+- How different registers are allowed to be used.
+- The way we pass arguments to and receive arguments from functions.
+- How the various data types in our language are represented.
+
+These questions (and more related ones we won't touch on) are called the *application binary interface*, or ABI.
+
+Usually, a platform has an ABI already defined and documented for the C programming language, and this serves as the "lowest common denominator" for other languages' ABIs.
+
+Even though you can make your compiler follow whatever ABI you want, it simplifies calling into other languages (and letting them call your code) if it roughly follows the C ABI.
+
+Although we aren't providing features for users to interoperate with any other code they want, we still need to call into our runtime.
+Since our runtime will be written in C, we want to make this as painless as possible.
+
+We're producing code to run on Linux on x86_64 CPUs, so the most relevant C ABI document is the [AMD64 Architecture Processor Supplement of the System V ABI].
+
+We can copy its choices about how registers can be used, and how arguments get passed to and return values get returned from functions:
+
+| Registers | Saved by | Notes |
+| -------------------------- | -------- | --------------------- |
+| rdi, rsi, rdx, rcx, r8, r9 | Caller | Function arguments |
+| rax | Caller | Function return value |
+| r10, r11 | Caller | |
+| rbp | Callee | Frame pointer |
+| rsp | Callee | Stack pointer |
+| rbx, r12, r13, r14, r15 | Callee | |
+
+When a register is caller-saved, that means that the functions we generate are allowed to freely modify them.
+However, so is any function we call, so we can't rely on values in them staying unchanged.
+
+Conversely, a callee-saved register must be restored to its original value before we return, but we can rely on functions we call doing the same.
+
+Next, we need to figure out how we're going to represent values.
+We have three types of values: integers, strings, and arrays.
+
+Since we're implementing a dynamically typed language, any variable needs to be able to store values of any of these types.
+
+We also want values to fit in a single (64-bit) register, for simplicity and performance.
+
+Finally, we want values that contain memory addresses to be represented by those addresses, so that the garbage collector we're using can recognize them as pointers.
+
+The easiest thing to do is to simply represent all three as pointers to structures in the heap that have information about the type stored in them.
+
+For example, the array `{42, "foo"}` might be represented as the pointer `0x08001230`, pointing to data like:
+
+```
+╭────────────╮
+│ 0x08001230 │ HEAP
+╰────────────╯
+ │ │ ... │
+ ╰─> ├────────────┤
+ type tag │ ARRAY │
+ data pointer │ 0x08001250 │───╮
+ length │ 2 │ │
+ capacity │ 4 │ │
+ ├────────────┤ <─╯
+ │ 0x08001270 │─────╮
+ │ 0x08001280 │───╮ │
+ │ 0 │ │ │
+ │ 0 │ │ │
+ ├────────────┤ <───╯
+ type tag │ INTEGER │ │
+ value │ 42 │ │
+ ├────────────┤ <─╯
+ type tag │ STRING │
+ data pointer │ 0x080012a0 │───╮
+ length │ 2 │ │
+ capacity │ 8 │ │
+ ├────────────┤ <─╯
+ │ "foo", ... │
+ ├────────────┤
+ │ ... │
+```
+
+We know that `0x08001230` points to an array, since when we dereference it, we get the `ARRAY` constant.
+
+It doesn't really matter what values the `INTEGER`, `ARRAY`, and `STRING` constants have.
+For simplicity, let's make them:
+
+| Constant | Value |
+| --------- | ----- |
+| `INTEGER` | 0 |
+| `ARRAY` | 1 |
+| `STRING` | 2 |
+
+So, putting it all together, let's imagine the equivalent of this simple function in C:
+
+```
+fun f(arr, x) {
+ return arr[x] + x;
+}
+```
+
+It might look something like:
+
+```c
+enum type_tag { INTEGER, ARRAY, STRING };
+struct array { struct value** data_ptr; size_t len, cap; };
+struct string { char* data_ptr; size_t len, cap; };
+struct value {
+ enum type_tag tag;
+ union {
+ int64_t integer;
+ struct array array;
+ struct string string;
+ };
+};
+
+struct value* f(struct value* arr, struct value* x) {
+ assert(arr->tag == ARRAY);
+ assert( x->tag == INTEGER);
+ assert(x->integer < arr->array.len);
+ struct value* arr_x = arr->array.data_ptr[x->integer];
+
+ assert(arr_x->tag == INTEGER);
+ assert( x->tag == INTEGER);
+ return make_int(arr_x->integer + x->integer);
+}
+```
+
+[AMD64 Architecture Processor Supplement of the System V ABI]: https://gitlab.com/x86-psABIs/x86-64-ABI
diff --git a/Compiler in a Day/run.sh b/Compiler in a Day/run.sh
new file mode 100755
index 0000000..1eebc4c
--- /dev/null
+++ b/Compiler in a Day/run.sh
@@ -0,0 +1,8 @@
+#!/bin/sh
+awk -f- *.md <<EOF | ruby
+BEGIN { emit = 0 }
+
+/^\`\`\`\$/ { if(emit) print ""; emit = 0 }
+{ if(emit) print }
+/^\`\`\`ruby\$/ { emit = 1 }
+EOF
generated by cgit v1.2.3 (git 2.25.1) at 2025-04-28 11:53:59 +0000