Master

Generating code instead of answering

The last pass stops answering and starts writing instructions. The instructions are a shape too, and the shape is the reason a compiler is a compiler rather than an interpreter.

What you will see

1. One distinct answer is the equality, which is the whole proof.

About 1 min of reading

Try It

Write instructions and prove agreement

1

Write three instructions

printf 'load r0 1\nload r1 2\nadd r0 r1\n' > /tmp/i.txt; wc -l < /tmp/i.txt

Before you run it, say out loud what it will print. Then open the answer.

What it prints
3. Three instructions is the shape, and slots are the places.
2

Run the machine

printf 'add r0 r1\n' | awk '{print $3+0}'

Before you run it, say out loud what it will print. Then open the answer.

What it prints
1. The machine read a slot, which is what makes the instruction runnable.
3

Prove the answers agree

printf 'eval 3\nrun 3\n' | awk '{print $2}' | sort -u | wc -l

Before you run it, say out loud what it will print. Then open the answer.

What it prints
1. One distinct answer is the equality, which is the whole proof.

Data Flow

A tree to instructions that agree
1 The tree is walked in the evaluator order
↓
2 Each node writes instructions with slots
↓
3 The instructions are run by a small machine
↓
4 The run answer equals the evaluator answer
Why this works
Why the instruction set is small

A small set is a machine that is easy to write. The machine is written once and the compiler is written many times, so the set is small.

The register is a slot

A slot has a number. A number is a place, and a place is what makes a value live rather than copied.

Examples

An instruction is a name and places

It says what to do with which slots. Slots rather than values is what makes the instruction runnable later.

The tree walk writes instructions in order

The children are written before the parent. The order is the same order the evaluator used, and the sameness is the claim.

The two answers must agree

The evaluator answer equals the run answer. The equality is checked by a test, and the test is the whole proof.

Words this lesson uses

Each one is defined here on this site. Open the entry for the full definition and the other words it points at.

← Names and scopes
Previous Lesson
Names and scopes
Next Lesson
Debugging a compiler that is wrong
Debugging a compiler that is wrong →