Compilation et langages
TP 9 - Gestion de la surcharge

L'objectif de cette séance est d'étendre le langage A6000 avec de la surcharge statique : un utilisateur pourra définir plusieurs fonctions de même nom et le compilateur choisira pour chaque appel quelle version utiliser, selon les types des paramètres effectifs.

Au préalable, nous allons introduire dans la chaîne de compilation un arbre de syntaxe abstraite annoté par des types, qui facilitera la gestion de la surcharge ainsi que d'autres extensions possibles.

1. Représentation intermédiaire annotée

L'objectif de cette première étape est de modifier la vérification des types (module SourceTypeChecker) pour ne pas seulement vérifier la cohérence des types, mais aussi produire un arbre de syntaxe abstraite dans lequel toutes les expressions et sous-expressions sont annotées par leur type. Cette nouvelle syntaxe TypedAst sera insérée comme une étape intermédiaire entre l'arbre SourceAst produit par l'analyse syntaxique et l'arbre UntypedAst à partir duquel la traduction dirigée par la syntaxe commence.

1.1. Définition

La syntaxe TypedAst est basée sur SourceAst et introduit de nouvelles constructions pour les expressions, emplacements, et appels de fonction annotés par des types :

  type typed_expression = (typ, expression)  annotated_element
  type typed_location   = (typ, location)    annotated_element  
  type typed_call       = (typ option, call) annotated_element

où le type des éléments annotés est défini par :

  type ('a, 'e) annotated_element = { annot: 'a ;
                                      elt:   'e }

En outre, la syntaxe TypedAst modifie les types instruction, expression et associés pour remplacer chaque paramètre de type expression, location ou call par son équivalent annoté.

1.2. Constructeurs

Pour assurer que seuls peuvent être construits des arbres de syntaxe correctement typés, on préconise d'utiliser des constructeurs (ou smart constructors) : des fonctions auxiliaires chargées de construire des nœuds de l'arbre de syntaxe abstraite après vérification de leur cohérence.

Par exemple, les accès aux tableaux pourront être associés à un constructeur

  mk_arrayaccess : typed_expression -> typed_expression -> typed_location

tel que mk_arrayaccess te₁ te₂ produit un emplacement annoté

  { annot= ty; elt= ArrayAccess(te₁, te₂) }

si te₁ est une expression typée de type TypArray(ty) et te₂ est une expression typée de type TypInteger, et lève une exception sinon.

1.3. Insertion dans le compilateur

Le travail de vérification anciennement effectué par le module SourceTypeChecker est remplacé par un module de traduction SourcetoTyped, qui prend un programme SourceAst et le traduit en un programme TypedAst si ses types sont cohérents. Le module SourcetoTyped fera appel aux constructeurs décrits ci-dessus pour construire les éléments et déléguer une partie de la vérification.

Le module SourcetoUntyped est remplacé par un module TypedtoUntyped qui traduit un programme TypedAst en programme UntypedAst en effaçant simplement toutes les annotations.

1.4. Travail attendu

Vous devez créer un module TypedAst définissant la syntaxe annotée par les types et ses constructeurs, et implémenter les deux modules de traduction SourcetoTyped et TypedtoUntyped.

Vous pouvez vous baser pour cela sur le code présent dans les modules SourceAst, SourceTypeChecker et SourcetoUntyped.

2. Surcharge résolue statiquement

2.1. Description

Rien n'avait été spécifié jusqu'ici sur le comportement d'un programme A6000 comportant deux définitions de fonctions d'un même nom. On veut maintenant obtenir le comportement suivant :

• Si un programme définit deux fonctions de même nom mais avec des paramètres formels de types différents, alors ces deux fonctions doivent être compilées.
• Lors d'un appel f(e₁,...,eₙ), le compilateur cherche une fonction de nom f et dont les types des paramètres formels sont, dans l'ordre, les types des expressions e₁ à eₙ. Si une telle fonction existe, c'est elle qui est considérée comme appliquée (et c'est son type de retour qui est retenu). Sinon, il s'agit d'une erreur de type.

Remarquez que l'ordre des types compte, mais qu'en revanche rien ne permet de distinguer deux fonctions dont les paramètres formels ont les mêmes types, dans le même ordre (notamment, les noms des paramètres formels ne sont pas utilisés).

2.2. Stratégie d'implémentation

Pour résoudre la surcharge des fonctions, le compilateur va en réalité donner des noms différents à deux fonctions ayant des paramètres de types différents.

Cette distinction sera créée lors de la phase de traduction TypedtoUntyped, et donc effective à partir de la représentation intermédiaire UntypedAst : après cette étape, le compilateur n'aura plus besoin de se soucier de la surcharge (ni même de savoir que la surcharge était permise dans le langage source).

Si une fonction de nom f a des paramètres formels de types ty₁, ..., tyₙ, on propose de la renommer f_⟦ty₁⟧_..._⟦tyₙ⟧ à partir de l'étape UntypedAst, où ⟦ty⟧ est une chaîne de caractères représentant le type ty.

Variante possible : même si les utilisations d'une fonction f ne seront traduites avec le nouveau nom que lors de l'étape TypedtoUntyped, la table des définitions des fonctions peut utiliser le nouveau nom dès l'origine.

2.3. Travail attendu

Assurez-vous que votre représentation des programmes sources autorise la définition de plusieurs fonctions du même nom, au moins dans le cas où les types des paramètres sont différents, puis adaptez en conséquence la vérification des types (par exemple au niveau du constructeur mk_call). Enfin, appliquez les noms de fonction étendus lors de la traduction TypedtoUntyped.

Remarque : à défaut d'un traitement particulier, la fonction principale portera dorénavant le nom main_integer. Il faudra donc remplacer la ligne jal main par jal main_integer dans la fonction init du module de génération de code assembleur (AllocatedtoMips).

3. Extensions

3.1. Améliorer les messages d'erreur

Remplacer la syntaxe source SourceAst par une nouvelle syntaxe LocatedSourceAst, similaire mais dont les éléments sont annotés par leur position dans le code source.

En profiter pour assurer que les messages d'erreur, par exemple lors de la vérification des types, indiquent à l'utilisateur la position des erreurs trouvées.

3.2. Avec un peu d'inférence de types

Faire en sorte que la résolution de la surcharge puisse se faire sur la base non seulement des types des paramètres effectifs, mais également sur les types de retour attendus.

Remarque : évidemment, cela ne marche que pour les fonctions utilisées à des positions dans lesquelles vous êtes capables de prédire le type de retour attendu. Il y a certains cas très simples à régler. Le cas général demande plus de réflexion.

3.3. Autres applications des smart constructors

Dès SourceAst, il est possible d'utiliser des smart constructors pour effectuer des simplifications à la volée.

Par exemple, vous pouvez introduire un constructeur pour Binop qui, dans le cas où les deux opérandes sont des constantes, calcule directement le résultat et produit finalement un Literal.