¡Me complace anunciar la finalización de mi primer compilador para un lenguaje de programación! Malcc es un compilador incremental de Lisp AOT escrito en C.

Hablaré brevemente sobre sus muchos años de desarrollo y lo que aprendí en el proceso. Título del artículo alternativo: "Cómo escribir un compilador en diez años o menos".

(Al final hay TL; DR , si no te importa el fondo).

Demo del compilador

tim ~/pp/malcc master 0 → ./malcc Mal [malcc] user> (println "hello world") hello world nil user> (+ 1 2) 3 user> (def! fib2 (fn* (n) (let* (f (fn* (n1 n2 c) (if (= cn) n2 (f n2 (+ n1 n2) (+ c 1))))) (f 0 1 1)))) <lambda> user> (fib2 25) 75025 user> ^D% tim ~/pp/malcc master 0 → ./malcc examples/hello.mal hello world tim ~/pp/malcc master 0 → ./malcc --compile examples/hello.mal hello gcc -g -I ./tinycc -I . -o hello hello.c ./reader.c ./printer.c ./hashmap.c ./types.c ./util.c ./env.c ./core.c ./tinycc/libtcc.a -ledit -lgc -lpcre -ldl tim ~/pp/malcc master 0 → ./hello hello world tim ~/pp/malcc master 0 → 

Fracasos exitosos

Durante casi diez años, soñé con escribir un compilador. Siempre me ha fascinado el trabajo de los lenguajes de programación, especialmente los compiladores. Aunque imaginé el compilador como magia oscura y entendí que era imposible para un simple mortal como yo hacerlo desde cero.

¡Pero aún lo intenté y estudié en el camino!

Primero, el intérprete

En 2011, comencé a trabajar en un intérprete simple para el lenguaje ficticio Airball (airball se puede traducir como "muff"). Por nombre, puede evaluar el grado de mi incertidumbre de que funcionará. Fue un programa Ruby bastante simple que analizó el código y caminó a través de un árbol de sintaxis abstracta (AST). Cuando el intérprete aún funcionaba, le cambié el nombre a Lydia y lo reescribí a C para hacerlo más rápido.



¡Recuerdo que la sintaxis de Lydia me pareció muy inteligente! Todavía disfruto de su simplicidad.

Aunque Lydia estaba lejos de ser un compilador perfecto, me inspiró a seguir experimentando. Sin embargo, todavía me atormentaban las preguntas sobre cómo hacer que funcione el compilador: ¿en qué compilar? ¿Necesito aprender ensamblador?

En segundo lugar, el compilador e intérprete de bytecode

Como siguiente paso, en 2014, comencé a trabajar en scheme-vm , una máquina virtual para Scheme escrita en Ruby. Pensé que una máquina virtual con su propia pila y código de bytes sería una etapa de transición de un intérprete con pases AST y un compilador completo. Y dado que Scheme está formalmente definido , no hay necesidad de inventar nada.

He estado jugando con esquema-vm durante más de tres años y he aprendido mucho sobre la compilación. Al final, me di cuenta de que no podía terminar este proyecto. El código se convirtió en un verdadero caos, pero no había un final a la vista. Sin un mentor o experiencia, parecía vagar en la oscuridad. Al final resultó que, la especificación de idioma no es la misma que el manual para ello. Lección aprendida!

A finales de 2017, pospuse el esquema-vm en busca de algo mejor.

Encuentro con Mal

En algún momento en 2018, me encontré con Mal , un intérprete Lisp de estilo Clojure.

Mal fue inventado por Joel Martin como una herramienta de entrenamiento. Desde entonces, se han desarrollado más de 75 implementaciones en diferentes idiomas. Cuando miré estas implementaciones, me di cuenta de que realmente ayudan: si estoy atascado, entonces puedo buscar pistas en la versión Ruby o Python. Finalmente, ¡al menos alguien habla mi idioma!

También pensé que si podía escribir un intérprete para Mal, podría repetir los mismos pasos y crear un compilador para Mal.

Mal intérprete en Rust

Primero, comencé a desarrollar el intérprete de acuerdo con el tutorial . En ese momento, estaba estudiando activamente Rust (lo dejaré para otro artículo), así que escribí mi propia implementación de Mal in Rust: mal-rust . Vea aquí para más información sobre este experimento.

Fue un placer perfecto! No sé cómo agradecer o alabar a Joel por crear una excelente guía para Mal. Cada paso se describe en detalle , hay diagramas de flujo, pseudocódigo y pruebas . Todo lo que un desarrollador necesita para crear un lenguaje de programación de principio a fin.

Hacia el final del tutorial, logré ejecutar mi implementación de Mal para Mal, escrita en Mal, además de mi implementación de Rust. (dos niveles de profundidad, wow). ¡Cuando trabajó por primera vez, salté sobre una silla con entusiasmo!

Compilador Mal C

Tan pronto como probé la viabilidad del mal óxido, inmediatamente comencé a investigar cómo escribir un compilador. Compilar al ensamblador? ¿Puedo compilar el código de la máquina directamente?

Vi el ensamblador x86 escrito en Ruby. Me intrigó, pero la idea de trabajar con ensamblador me hizo parar.

En un momento, me topé con este comentario en Hacker News , que se refería al compilador de Tiny C como un "backend de compilación". ¡Parecía una gran idea!

TinyCC tiene un archivo de prueba que muestra cómo usar libtcc para compilar el código C del programa C. Este es el punto de partida para "hello world".

Volviendo nuevamente al tutorial de Mal, recordando mi conocimiento de C, en un par de meses de tardes y fines de semana libres, pude escribir el compilador de Mal. Fue un verdadero placer.



Si está acostumbrado a desarrollar pruebas, evalúe la disponibilidad de un conjunto preliminar de pruebas. Las pruebas conducen a una implementación funcional.

No puedo decir mucho sobre este proceso, a menos que repita: el manual de Mal es un verdadero tesoro. ¡En cada paso, sabía exactamente qué hacer!

Dificultades

Mirando hacia atrás, aquí hay algunas dificultades al escribir el compilador de Mal, donde tuve que pensar:

1. Las macros deben compilarse sobre la marcha y estar listas para ejecutarse en el momento de la compilación. Esto es un poco desconcertante.
   
2. Es necesario proporcionar un "entorno" (un árbol de hashes / matrices asociativas / diccionarios con variables y sus valores) tanto para el código del compilador como para el código final del programa compilado. Esto le permite definir macros en tiempo de compilación.
   
3. Como el entorno está disponible en el momento de la compilación, inicialmente Malcc detectó errores indefinidos durante la compilación (acceso a una variable que no estaba definida), y en un par de lugares esto violó las expectativas del conjunto de pruebas. Al final, para pasar las pruebas, apagué esta función. Sería genial volver a agregarlo como un indicador adicional del compilador, ya que de esta manera puede detectar muchos errores por adelantado.
4. Compilé el código C escribiendo tres líneas de la estructura:
   • top : código de nivel top : aquí están las funciones
   • decl : declaración e inicialización de variables utilizadas en el cuerpo
   • body : cuerpo donde se realiza el trabajo principal
5. Todo el día me pregunté si podría escribir mi propio recolector de basura, pero decidí dejar este ejercicio para más tarde. La biblioteca de recolección de basura Boehm-Demers-Weiser es fácil de conectar y está disponible en muchas plataformas.
   
6. Es importante mirar el código que escribe su compilador. Siempre que el compilador encontró una variable de entorno DEBUG , devolvió el código C compilado donde se podían ver los errores.

¿Qué haría de otra manera?

1. Escribir código C e intentar mantener la sangría no fue fácil, entonces no rechazaría la automatización. Me parece que algunos compiladores escriben código feo, y luego una biblioteca especial lo "decora" antes de emitirlo. ¡Necesita ser estudiado!
   
2. Agregar líneas durante la generación de código es un poco complicado. Podría considerar crear un AST y luego convertirlo a la última línea de código C. Esto debería poner el código en orden y darle armonía.

Ahora consejo

Me gusta que tardó casi una década para el compilador. No realmente Cada paso en el camino es un recuerdo agradable de cómo me convertí gradualmente en un mejor programador.

Pero esto no significa que haya "terminado". Todavía hay cientos de métodos y herramientas que necesitas aprender para sentirte como un verdadero autor de compiladores. Pero puedo decir con confianza: "Lo hice".

Aquí está todo el proceso en forma concisa, cómo hacer su propio compilador Lisp:

1. Elija el idioma en el que se sienta cómodo. No desea aprender simultáneamente un nuevo idioma y cómo escribir otro nuevo idioma.
   
2. Siguiendo el manual de Mal, escriba un intérprete.
   
3. Alégrate!
   
4. Siga las instrucciones nuevamente, pero en lugar de ejecutar el código, escriba el código que lo ejecuta. (No solo "refactorizar" el intérprete existente. Debe comenzar desde cero, aunque no está prohibido copiar y pegar).

Creo que este método se puede usar con cualquier lenguaje de programación que se compila en un archivo ejecutable. Por ejemplo, puedes:

1. Escribe el intérprete de Mal en Go .
2. Modifique su código para:
   
   • cree una línea de código Go y escríbala en un archivo;
   • compile este archivo resultante con go build .

Idealmente, es mejor controlar el compilador Go como una biblioteca, ¡pero esta también es una forma de hacer un compilador!

Con la ayuda de la guía de Mal y tu ingenio, puedes hacer todo esto. Si incluso yo pudiera, entonces tú puedes!