Greg's Devblog Par un développeur, pour les développeurs

Javaz : Compiler du Java en bytecode Caml

Dans le cadre de la matière "Typage et Polymorphisme", à la fac, on avait un choix de sujet (projets ou articles), et avec mon binôme aucun ne nous plaisait. Du coup il a voulu qu'on propose au prof notre propre sujet : compiler des sources Java en bytecode Caml...

Bon, le prof n'était pas trop content, mais il a fini par accepter le projet. On a déjà un petit truc basique qui tourne, et c'est assez intéressant. Le tout est écrit en OCaml, comme ça c'est l'occasion pour moi de m'y remettre un peu (après 1 ou 2 ans sans y avoir touché), et il faut dire que ça se prête particulièrement bien à la tache.

Les différentes étapes du projet sont relativement classiques :

1. Conversion en Ast

On commence donc par convertir les sources en Ast (Arbre de syntaxe abstraite), grâce à Yacc et Lex. En gros, c'est un parcours du fichier source, et on transforme tous les mots-clés et autres éléments repérés sous forme d'arbre.

Ainsi, l'expression (2 + 3) devient un noeud "opération + ", qui a "2" et "3" comme noeuds. Et donc par extension, 2 + 3 * 4 devient "*" avec comme fils gauche "+" (ayant lui-même les fils "2" et "3") et à droite "4". C'est une façon de parser qui revient à mettre le parenthésage implicite qui va bien, et qui permet en fait de calculer le résultat très facilement et récursivement (on applique le méthode de calcul sur le fils gauche, puis sur le fils droit, et fait l'opération correspondante sur le résultat).

La transformation en Ast permet déjà de vérifier si la syntaxe est valide selon la norme...

2. Typage de l'Ast

Une fois qu'on a cet Ast, on va chercher à le typer, ce qui va permettre au passage de vérifier la validité de tout un tas de trucs, et d'appliquer les casts implicites. En Java, le typage est explicite, donc le typeur n'a pas un énorme travail à faire pour "déduire" des types, il se contente de regarder ce qu'il a un peu partout et de valider ou pas. On a ainsi plusieurs opérations d'effectuées :

• Typage de tous les noeuds de l'Ast : à la fin on obtient un Ast typé, correspondant au fait à tous les noeuds de l'Ast original (plus quelques nouveaux) auquel on ajoute le type résultant. Si on a un noeud "+" qui a comme fils un entier et un floatant, le noeud aura donc comme type "float".
• Insertion des casts implicites : à chaque fois qu'on a 2 types différents qui se "rencontrent", on regarde comment caster l'un en l'autre de façon implicite. Ainsi, si on a une opération "+" qui prend un entier et un string, on va rajouter le cast de l'entier en string pour faire une concaténation de chaines... De même, si on affecte un entier à une variable qui est de type floatant, on va rajouter le cast. Et en fait on se rend compte qu'on a pas mal de cas, notamment à cause de tous les types d'entiers (byte, char, short, int, long).
• Vérification de la validité des variables : pendant le parcours, on va "noter" toutes les variables locales que l'on rencontre (ainsi que les champs et paramètres, en fait), et donc quand on utilise une variable dans une méthode, on va tout de suite pouvoir vérifier si elle existe. Le cas échéant, on s'arrête avec un message d'erreur de type "Undeclared Variable XXX". Si elle existe, on va en profiter pour transformer le nom de la variable en une information un peu plus pratique le générateur de code pourra manipuler plus facilement : dans notre cas, on a choisi de représenter une variable locale par un couple d'entiers, le premier représentant le bloc relatif au courant auquel elle appartient, et le second le numéro de la variable dans ce bloc (par ordre de déclaration). Il est donc très facile pour le générateur de code de retrouver la variable dans la pile : soit c'est dans le bloc courant, donc on récupère sa position par rapport au pointeur de pile, soit c'est dans un bloc parent, et dans ce cas il suffit de connaitre le pointeur de pile correspondant à ce parent pour retrouver la position de la variable dans la pile.
• Vérification des méthodes : on va appliquer le même principe aux méthodes (pas tout à fait fini, mais c'est en cours), vérifier que la méthode existe bien (et est accessible) dans un objet de cette classe, etc...
• Transformation des boucles for en boucles while, histoire de ne pas se trainer des cas particuliers tout le temps. En cours de route on est tombé sur une petite subtilité : on ne peut pas se contenter de fusioner les instructions du corps avec le code à exécuter à la fin de chaque tour de boucle, car si on fait un "continue" au milieu du bloc, il faut bien exécuter les dernières instructions... Du coup la boucle while possède en fait 2 blocs : un bloc d'instruction pour le corps de la boucle, et une expression à évaluer après l'évaluation du bloc... Pour transformer la boucle for en boucle while, on créé juste un premier bloc d'instructions comprenant l'initialisation de la boucle, ainsi que la boucle while résultante. Ce qui permet de gérer automatiquement les variables déclarées à la volée dans la boucle for

Il reste encore pas mal de boulot au niveau du typeur, et c'est notamment lui qui va implémenter une première version de la gestion de surcharges...

3. Interprétation de l'Ast typé (optionnel)

Cette étape est un peu superflue et sert essentiellement pour des raisons de tests, car elle permet de tester le résultat de l'arbre typé en l'exécutant... Comme on tourne dans du code maison, on peut rajouter des affichages de debug un peu partout pour voir ce qui se passe. Et comme l'Ast est typé, l'interpréteur peut en fait vérifier les types à tout moment, sachant que jusqu'à maintenant la seule fois ou un type a été explosé (à savoir, une variable de type boolean contenant la valeur entière "0"), c'est quand j'ai fait péter le pointeur de pile ^^. C'est bien pratique pour repérer les conneries au niveau du typeur, comme des index de variables locales mal mis.

Les performances de l'interpréteur sont bien entendu catastrophique, puisqu'on ne fait que se balader dans un arbre dans un peu tous les sens, en récupérant les fils, puis en remontant, etc...

4. Génération de code

Pour l'instant, seul mon binôme s'est intéressé à cette partie, donc je n'ai pas encore mis les mains dedans. Mais en gros le principe est de prendre chacune des instructions/expressions de l'Ast typé, et de la traduire en code machine correspondante. On écrit ici du bytecode Caml, mais dans le fond c'est un peu la même démarche que quand on génère de l'assembleur (sauf que là ça serait un assembleur de plus haut niveau avec des instructions sympas ^^). Donc voilà, on pousse des valeurs sur la pile, on met le bytecode correspondant à l'addition, etc... C'est un peu long et fastidieux pour l'instant, mais quand on va arriver à la génération du code pour les objets ça devrait être assez sympa :p

Mots de la fin

Le projet n'est pas encore terminé, mais en quelques jours on a déjà bien avancé. C'est vraiment très instructif, car on en apprend à la fois sur Java (avec les spécifications à la con... c'est comme ça que j'ai appris qu'on pouvait mettre un label aux blocs pour ensuite appliquer ce label sur les continue/break !), sur Caml (car on a déjà plusieurs milliers de lignes de code, donc ça fait une bonne base de travail ^^), sur le typage en général, etc... En fait c'est une manière assez rapide de synthétiser tout un ensemble de cours que j'ai eu à la fac depuis 1 an (et d'autres en cours), donc c'est top !

Après, quant à savoir si le projet pourrait avoir un jour un intérêt autre que le délire de l'avoir fait, on est en train de se poser la question, et a priori... non ! Mais techniquement, ça marche déjà : on a fait plusieurs tests, notamment un qui consiste à calculer les nombres premiers dans les 10 000 premiers entiers, et on obtient bien le résultat voulu