Compile a language to the Kestrel CPU lesson plan
Write a compiler in Python on a Raspberry Pi that turns Orbit into machine code for the Kestrel: assembler, code generation, registers, jumps, a call stack and an optimizer, ending with your language running on the CPU you built from NAND gates.
Objectives and materials
By the end, students can
- The Kestrel, its words, and a tree turned into instructions.
- Where each value lives, and if and while as jumps.
- A call stack on a CPU with no call instruction, then fewer words and cycles.
- Your language, compiled on the Pi, running on gates.
Materials for the whole unit
- Bit switch
- chip:c26
- Half breadboard
- LED x 2
- Program ROM
- Raspberry Pi 4 Model B
- Resistor x 2
- Step clock
- Terminal
Every part is already on the simulator’s bench, so there is nothing to buy or hand out. The counts are the most any one lesson uses, if you build it on real breadboards too.
The target
The Kestrel, its words, and a tree turned into instructions.
| Lesson | Time | What students do |
|---|---|---|
| Targets and assemblyMeet the target: the Kestrel, the CPU built from NAND gates in From gates to a computer. Write an assembler in Python that turns its assembly into the 16-bit words its ROM holds, then an emulator that runs them. | 60 min |
|
| Code generationTurn Orbit into Kestrel assembly: parse into a tree, then walk the tree and emit an instruction for every node. Registers handed out by depth, a tree too deep for four of them, and characters on the terminal. | 60 min |
|
Materials
- Half breadboard
- LED x 2
- Raspberry Pi 4 Model B
- Resistor x 2
Check for understanding
Each student finishes "Code generation" on their own, without opening the hints. The simulator checks 5 of its 5 steps as they go.
Then ask each one to explain, in a sentence or two, the last thing it asked of them: "Characters".
Registers and jumps
Where each value lives, and if and while as jumps.
| Lesson | Time | What students do |
|---|---|---|
| RegistersVariables in the Kestrel's 8 bytes of RAM, one register kept back for addresses, assignment, picking the cheaper instruction for a constant, and the ninth variable that lands on the first. | 60 min |
|
| Control flowif and while compiled to labels and jumps, multiplication by a loop on a CPU with no multiply, not-equal as a subtraction, and a loop that never ends. | 60 min |
|
Materials
- Half breadboard
- LED x 2
- Raspberry Pi 4 Model B
- Resistor x 2
Check for understanding
Each student finishes "Control flow" on their own, without opening the hints. The simulator checks 5 of its 5 steps as they go.
Then ask each one to explain, in a sentence or two, the last thing it asked of them: "A loop that never ends".
Calls and speed
A call stack on a CPU with no call instruction, then fewer words and cycles.
| Lesson | Time | What students do |
|---|---|---|
| A stack and callsFunctions on a CPU with no call instruction: a return number and a jump table the compiler writes, a stack in RAM so calls can nest, recursion, and a stack overflow you can watch. | 60 min |
|
| OptimizingMake the code smaller and faster without changing what it prints: constant folding in the parser, and a peephole pass that drops address loads and reloads the Kestrel does not need. Measured in words and cycles. | 60 min |
|
Materials
- Half breadboard
- LED x 2
- Raspberry Pi 4 Model B
- Resistor x 2
Check for understanding
Each student finishes "Optimizing" on their own, without opening the hints. The simulator checks 5 of its 5 steps as they go.
Then ask each one to explain, in a sentence or two, the last thing it asked of them: "Faster is not free".
Boss
Your language, compiled on the Pi, running on gates.
| Lesson | Time | What students do |
|---|---|---|
| Boss: your language on your CPUThe Pi compiles an Orbit countdown with your compiler, and the words go into the program ROM of the computer you built from NAND gates. The Kestrel runs your language, and the terminal prints it. | 50 min |
|
Materials
- Bit switch
- chip:c26
- Program ROM
- Raspberry Pi 4 Model B
- Step clock
- Terminal
Check for understanding
Each student finishes "Boss: your language on your CPU" on their own, without opening the hints. The simulator checks 4 of its 4 steps as they go.
Then ask each one to explain, in a sentence or two, the last thing it asked of them: "What you built".
Teach this unit as a class
Start a class from this course and its 7 lessons are assigned in one go, in order. Students join with a six-character code or printed login cards, and each one’s work comes back to you.
The class tools are free for 30 days for one class of up to 20 students, with no card. The lessons themselves are free either way.