# Compilateur Ants ## Rapport de projet ### Présentation du groupe Notre groupe est composé des éleves suivants : - Jade GARCIA-BOURREE - Loïc DELABROUILLE - Sébastien BONDUELLE - Malo REVEL Nous n'avons pas attribué de rôles précis à chaque élève : lorsque quelqu'un finit une tâche, il en démarrait une nouvelle parmi ce qu'il y avait à faire (que ce soit dans la définition de la grammaire, la compilation, l'optimisation, la rédaction du README, les tests ou les stratégies de jeu). Certaines tâches particulièrement ardues ont également été réalisées en binôme. Globalement, malgré le grand nombre d'élèves dans le groupe, il n'y a pas eu beaucoup de moments de battements, sans qu'un élève n'ait rien à faire. ### Description générale du langage Les fichiers de notre langage ont pour extension .ant Un programme écrit dans notre langage est une suite de commandes, séparées par des `;`. Une commande peut être : - Une instruction (actions basiques des fourmis (`Drop`, `Move`, ...), appel de fonction, ...) - Une déclaration de variable ou de fonction - Une structure conditionnelle (`if`, `while`, ...) - Un commentaire (encadré par des `#`) Nous avons enrichi les instructions qui en "assembleur fourmi" prennent en paramètre un label à suivre en cas d'échec en laissant le choix au programmeur de spécifier ou non ce qu'il faut faire en cas d'échec/réussite (Par exemple, `Move` est décomposé en `move` (action en cas d'échec), `moven` (sans paramètre) et `movif` (action en cas de réussite et action en cas d'échec). Ces instructions se rapprochent ainsi de la structure `if`, que nous avons également décomposé en `if` (suivi de `then` puis `else`), et `ifn` (seulement suivi de `then`). Note : Les actions à réaliser en paramètre de ces commandes sont des programmes : on peut ainsi imbriquer sans problème les commandes. Les fonctions sont d'abord déclarées, puis appelées. Elles peuvent posséder des arguments spécifiés entre parenthèses. De même, les variables sont déclarées/attribuées et peuvent ensuite être utilisées. Pour implémenter ces deux notions, nous avons remplacé les valeurs "constantes" telles que les directions, les numéros de marqueurs, les entiers... par des expressions `exp`. Ces expressions peuvent être des valeurs constantes en tant que telles, des arguments de fonctions (encadrés par des `[]`) ou des variables (en débutant par `!`). Les conditions des structures conditionnelles (qui sont donc des `exp`) sont des expressions conditionnelles : elles peuvent être construites à partir des opérateurs booléens "ou", "et" et "non", et des constantes booléennes "true" et "false". `repeat` permet de répéter une portion de code un nombre fixé de fois (comme une boucle `for` limitée). Note : les commentaires sont bel et bien des commandes : ils faut les séparer par des ` ;` (avec une espace avant le `;`). Ces commentaires sont assez limités : seuls les identifiants (`` sont acceptés). Ils sont lors de la compilation retranscrits en commentaires .brain Nous allons maintenant décrire comment nous avons compilé certaines structures à l'aide des éléments de base du langage assembleur. Expressions booléennes : les manipulations de booléens se font essentiellement avec `Sense` : le traitement d'une expression booléenne doit se diriger vers un certain label `lab_true` si l'expression a pour valeur "vrai", et un label `lab_false` sinon. Les constructeurs élémentaires sont donc `True`, `False` et `Condition`. Les deux premiers se traduisent avec `Goto lab_true` et `Goto lab_false`, et le dernier se traduit avec `Sense`. Le `not` échange les deux labels, et les `et` et `ou` lient deux expressions booléennes avec un label intermédiaire. Ces dernières opérations sont paresseuses. Conditions : la condition `if` manipule des expression booléenne, en lui donnant en argument `lab_true` un label vers le programme à exécuter en cas de réussite du test, et `lab_false` un label vers le programme à exécuter en cas d'échec. Les blocs de ces deux labels se terminent par un `Goto` pointant vers un label de fin commun, qui correspond à la suite du programme. La condition `ifn` est identique à la précédente, si ce n'est que le label `lab_false` est identique au label de fin commun Boucles : La boucle `while` traite l'expression booléenne deux fois, une fois avant de rentrer dans la boucle et une fois à la fin de la boucle. Le `lab_true` est alors au début du programme, et le `lab_false` est le label de fin. Appels de variables : Lors du traitement d'un appel de variable, on remplace simplement la variable par la valeur associée à son identifiant dans l'environnement des variables. Appels de fonctions sans paramètres : On recopie simplement le contenu de la fonction à l'endroit où la fonction est appelée. Appels de fonctions avec paramètres : Lorsque la fonction possède des arguments, on remplace, comme pour les variables, chaque argument rencontré par la valeur correspondant qui est donnée en argument lors de l'appel de fonction, et ce en faisant correspondre le tableau des valeurs arguments avec le tableau des noms d'arguments (dans l'environnement des fonctions). Instructions conditionnelles : Elles se traitent de la même façon que les conditions, mais avec d'autres instructions de base que Sense. Wait : Pour permettre aux fourmis d'attendre un tour, on réalise un `Sense` inutile qui lui fait simplement consommer une unité de temps. Note : les variables et les fonctions sont accessibles partout, et pas seulement dans le bloc courant. Cela est du à la gestion globale des environnements. Elles ont également une durée de vie infinie. ### Description de la compilation La compilation des fichiers .ant s'effectue dans la fonction `write_file` du fichier antsc.ml. Pour pouvoir optimiser le code compilé (nous y reviendrons), nous stockons d'abord le code assembleur généré dans une structure de données, avant de l'écrire dans un fichier. Cette structure de données est une file de blocs, les blocs étant la donnée d'un nom de label et d'une liste de commandes. Le début des programmes .brain n'étant pas sous un label, nous avons utilisé le type `option` de Caml, en utilisant `None` pour le bloc initial. Une fois la commpilation terminée, cette file est convertie en tableau pour l'optimisation, puis optimisée, puis écrite dans le fichier .brain. Le parseur fournissant un arbre syntaxique, la compilation consiste à "matcher" ce programme. Les types étant mutuellement récursifs, les fonctions de match le sont également. Les fonctions et variables sont stockées dans deux environnements représentés par des tables de hachage. Pour les fonctions (`env_fun`) : - Clef : nom de la fonction - Valeur : couple `(prog, args)`, avec `prog` le programme de la fonction et `args` le tableau des noms d'arguments de la fonction. Pour les variables (`env_var`) : - Clef : nom de la variable - Valeur : valeur de la variable (type `value`) La compilation crée des labels dont le nom est généré avec la fonction `get_label`, qui utilise un entier `fresh_int` servant d'identifiant pour les labels. Nous utilisons deux fonctions pour l'écriture dans la liste de blocs : `write_command` et `write_label` ### Description de l'optimisation Les commandes `Goto` prenant une unité de temps aux fourmis, notre objectif était de réduire au minimum leur utilisation par les fourmis, quitte à rallonger le fichier .brain obtenu. Pour ce faire, nous avons eu l'idée de remplacer toutes les commandes de la forme `Goto labelx` par le contenu du bloc de label `labelx`. C'est ici que la structure de tableau de blocs intervient. L'optimisation de code assembleur s'effectue principalement dans la fonction `optimize`, qui modifie le tableau de blocs avant son écriture dans le fichier .brain. L'algorithme théorique est le suivant : - Tant que le programme est modifié : - Pour chaque bloc : - Parcourir les commandes du bloc jusqu'à rencontrer une commande de type `Goto labelx` - Dans ce cas, remplacer cette commande et toutes les commandes suivantes du bloc par le contenu du bloc d'étiquette `labelx`. La suppression des lignes suivant le `Goto` n'est pas gênante : ces lignes ne seraient de toute façon pas lues. La présence de la boucle "Tant que" (qui réalise des passes) s'explique par le fait que le bloc recopié peut contenir également un `Goto` : le nouveau bloc peut être optimisé de nouveau. On ne supprime pas les labels recopiés, car on doit toujours pouvoir y accéder par des `Sense`, `Move`, ... En pratique, des programmes du type `While true do done`, qui produisent des cycles de `Goto`/labels, font boucler le "Tant que" : les remplacements se font sans fin et le programme ne termine pas. Nous avons donc remplacé cette boucle "Tant que" par une boucle "Répète n fois", avec n le nombre de labels différents (la taille du tableau de blocs). En effet, la plus longue chaîne de `Goto`/labels possible parcourt une unique fois tous les blocs, donc est de taille n. Ainsi, beaucoup de répétitions et de code inutile sont générés, mais l'assembleur fourmi n'étant destiné à être lu que par des insectes et pas par des primates, nous avons estimé que la lisibilité du code généré était secondaire devant les performances des fourmis. Note : Pour retirer l'optimisation du code il suffit de commenter dans antsc.ml la ligne ``` optimize a_prog; ``` ### Pistes n'ayant pas abouti Nous avons tenté d'implémenter des listes dans notre langage, mais le manque de temps n'a pas fait aboutir cette idée. Plus utile, nous avons envisagé également la manipulation d'entiers à l'aide des opérateurs `+`, `*` et `mod`. Pour ce faire, nous aurions pu créer un nouveau type `exp_int`, similaire à `exp_bool`, qui peut être soit un entier, soit l'addition/multiplication/modulo de deux entiers. ## Dépendances Le compilateur est compilé avec les dépendances suivantes : - OCaml 4.08 ou plus - Le système de construction [Dune](https://dune.build/) version 1.11 ou plus - Le générateur de parser [`simple-parser-gen`](https://github.com/timothee-haudebourg/ocaml-simple-parser) - `ocp-indent` pour indenter les fichiers générés par le générateur de parser. Si OPAM (version 2 ou plus) est installé, l'installation des dépendances se fait en deux lignes dans votre terminal : ``` $ opam install ocamlfind dune ocp-indent $ curl http://people.irisa.fr/Timothee.Haudebourg/teaching/prog1/projects/ants/install-deps.sh | sh ``` Vous pouvez tester la bonne installation de `simple-parser-gen` avec la commande ``` $ simple-parser-gen --help ``` ## Compilation En vous plaçant dans le répertoire contenant le fichier `Makefile`, exécutez la commande : ``` $ make ``` L’exécutable `antsc` et tous les fichiers nécessaires à sa création seront construits en utilisant les règles décrites dans le `Makefile`. ### Génération du parser La génération du parser est effectuée dans le `Makefile` grâce à l’outil `simple-parser-gen`. L'outil prend en entrée le fichier `src/lang.grammar` décrivant la grammaire du langage que vous souhaitez compiler. 3 modules sont ainsi générés, en 6 fichiers : - Le module `Ast` (fichiers `ast.ml`, `ast.mli`) contient la définition de l'arbre de syntaxe abstraite (la structure d'un programme) du langage, et des fonctions d'affichage. ``` simple-parser-gen --ast src/lang.grammar | ocp-indent > src/ast.ml ``` Le pipe `|` redirige la sortie de `simple-parser-gen` vers `ocp-indent` pour indenter le code généré. Enfin `>` écrit la sortie dans le fichier `src/ast.ml`. Le fichier `src/ast.mli` est généré de la même manière en passant l'option `-i` (pour "interface") à `simple-parser-gen`. - Le module `Lexer` (fichiers `lexer.ml`, `lexer.mli`) contient le *lexer* du langage, qui s'occupe de découper les mots du langage. Il est généré avec l'option `--lexer` de `simple-parser-gen`. - Le module `Parser` (fichiers `parser.ml`, `parser.mli`) contient le *parser* du langage, qui s'occupe de générer un arbre de syntaxe abstraite à partir d'un *lexer*.