Lecciones y el juego de aprendizaje

Compila un lenguaje al CPU Kestrel

Escribe un compilador en Python en una Raspberry Pi, y ejecuta su código de máquina en la CPU que construiste con compuertas NAND.

El curso

Compile a language to the Kestrel CPU is an expert Coding course in seven lessons. It follows Construye un lenguaje de programación, cuyo lenguaje Orbit compila, y a De compuertas a una computadora, cuyo CPU Kestrel es el destino. Las lecciones 1 a 6 corren en una Raspberry Pi 4 (el circuito de dos LEDs de la galería), y cada paso se verifica contra lo que imprime la Pi.

  1. Destinos y ensamblador: la palabra de 16 bits del Kestrel (opcode, Rd, Rs, constante), un ensamblador con etiquetas en dos pasadas, un emulador que ejecuta las palabras, y líneas .word que la ROM del programa puede aceptar.
  2. Generación de código: Orbit analizado en un árbol y recorrido hasta instrucciones, registros asignados por profundidad, un árbol demasiado profundo para cuatro registros que primero compila a una respuesta incorrecta y luego es rechazado, y constantes de caracteres para la terminal.
  3. Registros: variables en los 8 bytes de RAM del Kestrel con R3 reservado para direcciones, asignación, ADDI elegido para constantes (de 41 palabras a 39), y la novena variable que cae sobre la primera.
  4. Flujo de control: if y while como etiquetas y saltos, 6 x 7 con un ciclo en un CPU sin multiplicación, != reducido a una resta, y un ciclo que nunca termina.
  5. Una pila y llamadas: el Kestrel no tiene CALL, ni RET, ni salto a través de un registro, así que cada sitio de llamada recibe un número y cada función termina en una tabla de saltos. Una pila en RAM permite que las llamadas se aniden y haya recursión, y un conteo desde 6 muestra un desbordamiento de pila sobrescribiendo una variable.
  6. Optimización: plegado de constantes y una pasada peephole, medidas en palabras y ciclos: de 24 palabras y 70 ciclos a 18 y 56, con la misma salida.
  7. Jefe final: tu lenguaje en tu CPU.

El Jefe final

El último lienzo contiene dos máquinas: una Raspberry Pi ejecutando el compilador terminado, y la computadora del curso de lógica (un reloj de pasos, una ROM de programa, el chip Kestrel de unas cuatro mil compuertas NAND, y una terminal). La Pi compila una cuenta regresiva en Orbit e imprime 23 líneas .word. Pegadas en la ROM, corren sobre las compuertas: después de RESET la terminal imprime 3 2 1 GO, y la verificación cuenta sus 8 bytes. Luego la cuenta regresiva empieza en 5, una palabra cambia, y la terminal imprime 12 bytes. Desde ahí el programa es tuyo.

Qué hace distinto el motor de la Pi

La Pi corre MicroPython 1.29, no CPython:

  • El compilador usa solo listas, tuplas, diccionarios para búsquedas, formato con % y métodos de cadena que MicroPython tiene (partition, strip, isdigit, isalpha), así que corre igual en CPython en una computadora de escritorio.
  • Un dict aquí no conserva el orden en que entraron sus llaves. Nada en el compilador depende de eso: las variables obtienen sus bytes de un contador, y los sitios de llamada se guardan en listas.
  • Los errores que el compilador lanza (out of registers, out of RAM) se imprimen como un traceback normal en el monitor serie.

La línea del catálogo nombra la ROM del programa y la terminal. Ambas están en el lienzo del Jefe final, junto a la Pi; las lecciones 1 a 6 prueban el código en el emulador que escribe quien aprende, el cual sigue el modelo de referencia del Kestrel.