Comparaison des différents backends
Voici la liste des langages supportés par metalang, classés par qualité de code généré : ruby, ocaml, python, c, php, go, objective-c, java, javascript, c++, c#, perl, ocaml fonctionnel, visual basic, pascal, common lisp, ada, racket.
Les chiffres sont calculés de la façon suivante : nombre de caractères non blancs * 1000 / nombre de caractères des metalang.
Passes de compilations
Pour tout les backends, le compilateur metalang commence par faire les opérations suivantes :
- Parsing
- L'évaluation des constantes et des macros
- Le typage
- la suppression des macros
- La suppression des fonctions inutiles de la librairie standard
- La suppression des types inutiles de la librairie standard
- Vérification des noms (de fonctions, de types, de variables, de champs de records, etc...)
- Vérification des returns
- La collecte des tags
- le renommage des variables qui ne sont pas autorisées dans le backend cible
- L'expension des prints de booleans (en gros, on transforme : print bool foo en if foo then print "True" else print False end)
- La collecte de tags internes (on définit le tag : __internal__allocArray si le programme fait de l'allocation de tableau, __internal__div si le programme fait une division et __internal__mod si il fait un modulo.)
- L'inline des variables
Ensuite, les transformations à effectuer sont vraiment spécifiques aux langages :
Les langages suivants : C, objective-C, pascal, ada, c++, C#, visual basic, java, javascript et go sont compilés avec la chaine suivante :
- La déclaration de types pour les tuples
- L'expension des tuples
- une phase de typage
- La transformation des expressions de type record en instructions
- une passe de typage
- une expansion des tableaux
- L'inline des variables
- une passe de typage
- l'analyse des read
- Une passe qui vérifie la compatibilité des reads avec les macros custom
Le caml est compilé avec :
- L'inline des variables
- une transformation des ifs qui permet d'englober des éléments dans les else quand il y a un return.
- une passe de typage
- l'analyse des read
- Une passe qui vérifie la compatibilité des reads avec les macros custom
Le caml fonctionnel est compilé avec :
- L'inline des variables
- l'analyse des read
- Une passe qui vérifie la compatibilité des reads avec les macros custom
- Une transformation vers un AST fonctionnel
- une passe qui transforme les (apply (lambda ...) ...) en let ... in ... Dans cette passe, on accèpte de currifier
Le common lisp est compilé avec :
- La déclaration de types pour les tuples
- L'expension des tuples
- une phase de typage
- La transformation des expressions de type record en instructions
- une passe de typage
- une transformation des ifs qui permet d'englober des éléments dans les else quand il y a un return.
- l'analyse des read
- Une passe qui vérifie la compatibilité des reads avec les macros custom
Le racket est compilé avec : en refusant la currification
- L'inline des variables
- l'analyse des read
- Une passe qui vérifie la compatibilité des reads avec les macros custom
- Une transformation vers un AST fonctionnel
- une passe qui transforme les (apply (lambda ...) ...) en let ... in ... Dans cette passe, on ne currifie pas.
Le perl, le python et le ruby est compilé avec :
- une passe de typage
- une expansion des tableaux
- L'inline des variables
- une passe de typage
- l'analyse des read
Le php est compilé avec :
- Une passe qui convertit les expressions de type record en instructions (pour le php, cette passe permet de gérer le passage par référence des records.)
- une passe de typage
- une expansion des tableaux
- L'inline des variables
- une passe de typage
- l'analyse des read
Explication des différentes passes
Evaluation des constantes et des macros
Cette passe permet d'évaluer les expressions qui contiennent des unquote (${}) principalement utilisés pour les read_int(), read_int_line(), etc...
Le typage
Cette passe permet d'inférer les types qui n'ont pas été écrits à la main. Il s'agit d'un simple algorithme d'unification. En metalang on a pas de polymorphisme et on est obligé de déclarer les types des fonctions, donc le typage est relativement simple.
Vérification des noms (de fonctions, de types, de variables, de champs de records, etc...)
Dans cette passe, on collecte les noms de variables, de fonctions, de types, de champs de records, utilisés ou déclarés. On affiche des erreurs quand un nom est utilisé à la fois pour un type et pour deux choses (exemple : variable et fonction). C'est une passe de vérifications.
Vérification des returns
Dans cette passe, on vérifie que les returns sont bien placés. On vérifie qu'une fonction renvoie forcément, qu'il n'y a pas d'instructions après un return, etc... Cette passe vérifie aussi les returns dans les allocations de tableaux
La collecte des tags
Cette passe introduit des chaines dans un StringSet global.
def inline int isqrt(int c) tag use_math return sqrt_(c) end
Dans le code ci-dessus, l'utilisation du mot clé tag permet de prévenir le backend C++ qu'il doit inclure math.h. C'est essentiellement pour une utilisation interne.
L'inline des variables
Quand on écrit def inline x = 4 ou quand une variable est inserrée par une autre passe de compilation, cette passe permet de supprimer cette variable quand elle trouve un moyen de le faire.
L'expension des tuples
L'expension des tuples transforme les tuples en records
La transformation des expressions de type record en instructions
En C (et dans pas mal de langages du genre) les records doivent être alloués et ensuite initialisés. En java ou C#, j'aurais pu faire un constructeur pour pouvoir les garder sous forme d'expressions, mais j'ai choisi (pour le moment) d'en faire des instructions. Il faut alors inserrer une variable temporaire pour l'inserrer ensuite dans l'expression.
une expansion des tableaux
Cette passe prend les lambdas des tableaux pour en faire des boucles for.
l'analyse des read
Dans cette passe, on collecte simplement de l'information : cette passe remplit un set de types. Ce set contient l'ensemble des types qui sont lus. Ensuite, on vérifie qu'on ne lit bien que des entiers et des chars.
Une passe qui vérifie la compatibilité des reads avec les macros custom
Cette passe vérifie que si on utilise les macros custom pour la lecture de l'entrée standard (le tag use_readmacros) alors on utilise pas read.
Une transformation vers un AST fonctionnel
Cette passe transforme l'ast contenu dans le fichier Ast/ast.ml en Astfun/astFun.ml. Cette passe se trouve dans Astfun/transformFun.ml. L'ast fonctionnel ne contient pas d'instruction, pas d'écrasement de variables, il ressemble en gros à un mini lisp, voir à un lambda calcul.
Conclusion
On voit qu'on effectue beaucoup de passes de typages inutiles. On pourrait certainement gagner beaucoup de temps CPU en en faisant qu'une et en produisant du code typé, mais c'est plus complexe à mettre en place. La passe d'analyse des noms date d'avant l'apparition de l'inférence, la moitié de son code est déjà vérifiée par le typer. On peut aussi noter que la première passe consiste à évaluer les macros et les constantes, et c'est très important que cette passe soit en premier : bien que les macros soient écrites en metalang, on s'en sert comme d'un préprocesseur et le code ne typerait pas forcément avant de les avoir étendus.