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. Question 1 Donner l’évaluation du programme def f(x) = add((x, x)) f(add((add((3,5)), add((5,8)))) 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 2 Donner un programme qui n’a pas d’évaluation. 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). 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. 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. 3 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. 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). Question 6 Donner le code assembleur des fonctions prédéﬁnies fst, snd et add. Question 7 Donner le code assembleur d’une fonction print_list qui reçoit en argument (dans %rdi) une valeur supposée être une liste d’entiers et aﬃche ses éléments dans l’ordre. On suppose l’existence d’une fonction print_int pour aﬃcher un entier, avec les conventions d’appel usuelles. Question 8 On aimerait pouvoir écrire une fonction assembleur print qui aﬃche n’importe quelle valeur supposée bien formée, par exemple sous la forme ((1, 2), ((3, 4), 0)) Ce n’est malheureusement pas possible, car il faudrait être capable de faire la diﬀérence entre un entier et un pointeur (vers une paire). Proposer une solution pour y remédier. 4 Analyse syntaxique On cherche maintenant à construire un analyseur syntaxique pour notre langage. On se donne la grammaire S → E E → int | x | ( E , E ) | ifzero E then E else E | ident ( E ) où S est l’axiome et où les terminaux sont int (une constante entière), x, (, ,, ), ifzero, then, else et ident (un identiﬁcateur autre que x, ifzero, then et else). 4 Γ ⊢n : int Γ = x : τ Γ ⊢x : τ Γ ⊢e1 : τ1 Γ ⊢e2 : τ2 Γ ⊢(e1, e2) : τ1 × τ2 f : τ1 →τ2 Γ ⊢e1 : τ1 Γ ⊢f(e1) : τ2 Γ ⊢e1 : int × int Γ ⊢add(e1) : int Γ ⊢e1 : τ1 × τ2 Γ ⊢fst(e1) : τ1 Γ ⊢e1 : τ1 × τ2 Γ ⊢snd(e1) : τ2 Γ ⊢e1 : τ1 Γ ⊢e2 : τ Γ ⊢e3 : τ Γ ⊢ifzero e1 then e2 else e3 : τ Figure 4 – Typage. Question 9 Montrer que cette grammaire est LR(0). Indication : on pourra construire l’automate déterministe directement ; il contient une vingtaine d’états. Question 10 Que peut-on en déduire quant à l’analyse de cette grammaire par un outil tel que cup ou menhir ? 5 Typage Dans cette partie, on va typer notre langage avec des types de la forme τ ::= type | int type d’un entier | τ × τ type d’une paire Un environnement de typage Γ est soit vide, soit réduit à x : τ. On note Γ ⊢e : τ le jugement « dans l’environnement Γ, l’expression e a le type τ ». On note f : τ1 →τ2 si la fonction f attend un argument de type τ1 et renvoie un résultat de type τ2. Les règles de typage des expressions sont données ﬁgure 4. Un programme est typable s’il existe un type pour chacune de ses fonctions de telle sorte que — si le type donné à f est τ1 →τ2 et def f(x) = e alors x : τ1 ⊢e : τ2 ; — l’expression principale est bien typée dans l’environnement vide. Question 11 Pour chacun des trois programmes suivants, indiquer s’il est typable. Si oui, donner un type à sa fonction. Sinon, justiﬁer qu’il n’est pas typable. 1. def oups(x) = oups(x) oups(0) 2. def len(x) = ifzero x then 0 else add((1, len(snd(x)))) len((1, (0, 0))) 3. def foo(x) = ifzero fst(x) then x else foo((fst(snd(x)), (snd(snd(x)), fst(x)))) foo((1,(2,0))) Sûreté du typage. Comme vu en cours, la sûreté du typage se déduit des résultats de progrès et de préservation, qui font l’objet des questions suivantes. Question 12 Montrer la propriété de progrès : si ⊢e : uploads/s3/ mars-18.pdf