Lessons and the learning game

Compile a language to the Kestrel CPU

Write a compiler in Python on a Raspberry Pi, and run its machine code on the CPU you built from NAND gates.

The course

Compile a language to the Kestrel CPU is an expert Coding course in seven lessons. It follows Build a programming language, whose Orbit language it compiles, and From gates to a computer, whose Kestrel CPU it targets. Lessons 1 to 6 run on a Raspberry Pi 4 (the gallery's two-LED circuit), and each step is checked against what the Pi prints.

  1. Targets and assembly: the Kestrel's 16-bit word (opcode, Rd, Rs, constant), an assembler with labels in two passes, an emulator that runs the words, and .word lines the program ROM can take.
  2. Code generation: Orbit parsed into a tree and walked into instructions, registers handed out by depth, a tree too deep for four registers that first compiles to a wrong answer and then is refused, and character constants for the terminal.
  3. Registers: variables in the Kestrel's 8 bytes of RAM with R3 kept back for addresses, assignment, ADDI picked for constants (41 words down to 39), and the ninth variable that lands on the first.
  4. Control flow: if and while as labels and jumps, 6 x 7 by a loop on a CPU with no multiply, != lowered to a subtraction, and a loop that never ends.
  5. A stack and calls: the Kestrel has no CALL, no RET and no jump through a register, so each call site gets a number and each function ends in a jump table. A stack in RAM lets calls nest and recurse, and a count from 6 shows a stack overflow writing over a variable.
  6. Optimizing: constant folding and a peephole pass, measured in words and cycles: from 24 words and 70 cycles to 18 and 56, with the same output.
  7. Boss: your language on your CPU.

The Boss

The last canvas holds two machines: a Raspberry Pi running the finished compiler, and the computer from the logic course (a step clock, a program ROM, the Kestrel chip of about four thousand NAND gates, and a terminal). The Pi compiles an Orbit countdown and prints 23 .word lines. Pasted into the ROM, they run on the gates: after RESET the terminal prints 3 2 1 GO, and the check counts its 8 bytes. Then the countdown starts at 5, one word changes, and the terminal prints 12 bytes. From there the program is yours.

What the Pi's engine does differently

The Pi runs MicroPython 1.29, not CPython:

  • The compiler uses only lists, tuples, dicts for lookups, % formatting and string methods MicroPython has (partition, strip, isdigit, isalpha), so it runs the same in CPython on a desk.
  • A dict here does not keep the order its keys went in. Nothing in the compiler depends on it: variables get their bytes from a counter, and call sites are kept in lists.
  • Errors the compiler raises (out of registers, out of RAM) print as a normal traceback in the Serial Monitor.

The catalog line names the program ROM and the terminal. Both are on the Boss canvas, beside the Pi; lessons 1 to 6 test the code on the emulator the learner writes, which follows the Kestrel's reference model.