Ce sujet traite de deux modifications du compilateur zyva du cours. La première partie traite d'une première modification et les deux parties suivantes d'une seconde modification. Les deux modifications sont indépendantes, et les parties le sont également dans une large mesure.

La boucle for est la construction naturelle pour parcourir les tableaux. Par exemple, on affiche un tableau t comportant n éléments de type integer par :

On notera que l'indice de boucle (c'est-à-dire la variable i) n'est pas déclaré explicitement. De fait, notre boucle for est celle de Caml, dont voici la sémantique informelle.

L'instruction « for i := e1 to  e2 do B » évalue d'abord les deux expressions e₁ et e₂ (les bornes) en deux valeurs entières (type integer) n et p.

Ensuite, le corps B (une instruction) est exécuté de façon répétée dans un environnement où l'indice i (un nom de variable) est lié successivement aux valeurs entières n, n+1, …, p−1, p. Le corps n'est pas exécuté si n > p.

L'affectation de l'indice de boucle i dans le corps B est interdite.

Question 1. On essaie tout d'abord d'opérer une tranformation « source to source » de la boucle for en boucle while.

Une procédure contenant une boucle for :

procedure p(…) ; var … begin … for i := e1 to e2 do B ; … end ;

sera transformée en :

procedure p(…) ; var i:integer ; … begin … i := e1 ; while i <= e2 do begin B ; i := i+1 end ; … end ;

Donner un exemple qui montre que la transformation décrite ci-dessus ne respecte pas la sémantique de la boucle for.

2
0
1

2
0
2
1
2

Plutôt que de suivre la technique de la question 1, on va intégrer complètement la nouvelle construction. La définition des arbres de syntaxe abstraite est étendue par l'ajout des lignes suivantes à la fin du fichier pp.mli.

Cela revient à ajouter une nouvelle instruction à Pseudo-Pascal.

Question 2. Modifier les analyseurs lexical et syntaxique de zyva (fichiers lexer.mll et parser.mly, donnés en annexe) pour intégrer la nouvelle instruction.

Question 3. On se propose de rejeter les programmes qui ne respectent pas la condition « l'affectation de l'indice de boucle dans le corps de la boucle est interdite ». Écrire, en Caml, une fonction checkCorrect de type Pp.instruction -> bool, qui prend en argument une instruction et renvoie true, si et seulement si l'interdiction est respectée.

Question 4. Proposer une sémantique précise de la boucle for. Pour répondre à cette question, le plus simple est sans doute de compléter l'interpréteur de zyva (fichier interpret.ml donné en annexe), mais on pourra aussi donner des règles d'inférence dans le style de celles du poly, section 3.4.2.

Question 5. Modifier le générateur de code intermédiaire pour traiter la boucle for. Le générateur est le fichier trans.ml donnée en annexe. Les interfaces code.mli (définition du code intermédiaire) gen.mli (temporaires et étiquettes) et env.mli (environnements de Pseudo-Pascal) sont données en annexe.

Question 6. Proposer une transformation correcte de la boucle for en boucle while équivalente. Concrètement, on expliquera comment transformer la procédure p de la question 1. Attention On veillera à traiter correctement le cas où la procédure p utilise une variable de nom i en dehors du corps de la boucle.

Dans cette partie (et dans la suivante) on se propose d'étendre zyva pour qu'il traite les calculs flottants. Seuls deux points importants seront traités, d'abord l'utilisation du coprocesseur flottant du MIPS, puis, dans la partie suivante, la distinction entre opérations flottantes et entières à l'aide du typage.

Le processeur MIPS peut donc être équipé d'un coprocesseur chargé des calculs flottants. Nous allons uniquement considérer des nombres flottants double précision (type real de Pseudo-Pascal) dont la taille est de deux mots mémoire ou 8 octets.

1. Le coprocesseur possède 16 registres (doubles) notés $f0, $f2, …, $f30 (de deux en deux). Chaque registre double $f<n> (n pair) regroupe en fait deux registres simple précision, notés $f<n> et $f<n+1>. En pratique, tout se passe le plus souvent comme si le coprocesseur possédait bien 16 registres doubles.
2. Les opérations flottantes sont du type « trois addresses » opérant exclusivement sur les registres flottants. Par exemple, l'instruction add.d   $f0, $f2, $f4 range la somme (addition flottante double précision) du contenu des registres $f2 et $f4 dans le registre $f0.
3. Il existe une instruction mov.d de transfert entre registres du copresseur dont l'usage est similaire à celui de l'instruction move du processeur. Par exemple, l'instruction mov.d  $f0, $f2 copie le contenu du registre (double) $f2 dans le registre (double) $f0.

Question 7. Énoncer des conventions d'appel pour les fonctions qui prennent des arguments flottants et rendent un résultat flottant. On illustrera ensuite ces conventions en « compilant » la fonction Pseudo-Pascal suivante :

Question 8. On suppose que le compilateur zyva est suffisament sophistiqué pour introduire des conversion des entiers (type integer) vers les flottants (type real) quand c'est utile. Comme par exemple dans la fonction suivante ou l'addition demande la conversion préalable de l'entier n :

Pour réaliser ces conversions, le processeur MIPS emploie les instructions suivantes :

1. Il est possible de copier (sans modification) le contenu d'un registre du processeur dans un registre (simple) du coprocesseur, par l'instruction mtc1 (Move To Coprocessor 1). Par exemple, l'instruction mtc1 $v0, $f2 copie le contenu du registre $v0 (du processeur), dans le registre $f2 (du coprocesseur).
2. Le coprocesseur peut effectuer des conversions de données binaires et en particulier des entiers (32bits) vers les flottants double précision à l'aide de l'instruction cvt.d.w. De sorte que, par exemple, l'instruction cvt.d.w $f0, $f2 convertit l'entier contenu dans le registre $f2 en flottant double précision et range ce résultat dans le registre (double) $f0 du coprocesseur.

Donner un code possible résultat de la compilation de fiadd.

Question 9. Compiler manuellement la fonction suivante :

Attention : On demande un code tel que produit par le compilateur zyva qui n'a pas connaissance des registres modifiés par les fonction appelées, mais s'appuie sur des conventions d'emploi des registres clairement énoncées. Le coprocesseur peut lire un flottant en mémoire par l'instruction l.d et écrire un flottant en mémoire par l'instruction s.d. Ces deux instructions fonctionnent comme les instructions lw et sw du processeur. Par exemple l.d  $f0, 0($a0) charge les deux mots mémoire d'adresses $a0 et $a0+4 dans le registre (double) f0.

Le programmeur Pseudo-Pascal ne fait aucune distinction entre opérations entières et opérations flottantes. C'est-à-dire qu'il écrit par exemple.

Ici, la première addition est une addition entière (en dernière analyse add), tandis que les deux suivantes sont des additions flottantes (en dernière analyse add.d). En outre, la dernière addition ne peut s'effectuer qu'une fois l'entier n converti (ou « promu ») en flottant. On dit que l'opérateur « + » est surchargé, il peut signifier des opérations différentes selon les types de ses arguments.

Question 10. Comment peut-on justifier l'introduction par le compilateur de conversions implicites des entiers vers les flottants ? On remarquera que l'utilisation implicite de la conversion inverse des flottants vers les entiers n'est pas autorisée.

Le compilateur zyva modifié procède à la résolution de la surcharge lors d'une phase sémantique de vérification des types. Concrètement, on va réécrire la syntaxe abstraite du programme en syntaxe abstraite typée.

La syntaxe abstraite est donnée dans l'annexe pp2.mli (attention la syntaxe abstraite a un peu changé par rapport à la première partie), la syntaxe abstraite typée est donnée dans le fichier tpp.mli. Les deux syntaxes abstraites non-typée et typée font référence aux types des opérations et des comparaisons définies dans le fichier primitive.mli.

Pour ce qui nous intéresse, la syntaxe typée étend et précise la syntaxe non-typéee au sens suivant :

1. Les expressions de la syntaxe typée possèdent toutes un argument supplémentaire (le dernier) qui est le type de l'expression.
2. Les opérateurs (type binop) de la syntaxe non-typée sont partitionnés entre calcul (constructeur Op) et comparaisons (constructeur Cmp). Ils apparaissent comme arguments du constructeur des expressions Bin.

   Les opérateurs (type fun_prim) de la syntaxe typée sont partitionnés de même et aussi entre opérations entières et flottantes (constructeurs IOp et ICmp d'une part, et FOp et FCmp d'autre part). Ils apparaissent comme arguments du constructeur des expressions Prim_call, qui représente l'application des opérateurs. Il y a quelques nouveaux opérateurs et notamment la promotion d'un entier en flottant (ItoF).

   On notera que  Prim_call prend une liste d'expressions en second argument, car tous les opérateurs n'ont pas exactement deux arguments. Par exemple, la promotion d'une expression de type entier e en flottant et l'addition de deux expressions entières s'expriment ainsi en syntaxe typée :

   Prim_call (ItoF, [e]) : Real     Prim_call (IOp (Add), [e1; e2]) : Integer

   Noter la syntaxe spéciale « … : t » qui met en valeur le dernier argument des constructeurs de la syntaxe typée (le type justement).

Question 11. L'action du vérificateur de type est donc une traduction de la syntaxe abstraite non-typée vers la syntaxe abstraite typée. On peut l'exprimer par des règles d'inférence qui prouvent des propositions de la forme : Γ ⊣ e ⇒ e':t, à lire comme : « dans l'environnement Γ, l'expression e non-typée e se traduit en expression typée e', de type t.

Voici par exemple, comment sont typées les constantes entières, les variables et l'addition entière :

Écrire les règles de l'addition flottante. Attention : Les règles doivent être suffisament puissantes pour typer tous les exemples d'addition de cette partie. Par ailleurs, le typage doit être déterministe, c'est-à-dire autoriser au plus une façon de typer une addition donnée.

Question 12. Le fichier typer.ml (la dernière annexe), réalise un vérificateur de type. Il est incomplet dans le sens qu'il ne réalise aucune promotion des entiers vers les flottants. Modifiez-le, afin d'introduire ces conversions partout où c'est possible. Ne pas se laisser impressionner par la longueur du code, une modification mineure permet de répondre à la question.

Ce document a été traduit de L^AT_EX par H^EV^EA