Mon petit compilateur
Page mise à jour le 11 novembre 1999

Contexte

J'ai suivi le cours de Licence d'Informatique de Patrick Cousot, Langages de programmation et Compilateurs. Les Travaux Dirigés ont consisté en l'écriture d'un petit compilateur. J'ai choisi d'implémenter un langage fonctionnel, sous ensemble de Caml Light que j'avais découvert en Math Sup dans le cadre de l'option Informatique.

Le compilateur est lui-même écrit en Caml Light, mais il est assez loin d'être bootstrapé (c'est-à-dire qu'il n'est pas capable de compiler son propre code source). Je pense qu'un langage comme Caml est idéal pour écrire un compilateur rapidemment (ou plus généralement tout programme qui manipule des expressions symboliques).

Le projet est tellement minimal que je n'ai pas osé lui donner de nom; voici un nom possible : mini-pico-Caml-ultra-Light-sans-filtre.


Schéma d'ensemble du compilateur

Pour présenter le schéma d'ensemble d'un compilateur, on donne en général les différentes phases de compilation (analyse lexicale, syntaxique, sémantique, production de code intermédiaire, etc ...). Je préfère adopter un point de vu orthogonal, c'est-à-dire donner d'abord les différentes représentations internes successives du programme. Les phases de compilation sont les ''flêches'' entre ces représentations. Voici donc ces représentations :

  • Code source
  • Arbre syntaxique
  • Code intermédiaire (Lambda-code)
  • Code symbolique (Labels non résolus)
  • Code définitif

    • Voyons cela plus en détails :

  • L'arbre syntaxique est construit depuis le code source par l'analyseur syntaxique qui s'appuie sur l'analyseur lexical.
  • L'arbre syntaxique est décoré :
  • on détermine les variables d'environnements de chaque expression (une variable d'environnement est un identificateur non global utilisé dans une expression; cette variable doit être disponible au moment de l'execution, soit sur la pile, soit dans l'environnement actif);
  • on effectue ensuite le typage des expressions, en utilisant un algorithme d'unification à la Milner. En fait, le typage est une phase de vérification statique, les informations obtenues ne sont plus utilisées dans les phases suivantes du compilateur.
  • Le code intermédiaire est produit à partir de l'arbre syntaxique par la phase de précompilation, qui consiste à affecter les positions des variables (dans la pile, dans l'environnement).
  • On peut voir ce code intermédiaire comme une sorte de programme en Lambda-calcul avec la notation de De Bruijn, d'où le nom de Lambda-code.
  • Cette représentation est encore arborescente.
  • La phase centrale de la compilation, le passage du code intermédiaire au code symbolique, est celle où l'on voit apparaître une structure linéaire; en effet, jusque là, le code est encore représenté sous forme arborescente.
  • Le choix des instructions de la machine abstraite se fait dans cette phase.
  • En fait, le code est produit ''en partant de la fin'', ce qui permet de savoir quelle instruction suit celle que l'on génère et cela facilite ainsi la détection, par exemple, de la récursivité terminale.
  • Le passage du code symbolique au code définitif est trivial : il s'agit juste de résoudre les noms symboliques des labels (utilisé pour faire des sauts dans le code) en des adresses physiques dans la mémoire de la machine.
  • En fait, le code n'est pas écrit dans un fichier : il est prêt à être executé; ainsi je n'ai pas eu à choisir une vraie représentation physique des OpCode de la machine, mais cela ne poserait aucun problème.

    • Une fois ces différents traitements effectués, le code définitif est prêt à être executé. En fait, le code n'est pas écrit dans un fichier; ainsi je n'ai pas eu à choisir une vraie représentation physique des OpCodes de la machine, mais cela ne poserait aucun problème.


    Modèle d'exécution et machine abstraite


    La machine abstraite, pour laquelle est produit le code définitif à la structure suivante :

  • machine à pile (+ un registre pointeur de pile)
  • un accumulateur
  • un registre d'environnement actif
  • une zone mémoire dans laquelle sont stockées les objets
  • la zone de code (+ un registre d'instruction)

    • La zone mémoire est normalement "garbage collectée".
  • En fait, comme la machine est simulée par un programme Caml qui s'occupe de la gestion mémoire, je n'ai pas eu à écrire de garbage collector.


    • Les données manipulées sont hétérogènes : les mots mémoires doivent ainsi être flaggés pour indiquer leur type :

  • entier;
  • pointeur sur un bloc dynamique :
  • vecteur de mots,
  • bloc binaire (comme une chaîne de caractères).

    • Voici la représentation des différentes structures du langage :
  • Un couple est représenté par un bloc de 2 mots.
  • Les constructeurs (de type somme) sont
  • soit constants : ils sont stockés comme des entiers;
  • soit avec argument : ils sont stockés comme un bloc de 2 mots; le premier mot est le numéro du constructeur dans son type somme; le deuxième mot est l'argument.
  • Une fermeture est également un couple : (adresse de saut, environnement). L'environnement est soit l'entier 0 (si celui-ci est vide), soit un pointeur sur un bloc.
  • Une référence est un bloc de taille 1.
  • Une cellule de liste (built-in) est un couple (tete, queue) ou l'entier 0 pour la liste vide; remarquons que par rapport aux listes que le programmeur peut définir avec un type somme, on économise ici une indirection (cette optimisation s'applique pour tout type somme avec un seul constructeur non constant).
  • Les entiers sont stockés directement, ansi que les booléens (0=false; 1=true) et les caractères (code ASCII).
  • Les chaînes de caractères sont stockées dans dans blocs qui ne sont pas soumis au garbage collector (blocs binaires).
  • Les vecteurs (tableaux) ne sont pas encore gérés au niveau du langage, mais en interne, ils seraient représentés simplement par un bloc.

    • L'instruction Call attend une fermeture dans l'accumulateur et l'argument effectif au sommet de la pile. Elle empile d'abord le pointeur de pile et le registre d'environnement, puis elle met à jour ce dernier (avec le deuxième mot de la fermeture) et effectue le saut (l'adresse de saut est le premier mot de la fermeture).
    L'instruction CallTerm s'occupe des appels récursifs terminaux (en déplacant l'argument avant le bloc de retour courant et en faisant un saut sans sauvegarder sur la pile les registres de pile et d'environnement).
    Globalement, la structure de pile à l'execution est la suivante :
  • Les valeurs globales (let id = expr;;) sont conservées en début de pile.
  • Les calculs en cours sont empilés au dessus des valeurs globales; par exemple, la construction let id = expr1 in expr2 laisse au sommet de la pile la valeur renvoyée par expr1 lors de l'execution de expr2.


    • Ce qu'il reste à faire


    Le compilateur est un projet de licence, et je n'ai pas pour objectif d'en faire un outil utilisable. Par arriver au niveau de son modèle, CamlLight, il resterait beaucoup de choses à faire :

  • Concernant la sémantique du langage :
  • Gérer les types enregistrement et les champs mutables.
  • Faire un vrai Pattern Matching optimisé (dans l'état actuel, on ne fait que le matching que sur un niveau et sans gérer les constantes).
  • Gérer les let rec pour des expressions comme let rec l = 1::2::l (dans l'état actuel, les let rec sont réservés aux fonctions récursives ou mutuellement récursives).
  • Implémenter un système de modules
  • Production de code et optimisations:
  • Optimiser le tagging (en utilisant les informations données par le typage)
  • Optimiser la gestion mémoire (libération explicite, coopération fine avec le garbage collector et le système d'exploitation)
  • Optimiser les appels de fonctions curryfiées à plusieurs arguments
  • Gérer des optimisations locales triviales (chargement redondant de l'accumulateur, ...)
  • Inlining des petites fonctions
  • Optimisation des appels directs (sans construire de fermeture)
  • Execution
  • Réecrire le bytecode interpreter en C
  • Choisir une stratégie de gestion mémoire :
  • Garbage collector : Mark & Sweep / Stop & Copy / Combinaison / Gestion particulière des cellules de listes, des couples et des fermetures (tous : taille fixe de 2 mots)
  • Region inference


    • Exemples


    Pour vous donner une idée du langage reconnu par mon compilateur, je vais lister quelques exemples de programmes. La ligne de commande du compilateur est rudimentaire : compil fichier.ml options

    Les options reconnues sont les suivantes :

  • -c pour afficher le code produit (opcode)
  • -t pour afficher le type des déclarations
  • -ta pour afficher le type des déclarations et des expressions de niveau supérieur
  • -e pour executer le code compilé

    • Le fichier compil/essai.ml contient le code source d'une programme d'exemple; le résultat ( -c -ta -e ) se trouve dans le fichier compil/essai.res.

    Pour montrer que l'algorithme de Milner peut donner des types de longueur exponentielle en la longueur du code source, on utilise un programme du genre :

    (* Le typage est exponentiel *) let pair x y z = (z x) y in let x1 y = (pair y) y in let x2 y=x1 (x1 y) in let x3 y=x2 (x2 y) in let x4 y=x3 (x3 y) in let x5 y=x4 (x4 y) in (* etc ... *) let id z = z in x5 id;; Pour vous en convaincre, regardez les fichiers compil/typ1.ml, compil/typ2.ml, compil/typ1.res et compil/typ2.res.

    Code source du compilateur

    Dans les premiers TD du cours de Cousot, le but était d'écrire un petit langage, du style calculette 4 opérations avec variables et fonctions. J'ai assez vite choisi, ainsi que d'autres élèves du cours, de faire evoluer le projet vers un langage fonctionnel du style Caml. J'ai commencé par écrire une version minimale de l'analyseur lexical/syntaxique puis un premier essai de typage, en utilisant un style uniquement fonctionnel. Pour des raisons d'efficacité, je l'ai fait réecrit par la suite. J'ai ensuite spécifié le cadre d'execution et j'ai réalisé l'interpreteur de la machine abstraite. Enfin, j'ai implementé les divers étapes de traduction de code en rajoutant progressivement les fonctionnalités du langage. Cela m'a poussé à revoir la grammaire du langage, ainsi qu'à rajouter quelques instructions à la machine abstraite.
    Les spécifications du compilateur ont ainsi évolué dynamiquement, et il n'est pas étonnant que le code soit vraiment moche. Je doute donc qu'il présente un interêt quelconque, mais le voici quand même.

  • Analyseurs grammaticaux
  • Analyseur lexical : compil/sources/lexical.mll
  • Analyseur syntaxique : compil/sources/parser.mly
  • Expressions et typage
  • Manipulation des expressions : compil/sources/expr.ml
  • Gestion des types : compil/sources/types.ml
  • Typage : compil/sources/typage.ml
  • Phases de traduction
  • Arbre syntaxique -> lambda-code : compil/sources/lambda.ml
  • Lambda-code -> code symbolique : compil/sources/gen.ml
  • Code symbolique -> code définitif : compil/sources/instr.ml
  • Compilateur
  • Identificateurs globaux : compil/sources/global.ml
  • Types de phrases du code source : compil/sources/topl.ml
  • Programme principal : compil/sources/main.ml
  • Executeur et évaluateur
  • Interpreteur machine abstraite : compil/sources/am.ml
  • Evaluateur (inutilisé) : compil/sources/eval.ml
  • Divers
  • Routines diverses : compil/sources/divers.ml
  • Gestion des types sommes : compil/sources/somme.ml


    • Références et liens

    Ce titre ne fait pas référence aux références du langage Caml, mais aux références que j'ai utilisé pour écrire mon compilateur

  • Thèse de doctorat de Xavier Leroy : Typage polymorphe d'un langage algorithmique (chapitre 1 surtout)
  • Source de Caml Light
  • A brief introduction to Regions Mads Tofte
  • A region inference algorithm Mads Tofte - Birkedal
  • Cours de P. Cousot

    • http://www.dmi.ens.fr/~cousot/cours.shtml Cours de P. Cousot
    http://www.cera2.com/softd/compiler.htm Compiler internet resources
    http://pauillac.inria.fr/caml/index-fra.html Site officiel de Caml à l'INRIA
    http://www.diku.dk/research-groups/topps/activities/mlkit.html Home Page for the ML Kit
    http://www.dina.kvl.dk/~sestoft/mosml.html Moscow ML
    http://pauillac.inria.fr/~xleroy/ Xavier Leroy's home page

    Joindre le webmaster:Alain Frisch
    Retour à la page principale
    Votre avis sur le site