Remerciez-le!

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

Mars 18 École Polytechnique INF Compilation examen X Jean- Christophe Filli? tre mars Les notes de cours manuscrites ou reprographiées sont les seuls documents autorisés L ? épreuve dure heures Dans tout ce sujet on considère un petit langage de programma

École Polytechnique INF Compilation examen X Jean- Christophe Filli? tre mars Les notes de cours manuscrites ou reprographiées sont les seuls documents autorisés L ? épreuve dure 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 def mult x ifzero fst x then else add snd x mult add fst x - snd x def fact x ifzero x then else mult x fact add x - fact 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 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 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 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 ? e ? e ? v L ? évaluation d ? un programme est l ? évaluation de son expression principale Question Donner l ? évaluation du programme def f x add x x f add add add Ce 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 def f x e dé ?nition de fonction p d d e programme Figure ?? Syntaxe abstraite v valeur n constante entière v v paire e ? e e e ? e e e ? e v e ? v e e ? e def f x e f e ? f e f v ? e x v n n n add n n ? n fst v v ? v snd v v ? v e ? e ifzero e then e else e ? ifzero e then e else e v ifzero then e else e ? e ifzero v then e else e ? e Figure ?? Sémantique opérationnelle à petits pas CQuestion Donner un programme qui n ? a pas d ? évaluation Listes On peut facilement représenter une