Projet de programmation 1: compilateur de C-- avec exceptions

1  Introduction

Le cours de programmation s’étend tout au long de la 1ère année à Cachan. Vous aurez à y faire plusieurs projets. Le tout premier d’entre eux commence le lundi 16 octobre 2006, et est à rendre le vendredi 24 novembre 2006.

Il s’agit d’écrire un compilateur pour un langage ressemblant à C, mais suffisamment réaliste. Il s’agit essentiellement d’un sous-ensemble strict du langage C, mais avec un mécanisme d’exceptions (throw, try…catch…finally) ressemblant à celui de Java. Nous appellerons ce langage C--. Le langage cible sera l’assembleur x86. Votre compilateur sera écrit en OCaml.

Voici un exemple de programme que votre compilateur devrait compiler:

Ce programme, qui a été un de nos exemples lors des premiers cours code la commande Unix cat.

Au passage, j’ai évidemment fait le projet avant vous. Voici ce que mon compilateur produit:

Vous avez déjà eu une bonne dose d’assembleur, et vous devriez donc être capables, avec un peu d’effort, de comprendre globalement ce que ça fait (surtout sachant que ceci vient du source C montré plus haut).

2  Comment ça se passe

D’abord, je vous recommande de travailler sous Linux. N’importe quelle version devrait faire l’affaire. Toutes les versions de Caml ou OCaml ≥ 2.04 devraient aussi faire l’affaire. Si vous voulez travailler sur un autre système d’exploitation (Windows par exemple), c’est votre choix. Sachez cependant que, même avec Cygwin sous Windows, vous vous exposez à des complications. Allez-y si vous avez une âme de hacker.

Ensuite, vous devez récupérer l’archive du projet. Décompressez-là avec gunzip et désarchivez le tout avec tar. Vous pouvez faire le tout en une seule étape en tapant tar -xvzf projet.tgz.

Vous devriez obtenir un répertoire MiniC et les fichiers suivants:

Votre travail consiste à écrire le fichier manquant compile.ml. Vous pouvez y écrire ce que vous voulez, l’important est de définir la fonction dont le type est spécifié dans le fichier d’interface compile.mli:

val compile : out_channel -> Cparse.var_declaration list -> unit;;

Cette fonction prend un canal de sortie en premier argument, appelons-le out, et un programme C--, appelons-le π, et imprime sur out un texte en assembleur x86 qui code le programme π. Ce texte en assembleur ressemblera donc au texte de l’introduction (voir le fichier cat.s).

Lorsque vous aurez écrit le fichier compile.mli, compilez le tout en invoquant make. Comme Emmanuel et moi vous l’avons expliqué, ceci va appliquer un certain nombre de commandes dans un ordre défini par les dépendances exprimées dans le fichier Makefile.

Le résultat sera un programme, qui s’appellera mcc et sera dans le répertoire ProjetMiniC2. Vous pourrez tester ce programme en tapant ./mcc suivi du nom d’un fichier C-- à compiler.

Par exemple, si vous tapez (en partant du répertoire ProjetMiniC2):

Ceci devrait produire un fichier assembleur cat.s, que vous pourrez consulter, et un fichier exécutable cat, que vous pourrez tester en tapant (sous le répertoire ProjetMiniC2/Exemples):

Il est évidemment plus que probable que le code assembleur que vous produisiez, au moins au début, ne soit pas de la meilleure qualité. Notamment, mcc appelle le compilateur gcc pour compiler le code assembleur que vous aurez produit vers un vrai exécutable. Si votre code assembleur n’est pas syntaxiquement correct, ceci échouera. Il se peut aussi que vous obteniez un exécutable, mais qu’il plante (message Segmentation fault, typiquement).

Dans tous les cas, vous pouvez:

• Limiter mcc à ne produire que le code assembleur, sans le compiler. Appelez-le avec l’option -S:

  ../mcc -S cat.c

  Ceci affichera le code que votre fonction compile produit. Vous pouvez envoyer ce code dans un fichier, disons cat.s encore une fois, par:

  ../mcc -S cat.c >cat.s

• Ou bien, et ceci si votre exécutable plante, utiliser le débogueur graphique ddd. Si vous ne l’avez pas, rabattez-vous sur xxgdb, ou dans le pire des cas sur gdb. Utilisez les commandes
  • Menu “Data”, item “Status Displays...”, cliquez sur “List of integer registers and their contents” (pas “List of all registers...”!), puis “Close” sous ddd pour voir le contenu des registres de la machine. Sous gdb, tapez info registers pour le même effet (en moins beau).
  • Menu “Data”, item “Memory...”, tapez sur disons 32 dans la case “View”, puis cochez “hex”, “words”, et l’adresse mémoire à laquelle vous voulez regardez dans la case “from”. Par exemple, si %esp vaut 0xbffff8e0, tapez 0xbffff8d0 dans le champ “from” pour voir un peu de part et d’autre de 0xbffff8e0. Sous gdb, vous obtiendrez le même effet (en moins beau) avec l’incantation:
    x/32xw 0xbffff8d0

3  Quelques règles du jeu

Vous pouvez allez regarder les fichiers que vous voulez. Le seul fichier que vous n’aurez pas est celui que vous avez à écrire, compile.ml.

Vous n’avez le droit de modifier aucun des fichiers de l’archive du projet. En fait, vous devrez vous limiter à écrire vos fonctions dans le fichier compile.ml. L’idée, c’est que si je prends votre fichier compile.ml et je l’ajoute à l’archive, que je tape make, j’obtiens un compilateur fonctionnel pour C--.

Une autre façon de le dire: vous pouvez aller bidouiller les autres fichiers du projet si ça vous chante, par exemple, pour ajouter des appels à Printf.printf, et voir comment ça marche, mais vous ne devez pas faire des modifications dans ces fichiers qui soit essentielles à la bonne marche de votre compilateur.

4  L’architecture de mcc

D’abord, quand on exécute mcc, il va commencer par exécuter le code qui se trouve dans le fichier main.ml.

Celui-ci lit les options de commande (-S par exemple), puis appelle l’analyseur syntaxique Ctab.translation_unit, auquel on passe l’analyseur lexical Clex.ctoken.

Le source de l’analyseur syntaxique, qui servira aussi de documentation pour la grammaire du langage C--, est dans le fichier ctab.mly. La description des tokens lexicaux est dans clex.mll.

L’analyseur syntaxique fournit un programme sous forme d’une liste de Cparse.var_declaration. Les d’une liste de var_declaration sont déclarées au début du fichier cparse.ml, comme suit:

Le type locator est juste un pointeur sur des informations permettant aux fonctions Error.error et Error.warning d’afficher des message d’erreur sensés.

Le fichier cparse.ml contient aussi des fonctions utiles, comme string_of_loc_expr, qui vous permettent d’obtenir une version imprimable d’une expression C--, ce que vous pouvez utiliser en phase de débogage.

Le fichier genlab.ml contient une fonction genlab qui vous permettra de fabriquer des labels uniques, ce qui devrait être bien pratique lorsque vous émettrez des instructions de saut dans votre code assembleur.

Le fichier verbose.ml déclare une variable verbose que vous pourrez tester pour régler le niveau d’informations de débogage que vous voudrez afficher (elle vaut 1 si vous appelez mcc avec l’option -v1, 2 si avec l’option -v2, et 0 par défaut).

5  Le langage C--

C-- est, si l’on excepte la notion d’exception, un sous-ensemble extrêmement réduit du langage C. Ont été supprimés de C: tous les types struct, union, enum, ainsi que les tableaux, et la plupart des types scalaires. En fait, il ne reste que les types int, char *, et les pointeurs sur les types C-- (récursivement).

L’avantage est que tous ces types tiennent sur 32 bits. Vous n’aurez donc pas à vous casser la tête pour savoir combien de place allouer à chaque variable: ce sera toujours 4 octets.

Ensuite, de nombreuses constructions de C ont été supprimées, mais pas suffisamment pour ne pas pouvoir compiler des programmes intéressants.

En principe, C-- est un sous-ensemble de C, ce qui signifie que vous pourrez tester mcc en comparant les programmes qu’il produit avec ceux produits par gcc.

Il n’y a que deux exceptions à ce principe. La première est l’ajout à C--, par rapport à C, des exceptions, c’est-à-dire des constructions throw et try…catch…finally. La seconde est l’arithmétique sur les pointeurs, qui a une sémantique différente en C-- et en C. Si vous déclarez int *p et écrivez p++ en C, ceci ajoute sizeof(int), soit 4, à l’adresse p. En C–, ça n’est censé qu’ajouter un. Je doute que vous ayez à considérer ce genre de subtilités, mais qui sait.

6  La sémantique opérationnelle à grands pas de C--

Définissons, petit à petit, la sémantique de C--, hors exceptions. Les exceptions seront décrites en section 7.

Soit Z₃₂ l’ensemble de tous les entiers signés 32 bits: Z₃₂ = [−2³¹, 2³¹−1]. Soit Addr le sous-ensemble de toutes les adresses.

Nous allons présenter la sémantique de C-- en deux étapes. En section 6.1, nous présenterons une sémantique pour un sous-ensemble extrêmement réduit de C--. L’avantage est que cette sémantique sera très simple. Certaines particularités de C-- nous forceront à décrire une sémantique plus compliquée en section 6.2.

6.1  Une sémantique simple pour un sous-ensemble de C--

Considérons un langage où les expressions sont juste celles de la forme:

et où les instructions sont de la forme:

Pour pouvoir donner une sémantique aux appels de fonction (call), il nous faut nous donner la description d’un programme π. Pour nous, un programme π sera une fonction mathématique, de domaine fini, qui à des noms de fonction f associe un triplet (l, c, e), où l est une liste de variables distinctes deux à deux (les paramètres formels de la fonction f), c est une instruction (le corps de la fonction), et e est une expression (dénotant la valeur retournée par la fonction).

Les expressions et les instructions seront évaluées dans un environnement ρ, qui est une fonction de domaine fini associant une valeur dans Z₃₂ à des variables.

Définissons des règles permettant de déduire des jugements de la forme

signifiant “dans l’environnement ρ, l’expression e a pour valeur V”.

On a d’abord une règle pour la variable:

(1)

Cette règle s’applique dès que x est dans le domaine de ρ. Elle n’a aucune (autre) prémisse.

On a ensuite une règle pour l’addition:

(2)

(La raison pour laquelle nous écrivons l’addition e₁ plus  e₂ plutôt que e₁+e₂ par exemple est pour bien distinguer l’opération syntaxique plus de l’opération mathématique d’addition, notée +.)

Nous traiterons de l’appel de fonctions plus loin.

On peut maintenant définir des jugements de la forme

pour chaque instruction c, signifiant “en partant de l’environnement ρ, l’instruction c termine sur un nouvel environnement ρ′, le programme courant étant π”. De nouveau, les jugements dérivables sont définis par des règles de déduction.

La première est pour l’affectation:

(3)

La notation

désigne la fonction de domaine dom  ρ union {x}, qui à x associe V et à tout y in dom  ρ ∖ {x} associe ρ (y).

L’instruction skip ne fait strictement rien de remarquable:

(4)

La séquence évalue ses arguments… en séquence:

(5)

Elle introduit donc un environnement intermédiaire ρ′ représentant l’environnement après l’exécution de e₁ et avant l’exécution de e₂.

Jusqu’ici, nous avions une règle de déduction par construction syntaxique. Ceci change pour le test. Nous avons une règle lorsque la condition testée est fausse, et une lorsqu’elle est vraie:

(6)

Comme en C, 0 est faux, et tout autre nombre est considéré comme vrai.

(7)

La boucle while  (e)  c est équivalente à if  (e) then  c;while  (e)  c  else skip. Ceci donne lieu, ici aussi, à deux règles pour l’évaluation des boucles.

(8)

(9)

La seconde règle a la particularité que sa seconde prémisse ne porte pas sur une instruction plus petite que celle en conclusion, contrairement aux règles présentées jusqu’ici. Ceci mène à des comportements non terminants. Disons que c termine dans π, à partir de ρ, si et seulement s’il existe ρ′ tel que soit déductible.

L’appel de fonction fait aussi ce qu’on attend de lui:

(10)

où est l’environnement qui à x₁ associe V₁, …, à x_n associe V_n.

Exercice 4   Montrer que cette sémantique est déterministe: si et sont déductibles, alors ρ′ = ρ″. Dites précisément sur quoi vous effectuez une récurrence, et décrivez quelques-uns des cas que vous traitez, notamment ceux utilisés lorsque c est une boucle while.

while e do c;;

let rec f () = 
        if e
           then begin
                  c;
                  f ()
                end
        else ()
in f ();;

Il manque à cette sémantique, notamment, l’allocation mémoire et les pointeurs, les variables globales, la possibilité d’effectuer des effets de bord à l’intérieur des expressions. Ceci sera réparé dans la sémantique de C--, que nous décrivons tout de suite.

De plus, la sémantique de l’appel de fonctions est en réalité un peu bricolée, autrement dit pas très élégante. On verra à la section 7.2 qu’un style de sémantique dit par continuations est plus élégant, tout en étant plus proche du code assembleur que l’on produit classiquement.

6.2  La sémantique de C--

Un programme π est pour nous un couple (ρ_π, fun_π):

• L’environnement global envoie chaque nom de variable globale vers une adresse allouée pour elle. (Les variables globales sont décrites par les CDECL (loc,x) dans la liste de var_declaration fournie à la fonction compile. Le compilateur doit donc allouer une place mémoire pour chaque.)
• La définition envoie chaque fonction définie dans le programme vers son code. (Ce sont les CFUN (loc, f, params, code) dans la liste de var_declaration fournie à la fonction compile.)

On supposera pour simplifier que fun_π contient aussi des entrées pour toutes les fonctions de la libc, comme printf, strcpy, malloc, free, etc. Et que, de même, ρ_π contient aussi des entrées pour toutes les variables globales de la libc, comme errno par exemple.

On définit une série de jugements de sémantique opérationnelle de la forme

qui dit qu’en partant d’une mémoire , et d’un environnement qui dit à quelles adresses sont stockées les variables, l’expression C-- e peut s’évaluer en la valeur v in Z₃₂, et modifier la mémoire en µ′.

Il y a deux sortes de variables. Les variables locales (ou automatiques dans le jargon du C) sont données dans l’environnement ρ:

(11)

Les variables globales sont décrites par l’environnement global ρ_π.

(12)

(13)

L’évaluation des chaînes est un peu plus étrange. Elle retourne une adresse mémoire quelconque où se trouve déjà la représentation de s. Disons que s est stockée à l’adresse a si et seulement si s ne contient pas l’octet 0, il existe une adresse a+k dans la mémoire µ contenant un octet nul, avec k minimal, et la suite de tous les octets aux adresses a, a+1, a+2, …, a+k−1 vaut s.

(14)

En pratique, le compilateur devra allouer de la place pour la chaîne s à la compilation. Ceci est fait pratiquement automatiquement par l’assembleur. Par exemple,

réserve de la place pour les octets ‘r’ et 0, les place à une adresse nommée .main_3. L’instruction mystérieuse .align 4 sert à assurer que ce qui suit commencera à une adresse multiple de 4, ce qui facilite la tâche du processeur pour certaines opérations.

Pour toute mémoire µ, pour toute adresse a in Addr, pour toute valeur v in Z₃₂, notons la mémoire qui à a associe v, et à toute autre adresse a′ ≠ a associe µ (a′).

On a encore deux règles pour SET_VAR, selon que la variable est locale ou globale.

(15)

(16)

Passons aux instructions de la forme x[i]=e. On comprend l’addition a+v comme étant effectuée modulo 2³².

(17)

(18)

Disons qu’une mémoire µ′ étend µ, ce que nous noterons , si et seulement si et µ′_{|dom  µ} = µ. On note la fonction qui à chaque x_i associe a_i, 1≤ i≤ n. Ceci est bien défini lorsque les x_i sont distinctes deux à deux.

(19)

Exercice 16   Pourquoi demande-t-on , …, , dans (19)? Pour répondre à cette question, imaginez que µ′_n=µ_n, …, µ′₂=µ₂ dans (19), et demandez-vous si votre compilateur produit effectivement du code correspondant à la spécification.

Exercice 19   Pourquoi demande-t-on , …, dans les prémisses de (19)?

Exercice 20   Rien n’empêche les variables x₁, …, x_n d’être non distinctes. Si c’est le cas, la notation n’a aucun sens. Réparez la règle (19) pour tenir compte de ce fait.

Passons aux opérations unaires. La négation effectue son calcul modulo 2³².

(20)

(21)

(22)

(23)

(24)

Exercice 25   Pourquoi ?

(25)

7  Quelle est la sémantique des exceptions?

Donnons d’abord une description intuitive de ce que font les instructions throw et try…catch…finally.

D’abord, try c évalue la commande c, dans la portée des handlers d’exception décrits par les clauses catch et la clause finally éventuelle. Si, à l’intérieur de cette portée, une exception est lancée, par une instruction throw exc (val), l’exécution du code se poursuit dans le handler correspondant: soit le code qui suit une des clauses catch (exc x) suivant le bloc c (avec le même nom d’exception exc; on dit que l’exception est rattrapée par cette clause), en stockant la valeur val de l’exception dans la variable locale x, soit une des clauses venant d’un handler d’exception antérieur.

À noter que si C--, comme C, est un langage à liaison lexicale, c’est-à-dire que la valeur de toute variable est déterminée par l’endroit, textuel, où on l’utilise, les portées des handlers d’exception est dynamique. Il est impossible de savoir vers quel handler d’exception (quelle clause catch, quel(s) code(s) de clause finally) l’exécution va se brancher lorsqu’une instruction throw exc (val) est exécutée. Ceci est déterminé par la liste active à ce moment-là de l’exécution du programme. C’est bien entendu voulu.

S’il existe une clause finally c′, alors le code c′ sera exécuté chaque fois que l’on sort de la portée du handler d’exception. C’est le cas lorsque c ne lance aucune exception (on dit que c termine normalement), lorsque c lance une exception rattrapée, ou bien lorsque c lance une exception non rattrapée par le handler courant. Le flot d’exécution du programme n’est pas modifié (sauf si c′ lance lui-même une exception!): si l’on passe par le bloc finally c′ à cause d’une exception non rattrapée, cette exception sera relancée à la fin de l’exécution de c′; aucune exception n’est relancée dans les autres cas. Pour mieux comprendre, vous pouvez exécuter les programmes exc1, exc2, exc3 dans le répertoire d’exemples, avec différents arguments en entrée (essayez 0, 1, 2, −1 notamment).

Il existe dans la littérature essentiellement deux styles de sémantiques pour décrire l’effet des exceptions.

Le premier consiste à faire comme si une exception lancée était juste une autre forme de résultat. Partant d’un environnement ρ, une commande peut donc s’évaluer soit en un environnement ρ′ après terminaison normale, soit en un paquet d’exception, à savoir un couple formé d’un nom et d’une valeur d’exception, qui a été lancée mais (pas encore) rattrapée. On développe une telle sémantique, dite directe, en section 7.1. Ceci a l’avantage de la simplicité (apparente). C’est le style employé par exemple dans la sémantique de Standard ML, par Harper, Tofte, et Milner.

Le second style consiste à évaluer toute commande c non seulement relativement à un environnement ρ avant son exécution, mais aussi relativement au code κ qu’il faudra exécuter une fois l’exécution de c terminée. Le code κ est la continuation. Un tel style a été inventée dans les années 1960, précisément pour donner une sémantique aux exceptions, aux goto, et autres joyeusetés du même style, dans le cadre de la sémantique du langage Algol 60. Cette sémantique, décrite en section 7.2, et qui part d’une idée a priori plus exotique, a l’avantage d’être plus souple, au sens où ce style permet de décrire uniformément plusieurs constructions de flôt de contrôle. De plus, si l’on identifie κ à l’adresse du code compilé qu’il faudra exécuter une fois c exécuté, on pourra observer que ce style de sémantique est en fait plus proche de ce que l’on implémente in fine en assembleur.

Au lieu de traiter de tout le langage C--, par souci de simplicité et de lisibilité, on traitera d’un langage réduit qui ne dispose que des constructions d’exception, de la séquence, et de l’appel de procédure. On laissera en exercice au lecteur le soin d’enrichir la sémantique des autres constructions du langage, en s’inspirant par exemple de la section 6. On ne considérera d’autre part aucun effet de bord, ce qui nous permettra de nous passer de la mémoire, et de revenir à une sémantique à environnement, proche de celle de la section 6.1.

Voici donc la syntaxe des commandes que nous considérons. On suppose donnée une grammaire d’expressions fixée, aucune n’ayant d’effet de bord (x+y OK, x=e non, call f (x) non plus). On peut toujours s’y ramener, par exemple en remplaçant l’expression call f (x) + y par z+y, juste après un appel de fonction z=call f (x), où z est une variable fraîche. Une autre différence est que les retours de fonction return x peuvent être situés au milieu du corps des fonctions. Exc parcourt l’ensemble des noms d’exceptions — en C--, ce sont juste des chaînes de caractères.

Ici, un programme π sera une fonction de domaine fini qui à des noms de fonction f associe un couple (l, c), où l est une liste de variables distinctes deux à deux (les paramètres formels de la fonction f), et c est une instruction (le corps de la fonction). On n’aura plus besoin de la troisième composante e, puisque return est maintenant une instruction comme les autres.

7.1  Sémantique des exceptions en style direct

Un paquet d’exception est un triplet (ρ, exc, V) formé d’un environnement ρ, d’un nom exc d’exception et d’une valeur V. Un paquet de retour est un triplet (ρ, *, V), où ρ est un environnement, * est un symbole différent de tous les noms d’exception, et V est une valeur. (Ceci sert à représenter l’effet d’une instruction return, qui en un sens est un lancement d’exception.) Un paquet est soit un paquet d’exception soit un paquet de retour. Un état st est soit un environnement ρ, soit un paquet.

L’affectation simple réussit toujours:

où ici comme dans la suite, ρ désigne n’importe quel environnement (mais pas un paquet!). C’est juste la règle (3), inchangée. Contrairement à ce qui se passait en section 6, ce ne sera pas la seule règle qui s’applique sur une affectation (l’autre est (29), plus bas).

Passons directement aux return et aux throw. Ces instructions retournent directement le paquet correspondant.

(26)

(27)

Pour la séquence, on aimerait écrire quelque chose de très similaire à (5):

(28)

La différence est qu’ici, les états intermédiaire st′ et final st″ ne sont pas garantis être des environnements, comme dans (5). Ils pourraient être des paquets, signifiant qu’une exception a été lancée lors de l’exécution de c₁ ou de c₂. Cependant, la règle ne s’applique que si l’on évalue c₁;c₂ en partant d’un environnement ρ, pas d’un paquet.

Lorsque l’on cherche à évaluer une commande c en partant d’un paquet, pas d’un environnement, c’est-à-dire que l’on a auparavant lancé une exception, ou déclenché une instruction return, alors c ne sera jamais exécutée. Par exemple, return  y; c n’exécutera jamais c. On a besoin pour ceci d’une règle exprimant qu’un paquet passe inchangé à travers toute commande:

(29)

La notation E ci-dessus dénote soit un nom d’exception Exc, soit *.

On s’attend alors que le corps d’une fonction appelée retourne soit un paquet de retour (ρ, *, V), dénotant un retour normal, soit un paquet d’exception (ρ, Exc, V). Le premier cas est traité par la règle:

(30)

À noter que l’environnement ρ′ présent dans le paquet de retour (en prémisse) est tout simplement jeté: on n’en voit plus trace dans la conclusion de la règle ci-dessus. C’est parce que ρ′ représente les valeurs des variables locales à la fonction appelée f, qui n’ont plus lieu d’être considérées lors du retour à l’appelant.

Le second cas est traité par la deuxième règle:

(31)

De même, ici, ρ′ est jeté, et l’on forme un nouveau paquet d’exception avec l’environnement ρ de l’appelant.

Le cœur de la nouvelle sémantique est la définition de throw. On laisse le plaisir au lecteur de comprendre par lui-même ce que signifient ces règles intuitivement.

(32)

(33)

(34)

Ici E′ est soit une exception soit *.

(35)

On utilise ici un jugement auxiliaire , où [catch (Exc_i x_i) c_i]_{1≤ i≤ n} finally c′ n’est, à proprement parler, pas une commande. De plus, on trouve à gauche du symbole un paquet d’exception ρ′, Exc, V et non un environnement.

(36)

(37)

(38)

(39)

7.2  Sémantique à continuations

L’idée de la sémantique à continuations est de dériver des jugements de la forme exprimant que c peut s’exécuter de sorte à ce que, lorsque son exécution termine, il ne restera plus qu’à exécuter la suite d’instructions décrites dans la continuation κ, laquelle retourne une réponse A. Cette réponse peut être un environnement final, par exemple. En réalité, une réponse peut être n’importe quel élémént d’un ensemble fixé a priori, qui importe peu.

Formellement, une continuation κ sera juste une fonction qui à chaque état st associe une réponse A: dans le jugement ci-dessus, on trouve la réponse finale A en appliquant κ à l’environnement ρ′ obtenu à la fin de l’exécution de c. (Si c ne lance pas d’exception.) En général, nous ne supposerons pas que la continuation est déterministe, et considérerons κ comme une relation binaire entre états de fin st′ et réponses A. On notera st′  κ  A si (st′, A) est dans κ.

L’affectation simple est donc décrite par la règle:

(40)

Les instructions return et throw ont aussi une description simple:

(41)

(42)

Pour la séquence, l’idée est qu’évaluer c₁;c₂ dans la continuation κ, c’est évaluer juste c₁ dans la continuation qui calcule d’abord c₂ puis appelle κ. Notons, pour toute commande c, et toute continuation κ, la relation reliant st à A si et seulement si:

• soit st est un environnement ρ et est dérivable,
• soit st est un paquet et st  κ  A.

On écrit donc:

(43)

Un petit truc: la prémisse se lit, intuititivement, “partant de c₁, faire c₁ puis, partant de l’environnement ainsi obtenu, faire c₂, puis appliquer κ, obtenant la réponse A”. Une continuation comme , en pratique, est juste une façon de représenter un saut (jmp en assembleur) à la fin de l’exécution de c₁ vers un morceau de code qui exécute c₂ (puis saute vers le morceau de code dont κ est une abstraction mathématique).

Là où en section 7.1 nous avions besoin de deux règles pour décrire la sémantique de l’appel de fonctions, nous n’avons plus besoin que d’une règle. On note la relation reliant f (x₁, …, x_n) à g (x₁, …, x_n) lorsque x₁, …, x_n varient dans leur domaine naturel, et P (x₁, …, x_n) est vrai.

(44)

L’idée est que, pour exécuter l’appel de fonction, il suffit d’exécuter son corps c. Si l’on finit par exécuter une instruction return, on continuera le calcul en invoquant la continuation κ sur l’environnement ρ [x:=V], poursuivant ainsi le calcul. Si c finit par lancer une exception, c’est κ_exc qui prendra le relais pour la suite du calcul, laquelle remplace l’environnement ρ′ de la fonction appelée par l’environnement ρ de la fonction appelante.

Exercice 32   Que se passe-t-il si l’exécution de c termine sans passer ni par un return ni par un throw, c’est-à-dire si l’on cherche à appliquer à un environnement? Comparer avec les règles (30) et (31) d’appel de fonction en style direct.

Les sémantiques à continuations ont été inventées dans les années 1960 pour donner une définition des mécanismes de goto et d’exceptions dans le langage Algol 60. Voyons comment ça se passe. Notons la continuation κ restreinte aux états qui sont des environnements ρ, et κ_|Paq la restriction de κ aux paquets, c’est-à-dire la relation reliant tout paquet (E, V) à tout A tel que (E, V)  κ  A, mais ne reliant aucun environnement ρ à aucune valeur. Finalement, on note la relation κ′ union tous les couples st, A tels que st  κ  A et st n’est pas dans le domaine de κ′.

(45)

Exercice 33   Démontrer que les deux sémantiques, directe et par continuations, sont équivalents, au sens où:

• si est dérivable dans la sémantique directe, alors pour toute continuation κ et toute réponse A, est dérivable dans la sémantique par continuations, dès que st  κ  A;
• réciproquement, si est dérivable dans la sémantique par continuations, alors il existe un état st tel que soit dérivable dans la sémantique directe, et st  κ  A.

En particulier, si l’on prend comme domaine de réponses l’ensemble des états, et κ la relation identité, en déduire que est dérivable dans la sémantique directe si et seulement si est dérivable dans la sémantique à continuations.

Si l’on prend comme domaine de réponses l’ensemble des booléens (vrai, faux), et si l’on contraint les continuations κ à être des fonctions partielles (pour tout st, il existe au plus une réponse A telle que st κ A) alors on peut penser aux continuations comme à des tests, ou bien des prédicats. Le jugement se lit “partant de ρ, l’exécution de c peut terminer dans un état vérifiant le prédicat κ”. Les règles de la sémantique à continuations s’interprètent alors comme un calcul connu sous le nom de calcul des “weakest preconditions”, dû à E.W. Dijkstra. Les notations traditionnelles pour ce dernier calcul sont un peu différentes. La “weakest precondition” wp (c) (κ) est par définition le prédicat qui envoie tout état st vers κ (st) si st est un paquet, et si st est un environnement ρ, l’envoie vers vrai si et seulement si est dérivable dans la sémantique à continuations.

Exercice 34   Démontrer que, si κ est une fonction partielle, alors la relation qui à ρ associe A si et seulement si est déricable dans la sémantique à continuations est elle aussi une fonction partielle.

Exercice 36   Démontrer que la sémantique par continuations est monotone en la continuation: si est dérivable, alors pour toute continuation κ⁺ telle que , alors est aussi dérivable.

Exercice 37   Notre construction de la sémantique par continuations est incomplètement spécifiée. Par exemple, la règle (43) utilise dans sa prémisse une continuation , laquelle n’est définie que lorsque la relation est déjà définie. Or c’est précisément la relation que l’on cherche à définir. Une solution classique dans la littérature est de considérer que de telles règles sont des règles à une infinité de prémisses. Ceci se voit mieux si on réécrit la règle (43) sous la forme:

Mais ceci n’a aucun sens. En revanche, la règle

(46)

qui est paramétrée par une continuation κ′, a juste une infinité de prémisses . En utilisant l’exercice 36, justifier pourquoi (46) et (43) sont en fait équivalentes.

En utilisant des règles du style de (46), que vous écrirez, on appellera ensemble des jugements dérivables le plus petit ensemble de jugements stable par les règles de déduction, c’est-à-dire tel que pour toute règle, si toutes ses prémisses sont dans l’ensemble, alors sa conclusion aussi.

8  Quelques conseils utiles

8.1  Quand commencer

Tout de suite!

D’abord, il vaut mieux se mettre à faire le projet de programmation le plus tôt possible! J’estime que vous pouvez faire un compilateur C--, sans les exceptions, en deux à trois semaines, à condition de ne pas tarder à s’y mettre. La gestion des exceptions (throw, try…catch…finally) est quelque chose d’un peu compliqué, qu’il vaut mieux aborder avec méthode.

8.2  La débrouille

Un peu de débrouille ne fait pas de mal… Si vous ne voyez pas bien comment compiler quelque chose que vous sauriez écrire en C, écrivez-le en C, appelez gcc -S pour produire le code assembleur correspondant, et déduisez-en quel code assembleur gcc fabrique. Par exemple, si vous ne savez pas comment calculer un quotient de deux entiers, créez un ficher /tmp/a.c, contenant:

et tapez gcc -S a.c dans le répertoire /tmp. Vous obtiendrez un fichier /tmp/a.s de la forme:

dont vous pourrez déduire que le quotient se calcule par une combinaison des instructions cltd et idivl: voir la section 9. (C’est l’instruction la plus compliquée à compiler, hormis les exceptions.)

8.3  Le style de programmation

On peut programmer en Caml en différents styles. Par exemple, une factorielle en style fonctionnel s’écrira:

La même, en style impératif, pourra s’écrire:

On peut encore l’écrire en style objet, soit grâce aux caractéristiques objet d’OCaml, soit en se fabriquant des classes à la main.

Tous les styles sont bons, et l’on peut coder ce que l’on veut dans chaque style. Chacun a ses préférences. Cependant, il est bon de savoir que le compilateur que vous avez à écrire s’écrit probablement le plus naturellement du monde dans un style fonctionnel.

Par exemple, j’ai défini dans ma version du compilateur une fonction compile_expr pour compiler les expressions, de type loc_expr, et une fonction compile_code pour compiler les instructions et les programmes, de type loc_code, les deux fonctions s’appelant récursivement, et la seconde fonction appelant naturellement la première.

Au passage, le type de ma fonction compile_expr est:

out_channel -> string -> (string * int) list -> int -> loc_expr -> unit

L’idée est que l’appel compile_expr out f env stack e, compile le code assembleur qui évalue l’expression e et retourne sa valeur dans %eax, où:

• out est le descripteur de fichier sur lequel imprimer les instructions assembleur;
• f est le nom de la fonction C que le compilateur est en train de compiler (ceci sert à appeler genlab pour fabriquer des labels frais);
• env est une liste de couples (nom de variable, offset), disant pour chaque variable locale à quel offset par rapport à %ebp il faut la chercher;
• stack est un entier n décrivant la profondeur de la pile courante depuis %ebp (autrement dit, on a l’invariant %esp=%ebp−n).

Il est quand même pratique d’utiliser quelques références (ref, !, :=), sans en abuser. Dans mon compilateur, je n’ai qu’une seule référence, qui est de plus une variable globale:

let strings = ref ([] : (string * string) list);;

et qui sert à associer à chaque constante chaîne (par exemple, "r" dans le fichier cat.c, mais aussi les noms d’exception comme Trouve dans le fichier exc1.c) le nom d’un label où cette chaîne sera stockée. Regardez bien, par exemple, où la chaîne "r" est décrite dans le fichier assembleur cat.s. Si vous ne comprenez pas tout de suite à quoi peut servir la variable globale strings ci-dessus, vous le comprendrez en écrivant le compilateur…

8.4  Quelques trucs sur les exceptions

En ce qui concerne les exceptions, leur sémantique, décrite dans un cadre plus simple que celui de C--, est donnée en section 7. C’est un peu compliqué à compiler, et la clause finally est particulièrement retorse. (Vous comprendrez pourquoi en la compilant…) Néanmoins, et même s’il existe de nombreuses façons de le faire, vous pouvez vous inspirer de ce que mon compilateur fait. Ma version du compilateur mcc a le bon goût d’ajouter plein de commentaires dans l’assembleur produit aux alentours des throw et des try…catch…finally pour expliquer ce que le code qu’il produit est censé faire, et sur quelles conventions (usage des registres %ebx, %ecx, ce qu’il y a sur la pile, comment la pile __exception_handler des handlers d’exception courants est gérée et ce qu’elle contient, etc.) Par exemple, le fichier exc1.s, qui est un exemple très simple d’utilisation des exceptions, sans clause finally, que voici:

se compile dans l’assembleur suivant, abondamment commenté quant à la gestion des exceptions:

8.5  Les fichiers ML fournis

Dans la distribution mcc qui vous est fournie, il ne manque que le fichier compile.ml, que vous devrez écrire. Certains pensent qu’il faut qu’ils lisent les fichiers ML fournis pour comprendre comment ça marche. En principe, je favorise la curiosité: si vous pouvez apprendre quelque chose en le faisant, faites-le!

Mais, en l’occurrence, ceci ne vous servira pas à grand-chose. Le code ML est probablement trop complexe, et utilise probablement des choses que vous ne connaissez pas (ocamllex, ocamlyacc), pour que vous puissiez en tirer vraiment profit.

Lire les fichiers ML fournis est donc, en fait, essentiellement une perte de temps dans le cadre du projet.

En revanche, il peut être utile de comprendre quel genre de syntaxe abstraite est produite par mcc à partir d’un fichier source C-- donné. Je rappelle que cette syntaxe abstraite est de type Cparse.var_declaration list, le type du deuxième argument de la fonction compile que vous devez écrire.

Une façon de faire est de réserver une variable globale Caml, disons ast (pour “abstract syntax tree”), de stocker l’arbre de syntaxe fourni à compile dedans, et de demander à afficher le contenu de ast après exécution, ce qui se fait bien sous le toplevel.

Pour utiliser les fonctions du compilateur mcc sous le toplevel Caml, lancer ocaml, et taper:

#use "top.ml";;

Le fichier top.ml est en gros le compilateur mcc en réduction. Si l’on écrit un fichier compile.ml bidon:

puis que l’on tape make pour recompiler le tout, enfin que l’on tape #use "top.ml";; sous le toplevel Caml (ce qui charge tous les fichiers compilés, y compris compile.ml), on obtiendra une fonction teste de type string -> unit.

Donnons-lui à traiter le fichier cat.c, par exemple. Contrairement au compilateur final mcc, le programme que nous venons de charger sous le toplevel Caml ne sait pas appeler le préprocesseur C tout seul. Appelons-le donc pour fabriquer le fichier préprocessé cat1.c, en tapant la ligne suivante sous le shell (note: le faire dans une autre fenêtre, par exemple):

cpp -DMCC cat.c >cat1.c

Sous le toplevel Caml avec top.ml chargé, on écrit:

teste "cat1.c";;

puis l’on demande la valeur de la variable ast, en tapant:

ast;;

ce qui donne en l’occurrence:

En général, le fichier top.ml permet de tester son compilateur sous le toplevel Caml. Mais l’insertion de Printf.printf judicieux dans le code du compilateur peut s’avérer être une technique plus efficace de debugging…

9  Guide de référence rapide de l’assembleur x86

Les registres: %eax %ebx %ecx %edx %esi %edi %ebp %esp.
Ils contiennent tous un entier de 32 bits (4 octets), qui peut aussi être vu comme une adresse. Le registre %esp est spécial, et pointe sur le sommet de pile; il est modifié par les instructions pushl, popl, call, ret notamment.

Il y a aussi d’autres registres que l’on ne peut pas manipuler directement. (L’instruction info registers sous gdb ou ddd vous les montrera.) Le plus important est eip, le compteur de programme: il contient en permanence l’adresse de la prochaine instruction à exécuter. 1em

• addl <source>, <dest>.......<dest>= <dest>+ <source> (addition)
  Ex: addl $1, %eax ajoute 1 au registre %eax.
  Ex: addl $4, %esp dépile un élément de 4 octets de la pile.
  Ex: addl %eax, (%ebx, %edi, 4) ajoute le contenu de %eax à la case mémoire à l’adresse %ebx + 4*%edi. (Imaginez que %ebx est l’adresse de début d’un tableau a, %edi est un index i, ceci stocke %eax dans a[i].)
  
• andl <source>, <dest>.......<dest>= <dest>& <source> (et bit à bit)
• call <dest>.......appel de procédure à l’adresse <dest>
  Équivalent à pushl $a, où a est l’adresse juste après l’instruction call (l’adresse de retour), suivi de jmp <dest>.
  Ex: call printf appelle la fonction printf.
  Ex: call *%eax (appel indirect) appelle la fonction dont l’adresse est dans le registre %eax. Noter qu’il y a une irrégularité dans la syntaxe, on écrit call *%eax et non call (%eax).
  
• cltd .......conversion 32 bits -> 64 bits
  Convertit le nombre 32 bits dans %eax en un nombre sur 64 bits stocké à cheval entre %edx et %eax.
  Note: %eax n’est pas modifié; %edx est mis à 0 si %eax est positif ou nul, à −1 sinon.
  À utiliser notamment avant l’instruction idivl.
  
• cmp <source>, <dest>.......comparaison
  Compare les valeurs de <source> et <dest>. Utile juste avant un saut conditionnel (je, jge, etc.). À noter que la comparaison est faite dans le sens inverse de celui qu’on attendrait. Par exemple, cmp <source>, <dest> suivi d’un jge (“jump if greater than or equal to”), va effectuer le saut si <dest>≥<source>: on compare <dest> à <source>, et non le contraire.
  
• idivl <dest>.......division entière et reste
  Divise le nombre 64 bits stocké en %edx et %eax (cf. cltd) par le nombre 32 bits <dest>. Retourne le quotient en %eax, le reste en %edx.
  
• imull <source>, <dest>.......multiplie <dest> par <source>, résultat dans <dest>
• jmp <dest>.......saut inconditionnel: eip=<dest>
• je <dest>.......saut conditionnel
  Saute à l’adresse <dest> si la comparaison précédente (cf. cmp) a conclu que <dest>=<source>, continue avec le flot normal du programme sinon.
  
• jg <dest>.......saut conditionnel
  Saute à l’adresse <dest> si la comparaison précédente (cf. cmp) a conclu que <dest>><source>, continue avec le flot normal du programme sinon.
  
• jge <dest>.......saut conditionnel
  Saute à l’adresse <dest> si la comparaison précédente (cf. cmp) a conclu que <dest>≥<source>, continue avec le flot normal du programme sinon.
  
• jl <dest>.......saut conditionnel
  Saute à l’adresse <dest> si la comparaison précédente (cf. cmp) a conclu que <dest><<source>, continue avec le flot normal du programme sinon.
  
• jle <dest>.......saut conditionnel
  Saute à l’adresse <dest> si la comparaison précédente (cf. cmp) a conclu que <dest>≤<source>, continue avec le flot normal du programme sinon.
  
• leal <source>, <dest>.......chargement d’adresse effective
  Au lieu de charger le contenu de <source> dans <dest>, charge l’adresse de <source>.
  Équivalent C: <dest>=&<source>.
  
• movl <source>, <dest>.......transfert
  Met le contenu de <source> dans <dest>. Équivalent C: <dest>=<source>.
  Ex: movl %esp, %ebp sauvegarde le pointeur de pile %esp dans le registre %ebp.
  Ex: movl %eax, 12(%ebp) stocke le contenu de %eax dans les quatre octets commençant à %ebp+12.
  Ex: movl (%ebx, %edi, 4), %eax lit le contenu de la case mémoire à l’adresse %ebx + 4*%edi, et le met dans %eax. (Imaginez que %ebx est l’adresse de début d’un tableau a, %edi est un index i, ceci stocke a[i] dans %eax.)
  
• negl <dest>.......<dest>=-<dest>(opposé)
• notl <dest>.......<dest>=~<dest>(non bit à bit)
• orl <source>, <dest>.......<dest>= <dest>| <source> (ou bit à bit)
• popl <dest>.......dépilement
  Dépile un entier 32 bits de la pile et le stocke en <dest>.
  Équivalent à movl (%esp),<dest> suivi de addl $4, %esp.
  Ex: popl %ebp récupère une ancienne valeur de %ebp sauvegardée sur la pile, typiquement, par pushl.
  
• pushl <source>.......empilement
  Empile l’entier 32 bits <source> au sommet de la pile.
  Équivalent à movl <source>, -4(%esp) suivi de subl $4, %esp.
  Ex: pushl %ebp sauvegarde la valeur de %ebp, qui sera rechargée plus tard par popl.
  Ex: pushl <source> permet aussi d’empiler les arguments successifs d’une fonction. (Note: pour appeler une fonction C comme printf par exemple, il faut empiler les arguments en commençant par celui de droite.)
  
• ret .......retour de procédure
  Dépile une adresse de retour a, et s’y branche. Lorsque la pile est remise dans l’état à l’entrée d’une procédure f, ceci a pour effet de retourner de f et de continuer l’exécution de la procédure appelante.
  Équivalent à popl eip... si cette instruction existait (il n’y a pas de mode d’adressage permettant de manipuler eip directement).
  
• subl <source>, <dest>.......<dest>= <dest>- <source>(soustraction)
  Ex: subl $1, %eax retire 1 du registre %eax.
  Ex: subl $4, %esp alloue de la place pour un nouvel élément de 4 octets dans la pile.
  
• xorl <source>, <dest>.......<dest>= <dest>^ <source> (ou exclusif bit à bit)

10  Un dernier mot

Bon courage, et travaillez bien! N’hésitez pas à nous contacter, goubault@lsv.ens-cachan.fr ou bardin@lsv.ens-cachan.fr

This document was translated from L^AT_EX by H^EV^EA.