Crocolang

Introduction

Crocolang est un langage de programmation qui peut soit être interprété, soit être compilé en code machine avec l'infrastructure de compilation LLVM. Crocolang a été le premier projet de grosse envergure que j'ai entrepris en Rust. C'est aussi le projet sur lequel j'ai passé le plus de temps, puisque le développement s'est étalé sur deux ans.

Néanmoins, si ce projet était à refaire je prendrais aujourd'hui des décisions différentes. Au niveau de l'implémentation, le dispatching dynamique et les pointeurs intelligents ralentissent beaucoup l'interpréteur. Le système de traits de Rust pourrait être utilisé de façon plus intelligente pour mieux structurer le code. Au niveau de la théorie, je me suis inspiré des articles Let’s Build A Simple Interpreter et de la syntaxe et du comportement de mes langages favoris. Pour concevoir un langage sérieux, il faut d'avantage s'intéresser au milieu académique en se documentant sur la théorie des types, sur les modèles de gestion de la mémoire, etc.

Motivation

Crocolang est avant tout une expérimentation dans la création d'un langage de programmation. Il est axé sur la productivité et tente donc de remplir une niche qui est plus ou moins occupée par Go. Le langage doit être simple à apprendre et avoir une syntaxe familière au C. Il doit être le plus performant possible tout en restant simple d'utilisation.

L'analyseur lexical est chargé de transformer le code source en jetons compréhensibles par l'analyseur syntaxique. Le code source est initialement lu depuis un fichier et stocké dans un String (un tableau dynamique de caractères). Les mots-clés, les identificateurs, les littéraux sont reconnus et stockés dans un tableau avec une information sur leur position initiale dans le fichier lu, afin de pouvoir afficher à l'utilisateur des messages précis en cas d'erreur.

L'analyseur lexical de Crocolang est entièrement écrit à la main. Des bibliothèques comme Nom ou Chumsky auraient pu être utilisées pour obtenir un code plus élégant et concis. Néanmoins, la grande majorité des langages de programmation utilisent un analyseur lexical personnalisé pour qu'il soit le plus rapide et flexible possible.

L'analyseur syntaxique se charge de transformer en programme valide la liste de jetons crée par l'analyseur lexical. Un programme est représentable par un arbre appelé arbre de syntaxe abstraite où chacun de ses noeuds est une opération. Les noeuds peuvent avoir une arité différente. Les feuilles de l'arbre sont les identifiants et les littéraux, car ils ne dépendent de rien d'autre. Une opération comme l'addition est représentée par un noeud relié à deux autres noeuds.

Une phase d'analyse sémantique est aussi menée. Par exemple, une inférence basique des types est réalisée. Le typage des variables est vérifié. S'il y a une erreur présente dans le programme, c'est là qu'elle est généralement trouvée. Dans ce cas, l'analyse est stoppée et l'erreur est affichée à l'utilisateur. La représentation du programme générée par l'analyseur syntaxique et sémantique est indépendante du backend. C'est à dire que le même arbre peut être utilisé pour qu'un code source soit compilé ou interprété.

L'interpréteur, appelé Crocoi, est le premier backend créé pour Crocolang. Il utilise directement la représentation de l'analyseur sémantique pour exécuter le code. Les identifiants, dont il faut garder en mémoire la valeur, sont stockés dans une table des symboles. Cette table prend en compte la portée des variables. C'est essentiellement un tableau dynamique de tables de hachage. Une bibliothèque de fonctions est disponible et directement implémentée en Rust pour donner accès à Crocoi aux fonctionnalités du système. Il est ainsi possible de lire et écrire dans des fichiers, de faire des requêtes HTTP, d'exécuter des commandes système.

Le compilateur, appelé Crocol, a mobilisé la majeure partie du temps de développement. Il utilise LLVM à travers la bibliothèque Inkwell. Au lieu d'interpréter directement l'arbre du programme comme Crocoi, Crocol émet des instructions LLVM. Cette représentation intermédiaire est très proche d'un langage assembleur. En ayant cette couche d'abstraction avant l'assembleur, LLVM peut exécuter plusieurs opérations d'optimisation. Ensuite, la représentation intermédiaire est transformée dans le bon langage assembleur par LLVM. Une fois l'édition des liens réalisée, un exécutable natif est créé.

Comme Crocol utilise LLVM, le compilateur bénéficie d'un nombre important d'optimisations, essentiellement les mêmes que celles de tous les compilateurs utilisant LLVM tels que Clang, Rustc et Swiftc. Cela rend le code compilé Crocolang presque aussi performant que du code compilé en C. Ainsi, sur un exemple simple comme le calcul récursif de la suite de Fibonacci, Crocol est quasiment aussi rapide que Clang.

L'édition des liens permet de résoudre les symboles externes en liant les fichiers objet émis par Crocol avec d'autres bibliothèques. Les exécutables crées avec Crocol nécessitent d'être liés avec la bibliothèque standard de C.

Pour Linux, l'édition des liens se fait historiquement avec ld. Cependant, il est très difficile de trouver le chemin d'accès des bibliothèques à lier. Celui-ci peut varier selon la distribution, la version du noyau Linux, l'implémentation de la librairie C utilisée, l'architecture de la machine, etc. Il y a littéralement des milliers de lignes de Clang qui sont destinées à trouver le chemin d'accès des bibliothèques à lier. Pour cette raison, l'éditeur de liens de Clang ou GCC est appelé directement avec clang -c et gcc -c. Cette solution est raisonnable car toute distribution Linux devrait contenir un de ces deux compilateurs.

Pour Windows, l'édition des liens est encore plus compliquée. Elle peut aussi se faire avec Clang ou GCC si ceux-ci sont disponibles, ce qui est plus rare. En général c'est plutôt les outils de compilation Visual Studio qui sont installés. Les bibliothèques à lier sont tout aussi difficiles à trouver que pour Linux. Microsoft propose ainsi un outil de plus de 8000 lignes de code pour les trouver. Crocol s'interface à la place à une bibliothèque C de seulement 600 lignes pour réaliser ce travail.

De nombreux tests d'intégration vérifient que toutes les primitives de Crocolang fonctionnent correctement, avec Crocoi comme avec Crocol.

Démonstration

La vidéo suivante montre la programmation de deux exemples simples en Crocolang. La coloration syntaxique est faite par une extension Visual Studio Code que j'ai développée. Voici une description des deux exemples de la vidéo :

• Séquence de Fibonacci. Implémentation récursive classique de la séquence de Fibonacci. Le code est d'abord interprété avec Crocoi. Ensuite, le code est compilé avec Crocol et exécuté. Un code équivalent en C est aussi compilé et exécuté pour montrer que l'ordre de grandeur du temps d'exécution est équivalent, et que le résultat donné par Crocol est correct.
• Classe. Un exemple d'utilisation d'une classe en Crocolang, pour montrer plus en détail la syntaxe du langage. Un objet de type Person est déclaré sans valeur explicite, ce qui initialise tous ses champs avec leur valeur par défaut.