Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

École Polytechnique INF564 : Compilation examen 2018 (X2015) Jean-Christophe Fi

École Polytechnique INF564 : Compilation examen 2018 (X2015) Jean-Christophe Filliâtre 19 mars 2018 Les notes de cours manuscrites ou reprographiées sont les seuls documents autorisés. L’épreuve dure 3 heures. Dans tout ce sujet, on considère un petit langage de programmation avec des entiers et des paires. Un programme est composé d’un ensemble de fonctions mutuellement récursives et d’une expression principale. Chaque fonction a un unique argument, toujours appelé x. Voici un programme dans ce langage, calculant la factorielle de 10 : def mult(x) = ifzero fst(x) then 0 else add((snd(x), mult((add((fst(x),-1)), snd(x))))) def fact(x) = ifzero x then 1 else mult((x, fact(add((x, -1))))) fact(10) Ce langage est muni d’une sémantique d’appel par valeur. Il y a trois fonctions prédéﬁnies : — add : attend une paire d’entiers en argument et renvoie leur somme ; — fst : attend une paire en argument et renvoie sa première composante ; — snd : attend une paire en argument et renvoie sa seconde composante. La syntaxe abstraite de ce langage est donnée ﬁgure 1. Les diﬀérentes parties du sujet sont indépendantes. Néanmoins, elles nécessitent d’avoir bien compris la sémantique de ce langage décrite dans la partie 1. 1 Sémantique On munit ce langage d’une sémantique opérationnelle à petits pas de la forme e →e′ où e et e′ sont deux expressions. Les règles de la sémantique opérationnelle sont données ﬁgure 2. La notation e[x ←v] désigne l’expression obtenue en remplaçant dans e toute occurrence de x par v. On prendra le temps de bien comprendre les règles de la sémantique. L’évaluation d’une expression e est une séquence de réductions partant de e et conduisant à une valeur, c’est-à-dire e →e1 →e2 · · · →v. L’évaluation d’un programme est l’évaluation de son expression principale. 1 e ::= expression | n constante entière n ∈Z | x variable | (e, e) construction d’une paire | f(e) appel de fonction | ifzero e then e else e conditionnelle d ::= déﬁnition de fonction | def f(x) = e p ::= programme | d . . . d e Figure 1 – Syntaxe abstraite. v ::= valeur | n constante entière | (v, v) paire e1 →e′ 1 (e1, e2) →(e′ 1, e2) e2 →e′ 2 (v1, e2) →(v1, e′ 2) e1 →e′ 1 f(e1) →f(e′ 1) def f(x) = e f(v) →e[x ←v] n = n1 + n2 add((n1, n2)) →n fst((v1, v2)) →v1 snd((v1, v2)) →v2 e1 →e′ 1 ifzero e1 then e2 else e3 →ifzero e′ 1 then e2 else e3 ifzero 0 then e2 else e3 →e2 v ̸= 0 ifzero v then e2 else e3 →e3 Figure 2 – Sémantique opérationnelle à petits pas. 2 Question 1 Donner l’évaluation du programme def f(x) = add((x, x)) f(add((add((3,5)), add((5,8)))) Correction : f(add((add((3,5)), add((5,8)))) -> f(add((8 , add((5,8)))) -> f(add((8 , 13 ))) -> f(21) -> add((21, 21)) -> 42 Question 2 Donner un programme qui n’a pas d’évaluation. Correction : Le plus simple est un programme réduit à l’expression x. Listes. On peut facilement représenter une liste contenant n valeurs x1, . . . , xn avec des paires, sous la forme (x1, (x2, . . . , (xn, 0) . . . )) c’est-à-dire exactement une paire pour chaque élément de la liste et l’entier 0 pour représenter la ﬁn de la liste. On peut alors déﬁnir des fonctions récursives sur de telles listes. Voici par exemple une fonction len qui renvoie la longueur d’une liste et une fonction rev qui renverse une liste : def len(x) = ifzero x then 0 else add((1, len(snd(x)))) def rev_aux(x) = ifzero fst(x) then snd(x) else rev_aux((snd(fst(x)), (fst(fst(x)), snd(x)))) def rev(x) = rev_aux((x, 0)) Question 3 Déﬁnir une fonction fib telle que, pour tout entier n ≥1, l’évaluation de fib(n) renvoie la liste des n+1 premiers entiers de la suite de Fibonacci, dans l’ordre croissant. On rappelle que la suite de Fibonacci est déﬁnie par    F0 = 0 F1 = 1 Fn+2 = Fn + Fn+1 pour n ≥0 La complexité, déﬁnie comme le nombre total de petits pas, doit être O(n). Correction : On généralise avec une fonction fib_aux qui prend en argument la paire (k, l) où k est le nombre de nombres de Fibonacci restant à calculer et l la liste des entiers Fn−k, Fn−k−1, . . . , F1, F0. 3 def fib_aux(x) = ifzero fst(x) then rev(snd(x)) else fib_aux((add((fst(x), -1)), (add((fst(snd(x)), fst(snd(snd(x))))), snd(x)))) Il suﬃt alors de l’appeler avec n −1 et la liste à deux éléments F1, F0. def fib(x) = fib_aux((add((x, -1)), (1, (0, 0)))) 2 Interprète On souhaite réaliser un interprète de notre langage, c’est-à-dire un programme qui reçoit en argument la syntaxe abstraite d’un programme de notre langage et qui — aﬃche la valeur à laquelle aboutit l’évaluation de ce programme, le cas échéant ; — signale une erreur si la séquence de réductions aboutit à une expression qui n’est pas une valeur et qui ne se réduit pas ; — ne termine pas sinon. Question 4 Donner les diﬀérents types, structures de données et fonctions/méthodes composant cet interprète, en OCaml ou en Java (au choix). On ne demande pas en revanche d’écrire le code de l’interprète. Correction : On choisit par exemple OCaml. La syntaxe abstraite des expressions est immédiate : type expr = | Ecst of int | Evar (* x *) | Epair of expr * expr | Eapp of string * expr | Eifz of expr * expr * expr type defn = string * expr type program = defn list * expr On se donne un type pour les valeurs : type value = | Vint of int | Vpair of value * value Note : on aurait pu utiliser le type expr pour cela, vu qu’il contient déjà toutes les valeurs possibles. On se donne une table de hachage globales defns pour les fonctions. On y met les fonctions prédéﬁnies aussi bien que les fonctions du programme. On lui donne le type suivant : defns: (string, value -> value) Hashtbl.t et on la remplit avec les fonctions prédéﬁnies : 4 compile(n) = movq $n, %rax compile(x) = movq %rdi, %rax compile((e1, e2)) = . . . compile(f(e1)) = . . . compile(ifzero e1 then e2 else e3) = . . . compile(def f(x) = e) = f : compile(e) ret Figure 3 – Compilation vers x86-64. let () = Hashtbl.add defns "add" (function Vpair (Vint n1, Vint n2) -> Vint (n1 + n2) | _ -> error "bad argument for add"); ... On déﬁnit ensuite trois fonctions pour l’interprète proprement dit : val of_value: value -> expr val subst: expr -> expr -> expr val expr: expr -> value Pour évaluer un programme, on ajoute ses fonctions à la table de hachage, ainsi : let defn e v = expr (subst e (of_value v)) in List.iter (fun (f, e) -> Hashtbl.add defns f (defn e)) dl; puis on évalue son expression principale avec expr. 3 Compilation vers x86-64 On se propose maintenant de compiler notre langage vers l’assembleur x86-64. On adopte le schéma de compilation suivant : — une valeur est soit un entier signé 64 bits, soit un pointeur vers un bloc de 16 octets sur le tas contenant les deux composantes d’une paire (juxtaposées) ; — la valeur d’une expression est calculée dans %rax ; — le valeur de x, le cas échéant, est contenue dans %rdi. La ﬁgure 3 contient une partie du compilateur. Une expression e est compilée par un appel à compile(e). Un aide-mémoire x86-64 est donné en annexe. Question 5 Donner le code du compilateur pour — la construction de la paire (e1, e2) ; — la conditionnelle ifzero e1 then e2 else e3 ; — l’application f(e1). 5 Correction : — la construction (e1, e2) : il faut penser à sauvegarder %rdi avant d’appeler malloc compile(e1) # la première composante est évaluée pushq %rax # et placée sur la pile compile(e2) # la seconde composante est évaluée pushq %rax # et placée sur la pile pushq %rdi # on sauvegarde %rdi movq $16, %rdi # on alloue 16 octets sur le tas call malloc popq %rdi # on restaure %rdi popq %rcx # on récupère la seconde composante movq %rcx, 8(%rax) # et on la stocke dans la paire popq %rcx # on récupère la première composante movq %rcx, (%rax) # et on la stocke dans la paire — la conditionnelle ifzero e1 then e2 else e3 : pas de diﬃculté ici compile(e1) testq %rax, %rax jz L2 compile(e3) jmp L1 L2:compile(e2) L1: où L1 et L2 sont deux étiquettes fraîches. — l’application f(e1) : là aussi il faut préserver %rdi qui est caller-save pushq %rdi # on sauvegarde %rdi compile(e1) # on évalue l’argument movq %rax, %rdi # et on le place dans %rdi call f # on fait l’appel popq %rdi # on restaure %rdi Question 6 Donner le code assembleur des fonctions prédéﬁnies fst, snd et add. Correction : fst: movq (%rdi), %rax ret snd: movq uploads/s3/ mars-18-correction.pdf