The talk, then the spine of the semester in an hour: the axis, the three theorems, and the definition a compiler class earns.
That sentence is the class: fourteen weeks of building starc, selfie's compiler, extension by extension.
The purpose is shared with the companion classes: principles deep enough to position generative AI, and whatever comes next, properly. A compiler is where notation meets meaning most exactly.
Twelve autograded extensions of selfie, from hexadecimal literals to structs, one per week. And in week 12: verify your own extension with a model checker.
What is Intelligence? The Programming chapter is this class. Read the Introduction and the Selfie chapter this week.
Finite, countable. Bits, and everything you can write down: programs, grammars, binaries. Weeks 2 to 5 live here — scanner, parser, code generator — and they never leave the decidable.
Uncountable. What programs mean. Weeks 6 to 9 — statements, procedures, self-compilation, optimisation — are where the compiler constructs meaning and where Gödel, Turing and Rice say what it cannot decide about it.
Cost. Weeks 10 to 12 turn the compiler's output into a formula, hand it to a solver, and meet NP-completeness. Then a week on generated code, and the definition.
The compiler compiles its own source and gets the same bytes twice. Gödel's self-reference, runnable. It proves self-agreement — and week 8 says what it cannot prove.
An emulator that runs every program for its machine, itself included. Turing's move, forwards. The target of every instruction you will emit.
A hypervisor that must isolate itself from the machines it isolates. The systems class. Here, only the reminder that the loop is the subject.
Programs are countable; behaviours are not. So almost every behaviour has no program, and no analysis of programs can list what they do. Semantic analysis is approximation, by counting alone.
No strong system certifies itself. A compiler that agrees with itself has certified nothing; the outside check is a second compiler, or a solver. Week 8, with Thompson.
Every non-trivial property of behaviour is undecidable; only questions about the text are safe. Type checking is about the text. Dead code is about behaviour. Week 4 and week 9.
All three are one move: assume a complete list, ask each item about itself, answer the opposite. The introduction class proves them; here they are the constraints the compiler is built under.
Twelve thousand lines, one file: the compiler starc, the emulator mipster, the hypervisor hypster, and a small library. The compiler is about four thousand of those lines and you will read all of them.
C*: 7 keywords, 22 symbols, LL(1), one type and pointers to it. RISC-U: 14 instructions, 32 registers, 4 GB. Small enough to hold in one head, which is the only argument for the size.
| wk | lecture | assignment |
|---|---|---|
| 2 | The scanner | hex-literal |
| 3 | The parser | — |
| 4 | Symbols and types | bitwise-shift-compilation |
| 5 | Expressions | bitwise-shift-execution |
| 6 | Statements | bitwise-and-or-not logical-and-or-not |
| 7 | Procedures | for-loop, lazy-evaluation |
| 8 | Self-compilation | array-access |
| wk | lecture | assignment |
|---|---|---|
| 9 | Optimisation and Rice | array-allocation |
| 10 | Semantics as a formula | array-multidimensional |
| 11 | SAT | struct-declaration |
| 12 | Bounded model checking | struct-execution rotor-check |
| 13 | Generated code | — |
| 14 | What a compiler is | — |
The scanner: characters into symbols, one finite state machine per kind of symbol, and your first extension of the grammar — hexadecimal integer literals.
Bach · The Art of Fugue — Musica Antiqua Köln, 1984. Fourteen fugues on one subject, and the last breaks off as the notes B-A-C-H enter: the work names its author and halts. A compiler class begins with a text that signs itself.
Compilers: Principles, Techniques, and Tools — Aho, Lam, Sethi and Ullman, the dragon book: the field in one volume, and the knight on the cover is you. And, more technical, Compiler Construction — Wirth, 2005, free from ETH: a whole compiler in a hundred pages, and the closest thing in print to how selfie does it.