Lesson plan

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.

4 chapters, 7 lessons, about 7 hours, on the Raspberry Pi 4 Model B. Every lesson runs in the browser, with nothing to install.

The unit

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.

Chapter 1. About 2 h

The target

The Kestrel, its words, and a tree turned into instructions.

LessonTimeWhat 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
  1. Run it: assembly into words
  2. Labels, in two passes
  3. An emulator
  4. Words for the ROM
  5. Read a word by hand
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
  1. Run it: a tree into instructions
  2. Subtraction
  3. Deeper trees, more registers
  4. Out of registers
  5. Characters

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".

Chapter 2. About 2 h

Registers and jumps

Where each value lives, and if and while as jumps.

LessonTimeWhat 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
  1. Run it: variables live in RAM
  2. Assignment
  3. Pick the cheaper instruction
  4. The ninth variable
  5. Where values live
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
  1. Run it: if is a jump
  2. while is two jumps
  3. Multiply without a multiply
  4. Not equal is a subtraction
  5. A loop that never ends

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".

Chapter 3. About 2 h

Calls and speed

A call stack on a CPU with no call instruction, then fewer words and cycles.

LessonTimeWhat 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
  1. Run it: a call is a jump
  2. Call it twice
  3. Calls inside calls need a stack
  4. Recursion
  5. Stack overflow
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
  1. Run it: measure first
  2. Constant folding
  3. A peephole pass
  4. Store, then load the same byte
  5. Faster is not free

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".

Chapter 4. About 50 min

Boss

Your language, compiled on the Pi, running on gates.

LessonTimeWhat 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
  1. Compile on the Pi
  2. Load the ROM and run it on gates
  3. Your program, your CPU
  4. What you built

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".

Your class

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.