Proving that a compiler is correct
This is the capstone project. After finishing this section, you will have a mini compiler, plus a theorem checked by Lean: for any expression, the result computed by the compiled instructions is the same as evaluating the expression directly.
Not "tested on many expressions and all passed" — all of them.
Everything used here is what you learned before: defining functions, doing induction on structures, and finding lemmas when stuck.
Before you start
- Learned about doing induction on lists, and know what a lemma is
- Create a new file
Compiler.lean, and write the code below into it in order
Step 1: Define expressions, and what they "should" evaluate to
An expression is either a number, the sum of two expressions, or the product of two expressions:
inductive Expr where
| num : Nat → Expr
| add : Expr → Expr → Expr
| mul : Expr → Expr → Exprinductive defines a new kind of data, listing all of its possible shapes.
Evaluate an expression directly:
def eval : Expr → Nat
| .num n => n
| .add a b => eval a + eval b
| .mul a b => eval a * eval beval is the definition of the "correct answer". Whether the compiler later is correct is judged against it.
Try it with 2 + 3 × 4:
def demo : Expr := .add (.num 2) (.mul (.num 3) (.num 4))
#eval eval demo14eval demoevaluates to 14
Step 2: Define a machine that only understands three instructions
This machine has a stack, that is, a pile of numbers that can only be added to and taken from the top. There are three instructions:
inductive Instr where
| push : Nat → Instr
| add
| mulpush n: put n on top of the stack.add: take the top two numbers off the stack, and put their sum back.mul: take the top two numbers off the stack, and put their product back.
Run a sequence of instructions:
def run : List Instr → List Nat → List Nat
| [], stack => stack
| .push n :: rest, stack => run rest (n :: stack)
| .add :: rest, b :: a :: stack => run rest ((a + b) :: stack)
| .mul :: rest, b :: a :: stack => run rest ((a * b) :: stack)
| _ :: rest, stack => run rest stackrun 指令 栈 returns the stack after the run. The last line handles the case where the stack has fewer than two numbers: it skips that instruction.
Instrandrunproduce no errors
Step 3: Write the compiler
Translate an expression into instructions. A number is just push; addition compiles the left side first, then the right side, and finally add:
def compile : Expr → List Instr
| .num n => [.push n]
| .add a b => compile a ++ compile b ++ [.add]
| .mul a b => compile a ++ compile b ++ [.mul]Compile the expression from before and run it on an empty stack:
#eval run (compile demo) [][14]The top of the stack is 14, same as eval demo. But this is only one expression.
run (compile demo) []gives[14]
Step 4: Write down the statement to prove
"The compiler is correct" first needs to be stated clearly:
theorem compile_correct (e : Expr) (s : List Nat) :
run (compile e) s = eval e :: sRead it out: for any expression e and any initial stack s, running the instructions compiled from e results in one more number on top of s, and that number is exactly eval e.
This step matters more than the proof itself. As said in the first section: Lean checks the statement you write down. Only if the statement is right does the proof mean anything.
Note that it says "any initial stack s", not just the empty stack. The reason will become clear shortly.
- I can state in my own words what
compile_correctis claiming
Step 5: Prove the helper first
The result of compile is several segments of instructions stitched together. To reason about it, you first need to know: running two stitched-together segments of instructions equals running the first segment, then running the second segment on the stack it leaves behind.
theorem run_append (p q : List Instr) (s : List Nat) :
run (p ++ q) s = run q (run p s) := by
induction p generalizing s with
| nil =>
rfl
| cons i rest ih =>
cases i <;> rcases s with _ | ⟨b, _ | ⟨a, s⟩⟩ <;> simp [run, ih]This is induction on the instruction list p. There are two new things:
generalizing s: makes the induction hypothesis hold for any stack. The stack changes with every instruction executed, so a hypothesis that holds only for one fixed stack is useless. This is also why the theorem in the previous step had to say "any stack s".- The last line: depending on which of the three kinds the first instruction is, and whether the stack has zero, one, or at least two numbers, it lists all the cases and hands each one to
simp.<;>means "do the following step on every goal produced".
You don't need to fully understand this line right now. Knowing that it does "split into cases, then simplify each one" is enough.
run_appendpasses
Step 6: Prove that the compiler is correct
Do induction on the shape of the expression. Expressions have three shapes, so there are three branches; addition and multiplication each have two sub-expressions, so each has two induction hypotheses. Walk through it yourself:
theorem compile_correct (e : Expr) (s : List Nat) : run (compile e) s = eval e :: s := by
induction e generalizing s with
| num n =>
rfl
| add a b iha ihb =>
simp [compile, run_append, iha, ihb, run, eval]
| mul a b iha ihb =>
simp [compile, run_append, iha, ihb, run, eval]
Write it into the file:
theorem compile_correct (e : Expr) (s : List Nat) :
run (compile e) s = eval e :: s := by
induction e generalizing s with
| num n =>
rfl
| add a b iha ihb =>
simp [compile, run_append, iha, ihb, run, eval]
| mul a b iha ihb =>
simp [compile, run_append, iha, ihb, run, eval]You should see: no errors.
What happens in the addition branch: compile expands into three segments of instructions; run_append breaks "running three segments" into running them one segment at a time; iha says that after the first segment runs, the stack has eval a more on top, and ihb says that after the second segment runs, it has eval b more; the final add adds them together, which is exactly eval (.add a b).
compile_correctpasses
Step 7: Deliberately write an incorrect compiler
Whether verification is useful depends on whether it can catch errors. Compile addition incorrectly: don't compile the right-hand expression, and compile the left-hand one twice.
def badCompile : Expr → List Instr
| .num n => [.push n]
| .add a _ => badCompile a ++ badCompile a ++ [.add]
| .mul a b => badCompile a ++ badCompile b ++ [.mul]
theorem bad_correct (e : Expr) (s : List Nat) :
run (badCompile e) s = eval e :: s := by
induction e generalizing s with
| num n =>
rfl
| add a b iha ihb =>
simp [badCompile, run_append, iha, ihb, run, eval]
| mul a b iha ihb =>
simp [badCompile, run_append, iha, ihb, run, eval]You should see: the addition branch fails to verify, and the error message starts with this line:
unsolved goalsThis incorrect compiler gives correct results for expressions like 1 + 1 and 2 + 2, where the two sides are the same. Testing only these would pass. The proof will not.
- I saw the incorrect compiler fail to verify
Checkpoint
- My
Compiler.leanhas no errors from start to finish - I can say what
eval,run, andcompileeach are - I can read out what the statement
compile_correctmeans - I know why the lemma
run_appendis needed - I have seen an error that a test can slip past but a proof cannot
Didn't work?
compile_correct reports an error saying it doesn't know run_append. The lemma must be written before it.
The addition branch still has unproven goals left. Check the six items inside the brackets of simp — not one can be missing. Especially run_append: without it, the stitched-together instructions cannot be taken apart.
The induction hypothesis can't be used. Check whether induction e is followed by generalizing s.
What you accomplished
You defined the meaning of a small language, wrote a compiler, and proved that it preserves the meaning. Verifying a program always comes down to these three things: write down what "correct" means, write the program, and prove that the program satisfies it.
Things you can try on your own next:
- Add a new shape to
Expr, such as subtraction. Lean will tell you which functions and proofs need a new branch added. - Swap the order of a and b in
compile, then look atcompile_correct. The addition branch will be left with one goal:eval b + eval a = eval a + eval b. This statement is true, andNat.add_commfrom the previous chapter can fill it in. What about subtraction? Is the remaining statement still true?