{"id":189,"date":"2022-01-26T15:53:19","date_gmt":"2022-01-26T15:53:19","guid":{"rendered":"https:\/\/9h15.net\/activ\/?p=189"},"modified":"2022-01-26T15:53:38","modified_gmt":"2022-01-26T15:53:38","slug":"programmation-logique-et-fonctionnelle-partie-a-2","status":"publish","type":"post","link":"https:\/\/9h15.net\/activ\/programmation-logique-et-fonctionnelle-partie-a-2\/","title":{"rendered":"Programmation logique et fonctionnelle &#8211; partie A"},"content":{"rendered":"<p><code>Par O. Bailleux, Ma\u00eetre de conf\u00e9rences HDR \u00e0 l'universit\u00e9 de Bourgogne.<\/code><\/p>\n<h1><a id=\"le-lambda-calcul\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Le lambda-calcul<\/h1>\n<p>Les activit\u00e9s <strong>#.dec<\/strong> (<strong>dec<\/strong> pour D\u00e9couverte) consistent \u00e0 \u00e9tudier des <strong>pr\u00e9sentations explicatives<\/strong> et \u00e0 traiter tous les <strong>exercices de d\u00e9couverte<\/strong> propos\u00e9s. Si vous ne r\u00e9pondez pas correctement \u00e0 un exercice de d\u00e9couverte, revenez en arri\u00e8re pour relire les explications et identifier la cause de votre erreur.<\/p>\n<p>Les activit\u00e9s <strong>#.ent<\/strong> (<strong>ent<\/strong> pour Entrainement) consistent \u00e0 traiter des <strong>exercices d&rsquo;entra\u00eenement<\/strong>. Vous devez d&rsquo;abord tenter de traiter ces exercices sans d\u00e9voiler d&rsquo;indice ni regarder la solution. Vous pouvez remonter dans le document pour relire certaines explications ou consulter les solutions des exercices de d\u00e9couverte ou d&rsquo;entra\u00eenement pr\u00e9c\u00e9demment trait\u00e9s.<\/p>\n<h2><a id=\"activit%C3%A9-de-d%C3%A9couverte-a-dec\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Activit\u00e9 de d\u00e9couverte A.dec<\/h2>\n<h3><a id=\"un-tr%C3%A8s-rapide-tour-d-horizon\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Un tr\u00e8s rapide tour d&rsquo;horizon<\/h3>\n<p>Le \\(\\lambda\\)-calcul est un langage rudimentaire permettant de r\u00e9aliser une forme de programmation non imp\u00e9rative appel\u00e9e <strong>programmation fonctionnelle<\/strong>.<\/p>\n<p>L&rsquo;ex\u00e9cution d&rsquo;un programme en \\(\\lambda\\)-calcul s&rsquo;effectue en appliquant des r\u00e8gles simples faisant appel \u00e0 des substitutions syntaxiques.<\/p>\n<p>Les donn\u00e9es et les programmes sont repr\u00e9sent\u00e9s par des \\(\\lambda\\)-termes constitu\u00e9 des \u00e9l\u00e9ments syntaxiques suivants :<\/p>\n<ul>\n<li>Les symboles \\(\\lambda\\) \\(.\\) \\(( )\\)<\/li>\n<li>des variables \\(a,b,c,&#8230;\\)<\/li>\n<\/ul>\n<p>Voici un exemple de programme et une donn\u00e9e \u00e0 laquelle il peut \u00eatre appliqu\u00e9 :<\/p>\n<p>\\[\\underbrace{(\\lambda p. \\lambda a. \\lambda b. pab)}_{\\text{programme }} \\underbrace{(\\lambda a. \\lambda b.a)}_{\\text{ donn\u00e9e}}<br \/>\n\\]<\/p>\n<p>Les \u00e9tapes d&rsquo;ex\u00e9cution de ce programme sont les suivantes :<\/p>\n<ol>\n<li>\\(\\lambda a. \\lambda b. (\\lambda a. \\lambda b.a)ab\\)<\/li>\n<li>\\(\\lambda a. \\lambda b. (\\lambda b.a)b\\)<\/li>\n<li>\\(\\lambda a. \\lambda b. a\\)<\/li>\n<\/ol>\n<p>Pour l&rsquo;instant, cette s\u00e9quence para\u00eet myst\u00e9rieuse. Nous verrons plus tard que les r\u00e8gles permettant de la r\u00e9aliser sont des substitutions, c&rsquo;est \u00e0 dire des &quot;copier coller&quot; qui remplacent certaines variables par des termes.<\/p>\n<p>Le \\(\\lambda\\)-calcul a la puissance d&rsquo;expression de la machine de Turing. Il permet de calculer les m\u00eames fonctions. C&rsquo;est un mod\u00e8le de <strong>calculateur universel<\/strong>.<\/p>\n<h3><a id=\"a-dec1-les-lambda-termes\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>A.dec1 : les lambda-termes<\/h3>\n<p>En \\(\\lambda\\)-calcul, les programmes et les donn\u00e9es sont repr\u00e9sent\u00e9s par des \\(\\lambda\\)-termes. Ces termes sont construits \u00e0 partir<\/p>\n<ul>\n<li>de <strong>variables<\/strong> (dans cet enseignement, on les d\u00e9signera par des lettres minuscules),<\/li>\n<li>des symboles \\(\\lambda\\), \\(.\\) et des parenth\u00e8ses \\(()\\).<\/li>\n<\/ul>\n<p>Un \\(\\lambda\\)-terme compl\u00e8tement parenth\u00e9s\u00e9 est :<\/p>\n<ul>\n<li>Soit une <strong>variable<\/strong> : \\(a\\), \\(b\\), \\(c\\),&#8230;<\/li>\n<li>Soit une <strong>abstraction<\/strong> \\((\\lambda x.T)\\), o\u00f9 \\(T\\) est une \\(\\lambda\\)-terme et \\(x\\) une variable.<\/li>\n<li>Soit une <strong>application<\/strong> \\((T U)\\), o\u00f9 \\(T\\) et \\(U\\) sont des termes.<\/li>\n<\/ul>\n<p>Voici quelques exemples de \\(\\lambda\\)-termes :<\/p>\n<ul>\n<li>\n<p>une application : \\((a b)\\)<\/p>\n<\/li>\n<li>\n<p>une abstraction : \\((\\lambda x . y)\\)<\/p>\n<\/li>\n<li>\n<p>une application compos\u00e9e de 2 abstractions :<\/p>\n<p>\\((\\overbrace{\\underbrace{(\\lambda x.a)}_{\\text{abstraction }} \\underbrace{(\\lambda y.y)}_{\\text{ abstraction}}}^{\\text{application}})\\)<\/p>\n<\/li>\n<\/ul>\n<h4><a id=\"exercice-de-d%C3%A9couverte-a-dec-x1\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Exercice de d\u00e9couverte A.dec.x1<\/h4>\n<p>Parmi les \u00e9critures suivantes, lesquelles sont des \\(\\lambda\\)-termes compl\u00e8tement parenth\u00e9s\u00e9s ?<\/p>\n<ol>\n<li>\\((a \\lambda a)\\)<\/li>\n<li>\\((a(\\lambda b.a))\\)<\/li>\n<li>\\((\\lambda x. (x \\lambda z))\\)<\/li>\n<li>\\((\\lambda x. (x (\\lambda z.a)))\\)<\/li>\n<\/ol>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Le 2 et le 4. Un \\(\\lambda\\) doit toujours \u00eatre suivi par une variable, elle-m\u00eame suivie d&rsquo;un point.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h3><a id=\"a-dec2-d%C3%A9composition-d-un-lambda-terme\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>A.dec2 : d\u00e9composition d&rsquo;un lambda-terme<\/h3>\n<p>Les r\u00e8gles suivantes permettent de supprimer certaines parenth\u00e8ses (qui deviennes implicites) pour une meilleure lisibilit\u00e9.<\/p>\n<ol>\n<li>Associativit\u00e9 \u00e0 gauche des applications : \\(((UT)X) \\equiv UTX\\)<\/li>\n<li>Associativit\u00e9 \u00e0 droite des abstractions : \\((\\lambda x . (\\lambda y. U)) \\equiv  \\lambda x . \\lambda y. U\\)<\/li>\n<li>Priorit\u00e9 des application sur les abstractions : \\(\\lambda x.(UT) \\equiv \\lambda x.UT\\)<\/li>\n<\/ol>\n<p>Voici, \u00e0 titre d&rsquo;exemple, la d\u00e9composition du terme \\(\\lambda x. \\lambda y . x y \\lambda t.t\\)<\/p>\n<p>On commence par encadrer les <strong>abstractions<\/strong> (ici en pointill\u00e9) en partant de la <strong>droite<\/strong>.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/01\/1-9.png\" alt=\"image-20220104213522070\" \/><\/p>\n<p>Puis on encadre (ici en trait plein) les applications en partant de la gauche.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/01\/2-8.png\" alt=\"image-20220104213646931\" \/><\/p>\n<h4><a id=\"exercice-de-d%C3%A9couverte-a-dec-x2\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Exercice de d\u00e9couverte A.dec.x2<\/h4>\n<p>D\u00e9composez le terme suivant en applications et abstractions.<\/p>\n<p>\\(\\lambda t . a \\lambda u . a t\\)<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/01\/3-8.png\" alt=\"image-20220104214613700\" \/><\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h4><a id=\"exercice-de-d%C3%A9couverte-a-dec-x3\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Exercice de d\u00e9couverte A.dec.x3<\/h4>\n<p>D\u00e9composez le terme suivant en applications et abstractions.<\/p>\n<p>\\((\\lambda t . \\lambda x . x t) u \\lambda x . x u\\)<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/01\/4-9.png\" alt=\"image-20220112070746499\" \/><\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h3><a id=\"a-dec3-variables-li%C3%A9es-et-variables-libres\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>A.dec3 : Variables li\u00e9es et variables libres<\/h3>\n<p>Le symbole \\(\\lambda\\) est appel\u00e9 <strong>lieur<\/strong>. Il introduit une <strong>variable li\u00e9e<\/strong> \u00e0 toutes les occurrence des variables de m\u00eame nom dans la <strong>port\u00e9e<\/strong> du lieur.<\/p>\n<p>Cette port\u00e9e est l&rsquo;abstraction engendr\u00e9e par le lieur, sauf les abstractions incluses avec une variable li\u00e9e de m\u00eame nom.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/01\/5-8.png\" alt=\"image-20220104221013164\" \/><\/p>\n<p>Toute variable qui n&rsquo;est pas li\u00e9e est dite <strong>libre<\/strong>.<\/p>\n<p>Voici un exemple de terme avec ses variables libres et ses occurrences de variables li\u00e9es entre elles.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/01\/6-8.png\" alt=\"image-20220104221812201\" \/><\/p>\n<h4><a id=\"exercice-de-d%C3%A9couverte-a-dec-x4\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Exercice de d\u00e9couverte A.dec.x4<\/h4>\n<p>Dans le terme suivant, entourez les variables libres et connectez avec des fl\u00e8ches les occurrences de variables li\u00e9es entre elles.<\/p>\n<p>\\(a\\lambda x . \\lambda y . x t y\\)<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/01\/7-6.png\" alt=\"image-20220104222536172\" \/><\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h4><a id=\"exercice-de-d%C3%A9couverte-a-dec-x5\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Exercice de d\u00e9couverte A.dec.x5<\/h4>\n<p>Dans le terme suivant, entourez les variables libres et connectez avec des fl\u00e8ches les occurrences de variables li\u00e9es entre elles.<\/p>\n<p>\\(a\\lambda a . ( b \\lambda a . a ) \\lambda z . a c\\)<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/01\/8-6.png\" alt=\"image-20220104223324541\" \/><\/p>\n<p>Remarquez que la variable \\(z\\) est li\u00e9e, parce qu&rsquo;elle suit imm\u00e9diatement un lieur \\(\\lambda\\), bien qu&rsquo;elle ne soit li\u00e9e qu&rsquo;\u00e0 elle-m\u00eame.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h3><a id=\"a-dec4%C3%89-quivalence-de-termes\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>A.dec4 : \u00c9quivalence de termes<\/h3>\n<p>Deux termes \\(T\\) et \\(U\\) sont dit <strong>\u00e9quivalents<\/strong> (plus pr\u00e9cis\u00e9ment \\(\\alpha\\)-\u00e9quivalents, mais nous ne parlerons que de cette forme d&rsquo;\u00e9quivalence) si et seulement si on peut transformet \\(T\\) et \\(U\\) en un m\u00eame terme \\(R\\) par les op\u00e9rations suivantes :<\/p>\n<ol>\n<li><strong>Renommer<\/strong> des occurrences de variables li\u00e9es sans changer les liens entre occurrences de variables li\u00e9es. Nous appellerons une telle op\u00e9ration <strong>renommage autoris\u00e9<\/strong>.<\/li>\n<li>Supprimer des <strong>parenth\u00e8ses non significatives<\/strong>, c&rsquo;est \u00e0 dire ne modifiant pas la d\u00e9composition d&rsquo;un terme en abstractions et applications.<\/li>\n<\/ol>\n<p>Par exemple \\(a \\lambda x . x  a\\) est \u00e9quivalent \u00e0 \\(a \\lambda y . y a\\) car on peut obtenir le deuxi\u00e8me terme en renommant en \\(y\\) les occurrences li\u00e9es entre elles de la variable \\(x\\) du premier terme.<\/p>\n<p>Mais \\(a \\lambda x . x  a\\) n&rsquo;est <strong>pas<\/strong> \u00e9quivalent \u00e0 \\(b \\lambda y . y b\\) car la variable \\(a\\) est une variable libre. Renommer des occurrences de variables libres change le sens d&rsquo;un \\(\\lambda\\)-terme.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/01\/8-1-2.png\" alt=\"image-20220107104125569\" \/><\/p>\n<h4><a id=\"exercice-de-d%C3%A9couverte-a-dec-x6\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Exercice de d\u00e9couverte A.dec.x6<\/h4>\n<p>Dans la liste suivante, quels sont les termes \u00e9quivalents \u00e0 \\(\\lambda t. \\lambda x. x t\\) ?<\/p>\n<ol>\n<li>\\(\\lambda t. \\lambda t. t t\\)<\/li>\n<li>\\(\\lambda w. \\lambda t. t w\\)<\/li>\n<li>\\((\\lambda t. \\lambda x. x) t\\)<\/li>\n<li>\\(\\lambda t. \\lambda y. (y t)\\)<\/li>\n<\/ol>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<ol>\n<li>Non. En renommant \\(x\\) en \\(t\\), le dernier \\(t\\) n&rsquo;est plus li\u00e9 par le premier, mais par le deuxi\u00e8me lieur. Le renommage n&rsquo;est pas autoris\u00e9 car il modifie les liaisons entre les occurrences de variables li\u00e9es.<\/li>\n<li>Oui. Les occurrences de \\(t\\) ont \u00e9t\u00e9 renomm\u00e9s en \\(w\\) et celle de \\(x\\) on \u00e9t\u00e9 renomm\u00e9es en \\(t\\).<\/li>\n<li>Non. Les d\u00e9compositions en abstractions et application, c&rsquo;est \u00e0 dire les structures des deux termes sont diff\u00e9rentes.<\/li>\n<li>Oui. D&rsquo;une part, le occurrences de \\(x\\) ont \u00e9t\u00e9 renomm\u00e9es en \\(y\\), d&rsquo;autre part, des parenth\u00e8ses non significatives (ne changeant pas la structure du terme) ont \u00e9t\u00e9 ajout\u00e9es.<\/li>\n<\/ol>\n<p><\/div>\n\t\t\t<\/div>\n<h4><a id=\"exercice-de-d%C3%A9couverte-a-dec-x7\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Exercice de d\u00e9couverte A.dec.x7<\/h4>\n<p>Dans la liste suivante, quels sont les termes \u00e9quivalents \u00e0 \\(\\lambda x.(a x a) \\lambda y. y\\) ?<\/p>\n<ol>\n<li>\\((\\lambda x.(a x a)) \\lambda y. y\\)<\/li>\n<li>\\((\\lambda y.(a y a)) \\lambda y. y\\)<\/li>\n<li>\\(\\lambda t.(a t a) \\lambda y. y\\)<\/li>\n<li>\\(\\lambda x.(b x b) \\lambda y. y\\)<\/li>\n<\/ol>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Uniquement le 3. L&rsquo;occurrence (li\u00e9e seulement \u00e0 elle-m\u00eame) de \\(x\\) a \u00e9t\u00e9 remplac\u00e9e par \\(t\\).<\/p>\n<p>Pas 1 ni 2 parce que les parenth\u00e8ses changent la structure (d\u00e9composition en abstractions et applications du terme). Faites un dessin si vous avez des difficult\u00e9s \u00e0 le visualiser mentalement.<\/p>\n<p>Pas 4 car des variables libres changent de nom.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h3><a id=\"a-dec5-redex\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>A.dec5 : Redex<\/h3>\n<p>Un <strong>redex<\/strong> est un terme ayant la forme \\((A)T\\), o\u00f9 \\(A\\) est une abstraction et \\(T\\) est un terme (pouvant \u00eatre une variable, une abstraction et une application).<\/p>\n<p>Identifier les redex est la cl\u00e9 de l&rsquo;\u00e9valuation des termes, ce qui correspond \u00e0 l&rsquo;ex\u00e9cution des &quot;programmes&quot; en \\(\\lambda\\)-calcul.<\/p>\n<p>Voici un exemple de redex qui introduit une terminologie pas sp\u00e9cialement standard, mais qui permettra de simplifier les explications du principe de r\u00e9duction pr\u00e9sent\u00e9 dans la section suivante, qui correspond \u00e0 une \u00e9tape d&rsquo;\u00e9valuation d&rsquo;un terme.<\/p>\n<p>Soit le terme \\(\\lambda x . (\\lambda z . z x) x y\\). Ce terme comporte un redex qui est le terme \\((\\lambda z . z x) x\\).<\/p>\n<p>\\(\\lambda x . \\; \\underbrace{(\\lambda z . z x) x}_\\text{redex} \\; y\\).<\/p>\n<h4><a id=\"exercice-de-d%C3%A9couverte-a-dec-x8\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Exercice de d\u00e9couverte A.dec.x8<\/h4>\n<p>Pourquoi le redex n&rsquo;est-il pas \\((\\lambda z . z x) x y\\) ?<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Si on d\u00e9compose le terme en applications et abstractions, on obtient la structure suivante :<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/01\/9-5.png\" alt=\"image-20220105191953060\" \/><\/p>\n<p>L&rsquo;abstraction entre parenth\u00e8se est appliqu\u00e9e \u00e0 la variable \\(x\\) et non \u00e0 \\(xy\\) en raison de l&rsquo;associativit\u00e9 \u00e0 gauche des applications.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<p>Nous allons donner des noms aux diff\u00e9rentes parties d&rsquo;un redex \\((\\lambda x.C)T\\) :<\/p>\n<ul>\n<li>La <strong>variable de liaison<\/strong> \\(x\\).<\/li>\n<li>Le <strong>corps du redex<\/strong> \\(C\\).<\/li>\n<li>L&rsquo;<strong>argument du redex<\/strong> \\(T\\)<\/li>\n<\/ul>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/01\/10-5.png\" alt=\"image-20220107114301858\" \/><\/p>\n<p>Le corps et l&rsquo;argument peuvent \u00eatre n&rsquo;importe quels \\(\\lambda\\)-termes. Il peuvent comporter des abstractions et des applications.<\/p>\n<h4><a id=\"exercice-de-d%C3%A9couverte-a-dec-x9\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Exercice de d\u00e9couverte A.dec.x9<\/h4>\n<p>Dans le terme \\(\\lambda x . (\\lambda y. a x) b \\lambda t . t\\), identifiez (si applicable) le redex en le mettant entre crochets et en soulignant sa variable de liaison.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Le redex est \\(\\lambda x . [(\\lambda \\underline{y}. a x) b] \\lambda t . t\\)<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h4><a id=\"exercice-de-d%C3%A9couverte-a-dec-x10\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Exercice de d\u00e9couverte A.dec.x10<\/h4>\n<p>Dans le terme \\(\\lambda x . (x \\lambda y . a x) b \\lambda t . t\\), identifiez (si applicable) le redex en le mettant entre crochets et en soulignant sa variable de liaison.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Il n&rsquo;y a pas de redex. C&rsquo;\u00e9tait un pi\u00e8ge. En effet, dans un redex, il y a toujours un symbole \\(\\lambda\\) imm\u00e9diatement apr\u00e8s la premi\u00e8re parenth\u00e8se ouvrante.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h4><a id=\"exercice-de-d%C3%A9couverte-a-dec-x11\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Exercice de d\u00e9couverte A.dec.x11<\/h4>\n<p>Dans le terme \\((\\lambda x . (\\lambda y . a x) b ) \\lambda t . t\\), identifiez (si applicable) le redex en le mettant entre crochets et en soulignant sa variable de liaison.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Le terme entier est un redex : \\([(\\lambda \\underline{x} . (\\lambda y . a \\underline{x}) b ) \\lambda t . t]\\)<\/p>\n<p>Et il y a aussi le redex \\((\\lambda x . [(\\lambda \\underline{y} . a x) b )] \\lambda t . t\\).<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h4><a id=\"exercice-de-d%C3%A9couverte-a-dec-x12\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Exercice de d\u00e9couverte A.dec.x12<\/h4>\n<p>Dans le terme \\(\\lambda x . x y (\\lambda z . z) x\\), identifiez (si applicable) le redex en le mettant entre crochets et en soulignant sa variable de liaison.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Il n&rsquo;y a pas de redex car le terme se d\u00e9compose de la mani\u00e8re suivante :<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/01\/11-5.png\" alt=\"image-20220105202741482\" \/><\/p>\n<p>On voit que l&rsquo;application ayant \\(x\\) comme deuxi\u00e8me terme (le plus grand rectangle en trait plein) n&rsquo;a pas une abstraction comme premier terme. Il ne suffit donc pas qu&rsquo;il y ait un motif \\((\\lambda x.C)T\\) pour que ce soit un redex. Par exemple, dans un terme ayant la forme \\(W(\\lambda x.C)T\\), \\((\\lambda x.C)T\\) n&rsquo;est pas un redex parce qu&rsquo;en raison de l&rsquo;associativit\u00e9 \u00e0 gauche des applications, le terme se d\u00e9compose en \\((W(\\lambda x.C))T\\), i.e., (\\(W\\) appliqu\u00e9 \u00e0 \\((\\lambda x.C)\\)), le tout appliqu\u00e9 \u00e0 \\(T\\).<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h3><a id=\"a-dec6-r%C3%A9duction-cas-simple\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>A.dec6 : R\u00e9duction, cas simple<\/h3>\n<p>La <strong>r\u00e9duction<\/strong> est une \u00e9tape d&rsquo;\u00e9valuation d&rsquo;un \\(\\lambda\\)-terme. Elles s&rsquo;applique \u00e0 un redex \\(R = (\\lambda x.C)T\\) et consiste \u00e0 remplacer ce redex \\(R\\) par le terme \\((C)\\) dans lequel toutes les occurrences de variables li\u00e9es \u00e0 \\(x\\) ont \u00e9t\u00e9 remplac\u00e9es par \\((T)\\).<\/p>\n<p>Reformulons pour bien comprendre le principe :<\/p>\n<ol>\n<li>On prend le corps du redex \\(C\\).<\/li>\n<li>On identifie chaque occurrence de la variable de liaison dans \\(C\\).<\/li>\n<li>On remplace chacune de ces occurrences par \\((T)\\), c&rsquo;est \u00e0 dire l&rsquo;argument entre parenth\u00e8ses.<\/li>\n<li>On met entre parenth\u00e8ses le terme obtenu.<\/li>\n<\/ol>\n<p>Le r\u00e9sultat est la r\u00e9duction du redex. Certaines des parenth\u00e8ses peuvent \u00eatre supprim\u00e9es si cela ne modifie pas la structure du terme.<\/p>\n<p>Voici un exemple de r\u00e9duction d&rsquo;un redex dans le terme \\((\\lambda x . \\lambda y . x) z \\lambda t . t\\). La premi\u00e8re chose \u00e0 faire est de trouver le redex, sa variable de liaison, son corps et son argument.<\/p>\n<p>\\([(\\;\\lambda \\underline{x} .\\; \\lambda y .\\; \\underline{x}\\;)\\; z] \\;\\lambda t .\\; t\\)<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/01\/12-4.png\" alt=\"image-20220107114116868\" \/><\/p>\n<p>Maintenant, on remplace le redex par son corps \\((\\lambda y . x)\\) dans lequel chaque occurrence de la variable de liaison du redex, \\(x\\), est remplac\u00e9e par l&rsquo;argument entre parenth\u00e8ses, \\((z)\\). Tous ce qui est en dehors des limites du redex reste inchang\u00e9.<\/p>\n<p>Le redex r\u00e9duit est \\((\\lambda y . (z))\\). Apr\u00e8s r\u00e9duction, le terme devient \\((\\lambda y.(z))\\lambda t.t\\). Ce terme peut \u00eatre simplifi\u00e9 en virant les parenth\u00e8ses autour de \\(z\\). Par contre, les autres parenth\u00e8ses ne doivent pas \u00eatre supprim\u00e9es car cela changerait la structure du terme.<\/p>\n<p>On obtient donc \\((\\lambda y.z)\\lambda t.t\\).<\/p>\n<h4><a id=\"exercice-de-d%C3%A9couverte-a-dec-x13\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Exercice de d\u00e9couverte A.dec.x13<\/h4>\n<p>Identifiez le redex du terme \\(\\lambda a.(\\lambda x . x y) y z\\) et les occurrences de sa variable de liaison, puis r\u00e9duisez-le.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Identification du redex dans le terme (entre crochets) : \\(\\lambda a. [(\\lambda \\underline{x} . \\underline{x} y) y] z\\).<\/p>\n<p>Si vous avez du mal \u00e0 comprendre cette premi\u00e8re \u00e9tape, prenez le temps de d\u00e9composer le terme en applications et abstraction.<\/p>\n<p>Maintenant, il faut r\u00e9duire le redex, donc le remplacer par son corps \\(\\underline{x} y\\) dans lequel \\(\\underline{x}\\) est remplac\u00e9 par l&rsquo;argument \\(y\\).<\/p>\n<p>Le redex est donc remplac\u00e9 par \\((yy)\\).<\/p>\n<p>Le terme complet apr\u00e8s r\u00e9duction est \\(\\lambda a . (yy) z\\), qui se simplifie en \\(\\lambda a . y y z\\).<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h4><a id=\"exercice-de-d%C3%A9couverte-a-dec-x14\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Exercice de d\u00e9couverte A.dec.x14<\/h4>\n<p>Identifiez le redex du terme \\((\\lambda a. \\lambda b . b a) c \\lambda x.x\\) et les occurrences de sa variable de liaison, puis r\u00e9duisez-le.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>On isole le redex : \\([(\\lambda \\underline{a}. \\lambda b . b \\underline{a}) c]\\lambda x.x\\).<\/p>\n<p>On r\u00e9duit le redex : \\((\\lambda b . b c)\\lambda x . x\\).<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h3><a id=\"a-dec7-r%C3%A9duction-n%C3%A9cessitant-un-renommage\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>A.dec7 : R\u00e9duction n\u00e9cessitant un renommage<\/h3>\n<p>Il y a un cas particulier dans lequel un renommage doit \u00eatre r\u00e9alis\u00e9 avant de proc\u00e9der \u00e0 une r\u00e9duction :<\/p>\n<p><strong>Lorsqu&rsquo;une variable libre situ\u00e9e dans l&rsquo;argument du redex serait captur\u00e9e par un lieur situ\u00e9 dans le corps du redex<\/strong>, c&rsquo;est \u00e0 dire une variable qui ne serait plus libre apr\u00e8s la r\u00e9duction.<\/p>\n<p>Il faut donc une sorte de concours de circonstances :<\/p>\n<ul>\n<li>Il faut qu&rsquo;il y ait un lieur \\(\\lambda \\underline{x}\\) <strong>dans le corps<\/strong> du redex.<\/li>\n<li>Il faut qu&rsquo;il y ait une variable <strong>libre<\/strong> \\(\\underline{x}\\) <strong>dans l&rsquo;argument<\/strong> du redex.<\/li>\n<\/ul>\n<p>On doit alors <strong>renommer<\/strong> toutes les occurrences de \\(\\underline{x}\\) dans le corps du redex de mani\u00e8re \u00e9viter toute capture de variable libre.<\/p>\n<p>Voici un exemple de redex n\u00e9cessitant un tel renommage.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/01\/13-4.png\" alt=\"image-20220106161618715\" \/><\/p>\n<p>On voit que les occurrences de \\(y\\) situ\u00e9es dans le corps du redex sont li\u00e9es. Par ailleurs, il y a une variable \\(y\\) libre dans l&rsquo;argument du redex. C&rsquo;est LE type de situation o\u00f9 un renommage est n\u00e9cessaire. Or il est interdit de renommer une variables libres (cela change le sens d&rsquo;un terme), donc ce sont les occurrences de \\(y\\) dans le corps du redex qu&rsquo;il faut renommer.<\/p>\n<p>On peut par exemple les remplacer par une variable \\(w\\). Le redex devient \\((\\lambda x.\\lambda w.w x)\\lambda t.y\\) qui est \u00e9quivalent au redex initial mais ne pose pas de probl\u00e8me de capture de variable libre lors de sa r\u00e9duction.<\/p>\n<p>Le r\u00e9sultat de la r\u00e9duction est \\(\\lambda w.w(\\lambda t . y)\\). (L&rsquo; occurrence de la variable de liaison \\(\\underline x\\) a \u00e9t\u00e9 remplac\u00e9e par l&rsquo;argument \\(\\lambda t.y\\)). Les parenth\u00e8ses peuvent \u00eatre supprim\u00e9es sans changer la structure du terme, ce qui nous donne \\(\\lambda w.w \\lambda t . y\\).<\/p>\n<p>Mais que ce serait-il pass\u00e9 sans le renommage ? Nous aurions obtenu \\(\\lambda y.y \\lambda t . y\\), qui a une structure diff\u00e9rente puisque les trois occurrences de \\(y\\) sont li\u00e9es.<\/p>\n<p><strong>Attention<\/strong> : Une variable peut \u00eatre li\u00e9e dans un terme tout en \u00e9tant libre dans un des ses sous-termes, notamment dans un redex. Pour d\u00e9terminer la n\u00e9cessit\u00e9 d&rsquo;un renommage, ce sont les variables libres dans le redex qui nous int\u00e9ressent.<\/p>\n<p>Par exemple, dans le terme \\(\\lambda y. [(\\lambda x.\\lambda y.y x)\\lambda t.y]\\), l&rsquo;occurrence de la variable \\(y\\) situ\u00e9e \u00e0 la fin est li\u00e9e par le lieur situ\u00e9 au d\u00e9but. Mais <strong>dans le scope du redex<\/strong> \\((\\lambda x.\\lambda y.y x)\\lambda t.y\\), cette variable est <strong>libre<\/strong> (parce que son lieur n&rsquo;est pas dans le redex). Il <strong>faut<\/strong> faire un renommage pour r\u00e9duire ce redex.<\/p>\n<p>La question \u00e0 se poser est donc : Y-a-t-il <strong>dans le scope du redex<\/strong> (en masquant tout ce qui est autour), une variable qui est libre dans l&rsquo;argument du redex et li\u00e9es dans le corps du redex.<\/p>\n<h4><a id=\"exercice-de-d%C3%A9couverte-a-dec-x15\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Exercice de d\u00e9couverte A.dec.x15<\/h4>\n<p>Le redex \\((\\lambda x . \\lambda y. y x) (y a)\\) n\u00e9cessite-t-il un renommage ? Si oui, soulignez les occurrences de variables devant \u00eatre renomm\u00e9es.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Un renommage est n\u00e9cessaire : \\((\\lambda x . \\lambda \\underline{y}. \\underline{y} x) (y a)\\).<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h4><a id=\"exercice-de-d%C3%A9couverte-a-dec-x16\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Exercice de d\u00e9couverte A.dec.x16<\/h4>\n<p>Le redex \\((\\lambda t . a t) t\\) n\u00e9cessite-t-il un renommage ? Si oui, soulignez les occurrences de variables devant \u00eatre renomm\u00e9es.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Aucun renommage n&rsquo;est n\u00e9cessaire car il n&rsquo;y a pas de lieur dans le corps du redex, qui est \\(a t\\).<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h4><a id=\"exercice-de-d%C3%A9couverte-a-dec-x17\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Exercice de d\u00e9couverte A.dec.x17<\/h4>\n<p>Le redex \\((\\lambda w . a \\lambda t.t) \\lambda x . t x\\) n\u00e9cessite-t-il un renommage ? Si oui, soulignez les occurrences de variables devant \u00eatre renomm\u00e9es.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Ce cas est particulier : la variable de liaison du redex n&rsquo;apparait pas dans le corps du redex, donc le r\u00e9sultat de la r\u00e9duction sera le corps du redex non modifi\u00e9. Comme l&rsquo;argument ne sera pas recopi\u00e9 dans le r\u00e9sultat de l&rsquo;\u00e9valuation, il n&rsquo;y aura pas de probl\u00e8me de capture de sa variable libre. Un renommage n&rsquo;est pas n\u00e9cessaire.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h3><a id=\"a-dec8%C3%89-valuation-d-un-terme\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>A.dec8 : \u00c9valuation d&rsquo;un terme<\/h3>\n<p>L&rsquo;\u00e9valuation d&rsquo;un terme consiste \u00e0 r\u00e9aliser des r\u00e9ductions successives jusqu&rsquo;\u00e0 ce qu&rsquo;il n&rsquo;y ait plus aucun redex. Il peut arriver que l&rsquo;\u00e9valuation ne s&rsquo;arr\u00eate jamais, comme c&rsquo;est le cas pour certains programmes dans tous les langages ayant la puissance d&rsquo;expression de la machine de Turing.<\/p>\n<p>Si, \u00e0 certaines \u00e9tapes de la r\u00e9duction, il y a plusieurs redex, il faut en choisir un. Le r\u00e9sultat final sera toujours le m\u00eame quelque soit le redex choisi.<\/p>\n<p>\u00c0 titre d&rsquo;exemple, voici l&rsquo;\u00e9valuation du terme \\((\\lambda x . x x)(\\lambda a . a b) c\\).<\/p>\n<ol>\n<li>On identifie un redex : \\([(\\lambda \\underline{x} . \\underline{x} \\underline{x})(\\lambda a . a b)] c\\).<\/li>\n<li>On r\u00e9duit ce redex : \\((\\lambda a . a b) (\\lambda a . a b) c\\).<\/li>\n<li>On identifie un redex : \\([(\\lambda \\underline{a} . \\underline{a} b) (\\lambda a . a b)] c\\). Attention, il y a un seul redex. Si vous en voyez deux, c&rsquo;est que vous avez mal d\u00e9compos\u00e9 le terme.<\/li>\n<li>On r\u00e9duit le redex : \\(((\\lambda a . a b) b)c\\).<\/li>\n<li>On identifie un redex : \\([(\\lambda \\underline{a} . \\underline{a} b) b] c\\).<\/li>\n<li>On r\u00e9duit le redex : \\((b b)c\\), , qui peut \u00eatre simplifi\u00e9 en \\(bbc\\).<\/li>\n<li>Il n&rsquo;y a plus de redex, l&rsquo;\u00e9valuation est termin\u00e9e.<\/li>\n<\/ol>\n<h4><a id=\"exercice-de-d%C3%A9couverte-a-dec-x18\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Exercice de d\u00e9couverte A.dec.x18<\/h4>\n<p>D\u00e9taillez l&rsquo;\u00e9valuation du terme \\((\\lambda x . x x )(\\lambda t . t a) b\\).<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<ol>\n<li>redex : \\([(\\lambda \\underline{x} . \\underline{x} \\underline{x} ) (\\lambda t . t a)] b\\).<\/li>\n<li>r\u00e9duction : \\(((\\lambda t . t a) (\\lambda t . t a)) b\\).<\/li>\n<li>redex : \\([(\\lambda \\underline{t} . \\underline{t} a) (\\lambda t . t a)] b\\).<\/li>\n<li>r\u00e9duction : \\(((\\lambda t . t a) a) b\\).<\/li>\n<li>redex : \\([(\\lambda \\underline{t} . \\underline{t} a) a] b\\).<\/li>\n<li>r\u00e9duction : \\((a a) b\\), pouvant \u00eatre simplifi\u00e9 en \\(a a b\\).<\/li>\n<li>plus de redex, l&rsquo;\u00e9valuation est termin\u00e9e.<\/li>\n<\/ol>\n<p><\/div>\n\t\t\t<\/div>\n<h4><a id=\"exercice-de-d%C3%A9couverte-a-dec-x19\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Exercice de d\u00e9couverte A.dec.x19<\/h4>\n<p>D\u00e9taillez l&rsquo;\u00e9valuation du terme \\((\\lambda x . \\lambda y . x y ) y (\\lambda x . x)\\).<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<ol>\n<li>redex : \\([(\\lambda x . \\lambda y . x y ) y] (\\lambda x . x)\\).<\/li>\n<li>renommage n\u00e9cessaire : \\([(\\lambda x . \\lambda t . x t ) y] (\\lambda x . x)\\).<\/li>\n<li>r\u00e9duction : \\((\\lambda t . y t ) (\\lambda x . x)\\).<\/li>\n<li>redex : \\([(\\lambda t . y t ) (\\lambda x . x)]\\).<\/li>\n<li>r\u00e9duction : \\(y (\\lambda x . x)\\).<\/li>\n<li>plus de redex, fin de l&rsquo;\u00e9valuation.<\/li>\n<\/ol>\n<p><\/div>\n\t\t\t<\/div>\n<h2><a id=\"activit%C3%A9-d-entra%C3%AEnement-a-ent\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Activit\u00e9 d&rsquo;entra\u00eenement A.ent<\/h2>\n<p>Cette activit\u00e9 est essentielle. C&rsquo;est gr\u00e2ce \u00e0 elle que vous apprendrez vraiment \u00e0 comprendre et utiliser les notions vues pr\u00e9c\u00e9demment. Elle se d\u00e9compose en deux <strong>it\u00e9rations<\/strong> : <strong>ent1<\/strong>, <strong>ent2<\/strong>. Vous devez r\u00e9aliser au moins une it\u00e9ration et \u00e9valuer votre niveau de r\u00e9ussite.<\/p>\n<p>Si vous avez eu beaucoup de difficult\u00e9 \u00e0 traiter les exercices et fait beaucoup d&rsquo;erreurs, vous devrez traiter \u00e0 nouveau l&rsquo;activit\u00e9 de d\u00e9couverte pr\u00e9c\u00e9dente, en laissant passer au moins une nuit, avant de revenir \u00e0 cette activit\u00e9 d&rsquo;entra\u00eenement en r\u00e9alisant \u00e0 nouveau la premi\u00e8re l&rsquo;it\u00e9ration. Vous devez aussi essayer d&rsquo;identifier les points de blocage et demander \u00e0 votre enseignant de vous aider \u00e0 les surmonter.<\/p>\n<p>Si vous avez r\u00e9ussi certains exercices, mais \u00e9chou\u00e9 \u00e0 d&rsquo;autres, vous devrez d&rsquo;abord comprendre ce qui vous a conduit \u00e0 des erreurs et \/ ou ce qui vous a bloqu\u00e9. Si vous avez des doutes, des difficult\u00e9s, essayez de trouver les r\u00e9ponses dans les pr\u00e9sentations et explications de l&rsquo;activit\u00e9 de d\u00e9couverte pr\u00e9c\u00e9dente et demandez toute l&rsquo;aide n\u00e9cessaire \u00e0 votre enseignant. Ensuite, vous devrez r\u00e9aliser l&rsquo;it\u00e9ration suivante apr\u00e8s au moins une nuit de sommeil et au plus une semaine.<\/p>\n<p>Si vous avez r\u00e9ussi presque tous les exercices et que vos rares erreurs sont dues \u00e0 l&rsquo;inattention, vous devriez revenir traiter l&rsquo;it\u00e9ration suivante apr\u00e8s un d\u00e9lai de plusieurs semaines.<\/p>\n<p>Si besoin, apr\u00e8s avoir trait\u00e9 la deuxi\u00e8me it\u00e9ration, vous pouvez revenir \u00e0 la premi\u00e8re. Vous pouvez aussi traiter des annales d&rsquo;\u00e9valuations de l&rsquo;unit\u00e9 d&rsquo;enseignement.<\/p>\n<h3><a id=\"it%C3%A9ration-a-ent1\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>It\u00e9ration A.ent1<\/h3>\n<h4><a id=\"exercice-d-entrainement-a-ent1-1\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Exercice d&rsquo;entrainement A.ent1.1<\/h4>\n<p>D\u00e9composez les termes suivants en abstractions et applications, entourez les variables libres et connectez les variables li\u00e9es entre elles.<\/p>\n<ol>\n<li>\\(y\\;\\lambda x. \\; \\lambda y. \\; x \\; y\\)<\/li>\n<li>\\(\\lambda y.\\; x\\; y\\; \\lambda t.\\; x\\; y\\; \\lambda x .\\; z\\).<\/li>\n<\/ol>\n<p>Attention, toute variable situ\u00e9e entre le symbole \\(\\lambda\\) et le point est li\u00e9e, m\u00eame si elle n&rsquo;est pas li\u00e9e \u00e0 d&rsquo;autres occurrences( auquel cas elle n&rsquo;est li\u00e9e qu&rsquo;\u00e0 elle-m\u00eame.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Solution1&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/01\/14-1.png\" alt=\"image-20220106181203829\" \/><\/p>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Solution2&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/01\/15-1.png\" alt=\"image-20220106182628430\" \/><\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h4><a id=\"exercice-d-entrainement-a-ent1-2\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Exercice d&rsquo;entrainement A.ent1.2<\/h4>\n<p>Pour chacune des paires de termes suivants, d\u00e9terminez s&rsquo;il y a \u00e9quivalence.<\/p>\n<ol>\n<li>\\(\\lambda x. y x\\) et \\(\\lambda z. y z\\).<\/li>\n<li>\\(\\lambda x. y x\\) et \\(\\lambda x. y y\\).<\/li>\n<li>\\(\\lambda x.y x\\) et \\(\\lambda x. z x\\).<\/li>\n<li>\\(\\lambda x.\\lambda y. y x\\) et \\(\\lambda y.\\lambda x. x y\\).<\/li>\n<li>\\(\\lambda x. y \\lambda z. z x\\) et \\(\\lambda x . y \\lambda y.y x\\).<\/li>\n<\/ol>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse1&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Oui, la variable \\(x\\) du premier terme est renomm\u00e9e \\(z\\) dans le deuxi\u00e8me.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse2&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Non, une seule des 2 occurrence de la variable li\u00e9e du premier terme a \u00e9t\u00e9 renomm\u00e9e dans le deuxi\u00e8me terme.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse3&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Non, la variable libre \\(y\\) du premier terme ne peut pas \u00eatre renomm\u00e9e. Seules les variables li\u00e9es peuvent \u00eatre renomm\u00e9es sans changer le sens d&rsquo;un terme.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse4&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Oui, un double renommage permet de passer d&rsquo;un terme \u00e0 l&rsquo;autre.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse5&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Oui, la variable \\(z\\) du premier terme est renomm\u00e9e en \\(y\\) dans le deuxi\u00e8me, et la variable libre \\(y\\) reste libre et garde le m\u00eame nom dans les deux termes.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h4><a id=\"exercice-d-entrainement-a-ent1-3\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Exercice d&rsquo;entrainement A.ent1.3<\/h4>\n<p>\u00c9valuez les termes suivants :<\/p>\n<ol>\n<li>\\((\\lambda x.\\lambda y. xyx)(\\lambda x. x)\\)<\/li>\n<li>\\((\\lambda t.tt)\\lambda x.x\\)<\/li>\n<li>\\(\\lambda t.tt \\lambda x.x\\)<\/li>\n<li>\\((\\lambda t.tt)(\\lambda x. \\lambda y. x y)\\)<\/li>\n<\/ol>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse1&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<ol>\n<li>redex : \\([(\\lambda x.\\lambda y. xyx)(\\lambda x. x)]\\)<\/li>\n<li>r\u00e9duction : \\(\\lambda y. (\\lambda x. x)y(\\lambda x. x)\\)<\/li>\n<li>redex : \\(\\lambda y. [(\\lambda x. x)y](\\lambda x. x)\\)<\/li>\n<li>r\u00e9duction : \\(\\lambda y. y(\\lambda x. x)\\)<\/li>\n<li>Fin.<\/li>\n<\/ol>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse2&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<ol>\n<li>redex : \\([(\\lambda t.tt)\\lambda x.x]\\)<\/li>\n<li>r\u00e9duction : \\((\\lambda x.x)(\\lambda x.x)\\)<\/li>\n<li>redex : \\([(\\lambda x.x)(\\lambda x.x)]\\)<\/li>\n<li>r\u00e9duction : \\(\\lambda x.x\\)<\/li>\n<li>Fin.<\/li>\n<\/ol>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse3&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<ol>\n<li>Il n&rsquo;y a pas de redex. Fin.<\/li>\n<\/ol>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse4&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<ol>\n<li>redex : \\([(\\lambda tt)(\\lambda x. \\lambda y. x y)]\\)<\/li>\n<li>r\u00e9duction : \\((\\lambda x. \\lambda y. x y)(\\lambda x. \\lambda y. x y)\\)<\/li>\n<li>redex : \\([(\\lambda x. \\lambda y. x y)(\\lambda x. \\lambda y. x y)]\\)<\/li>\n<li>r\u00e9duction : \\(\\lambda y. (\\lambda x. \\lambda y. x y) y\\)<\/li>\n<li>redex : \\(\\lambda y. [(\\lambda x. \\lambda y. x y) y]\\)<\/li>\n<li>renommage n\u00e9cessaire : \\(\\lambda y. [(\\lambda x. \\lambda w. x w) y]\\)<\/li>\n<li>r\u00e9duction : \\(\\lambda y. (\\lambda w. y w)\\)<\/li>\n<li>Fin.<\/li>\n<\/ol>\n<p><\/div>\n\t\t\t<\/div>\n<h3><a id=\"it%C3%A9ration-a-ent2\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>It\u00e9ration A.ent2<\/h3>\n<h4><a id=\"exercice-d-entrainement-a-ent2-1\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Exercice d&rsquo;entrainement A.ent2.1<\/h4>\n<p>D\u00e9composez les termes suivants en abstractions et applications, entourez les variables libres et connectez les variables li\u00e9es entre elles.<\/p>\n<ol>\n<li>\\(\\lambda t.\\; x\\; \\lambda f .\\; t\\)<\/li>\n<li>\\(\\lambda x .\\; x\\; y\\;(\\;\\lambda y.\\;x\\; y\\;)(\\;\\lambda x.\\;x\\;)\\).<\/li>\n<\/ol>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Solution1&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/01\/16-1.png\" alt=\"image-20220106183153009\" \/><\/p>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Solution2&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/01\/17-2.png\" alt=\"image-2022010618365744\" \/><\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h4><a id=\"exercice-d-entrainement-a-ent2-2\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Exercice d&rsquo;entrainement A.ent2.2<\/h4>\n<p>Pour chacune des paires de termes suivants, d\u00e9terminez s&rsquo;il y a \u00e9quivalence.<\/p>\n<ol>\n<li>\\(a\\lambda b . ab\\) et \\(a\\lambda c . ac\\)<\/li>\n<li>\\(a\\lambda b . ab\\) et \\(b\\lambda c. bc\\)<\/li>\n<li>\\(\\lambda x. \\lambda f.f(fx)\\) et \\(\\lambda x. \\lambda f.ffx\\)<\/li>\n<li>\\(\\lambda x. \\lambda f.f(fx)\\) et \\(\\lambda f. \\lambda x.x(xf)\\)<\/li>\n<li>\\(\\lambda x.yx\\lambda x.x\\) et \\(\\lambda x.y x\\lambda y.y\\)<\/li>\n<\/ol>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse1&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Oui, on passe du premier terme au second en renommant \\(b\\) en \\(c\\).<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse2&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Non, car la variable libre \\(a\\) du premier terme change de nom dans le deuxi\u00e8me.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse3&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Non, car l&rsquo;applications est associative \u00e0 gauche, donc \\(ffx\\) est \u00e9quivalent \u00e0 \\((ff)x\\) et pas \u00e0 \\(f(fx)\\).<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse4&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Oui car on peut passer du premier terme au deuxi\u00e8me par un double renommage.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse5&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Oui, les deux derni\u00e8res occurrences de \\(x\\) dans le premier terme ne sont pas li\u00e9es au deux premi\u00e8res et peuvent \u00eatre renomm\u00e9es sans changer le sens du terme.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h4><a id=\"exercice-d-entrainement-a-ent2-3\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Exercice d&rsquo;entrainement A.ent2.3<\/h4>\n<p>\u00c9valuez le termes suivants :<\/p>\n<ol>\n<li>\\((\\lambda w.ww) a a\\)<\/li>\n<li>\\((\\lambda x. \\lambda y. xy)(\\lambda x.x x)\\)<\/li>\n<li>\\(((\\lambda x.x \\lambda t.t)\\lambda w.w) t\\)<\/li>\n<li>\\((\\lambda w.\\lambda y.a w) \\lambda x.y b\\)<\/li>\n<\/ol>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse1&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<ol>\n<li>redex : \\([(\\lambda w.ww) a] a\\)<\/li>\n<li>r\u00e9duction : \\(aaa\\)<\/li>\n<li>Fin.<\/li>\n<\/ol>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse2&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<ol>\n<li>redex : \\([(\\lambda x. \\lambda y. xy)(\\lambda x.x x)]\\)<\/li>\n<li>r\u00e9duction : \\(\\lambda y. (\\lambda x.x x)y\\)<\/li>\n<li>redex : \\(\\lambda y. [(\\lambda x.x x)y]\\)<\/li>\n<li>r\u00e9duction : \\(\\lambda y. yy\\)<\/li>\n<li>Fin.<\/li>\n<\/ol>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse3&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<ol>\n<li>redex : \\(([(\\lambda x.x \\lambda t.t)\\lambda w.w]) t\\)<\/li>\n<li>r\u00e9duction : \\(((\\lambda w.w) \\lambda t.t) t\\)<\/li>\n<li>redex : \\(([(\\lambda w.w) \\lambda t.t]) t\\)<\/li>\n<li>r\u00e9duction : \\((\\lambda t.t) t\\)<\/li>\n<li>redex : \\([(\\lambda t.t) t]\\)<\/li>\n<li>r\u00e9duction : \\(t\\)<\/li>\n<li>Fin.<\/li>\n<\/ol>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse4&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<ol>\n<li>redex : \\([(\\lambda w.\\lambda y.a w) \\lambda x.y b]\\)<\/li>\n<li>renommage n\u00e9cessaire : \\([(\\lambda w.\\lambda t.a w) \\lambda x.y b]\\)<\/li>\n<li>r\u00e9duction : \\((\\lambda t.a (\\lambda x.y b))\\)<\/li>\n<li>Fin.<\/li>\n<\/ol>\n<p><\/div>\n\t\t\t<\/div>\n<h2><a id=\"activit%C3%A9-a-top\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Activit\u00e9 A.top<\/h2>\n<p>Cette activit\u00e9 propose des exercices de <strong>consolidation<\/strong> qui ne doivent \u00eatre abord\u00e9s que par les personnes apprenantes ma\u00eetrisant bien la partie A et les parties suivantes disponibles.<\/p>\n<p>Par exemple, si les parties actuellement disponibles sont A et B, vous devez d&rsquo;abord ma\u00eetriser la parie B avant de faire cette activit\u00e9 de consolidation de la partie A.<\/p>\n<h3><a id=\"it%C3%A9ration-a-top1\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>It\u00e9ration A.top1<\/h3>\n<h4><a id=\"exercice-de-consolidation-a-top1\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Exercice de consolidation A.top1<\/h4>\n<p>Dans les activit\u00e9s de d\u00e9couverte et d&rsquo;entra\u00eenement, nous avons \u00e9valu\u00e9 des termes qui n&rsquo;ont qu&rsquo;un int\u00e9r\u00eat purement p\u00e9dagogique, par leur simplicit\u00e9, pour apprendre les m\u00e9canismes d&rsquo;\u00e9valuation des \\(\\lambda\\)-termes. Dans cet exercice, nous allons d\u00e9couvrir comment utiliser le \\(\\lambda\\)-calcul pour \u00e9valuer des expressions Bool\u00e9ennes.<\/p>\n<p>On peut repr\u00e9senter les Bool\u00e9ens <code>vrai<\/code> et <code>faux<\/code> de la mani\u00e8re suivante :<\/p>\n<ul>\n<li><code>vrai<\/code> : \\((\\lambda a. \\lambda b. a)\\), que nous noterons \\(\\boxed{T}\\).<\/li>\n<li><code>faux<\/code> : \\((\\lambda a. \\lambda b. b)\\), que nous noterons \\(\\boxed{F}\\).<\/li>\n<\/ul>\n<p>Le \\(\\lambda\\)-terme \\((\\lambda p.\\lambda a.\\lambda b.pab)\\), not\u00e9 \\(\\boxed{ite}\\), encode la fonction <code>if then else<\/code>.<\/p>\n<h5><a id=\"question-1\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Question 1<\/h5>\n<p>\u00c9valuez \\(\\boxed{ite}\\; \\boxed{T}\\).<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>On remplace \\(\\boxed{ite}\\) par le terme correspondant. On a alors :<\/p>\n<p>\\(\\boxed{ite}\\; \\boxed{T}\\) = \\((\\lambda p.\\lambda a.\\lambda b.pab)\\; \\boxed{T}\\)<\/p>\n<p>= \\((\\lambda a.\\lambda b.\\boxed{T} \\;ab)\\)<\/p>\n<p>= \\((\\lambda a.\\lambda b.(\\lambda a. \\lambda b. a)ab)\\)<\/p>\n<p>= \\((\\lambda a.\\lambda b.[(\\lambda a. \\lambda b. a)a]b)\\)<\/p>\n<p>= \\((\\lambda a.\\lambda b.(\\lambda b. a)b)\\)<\/p>\n<p>= \\((\\lambda a.\\lambda b.[(\\lambda b. a)b])\\)<\/p>\n<p>= \\(\\lambda a.\\lambda b.a\\) = \\(\\boxed{T}\\).<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h5><a id=\"question-2\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Question 2<\/h5>\n<p>\u00c9valuez \\(\\boxed{ite}\\; \\boxed{F}\\).<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>On remplace \\(\\boxed{ite}\\) par le terme correspondant. On a alors :<\/p>\n<p>\\(\\boxed{ite}\\; \\boxed{F}\\) = \\((\\lambda p.\\lambda a.\\lambda b.pab)\\; \\boxed{F}\\)<\/p>\n<p>= \\((\\lambda a.\\lambda b.\\boxed{F} \\;ab)\\)<\/p>\n<p>= \\((\\lambda a.\\lambda b.(\\lambda a. \\lambda b. b)ab)\\)<\/p>\n<p>= \\((\\lambda a.\\lambda b.[(\\lambda a. \\lambda b. b)a]b)\\)<\/p>\n<p>= \\((\\lambda a.\\lambda b.(\\lambda b. b)b)\\)<\/p>\n<p>= \\((\\lambda a.\\lambda b.[(\\lambda b. b)b])\\)<\/p>\n<p>= \\(\\lambda a.\\lambda b.b\\) = \\(\\boxed{F}\\).<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<p>Donc \\(\\boxed{ite}\\; \\boxed{T}\\) = \\(\\boxed{T}\\) et \\(\\boxed{ite}\\; \\boxed{F}\\) = \\(\\boxed{F}\\) .<\/p>\n<p>Soient \\(A\\) et \\(B\\) deux termes quelconques entour\u00e9 de parenth\u00e8ses.<\/p>\n<h5><a id=\"question-3\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Question 3<\/h5>\n<p>\u00c9valuez \\(\\boxed{ite}\\; \\boxed{T}\\; A\\; B\\).<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>\\(\\boxed{ite}\\; \\boxed{T}\\; A\\; B\\) = \\((\\lambda p.\\lambda a.\\lambda b.pab)\\; \\boxed{T}\\; A\\; B\\)<\/p>\n<p>= \\([(\\lambda p.\\lambda a.\\lambda b.pab)\\; \\boxed{T}\\;]\\; A\\; B\\)<\/p>\n<p>= \\((\\lambda a.\\lambda b. \\;\\boxed{T}\\;ab)\\; A\\; B\\)<\/p>\n<p>= \\([(\\lambda a.\\lambda b. \\;\\boxed{T}\\;ab)] A\\; B\\)<\/p>\n<p>= \\((\\lambda b. \\;\\boxed{T}\\;A b) B\\)<\/p>\n<p>= \\([(\\lambda b. \\;\\boxed{T}\\;A b) B]\\)<\/p>\n<p>= \\(\\boxed{T}\\;A \\; B\\)<\/p>\n<p>= \\((\\lambda a. \\lambda b. a) A B\\)<\/p>\n<p>= \\([(\\lambda a. \\lambda b. a) A] B\\)<\/p>\n<p>= \\((\\lambda b. A) B\\)<\/p>\n<p>= \\(A\\).<\/p>\n<p>Concernant la derni\u00e8re r\u00e9duction, il faut comprendre que le corps du redex ne comporte pas d&rsquo;occurrence de variable li\u00e9e \u00e0 sa variable de liaison \\(b\\). Il peut y avoir des occurrences d&rsquo;une variable \\(b\\) dan le terme \\(A\\), mais soit elles sont li\u00e9es dans le scope de \\(A\\), soit elles sont libres dans ce scope, mais alors elles auront \u00e9t\u00e9 renomm\u00e9es \u00e0 l&rsquo;\u00e9tape d&rsquo;\u00e9valuation pr\u00e9c\u00e9dente.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<p>On a la propri\u00e9t\u00e9 : \\(\\boxed{ite}\\; \\boxed{T}\\; A\\; B\\) = \\(A\\).<\/p>\n<p>On peut aussi monter que \\(\\boxed{ite}\\; \\boxed{F}\\; A\\; B\\) = \\(B\\).<\/p>\n<p>On voit que ce codage de <code>if then else<\/code> permet de s\u00e9lectionner un terme \\(A\\) ou \\(B\\) selon que la valeur Bool\u00e9enne d&rsquo;un terme de contr\u00f4le est <code>vrai<\/code> ou <code>faux<\/code>. Cette propri\u00e9t\u00e9 permet de coder n&rsquo;importe quelle fonction Bool\u00e9enne.<\/p>\n<p>Par exemple, la <strong>n\u00e9gation logique<\/strong> peut \u00eatre cod\u00e9e par le terme :<\/p>\n<p>\\(\\boxed{not}\\) = \\((\\lambda x.\\boxed{ite} \\;x\\; \\boxed{F}\\; \\boxed{T}\\;)\\), qui peut s&rsquo;\u00e9crire, pour une meilleure compr\u00e9hension :<\/p>\n<p>\\((\\lambda x.((\\;\\boxed{ite} \\;x)\\; \\boxed{F}\\;)\\; \\boxed{T}\\;)\\)<\/p>\n<p><strong>Question 4<\/strong> : \u00e9valuez \\(\\boxed{not}\\; \\boxed{T}\\) et  \\(\\boxed{not}\\; \\boxed{F}\\;\\).<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>\\(\\boxed{not}\\; \\boxed{T}\\) = \\((\\lambda x.\\;\\boxed{ite} \\;x\\; \\boxed{F}\\; \\boxed{T}\\;)\\; \\boxed{T}\\)<\/p>\n<p>= \\(\\boxed{ite} \\;\\boxed{T}\\; \\boxed{F}\\; \\boxed{T}\\)<\/p>\n<p>= \\(\\boxed{F}\\)<\/p>\n<p>\\(\\boxed{not}\\; \\boxed{F}\\) = \\((\\lambda x.\\;\\boxed{ite} \\;x\\; \\boxed{F}\\; \\boxed{T}\\;)\\; \\boxed{F}\\)<\/p>\n<p>= \\(\\boxed{ite} \\;\\boxed{F}\\; \\boxed{F}\\; \\boxed{T}\\)<\/p>\n<p>= \\(\\boxed{T}\\)<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<p>Si vous \u00eates arriv\u00e9 jusqu&rsquo;ici, vous \u00eates en mesure de commencer \u00e0 percevoir comment, en combinant des termes de \\(\\lambda\\)-calcul, on peut concevoir des fonctions r\u00e9alisant des traitements complexes.<\/p>\n<p>Nous sommes au del\u00e0 des objectifs p\u00e9dagogiques de cette introduction au \\(\\lambda\\)-calcul, mais on commence \u00e0 comprendre qu&rsquo;<strong>une abstraction repr\u00e9sente le code permettant de calculer une fonction \u00e0 un param\u00e8tre<\/strong> et qu&rsquo;une application \\(A D\\) repr\u00e9sente le <strong>calcul de l&rsquo;image<\/strong> de \\(D\\) <strong>par cette fonction<\/strong>.<\/p>\n<p>Par exemple, la d\u00e9finition \\(\\boxed{not}\\) = \\((\\lambda x.\\boxed{ite} \\;x\\; \\boxed{F}\\; \\boxed{T}\\;)\\) dit que l&rsquo;abstraction \\(\\boxed{not}\\) est une fonction qui \u00e0 tout Bool\u00e9en \\(x\\) associe <code>faux<\/code> si \\(x\\) s&rsquo;\u00e9value \u00e0 <code>vrai<\/code> et <code>vrai<\/code> si x s&rsquo;\u00e9value \u00e0 <code>faux<\/code>.<\/p>\n<p>On touche du doigt \u00e0 la foi la puissance du \\(\\lambda\\)-calcul, mais aussi l&rsquo;extr\u00eame difficult\u00e9 \u00e0 sp\u00e9cifier des calculs complexes dans ce langage. On peut <strong>monter<\/strong> que toutes fonction calculable peut \u00eatre impl\u00e9ment\u00e9e en \\(\\lambda\\)-calcul, mais le <strong>faire<\/strong> est trop compliqu\u00e9 pour avoir un int\u00e9r\u00eat pratique.<\/p>\n<p>Par contre, le <strong>principe<\/strong> d&rsquo;\u00e9valuation peut \u00eatre mais en oeuvre dans des langages beaucoup plus faciles \u00e0 exploiter, tels que <code>CAML<\/code>. Dans la suite de cet enseignement, nous utiliserons ce langage pour r\u00e9aliser des programmes.<\/p>\n<hr \/>\n","protected":false},"excerpt":{"rendered":"<p>Par O. Bailleux, Ma\u00eetre de conf\u00e9rences HDR \u00e0 l&rsquo;universit\u00e9 de Bourgogne. Le lambda-calcul Les activit\u00e9s #.dec (dec pour D\u00e9couverte) consistent \u00e0 \u00e9tudier des pr\u00e9sentations explicatives et \u00e0 traiter tous les exercices de d\u00e9couverte propos\u00e9s. Si vous ne r\u00e9pondez pas correctement \u00e0 un exercice de d\u00e9couverte, revenez en arri\u00e8re pour relire les explications et identifier la [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[3],"tags":[],"class_list":["post-189","post","type-post","status-publish","format-standard","hentry","category-plf","entry"],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/posts\/189","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/comments?post=189"}],"version-history":[{"count":2,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/posts\/189\/revisions"}],"predecessor-version":[{"id":487,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/posts\/189\/revisions\/487"}],"wp:attachment":[{"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/media?parent=189"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/categories?post=189"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/tags?post=189"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}