J'ai écrit un langage de programmation. Voici comment vous pouvez aussi.

Au cours des 6 derniers mois, j'ai travaillé sur un langage de programmation appelé Pinecone. Je ne l'appellerais pas encore mature, mais il dispose déjà de suffisamment de fonctionnalités pour être utilisable, telles que:

  • variables
  • les fonctions
  • structures définies par l'utilisateur

Si cela vous intéresse, consultez la page de destination de Pinecone ou son dépôt GitHub.

Je ne suis pas un expert. Quand j'ai commencé ce projet, je n'avais aucune idée de ce que je faisais, et je ne le fais toujours pas. Je n'ai suivi aucun cours sur la création de langage, je n'en ai lu qu'un peu en ligne et n'ai pas suivi beaucoup des conseils qui m'ont été donnés.

Et pourtant, j'ai toujours créé un langage complètement nouveau. Et il fonctionne. Je dois donc faire quelque chose de bien.

Dans cet article, je vais plonger sous le capot et vous montrer le pipeline que Pinecone (et d'autres langages de programmation) utilise pour transformer le code source en magie.

Je vais également aborder certains des compromis que j'ai faits et pourquoi j'ai pris les décisions que j'ai prises.

Ce n'est en aucun cas un tutoriel complet sur l'écriture d'un langage de programmation, mais c'est un bon point de départ si vous êtes curieux de développer un langage.

Commencer

«Je n'ai absolument aucune idée par où je commencerais», c'est quelque chose que j'entends souvent quand je dis aux autres développeurs que j'écris un langage. Au cas où c'est votre réaction, je vais maintenant passer en revue certaines décisions initiales qui sont prises et les étapes à suivre lors du démarrage d'une nouvelle langue.

Compilé vs interprété

Il existe deux grands types de langages: compilés et interprétés:

  • Un compilateur comprend tout ce qu'un programme va faire, le transforme en «code machine» (un format que l'ordinateur peut exécuter très rapidement), puis l'enregistre pour l'exécuter plus tard.
  • Un interpréteur parcourt le code source ligne par ligne, déterminant ce qu'il fait au fur et à mesure.

Techniquement, n'importe quelle langue peut être compilée ou interprétée, mais l'une ou l'autre a généralement plus de sens pour une langue spécifique. En général, l'interprétation a tendance à être plus flexible, tandis que la compilation a tendance à avoir des performances plus élevées. Mais cela ne fait qu'effleurer la surface d'un sujet très complexe.

J'apprécie beaucoup les performances et j'ai constaté un manque de langages de programmation à la fois haute performance et axés sur la simplicité, alors j'ai choisi compiled pour Pinecone.

C'était une décision importante à prendre dès le début, car beaucoup de décisions de conception de langage en sont affectées (par exemple, le typage statique est un grand avantage pour les langages compilés, mais pas tant pour les langages interprétés).

Malgré le fait que Pinecone a été conçu avec la compilation à l'esprit, il dispose d'un interpréteur entièrement fonctionnel, ce qui était le seul moyen de l'exécuter pendant un certain temps. Il y a un certain nombre de raisons à cela, que j'expliquerai plus tard.

Choisir une langue

Je sais que c'est un peu méta, mais un langage de programmation est lui-même un programme, et donc vous devez l'écrire dans un langage. J'ai choisi C ++ en raison de ses performances et de son vaste ensemble de fonctionnalités. De plus, j'aime travailler en C ++.

Si vous écrivez un langage interprété, il est très judicieux de l'écrire dans un langage compilé (comme C, C ++ ou Swift) car les performances perdues dans le langage de votre interprète et de l'interpréteur qui interprète votre interprète vont s'aggraver.

Si vous prévoyez de compiler, un langage plus lent (comme Python ou JavaScript) est plus acceptable. Le temps de compilation peut être mauvais, mais à mon avis, ce n'est pas aussi grave qu'un mauvais temps d'exécution.

Conception de haut niveau

Un langage de programmation est généralement structuré comme un pipeline. Autrement dit, il comporte plusieurs étapes. Chaque étape comporte des données formatées d'une manière spécifique et bien définie. Il a également des fonctions pour transformer les données de chaque étape à la suivante.

La première étape est une chaîne contenant l'intégralité du fichier source d'entrée. La dernière étape est quelque chose qui peut être exécuté. Tout cela deviendra clair au fur et à mesure que nous parcourrons le pipeline Pinecone, étape par étape.

Lexing

La première étape dans la plupart des langages de programmation est le lexing ou la création de jetons. «Lex» est l'abréviation de l'analyse lexicale, un mot très sophistiqué pour diviser un tas de texte en jetons. Le mot «tokenizer» a beaucoup plus de sens, mais «lexer» est tellement amusant à dire que je l'utilise quand même.

Jetons

Un jeton est une petite unité d'une langue. Un jeton peut être un nom de variable ou de fonction (AKA un identifiant), un opérateur ou un nombre.

Tâche du Lexer

Le lexer est censé prendre une chaîne contenant un fichier entier d'une valeur de code source et cracher une liste contenant chaque jeton.

Les étapes futures du pipeline ne renverront pas au code source d'origine, le lexer doit donc produire toutes les informations dont il a besoin. La raison de ce format de pipeline relativement strict est que le lexer peut effectuer des tâches telles que la suppression de commentaires ou la détection si quelque chose est un nombre ou un identifiant. Vous voulez garder cette logique verrouillée à l'intérieur du lexer, à la fois pour ne pas avoir à penser à ces règles lors de l'écriture du reste du langage, et ainsi vous pouvez changer ce type de syntaxe en un seul endroit.

Fléchir

Le jour où j'ai commencé la langue, la première chose que j'ai écrite était un simple lexer. Peu de temps après, j'ai commencé à découvrir des outils censés rendre le lexing plus simple et moins buggé.

L'outil prédominant est Flex, un programme qui génère des lexers. Vous lui donnez un fichier qui a une syntaxe spéciale pour décrire la grammaire de la langue. À partir de là, il génère un programme C qui lexique une chaîne et produit la sortie souhaitée.

Ma décision

J'ai choisi de conserver le lexer que j'ai écrit pour le moment. En fin de compte, je n'ai pas vu d'avantages significatifs à utiliser Flex, du moins pas assez pour justifier l'ajout d'une dépendance et compliquer le processus de construction.

Mon lexer ne fait que quelques centaines de lignes et me pose rarement des problèmes. Faire rouler mon propre lexer me donne également plus de flexibilité, comme la possibilité d'ajouter un opérateur à la langue sans modifier plusieurs fichiers.

Analyse

L'analyseur syntaxique est la deuxième étape du pipeline. L'analyseur transforme une liste de jetons en une arborescence de nœuds. Un arbre utilisé pour stocker ce type de données est connu sous le nom d'arborescence de syntaxe abstraite, ou AST. Au moins dans Pinecone, l'AST ne dispose d'aucune information sur les types ou sur les identifiants. Il s'agit simplement de jetons structurés.

Fonctions de l'analyseur

L'analyseur ajoute de la structure à la liste ordonnée de jetons produit par le lexer. Pour éviter les ambiguïtés, l'analyseur doit prendre en compte les parenthèses et l'ordre des opérations. Analyser simplement les opérateurs n'est pas très difficile, mais à mesure que de plus en plus de constructions de langage sont ajoutées, l'analyse peut devenir très complexe.

Bison

Encore une fois, il y a eu une décision à prendre concernant une bibliothèque tierce. La bibliothèque d'analyse prédominante est Bison. Bison fonctionne beaucoup comme Flex. Vous écrivez un fichier dans un format personnalisé qui stocke les informations de grammaire, puis Bison l'utilise pour générer un programme C qui effectuera votre analyse. Je n'ai pas choisi d'utiliser Bison.

Pourquoi la personnalisation est meilleure

Avec le lexer, la décision d'utiliser mon propre code était assez évidente. Un lexer est un programme si trivial que ne pas écrire le mien me paraissait presque aussi stupide que de ne pas écrire mon propre «pad gauche».

Avec l'analyseur, c'est une autre affaire. Mon analyseur Pinecone fait actuellement 750 lignes, et j'en ai écrit trois parce que les deux premières étaient des ordures.

J'ai initialement pris ma décision pour un certain nombre de raisons, et même si cela ne s'est pas déroulé sans heurts, la plupart d'entre elles sont vraies. Les principaux sont les suivants:

  • Minimiser le changement de contexte dans le flux de travail: le changement de contexte entre C ++ et Pinecone est déjà assez mauvais sans jeter dans la grammaire de Bison
  • Gardez la construction simple: chaque fois que la grammaire change, Bison doit être exécuté avant la construction. Cela peut être automatisé, mais cela devient une douleur lors du basculement entre les systèmes de construction.
  • J'aime créer des trucs sympas: je n'ai pas fait Pinecone parce que je pensais que ce serait facile, alors pourquoi déléguerais-je un rôle central alors que je pourrais le faire moi-même? Un analyseur personnalisé n'est peut-être pas trivial, mais c'est tout à fait faisable.

Au début, je n'étais pas tout à fait sûr que j'allais sur une voie viable, mais j'ai eu confiance en ce que Walter Bright (un développeur sur une première version de C ++, et le créateur du langage D) avait à dire sur le sujet:

«Un peu plus controversé, je ne prendrais pas la peine de perdre du temps avec les générateurs de lexer ou d'analyseur et d'autres soi-disant« compilateurs de compilateurs ». C'est une perte de temps. L'écriture d'un lexeur et d'un analyseur est un petit pourcentage du travail d'écriture d'un compilateur. Utiliser un générateur prendra à peu près autant de temps que d'en écrire un à la main, et cela vous mariera avec le générateur (ce qui compte lors du portage du compilateur sur une nouvelle plate-forme). Et les générateurs ont également la fâcheuse réputation d'émettre de mauvais messages d'erreur. »

Arbre d'action

Nous avons maintenant quitté le domaine des termes communs et universels, ou du moins je ne sais plus quels sont les termes. D'après ce que j'ai compris, ce que j'appelle «l'arbre des actions» est plus proche de l'IR de LLVM (représentation intermédiaire).

Il existe une différence subtile mais très significative entre l'arbre d'actions et l'arbre de syntaxe abstraite. Il m'a fallu un certain temps pour comprendre qu'il devrait même y avoir une différence entre eux (ce qui a contribué au besoin de réécritures de l'analyseur).

Arbre d'action vs AST

En termes simples, l'arbre d'action est l'AST avec contexte. Ce contexte est des informations telles que le type qu'une fonction retourne, ou que deux endroits dans lesquels une variable est utilisée utilisent en fait la même variable. Parce qu'il a besoin de comprendre et de se souvenir de tout ce contexte, le code qui génère l'arborescence d'actions a besoin de beaucoup de tables de recherche d'espace de noms et d'autres objets.

Exécution de l'arborescence d'actions

Une fois que nous avons l'arbre d'actions, exécuter le code est facile. Chaque nœud d'action a une fonction «exécuter» qui prend une entrée, fait tout ce que l'action devrait (y compris éventuellement l'appel d'une sous-action) et renvoie la sortie de l'action. C'est l'interprète en action.

Options de compilation

"Mais attendez!" Je vous entends dire: "Pinecone n'est-il pas censé être compilé?" Oui, ça l'est. Mais la compilation est plus difficile que l'interprétation. Il existe quelques approches possibles.

Construire mon propre compilateur

Cela m'a semblé une bonne idée au début. J'adore faire des choses moi-même, et je cherchais une excuse pour devenir bon en assemblage.

Malheureusement, écrire un compilateur portable n'est pas aussi simple que d'écrire du code machine pour chaque élément du langage. En raison du nombre d'architectures et de systèmes d'exploitation, il n'est pas pratique pour quiconque d'écrire un backend de compilateur multiplateforme.

Même les équipes derrière Swift, Rust et Clang ne veulent pas se soucier de tout cela par elles-mêmes, alors elles utilisent toutes ...

LLVM

LLVM est une collection d'outils de compilation. C'est essentiellement une bibliothèque qui transformera votre langage en un exécutable compilé. Cela semblait être le choix parfait, alors j'ai sauté dedans. Malheureusement, je n'ai pas vérifié la profondeur de l'eau et je me suis immédiatement noyé.

LLVM, bien que n'étant pas un langage d'assemblage difficile, est une bibliothèque gigantesque et complexe. Ce n'est pas impossible à utiliser et ils ont de bons tutoriels, mais j'ai réalisé que je devrais m'entraîner avant d'être prêt à implémenter complètement un compilateur Pinecone avec.

Transpiler

Je voulais une sorte de pomme de pin compilée et je la voulais rapidement, alors je me suis tournée vers une méthode dont je savais que je pouvais faire fonctionner: le transpiling.

J'ai écrit un transpilateur Pinecone to C ++ et ajouté la possibilité de compiler automatiquement la source de sortie avec GCC. Cela fonctionne actuellement pour presque tous les programmes Pinecone (bien qu'il y ait quelques cas extrêmes qui le cassent). Ce n'est pas une solution particulièrement portable ou évolutive, mais cela fonctionne pour le moment.

Futur

En supposant que je continue à développer Pinecone, il bénéficiera tôt ou tard du support de compilation LLVM. Peu importe combien je travaille dessus, le transpileur ne sera jamais complètement stable et les avantages de LLVM sont nombreux. C'est juste une question de savoir quand j'ai le temps de faire quelques exemples de projets dans LLVM et de comprendre.

Jusque-là, l'interpréteur est idéal pour les programmes triviaux et le transpiling C ++ fonctionne pour la plupart des choses qui nécessitent plus de performances.

Conclusion

J'espère avoir rendu les langages de programmation un peu moins mystérieux pour vous. Si vous souhaitez en fabriquer un vous-même, je le recommande vivement. Il y a une tonne de détails d'implémentation à comprendre, mais le plan ici devrait être suffisant pour vous permettre de démarrer.

Voici mes conseils de haut niveau pour commencer (rappelez-vous, je ne sais pas vraiment ce que je fais, alors prenez-le avec un grain de sel):

  • En cas de doute, allez interprété. Les langues interprétées sont généralement plus faciles à concevoir, à construire et à apprendre. Je ne vous décourage pas d'en écrire une compilée si vous savez que c'est ce que vous voulez faire, mais si vous êtes sur la clôture, j'irais interpréter.
  • Quand il s'agit de lexers et d'analyseurs, faites ce que vous voulez. Il existe des arguments valables pour et contre l'écriture des vôtres. En fin de compte, si vous pensez à votre conception et implémentez tout de manière sensée, cela n'a pas vraiment d'importance.
  • Apprenez du pipeline avec lequel je me suis retrouvé. Beaucoup d'essais et d'erreurs ont été nécessaires pour concevoir le pipeline que je possède actuellement. J'ai tenté d'éliminer les AST, les AST qui se transforment en arbres d'actions en place et d'autres idées terribles. Ce pipeline fonctionne, alors ne le changez pas à moins d'avoir une très bonne idée.
  • Si vous n'avez pas le temps ou la motivation pour implémenter un langage complexe à usage général, essayez d'implémenter un langage ésotérique tel que Brainfuck. Ces interprètes peuvent être aussi courts que quelques centaines de lignes.

J'ai très peu de regrets en ce qui concerne le développement de Pinecone. J'ai fait un certain nombre de mauvais choix en cours de route, mais j'ai réécrit la plupart du code affecté par de telles erreurs.

À l'heure actuelle, Pinecone est dans un état suffisamment bon pour qu'il fonctionne bien et puisse être facilement amélioré. Ecrire Pinecone a été une expérience extrêmement éducative et agréable pour moi, et cela ne fait que commencer.