Je suis très heureux d'annoncer la fin de mon premier compilateur pour un langage de programmation! Malcc est un compilateur incrémental Lisp AOT écrit en C.

Je parlerai brièvement de ses nombreuses années de développement et de ce que j'ai appris au cours du processus. Titre alternatif de l'article: "Comment écrire un compilateur en dix ans ou moins."

(À la fin, il y a un TL; DR si vous ne vous souciez pas du fond).

Démo du compilateur

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 → 

Échecs réussis

Pendant près de dix ans, j'ai rêvé d'écrire un compilateur. J'ai toujours été fasciné par le travail des langages de programmation, en particulier les compilateurs. Bien que j'imaginais le compilateur comme de la magie noire et comprenais qu'il était impossible pour un simple mortel comme moi de le faire à partir de zéro.

Mais j'ai quand même essayé et étudié en cours de route!

Tout d'abord, l'interprète

En 2011, j'ai commencé à travailler sur un simple interprète pour la langue fictive Airball (airball peut être traduit par «manchon»). Par son nom, vous pouvez évaluer le degré d'incertitude que cela fonctionnera. C'était un programme Ruby assez simple qui analysait le code et parcourait un arbre de syntaxe abstraite (AST). Lorsque l'interprète fonctionnait toujours, je l'ai renommé en Lydia et réécrit en C pour le rendre plus rapide.



Je me souviens que la syntaxe de Lydia me semblait très intelligente! J'apprécie toujours sa simplicité.

Bien que Lydia soit loin d'être un compilateur parfait, cela m'a inspiré pour continuer à expérimenter. Cependant, j'étais encore tourmenté par des questions, comment faire fonctionner le compilateur: dans quoi compiler? dois-je apprendre l'assembleur?

Deuxièmement, le compilateur et l'interpréteur de bytecode

Dans une prochaine étape, en 2014, j'ai commencé à travailler sur schem-vm , une machine virtuelle pour Scheme écrite en Ruby. Je pensais qu'une machine virtuelle avec sa propre pile et son propre bytecode serait une étape de transition d'un interprète avec des passes AST et un compilateur à part entière. Et puisque Scheme est formellement défini , il n'est pas nécessaire d'inventer quoi que ce soit.

Cela fait plus de trois ans que je joue avec le schéma-vm et j'ai beaucoup appris sur la compilation. Finalement, j'ai réalisé que je ne pouvais pas terminer ce projet. Le code s'est transformé en véritable chaos, mais il n'y avait pas de fin en vue. Sans mentor ni expérience, je semblait errer dans le noir. Il s'est avéré que la spécification de la langue n'est pas la même que celle du manuel . Leçon apprise!

À la fin de 2017, j'ai reporté le schéma-vm à la recherche de quelque chose de mieux.

Rencontre avec Mal

En 2018, je suis tombé sur Mal , un interprète Lisp de style Clojure.

Le mal a été inventé par Joel Martin comme outil de formation. Depuis lors, plus de 75 implémentations dans différents langages ont été développées! Quand j'ai regardé ces implémentations, j'ai réalisé qu'elles aidaient beaucoup: si je suis bloqué, alors je peux aller chercher des astuces dans la version Ruby ou Python. Enfin, au moins quelqu'un parle ma langue!

J'ai aussi pensé que si je pouvais écrire un interprète pour Mal, je pourrais répéter les mêmes étapes - et faire un compilateur pour Mal.

Interprète mal sur Rust

Tout d'abord, j'ai commencé à développer l'interprète selon la procédure pas à pas . À cette époque, j'étudiais activement Rust (je vais le laisser pour un autre article), j'ai donc écrit ma propre implémentation de Mal in Rust: mal-rust . Voir ici pour en savoir plus sur cette expérience.

Ce fut un plaisir parfait! Je ne sais pas comment remercier ou féliciter Joel pour avoir créé un excellent guide de Mal. Chaque étape est décrite en détail , il y a des organigrammes, des pseudo-codes et des tests ! Tout ce dont un développeur a besoin pour créer un langage de programmation du début à la fin.

Vers la fin du tutoriel, j'ai réussi à exécuter mon implémentation Mal pour Mal, écrite en mal, en plus de mon implémentation Rust. (deux niveaux de profondeur, wow). Quand elle a travaillé pour la première fois, j'ai sauté sur une chaise avec enthousiasme!

Compiler Mal C

Dès que j'ai prouvé la viabilité du mal-rust, j'ai immédiatement commencé à rechercher comment écrire un compilateur. Compiler vers l'assembleur? Puis-je compiler le code machine directement?

J'ai vu l'assembleur x86 écrit en Ruby. Il m'a intrigué, mais l'idée de travailler avec l'assembleur m'a fait arrêter.

À un moment donné, je suis tombé sur ce commentaire sur Hacker News , qui faisait référence au compilateur Tiny C comme un «backend de compilation». Cela semblait être une excellente idée!

TinyCC a un fichier de test montrant comment utiliser libtcc pour compiler du code C à partir d'un programme C. C'est le point de départ de «hello world».

Revenant à nouveau à la procédure pas à pas de Mal, rappelant ma connaissance de C, dans quelques mois de soirées et de week-ends gratuits, j'ai pu écrire le compilateur Mal. Ce fut un vrai plaisir.



Si vous avez l'habitude de développer par le biais de tests, évaluez la disponibilité d'un ensemble préliminaire de tests. Les tests conduisent à une implémentation fonctionnelle.

Je ne peux pas dire grand-chose sur ce processus, sauf si je le répète: le manuel Mal est un vrai trésor. À chaque étape, je savais exactement quoi faire!

Des difficultés

Avec le recul, voici quelques difficultés lors de l'écriture du compilateur Mal, où j'ai dû bricoler:

1. Les macros doivent être compilées à la volée et être prêtes à être exécutées au moment de la compilation. C'est un peu déroutant.
   
2. Il est nécessaire de fournir un «environnement» (un arbre de hachages / tableaux associatifs / dictionnaires avec des variables et leurs valeurs) à la fois pour le code du compilateur et pour le code final du programme compilé. Cela vous permet de définir des macros au moment de la compilation.
   
3. Étant donné que l'environnement est disponible au moment de la compilation, Malcc a initialement détecté des erreurs non définies lors de la compilation (accès à une variable qui n'était pas définie), et à quelques endroits, cela a violé les attentes de la suite de tests. Au final, pour réussir les tests, j'ai désactivé cette fonctionnalité. Ce serait formidable de l'ajouter en tant que drapeau supplémentaire du compilateur, car de cette façon, vous pouvez attraper beaucoup d'erreurs à l'avance.
4. J'ai compilé du code C en écrivant sur trois lignes de la structure:
   • top : code de niveau supérieur - voici les fonctions
   • decl : déclaration et initialisation des variables utilisées dans le corps
   • body : corps où le travail principal est effectué
5. Toute la journée, je me suis demandé si je pouvais écrire mon propre ramasse-miettes, mais j'ai décidé de quitter cet exercice pour plus tard. La bibliothèque de collecte de déchets Boehm-Demers-Weiser est facile à connecter et disponible sur de nombreuses plates-formes.
   
6. Il est important de regarder le code que votre compilateur écrit. Chaque fois que le compilateur rencontrait une variable d'environnement DEBUG , il renvoyait du code C compilé où les erreurs pouvaient être affichées.

Que ferais-je sinon

1. Écrire du code C et essayer de garder l'indentation n'était pas facile, alors je ne refuserais pas l'automatisation. Il me semble que certains compilateurs écrivent du code laid, puis une bibliothèque spéciale le "décore" avant de le publier. Il faut l'étudier!
   
2. L'ajout de lignes lors de la génération de code est un peu compliqué. Vous pouvez envisager de créer un AST, puis de le convertir à la dernière ligne de code C. Cela devrait mettre le code en ordre et donner l'harmonie.

Maintenant des conseils

J'aime que cela ait pris près d'une décennie pour le compilateur. Non vraiment. Chaque étape sur le chemin est un agréable souvenir de la façon dont je suis progressivement devenu un meilleur programmeur.

Mais cela ne veut pas dire que j'ai "fini". Il existe encore des centaines de méthodes et d'outils que vous devez apprendre à vous sentir comme un véritable auteur de compilateur. Mais je peux dire en toute confiance: "Je l'ai fait."

Voici l'ensemble du processus sous une forme concise, comment créer votre propre compilateur Lisp:

1. Choisissez la langue dans laquelle vous vous sentez à l'aise. Vous ne voulez pas apprendre simultanément une nouvelle langue et comment écrire une autre nouvelle langue.
   
2. En suivant le manuel de Mal, écrivez un interprète.
   
3. Réjouis-toi!
   
4. Suivez à nouveau les instructions, mais au lieu d'exécuter le code, écrivez le code qui exécute le code. (Pas seulement «refactoring» de l'interpréteur existant. Vous devez recommencer à zéro, bien que le copier-coller ne soit pas interdit).

Je crois que cette méthode peut être utilisée avec n'importe quel langage de programmation qui se compile dans un fichier exécutable. Par exemple, vous pouvez:

1. Écrivez l'interprète de Mal sur Go .
2. Modifiez votre code pour:
   
   • créer une ligne de code Go et l'écrire dans un fichier;
   • compiler ce fichier résultant avec go build .

Idéalement, il vaut mieux contrôler le compilateur Go en tant que bibliothèque, mais c'est aussi un moyen de faire un compilateur!

Avec l'aide du guide de Mal et votre ingéniosité, vous pouvez faire tout cela. Si même je le pouvais, alors vous le pouvez!