{"id":354,"date":"2022-03-13T12:29:01","date_gmt":"2022-03-13T12:29:01","guid":{"rendered":"https:\/\/9h15.net\/activ\/?p=354"},"modified":"2022-06-22T08:35:17","modified_gmt":"2022-06-22T08:35:17","slug":"le-langage-prolog","status":"publish","type":"post","link":"https:\/\/9h15.net\/activ\/le-langage-prolog\/","title":{"rendered":"Le langage Prolog"},"content":{"rendered":"\n<div class=\"wp-block-jetpack-markdown\"><h1>Programmation logique et fonctionnelle &#8211; partie E<\/h1>\n<p><code>Par O. Bailleux, Ma\u00eetre de conf\u00e9rences HDR \u00e0 l'universit\u00e9 de Bourgogne.<\/code><\/p>\n<h1>Le langage PROLOG<\/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>Activit\u00e9 de d\u00e9couverte E.dec<\/h2>\n<h3>Introduction<\/h3>\n<p><strong>Prolog<\/strong> est un langage de programmation d\u00e9claratif bas\u00e9 sur la logique du premier ordre. Il permet d&rsquo;\u00e9crire en quelques lignes des programmes qui n\u00e9cessiterait des pages de codes avec les langages imp\u00e9ratifs tels que Python, Java, C ou C++ par exemple.<\/p>\n<p>Mais il est difficile de parler de ce langage sans le pratiquer, donc je vous propose de commencer tout de suite \u00e0 le d\u00e9couvrir avec les exemples.<\/p>\n<h3>E.dec1 : Faits et buts<\/h3>\n<p>Voici un exemple de relations entre des joueurs, des classes et des comp\u00e9tence dans un jeu de r\u00f4le.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/03\/prolog1.png\" alt=\"prolog1\"><\/p>\n<p>La relation <code>jc<\/code> relie des joueurs et des classes. La relation <code>cc<\/code> relie des classes et des comp\u00e9tences. Voici comment ces relations peuvent \u00eatre d\u00e9finies en Prolog.<\/p>\n<pre><code>jc(anne,voleur).\njc(bart,mage).\njc(charlie,druide).\njc(dave,paladin).\njc(edouard,paladin).\n<\/code><\/pre>\n<pre><code>cc(voleur,dps).\ncc(mage,dps).\ncc(druide,dps).\ncc(druide,soigneur).\ncc(paladin,soigneur).\ncc(paladin,tank).\ncc(guerrier,tank).\n<\/code><\/pre>\n<p>Des lettres minuscules ont \u00e9t\u00e9 utilis\u00e9es pour les pr\u00e9noms car en Prolog les identificateurs commen\u00e7ant par une majuscule repr\u00e9sentent des variables. Il est possible d&rsquo;utiliser des chaines de caract\u00e8res en les mettant entre guillemets doubles.<\/p>\n<h5>Exercice de d\u00e9couverte E.dec.x1<\/h5>\n<p>Quels joueurs ont la comp\u00e9tence <code>soigneur<\/code> ?<\/p>\n<p>Quels joueurs peuvent tanker et soigner ?<\/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>Charlie, Dave et Edouard sont soigneurs.<\/p>\n<p>Dave et Edouard peuvent tanker et soigner.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h3>E.dec2 : Requ\u00eates sur des faits<\/h3>\n<p>En Prolog, une requ\u00eate est appel\u00e9e <strong>but<\/strong>. Voici un exemple de but avec le pr\u00e9dicat <code>jc<\/code> d\u00e9fini pr\u00e9c\u00e9demment :<\/p>\n<pre><code>jc(X,voleur).\n<\/code><\/pre>\n<p>La r\u00e9ponse produite parle d&rsquo;elle-m\u00eame :<\/p>\n<pre><code>X = anne\n<\/code><\/pre>\n<p>Prolog recherche toutes les valuations des variables concern\u00e9es qui satisfont le but. Lorsqu&rsquo;il n&rsquo;y a pas de variable, la r\u00e9ponse est <code>true<\/code> ou <code>false<\/code> :<\/p>\n<pre><code>jc(anne,voleur). --&gt; true\njc(dave,voleur). --&gt; false\njc(olivier,voleur). --&gt; false\n<\/code><\/pre>\n<hr>\n<p>On peut formuler des buts compos\u00e9s de plusieurs <strong>sous-buts<\/strong>, comme par exemple&#8230;<\/p>\n<pre><code>jc(X,Y),cc(Y,dps).\n<\/code><\/pre>\n<p>&#8230;qui recherche les joueurs <code>X<\/code> dont la classe <code>Y<\/code> leur donne la comp\u00e9tence <code>dps<\/code>. On obtient la r\u00e9ponse :<\/p>\n<pre><code>X = anne, Y = voleur\nX = bart, Y = mage\nX = charlie, Y = druide\nfalse\n<\/code><\/pre>\n<p>La valeur <code>false<\/code> \u00e0 l&rsquo;issue de l&rsquo;\u00e9num\u00e9ration des solutions est un effet de bord du m\u00e9canisme d&rsquo;\u00e9valuation de Prolog, que nous n&rsquo;aborderons pas tout de suite. Elle peut \u00eatre ignor\u00e9e.<\/p>\n<p>Voici une repr\u00e9sentation graphique des solutions :<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/03\/prolog2.png\" alt=\"prolog2\"><\/p>\n<h5>Exercice de d\u00e9couverte E.dec.x2<\/h5>\n<p>Donnez le but permettant de savoir quelles sont les comp\u00e9tences de Dave.<\/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<pre><code>jc(dave,Classe), cc(Classe,Comp).\n<\/code><\/pre>\n<p>N&rsquo;oubliez pas que les identificateurs commen\u00e7ant par une majuscule sont des variables. La r\u00e9ponse obtenue est :<\/p>\n<pre><code>Classe = paladin, Comp = soigneur\nClasse = paladin, Comp = tank\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<p>Donnez le but permettant de savoir quelles sont les classes ayant la comp\u00e9tence <code>dps<\/code>.<\/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<pre><code>cc(Classe,dps).\n<\/code><\/pre>\n<p>On obtient la r\u00e9ponse :<\/p>\n<pre><code>Classe = voleur\nClasse = mage\nClasse = druide\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<p>Quelle est la r\u00e9ponse donn\u00e9e au but ci-dessous, et pourquoi ?<\/p>\n<pre><code>jc(anne,X),cc(X,soigneur).\n<\/code><\/pre>\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>La r\u00e9ponse est <code>false<\/code>, car il n&rsquo;y a aucune valeur X telle que les 2 sous-buts <code>jc(anne,X)<\/code> et <code>cc(X,soigneur)<\/code> sont satisfaits.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<p>Le but&#8230;<\/p>\n<pre><code>jc(anne,X),cc(X,soigneur).\n<\/code><\/pre>\n<p>&#8230;peut \u00eatre formul\u00e9 de la mani\u00e8re suivante en logique du premier ordre :<\/p>\n<p>$\\exists X$ $(\\text{jc}(\\text{anne}, X) \\wedge \\text{cc}(X, \\text{soigneur}))$<\/p>\n<p>Les identificateurs <code>jc<\/code> et <code>cc<\/code> sont des symboles relationnels et les identificateurs <code>anne<\/code> et <code>soigneur<\/code> sont des termes fonctionnels, plus pr\u00e9cis\u00e9ment des constantes fonctionnelles.<\/p>\n<h3>E.dec3 : Clauses<\/h3>\n<p>Les fait ne sont pas la seule mani\u00e8re de d\u00e9finir des pr\u00e9dicats. On peut \u00e9galement le faire avec des <strong>clauses<\/strong>, comme dans cet exemple :<\/p>\n<pre><code>peut(J,A) :- jc(J,X), cc(X,A).\n<\/code><\/pre>\n<p>Un nouveau pr\u00e9dicat <code>peut<\/code> est d\u00e9finit. Le pr\u00e9dicat <code>peut(J,A)<\/code>, est satisfait si et seulement si il existe une valeur <code>X<\/code> telle que <code>jc(J,X)<\/code> et <code>cc(X,A)<\/code> soient satisfaits.<\/p>\n<p>Le symbole <code>:-<\/code> repr\u00e9sente le connecteur logique implique \u00e9crit \u00e0 l&rsquo;envers, c&rsquo;est \u00e0 dire $\\leftarrow$. La clause d\u00e9finissant le pr\u00e9dicat <code>peut<\/code> correspond \u00e0 la formule du premier ordre suivante :<\/p>\n<p>$\\exists X (\\text{jc}(J,X) \\wedge \\text{cc}(X,A))$ $\\to$ $\\text{peut}(J,A)$<\/p>\n<p>En fran\u00e7ais, on peut d\u00e9finir le pr\u00e9dicat ainsi :<\/p>\n<blockquote>\n<p>Si <code>J<\/code> a la classe <code>X<\/code> et si <code>X<\/code> a la comp\u00e9tence <code>A<\/code>, alors <code>J<\/code> a la comp\u00e9tence <code>A<\/code>.<\/p>\n<\/blockquote>\n<p>L&rsquo;expression <code>peut(J,A)<\/code> est appel\u00e9e <strong>t\u00eate<\/strong> de la clause, et les expressions <code>jc(J,X)<\/code> et <code>cc(X,A)<\/code> sont appel\u00e9es les <strong>sous-buts<\/strong> de la clause.<\/p>\n<p>On peut utiliser notre nouveau pr\u00e9dicat dans un but, tel que par exemple&#8230;<\/p>\n<pre><code>peut(charlie,A).\n<\/code><\/pre>\n<p>&#8230;qui donne la r\u00e9ponse :<\/p>\n<pre><code>A = dps\nA = soigneur\n<\/code><\/pre>\n<h5>Exercice de d\u00e9couverte E.dec.x3<\/h5>\n<p>Sans utiliser d&rsquo;interpr\u00e9teur Prolog, donnez les r\u00e9sultats du but :<\/p>\n<pre><code>peut(J, soigneur).\n<\/code><\/pre>\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<pre><code>J = charlie\nJ = dave\nJ = edouard\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<p>Sans utiliser d&rsquo;interpr\u00e9teur Prolog, donnez les r\u00e9sultats du but :<\/p>\n<pre><code>peut(anne, tank).\n<\/code><\/pre>\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<pre><code>false\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<p>Sans utiliser d&rsquo;interpr\u00e9teur Prolog, donnez les r\u00e9sultats du but :<\/p>\n<pre><code>peut(dave, soigneur).\n<\/code><\/pre>\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<pre><code>true\n<\/code><\/pre>\n<p>En ex\u00e9cutant le but sur machine, on constate qu&rsquo;un <code>false<\/code> est affich\u00e9 apr\u00e8s le <code>true<\/code>. Il ne faut pas en tenir compte. Cet affichage &quot;parasite&quot; est li\u00e9 au m\u00e9canisme d&rsquo;\u00e9valuation de Prolog, comme mentionn\u00e9 pr\u00e9c\u00e9demment.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h3>E.dec4 : Pr\u00e9dicats d\u00e9finis par plusieurs clauses<\/h3>\n<p>Un pr\u00e9dicat peut \u00eatre d\u00e9fini par plusieurs clauses, comme le montre l&rsquo;exemple suivant :<\/p>\n<pre><code>polyvalent(J) :- peut(J, tank), peut(J,soigneur).\npolyvalent(J) :- peut(J,dps), peut(J,soigneur).\n<\/code><\/pre>\n<p>Chacune des clauses sp\u00e9cifie une fa\u00e7on de satisfaire le pr\u00e9dicat <code>polyvalent<\/code> :<\/p>\n<ol>\n<li>Si <code>J<\/code> peut tanker et si <code>J<\/code> peut soigner alors  <code>J<\/code> est polyvalent.<\/li>\n<li>Si <code>J<\/code> peut faire des d\u00e9g\u00e2ts (<code>dps<\/code>) et si <code>J<\/code> peut soigner alors  <code>J<\/code> est polyvalent.<\/li>\n<\/ol>\n<p>Le but&#8230;<\/p>\n<pre><code>polyvalent(J).\n<\/code><\/pre>\n<p>&#8230;donne comme r\u00e9sultat :<\/p>\n<pre><code>J = dave\nJ = edouard\nJ = charlie\n<\/code><\/pre>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/03\/prolog3.png\" alt=\"prolog3\"><\/p>\n<h5>Exercice de d\u00e9couverte E.dec.x4<\/h5>\n<p>Pour que deux joueurs puissent former un duo, il faut respecter l&rsquo;une ou l&rsquo;autre des conditions suivantes :<\/p>\n<ul>\n<li>L&rsquo;un des joueurs peut tanker et un des joueurs peut soigner.<\/li>\n<li>L&rsquo;un des joueurs peut faire des d\u00e9g\u00e2ts (<code>dps<\/code>) et l&rsquo;autre peut soigner.<\/li>\n<\/ul>\n<p>D\u00e9finissez un pr\u00e9dicat <code>duo\/2<\/code> tel que le but <code>duo(X,Y)<\/code> soit satisfait si et seulement si <code>X<\/code> et <code>Y<\/code> peuvent former un duo. Vous devez utiliser le pr\u00e9dicat <code>peut\/2<\/code> d\u00e9fini pr\u00e9c\u00e9demment :<\/p>\n<pre><code>peut(J,A) :- jc(J,X), cc(X,A).\n<\/code><\/pre>\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<pre><code>duo(X,Y) :- peut(X,tank), peut(Y,soigneur).\nduo(X,Y) :- peut(X,dps), peut(Y,soigneur).\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<p>Parmi les nombreuses r\u00e9ponses du but&#8230;<\/p>\n<pre><code>duo(X,Y).\n<\/code><\/pre>\n<p>&#8230;il y a :<\/p>\n<pre><code>X = Y, Y = dave\nX = Y, Y = edouard\nX = Y, Y = charlie\n<\/code><\/pre>\n<p>Proposez une explication.<\/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>Dave peut tanker et soigner, ce qui permet de satisfaire la premi\u00e8re clause. Edouard est dans le m\u00eame cas. Charlie peut faire des d\u00e9g\u00e2ts et soigner, ce qui permet de satisfaire le deuxi\u00e8me clause.<\/p>\n<p>On peut \u00e9viter ce probl\u00e8me en ajoutant le but <code>X\\==Y<\/code> \u00e0 la fin de chacune des deux clauses.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h3>E.dec5 : Slots d&rsquo;entr\u00e9e et de sortie<\/h3>\n<p>Dans la suite du cours, le mot <strong>slot<\/strong> d\u00e9signera la position d&rsquo;une variable ou d&rsquo;un terme fonctionnel dans un pr\u00e9dicat. Le nombre de slots d&rsquo;un pr\u00e9dicat est donc \u00e9gal \u00e0 son arit\u00e9.<\/p>\n<p>Par exemple, dans le but&#8230;<\/p>\n<pre><code>duo(anne,dave).\n<\/code><\/pre>\n<p>&#8230;le premier slot re\u00e7oit la valeur <code>anne<\/code> et le deuxi\u00e8me la valeur <code>dave<\/code>. Ces deux slots sont utilis\u00e9s comme des <strong>entr\u00e9es<\/strong>, dans le sens ou leurs valeurs sont connues au moment de l&rsquo;invocation du pr\u00e9dicat dans un but.<\/p>\n<p>Dans ce deuxi\u00e8me exemple&#8230;<\/p>\n<pre><code>duo(anne,P).\n<\/code><\/pre>\n<p>&#8230;le premier slot est utilis\u00e9 en entr\u00e9e et le deuxi\u00e8me en <strong>sortie<\/strong>, dans le sens ou il est occup\u00e9 par une variable non instanci\u00e9e. Si le but peut \u00eatre satisfait, son ex\u00e9cution va faire remonter dans cette variable les valeurs qui permettent de le satisfaire. On r\u00e9cup\u00e9rera dans cette variable les r\u00e9sultats, donc en quelques sorte les donn\u00e9es de sortie.<\/p>\n<h5>Exercice de d\u00e9couverte E.dec.x5<\/h5>\n<p>Quels sont les slots d&rsquo;entr\u00e9e et de sortie de chacun des pr\u00e9dicats du but suivant, sachant que le premier sous-but est d&rsquo;abord \u00e9valu\u00e9, puis que le deuxi\u00e8me sous-but est ensuite \u00e9valu\u00e9 pour chaque r\u00e9ponse du premier sous-but ?<\/p>\n<pre><code>duo(X,dave),peut(X,soigneur).\n<\/code><\/pre>\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 premier slot de <code>duo<\/code> est utilis\u00e9 en sortie, car X n&rsquo;est pas instanci\u00e9e (n&rsquo;a pas de valeur) au moment de l&rsquo;ex\u00e9cution de ce premier sous-but. Le deuxi\u00e8me slot de <code>duo<\/code> est utilis\u00e9 en entr\u00e9e.<\/p>\n<p>Les <strong>deux<\/strong> slots de <code>peut<\/code> sont utilis\u00e9s en <strong>entr\u00e9es<\/strong>. En effet, apr\u00e8s chaque ex\u00e9cution r\u00e9ussie de <code>duo(X,dave)<\/code>, la variable <code>X<\/code> est instanci\u00e9e avec un joueur pouvant faire un duo avec <code>dave<\/code>. Donc au moment d&rsquo;invoquer le pr\u00e9dicat <code>peut<\/code>, si applicable, la variable <code>X<\/code> a une valeur. Le premier slot de <code>peut<\/code> est donc utilis\u00e9 en entr\u00e9e, tout comme le deuxi\u00e8me puisqu&rsquo;il contient une valeur et non une variable.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<p>Que est le r\u00e9sultat de ce but ?<\/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<pre><code>X = edouard\nX = charlie\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h3>E.dec6 : Principe d&rsquo;\u00e9valuation<\/h3>\n<p>Nous allons tenter d&rsquo;\u00e9lucider partiellement le fonctionnement de Prolog lors de l&rsquo;\u00e9valuation d&rsquo;un but.<\/p>\n<p>Pour ce faire, nous reprenons le pr\u00e9dicat <code>duo\/2<\/code> dans sa variante qui oblige \u00e0 ce que les joueurs d&rsquo;un duo soient diff\u00e9rents :<\/p>\n<pre><code>duo(X,Y) :- peut(X,tank), peut(Y,soigneur), X\\==Y.\nduo(X,Y) :- peut(X,dps), peut(Y,soigneur), X\\==Y.\n<\/code><\/pre>\n<p>Consid\u00e9rons le but :<\/p>\n<pre><code>duo(charlie,P).\n<\/code><\/pre>\n<p>Prolog va d&rsquo;abord chercher \u00e0 satisfaire le but avec <strong>la premi\u00e8re clause<\/strong> en substituant aux variables apparaissant dans la t\u00eate de la clause les arguments du but, c&rsquo;est \u00e0 dire <code>charlie<\/code> et <code>P<\/code>.<\/p>\n<pre><code>duo(charlie,P) :- peut(charlie,tank), peut(P,soigneur), charlie\\==P.\n<\/code><\/pre>\n<p>Le premier sous-but <code>peut(charlie,tank)<\/code> est d&rsquo;abord \u00e9valu\u00e9, avec r\u00e9sultat  <code>false<\/code>. Comme le premier sous-but \u00e9choue, l&rsquo;\u00e9valuation de la premi\u00e8re clause \u00e9choue.<\/p>\n<p>Prolog va alors tenter d\u00e9s satisfaire le but avec la <strong>deuxi\u00e8me clause<\/strong>. Il le ferait \u00e9galement si des solutions avaient \u00e9t\u00e9 trouv\u00e9e avec la premi\u00e8re clause, car par d\u00e9faut, toutes les solutions sont recherch\u00e9es.<\/p>\n<pre><code>duo(X,Y) :- peut(X,dps), peut(Y,soigneur), X\\==Y.\n<\/code><\/pre>\n<p>La variable d&rsquo;entr\u00e9e est remplac\u00e9e par sa valeur :<\/p>\n<pre><code>duo(charlie,P) :- peut(charlie,dps), peut(P,soigneur), charlie\\==P.\n<\/code><\/pre>\n<p>Cette fois-ci, le premier sous-but <code>peut(charlie,dps)<\/code> r\u00e9ussit. Le deuxi\u00e8me sous-but <code>peut(P,soigneur)<\/code> est donc \u00e9valu\u00e9.<\/p>\n<p>Pour chaque solution de ce deuxi\u00e8me sous-but, respectivement <code>P=charlie<\/code>, <code>P= dave<\/code> et <code>P=edouard<\/code>, le troisi\u00e8me sous-but <code>charlie\\==P<\/code> est \u00e9valu\u00e9. La premi\u00e8re des trois \u00e9valuations \u00e9choue, car le symbole <code>\\==<\/code> r\u00e9ussit si et seulement les deux valeurs compar\u00e9es sont identiques. Les deux autres \u00e9valuations r\u00e9ussissent, ce qui donne produit les deux solutions du but :<\/p>\n<pre><code>P = dave\nP = edouard\n<\/code><\/pre>\n<hr>\n<p>L&rsquo;exemple que nous venons de donner est un cas simple. L&rsquo;\u00e9valuation des buts par Prolog repose sur un m\u00e9canisme plus complexe appel\u00e9 <strong>unification<\/strong>, qui consiste \u00e0 rechercher les valeurs des variables apparaissant dans deux termes fonctionnel permettant, si applicable, de rendre ces termes identiques.<\/p>\n<p>L&rsquo;unification des termes <code>duo(charlie,P)<\/code> (le but \u00e0 \u00e9valuer) et <code>duo(X,Y)<\/code> (la t\u00eate de la premi\u00e8re clause du pr\u00e9dicat duo), conduit \u00e0 remplacer <code>X<\/code> par <code>charlie<\/code> et <code>Y<\/code> par <code>P<\/code>, ce qui revient \u00e0 une simple substitution, mais parfois c&rsquo;est plus compliqu\u00e9. Par exemple l&rsquo;unification des deux termes&#8230;<\/p>\n<pre><code>t(A,f(B))\nt(g(X,B),f(alpha))\n<\/code><\/pre>\n<p>&#8230; a pour r\u00e9sultat&#8230;<\/p>\n<pre><code>B = alpha\nA = g(X,alpha)\n<\/code><\/pre>\n<p>&#8230;qui unifie les deux termes en :<\/p>\n<pre><code>t(g(X,alpha),f(alpha))\n<\/code><\/pre>\n<p>Nous ne rentrerons pas dans le d\u00e9tail du principe d&rsquo;unification. Les exemples suivants permettent de faire la diff\u00e9rence entre comparaison avec <code>==<\/code> et unification avec <code>=<\/code> .<\/p>\n<p>Commen\u00e7ons par la comparaison :<\/p>\n<pre><code>anne == anne.    --&gt; true\nanne == charlie. --&gt; false\nanne == X.       --&gt; false\nX == Y.          --&gt; false\n<\/code><\/pre>\n<p>Et regardons maintenant les r\u00e9sultats en rempla\u00e7ant le symbole de comparaison <code>==<\/code> par le symbole d&rsquo;unification <code>=<\/code> :<\/p>\n<pre><code>anne = anne.    --&gt; true\nanne = charlie. --&gt; false\nanne = X.       --&gt; X = anne\nX = Y.          --&gt; X = Y\n<\/code><\/pre>\n<p>La comparaison est purement syntaxique. Elle a pour r\u00e9sultat <code>true<\/code> ou <code>false<\/code>. L&rsquo;unification tente d&rsquo;assigner aux variables des valeurs qui permettent de rendre les termes identiques.<\/p>\n<p>La n\u00e9gation du symbole de comparaison est not\u00e9e <code>\\==<\/code>. Le r\u00e9sultat est la n\u00e9gation logique de celui de <code>==<\/code>.<\/p>\n<p>La n\u00e9gation du symbole d&rsquo;unification est not\u00e9e <code>\\=<\/code>. Son r\u00e9sultat est <code>true<\/code> si l&rsquo;unification \u00e9choue, <code>false<\/code> si l&rsquo;unification est possible.<\/p>\n<h5>Exercice de d\u00e9couverte E.dec.x6<\/h5>\n<p>Quel est le r\u00e9sultat du but suivant :<\/p>\n<pre><code>peut(X,tank), peut(Y,soigneur), X=Y.\n<\/code><\/pre>\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<pre><code>X = Y, Y = dave\nX = Y, Y = edouard\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<p>Quel est le r\u00e9sultat du but suivant :<\/p>\n<pre><code>peut(X,tank), peut(Y,soigneur), X==Y.\n<\/code><\/pre>\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<pre><code>X = Y, Y = dave\nX = Y, Y = edouard\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<p>Quel est le r\u00e9sultat du but suivant :<\/p>\n<pre><code>peut(X,tank), peut(Y,soigneur), X\\=Y.\n<\/code><\/pre>\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<pre><code>X = dave, Y = charlie\nX = dave, Y = edouard\nX = edouard, Y = charlie\nX = edouard, Y = dave\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<p>Quel est le r\u00e9sultat du but suivant :<\/p>\n<pre><code>peut(X,tank), peut(Y,soigneur), X\\==Y.\n<\/code><\/pre>\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<pre><code>X = dave, Y = charlie\nX = dave, Y = edouard\nX = edouard, Y = charlie\nX = edouard, Y = dave\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<p>Quel est le r\u00e9sultat du but suivant :<\/p>\n<pre><code>X=Y, peut(X,tank), peut(Y,soigneur).\n<\/code><\/pre>\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<pre><code>X = Y, Y = dave\nX = Y, Y = edouard\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<p>Quel est le r\u00e9sultat du but suivant :<\/p>\n<pre><code>X==Y, peut(X,tank), peut(Y,soigneur).\n<\/code><\/pre>\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<pre><code>false\n<\/code><\/pre>\n<p>La comparaison entre deux variables diff\u00e9rentes \u00e9choue, ce qui fait \u00e9chouer le but, alors que dans l&rsquo;exemple pr\u00e9c\u00e9dent, l&rsquo;unification r\u00e9ussit et fait en sorte que X et Y repr\u00e9sentent la m\u00eame variable.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<p>Quel est le r\u00e9sultat du but suivant :<\/p>\n<pre><code>X\\=Y, peut(X,tank), peut(Y,soigneur).\n<\/code><\/pre>\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<pre><code>false\n<\/code><\/pre>\n<p>Comme X s&rsquo;unifie avec Y, <code>X\\=Y<\/code> \u00e9choue et le reste du but n&rsquo;est pas \u00e9valu\u00e9.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<p>R\u00e9crivez plus simplement le but suivant, sans utiliser <code>=<\/code> :<\/p>\n<pre><code>X=Y, peut(X,tank), peut(Y,soigneur).\n<\/code><\/pre>\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<pre><code>peut(X,tank), peut(X,soigneur).\n<\/code><\/pre>\n<p>D&rsquo;une mani\u00e8re g\u00e9n\u00e9rale, on a jamais besoin d&rsquo;utiliser une expression du type <code>X=Y<\/code> en Prolog parce qu&rsquo;elle se simplifie en rempla\u00e7ant toutes les occurrences de <code>X<\/code> par <code>Y<\/code>, ou r\u00e9ciproquement.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h3>E.dec7 : R\u00e9cursivit\u00e9<\/h3>\n<p>On introduit une nouvelle relation qui d\u00e9crit une hi\u00e9rarchie entre joueurs. Cette relation est d\u00e9finie par le pr\u00e9dicat <code>mentor\/2<\/code>.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/03\/prolog4.png\" alt=\"prolog4\"><\/p>\n<p>Dans le code Prolog, ce pr\u00e9dicat est d\u00e9fini par les faits suivants :<\/p>\n<pre><code>mentor(anne,charlie).\nmentor(charlie,dave).\nmentor(dave,edouard).\nmentor(anne,bart).\n<\/code><\/pre>\n<p>On d\u00e9finit un pr\u00e9dicat <code>sup<\/code>, repr\u00e9sentant le concept de sup\u00e9rieur hi\u00e9rarchique, de la mani\u00e8re suivante :<\/p>\n<pre><code>sup(S,J) :- mentor(S,J).\nsup(S,J) :- mentor(S,T), sup(T,J).\n<\/code><\/pre>\n<p>Ce pr\u00e9dicat est r\u00e9cursif. Il est d\u00e9finit par deux clauses qui pourraient \u00eatre traduite en fran\u00e7ais de la mani\u00e8re suivante.<\/p>\n<p><strong>Premi\u00e8re clause<\/strong> :<\/p>\n<blockquote>\n<p><strong>Si<\/strong> <code>S<\/code> est un mentor de <code>J<\/code>, <strong>alors<\/strong> <code>S<\/code> est un sup\u00e9rieur hi\u00e9rarchique de <code>J<\/code>.<\/p>\n<\/blockquote>\n<p><strong>Deuxi\u00e8me clause<\/strong> :<\/p>\n<blockquote>\n<p><strong>Si<\/strong> <code>S<\/code> est un mentor de <code>T<\/code> <strong>et<\/strong> si <code>T<\/code> est un sup\u00e9rieur hi\u00e9rarchique de  <code>J<\/code>, <strong>alors<\/strong> <code>S<\/code> est un sup\u00e9rieur hi\u00e9rarchique de <code>J<\/code>.<\/p>\n<\/blockquote>\n<p>Par exemple, le but&#8230;<\/p>\n<pre><code>sup(S,edouard).\n<\/code><\/pre>\n<p>&#8230;a pour r\u00e9sultat :<\/p>\n<pre><code>S = dave\nS = anne\nS = charlie\n<\/code><\/pre>\n<h5>Exercice de d\u00e9couverte E.dec.x7<\/h5>\n<p>Sans utiliser d&rsquo;interpr\u00e9teur Prolog, d\u00e9terminez le r\u00e9sultat du but suivant :<\/p>\n<pre><code>sup(charlie,J).\n<\/code><\/pre>\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<pre><code>J = dave\nJ = edouard\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<p>On dit que deux joueurs sont condisciples s&rsquo;ils ont au moins un sup\u00e9rieur hi\u00e9rarchique commun. Sp\u00e9cifiez un pr\u00e9dicat <code>cond\/2<\/code> tel que <code>cond(A,B)<\/code> est satisfait si et seulement si <code>A<\/code> et <code>B<\/code> sont condisciples.<\/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<pre><code>cond(A,B) :- sup(S,A), sup(S,B).\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<p>Dans un Prolog id\u00e9al, on devrait pouvoir donner les sous-buts d&rsquo;une clause dans n&rsquo;importe quel ordre, et \u00e9crire par exemple :<\/p>\n<pre><code>sup(S,J) :- mentor(S,J).\nsup(S,J) :- sup(T,J), mentor(S,T).\n<\/code><\/pre>\n<p>Mais en pratique, une telle impl\u00e9mentation va conduire \u00e0 des bouclages infinis lors de l&rsquo;ex\u00e9cution de certains buts.<\/p>\n<p>La bonne pratique \u00e0 respecter est de faire les appels r\u00e9cursifs le plus tardivement possible dans la liste des sous-buts des clauses r\u00e9cursives.<\/p>\n<h3>E.dec8 : N\u00e9gation et jokers<\/h3>\n<p>On dit qu&rsquo;un joueur <code>L<\/code> est leader d&rsquo;un joueur <code>J<\/code> si et seulement si <code>L<\/code> est un sup\u00e9rieur hi\u00e9rarchique de <code>J<\/code> et n&rsquo;a lui-m\u00eame aucun sup\u00e9rieur hi\u00e9rarchique.<\/p>\n<p>Pour d\u00e9finir le pr\u00e9dicat <code>leader<\/code> exprimant cette propri\u00e9t\u00e9, nous utilisons une n\u00e9gation et une variable joker :<\/p>\n<pre><code>leader(L,J) :- sup(L,J), not(mentor(_,L)).\n<\/code><\/pre>\n<p>Le premier sous-but \u00e9tant \u00e9vident, int\u00e9ressons-nous au deuxi\u00e8me :<\/p>\n<ul>\n<li>Dans <code>mentor(_,L)<\/code>, le symbole <code>_<\/code> repr\u00e9sente une variable dont la valeur n&rsquo;est pas r\u00e9utilis\u00e9e et n&rsquo;a pas d&rsquo;importance. Le but <code>mentor(_,L)<\/code> est satisfait si <code>L<\/code> a au moins un mentor, dont le nom est sans importance.<\/li>\n<li>La n\u00e9gation <code>not(mentor(_,L))<\/code> a pour r\u00e9sultat la n\u00e9gation logique de l&rsquo;\u00e9valuation de <code>mentor(_,L)<\/code>.<\/li>\n<\/ul>\n<p><strong>L&rsquo;\u00e9valuation d&rsquo;une n\u00e9gation ne peut pas assigner de variable.<\/strong> Son r\u00e9sultat est juste une valeur de v\u00e9rit\u00e9, <code>true<\/code> ou <code>false<\/code>. En d&rsquo;autres termes, les variables situ\u00e9es dans un <code>not<\/code> ne peuvent \u00eatre utilis\u00e9es comme sorties. Si elle ne sont pas instanci\u00e9es (n&rsquo;ont pas de valeur) au moment de l&rsquo;\u00e9valuation du <code>not<\/code>, elle sont consid\u00e9r\u00e9es comme des variables joker.<\/p>\n<p>Par exemple, le but&#8230;<\/p>\n<pre><code>not(leader(L,charlie)).\n<\/code><\/pre>\n<p>&#8230;a pour r\u00e9sultat <code>false<\/code>. Ce but ne permet <strong>pas<\/strong> de r\u00e9cup\u00e9rer touts les joueurs qui ne sont pas leader de Charlie, comme on aurait pu l&rsquo;esp\u00e9rer. C&rsquo;est une limitation de la n\u00e9gation en Prolog.<\/p>\n<p>Si on veut d\u00e9terminer les joueurs qui ne sont pas leader de Charlie, on peut utiliser le but suivant :<\/p>\n<pre><code>jc(J,_), not(leader(J,charlie)).\n<\/code><\/pre>\n<p>On obtient la r\u00e9ponse :<\/p>\n<pre><code>J = bart\nJ = charlie\nJ = dave\nJ = edouard\n<\/code><\/pre>\n<p>Le premier sous-but permet d&rsquo;instancier <code>J<\/code>, utilis\u00e9e en sortie, successivement avec tous les joueurs. Pour chaque valeur de <code>J<\/code> remont\u00e9e, le deuxi\u00e8me sous-but r\u00e9ussi si et seulement si la valeur de <code>J<\/code>, qui est utilis\u00e9e en entr\u00e9e, n&rsquo;est <strong>pas<\/strong> leader de Charlie.<\/p>\n<h5>Exercice de d\u00e9couverte E.dec.x8<\/h5>\n<p>Donnez le but permettant de rechercher les joueurs qui ont au moins un sup\u00e9rieur hi\u00e9rarchique et ne sont sup\u00e9rieur hi\u00e9rarchique de personne. (Le r\u00e9sultat devrait \u00eatre <code>edouard<\/code> et <code>bart<\/code>.)<\/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<pre><code>sup(_,J), not(sup(J,_)).\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<p>On veut afficher les joueurs qui ne sont pas paladin. Le but suivant ne permet pas de r\u00e9aliser cette requ\u00eate car son ex\u00e9cution retourne <code>false<\/code>.<\/p>\n<pre><code>not(jc(J,paladin)).\n<\/code><\/pre>\n<p>Proposez un moyen de produire le r\u00e9sultat attendu.<\/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<pre><code>jc(J,_), not(jc(J,paladin)).\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h3>E.dec9 : Listes<\/h3>\n<p>Prolog permet de construire et exploiter des listes repr\u00e9sent\u00e9e de la mani\u00e8re suivante. Une liste est :<\/p>\n<ul>\n<li>soit vide (on note <code>[]<\/code>),<\/li>\n<li>soit compos\u00e9e d&rsquo;un \u00e9l\u00e9ment de t\u00eate <code>T<\/code> et d&rsquo;un reste <code>R<\/code>, qui est une liste pouvant \u00eatre vide (on note <code>[T|R]<\/code>).<\/li>\n<\/ul>\n<p>Par exemple, le but&#8230;<\/p>\n<pre><code>[7,5,3] = [T|R].\n<\/code><\/pre>\n<p>&#8230;donne comme r\u00e9sultat :<\/p>\n<pre><code>R = [5, 3], T = 7\n<\/code><\/pre>\n<p>Ou encore, par exemple&#8230;<\/p>\n<pre><code>[a|[]] = L.\n<\/code><\/pre>\n<p>&#8230; produit le r\u00e9sultat :<\/p>\n<pre><code>L = [a]\n<\/code><\/pre>\n<p>Cette repr\u00e9sentation permet d\u00e9finir des pr\u00e9dicats exploitant des listes, tels que par exemple le pr\u00e9dicat <code>dernier<\/code> qui permet de r\u00e9cup\u00e9rer le dernier \u00e9l\u00e9ment d&rsquo;une liste :<\/p>\n<pre><code>dernier([D],D).\ndernier([_|R],D) :- dernier(R,D).\n<\/code><\/pre>\n<p>La premi\u00e8re clause repr\u00e9sente le cas trivial (ne n\u00e9cessitant pas d&rsquo;appel r\u00e9cursif) dans lequel la liste comporte un unique \u00e9l\u00e9ment.<\/p>\n<blockquote>\n<p>Le dernier \u00e9l\u00e9ment d&rsquo;une liste qui contient un seul \u00e9l\u00e9ment est cet \u00e9l\u00e9ment.<\/p>\n<\/blockquote>\n<p>La deuxi\u00e8me clause repr\u00e9sente le cas g\u00e9n\u00e9ral d&rsquo;une liste de plusieurs \u00e9l\u00e9ments.<\/p>\n<blockquote>\n<p><strong>Si<\/strong> D est le dernier \u00e9l\u00e9ment de la liste <code>R<\/code>, <strong>alors<\/strong> <code>D<\/code> est le dernier \u00e9l\u00e9ment de toute liste ayant pour reste <code>R<\/code>.<\/p>\n<\/blockquote>\n<p>Une chose int\u00e9ressante avec ce pr\u00e9dicat est que son deuxi\u00e8me slot peut \u00eatre utilis\u00e9 en entr\u00e9e ou en sortie. Voici deux exemples de buts qui illustrent ces deux situations :<\/p>\n<pre><code>dernier([1,2,3],D). --&gt; D=3\ndernier([1,2,3],2). --&gt; false\n<\/code><\/pre>\n<p>Dans les deux buts, le premier slot est utilis\u00e9 en entr\u00e9e. Le deuxi\u00e8me slot est utilis\u00e9 en sortie dans le premier but et en entr\u00e9e dans le deuxi\u00e8me. Le pr\u00e9dicat peut donc permettre de tester si un \u00e9l\u00e9ment donn\u00e9 est le dernier \u00e9l\u00e9ment d&rsquo;une liste et de produire le dernier \u00e9l\u00e9ment d&rsquo;une liste.<\/p>\n<p>Dans le cas o\u00f9 la liste d&rsquo;entr\u00e9e est vide, le r\u00e9sultat est toujours <code>false<\/code> :<\/p>\n<pre><code>dernier([],D). --&gt; false\n<\/code><\/pre>\n<h5>Exercice de d\u00e9couverte E.dec.x9<\/h5>\n<p>On veut d\u00e9finir un pr\u00e9dicat <code>addFin<\/code> tel que si <code>L<\/code> est une liste connue, <code>F<\/code> un \u00e9l\u00e9ment connu, ce qui suppose que les deux premiers slots sont utilis\u00e9 en entr\u00e9es, et <code>R<\/code> est une variable de sortie (non instanci\u00e9e), alors le but&#8230;<\/p>\n<pre><code>addFin(L,F,R)\n<\/code><\/pre>\n<p>&#8230;fait remonter dans <code>R<\/code> la liste obtenue en ajoutant <code>F<\/code> \u00e0 la fin de <code>L<\/code>.<\/p>\n<p>Par exemple,<\/p>\n<pre><code>addFin([1,2,3],4,L).\n<\/code><\/pre>\n<p>&#8230;a pour r\u00e9sultat :<\/p>\n<pre><code>L = [1, 2, 3, 4]\n<\/code><\/pre>\n<p>voici la d\u00e9finition du pr\u00e9dicat <code>addFin<\/code> \u00e0 compl\u00e9ter.<\/p>\n<pre><code>addFin([],F,[F]).\naddFin([T|Q],F,[T|R]) :- \u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026 .\n<\/code><\/pre>\n<p>La premi\u00e8re clause dit :<\/p>\n<blockquote>\n<p>Ajouter un \u00e9l\u00e9ment <code>F<\/code> \u00e0 la fin d&rsquo;une liste vide revient \u00e0 produire la liste <code>[F]<\/code>.<\/p>\n<\/blockquote>\n<p>La deuxi\u00e8me clause dit :<\/p>\n<blockquote>\n<p>La liste de sortie (troisi\u00e8me slot) obtenue en ajoutant l&rsquo;\u00e9l\u00e9ment <code>F<\/code> (entr\u00e9e, deuxi\u00e8me slot)) \u00e0 la fin d&rsquo;une liste <code>[T|Q]<\/code> (entr\u00e9e, premier slot) a pour t\u00eate <code>T<\/code> et pour reste la liste <code>R<\/code> obtenue en&#8230;<\/p>\n<\/blockquote>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<blockquote>\n<p>La liste de sortie (troisi\u00e8me slot) obtenue en ajoutant l&rsquo;\u00e9l\u00e9ment <code>F<\/code> (entr\u00e9e, deuxi\u00e8me slot)) \u00e0 la fin d&rsquo;une liste <code>[T|Q]<\/code> (entr\u00e9e, premier slot) a pour t\u00eate <code>T<\/code> et pour reste la liste <code>R<\/code> obtenue en ajoutant <code>F<\/code> \u00e0 la fin de <code>Q<\/code>.<\/p>\n<\/blockquote>\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\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code>addFin([],F,[F]).\naddFin([T|Q],F,[T|R]) :- addFin(Q,F,R).\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<p>Bien que, lors de la conception du pr\u00e9dicat, nous ayant raisonn\u00e9 en consid\u00e9rant que le premier et le deuxi\u00e8me slots \u00e9taient des entr\u00e9es et le troisi\u00e8me des sorties, il est parfaitement possible d&rsquo;utiliser le pr\u00e9dicat de mani\u00e8re diff\u00e9rente.<\/p>\n<p>Donnez le but permettant de r\u00e9cup\u00e9rer dans une variable <code>D<\/code> le dernier \u00e9l\u00e9ment de la liste <code>[1,2,3]<\/code> et dans une variable <code>L<\/code> tous les \u00e9l\u00e9ments de cette m\u00eame liste sauf le dernier.<\/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<pre><code>addFin(L,D,[1,2,3]).\n<\/code><\/pre>\n<p>Le r\u00e9sultat obtenu est :<\/p>\n<pre><code>D = 3, L = [1, 2]\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<p>Donnez la d\u00e9finition d&rsquo;un pr\u00e9dicat <code>der<\/code> \u00e9quivalent au pr\u00e9dicat dernier de la section E.dec9 avec une seule clause faisant appel au pr\u00e9dicat <code>addFin<\/code>.<\/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<pre><code>der(L,D) :- addFin(_,D,L).\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h3>E.dec10 : Arithm\u00e9tique<\/h3>\n<p>Prolog n&rsquo;est pas un as de l&rsquo;arithm\u00e9tique, mais il est capable de r\u00e9aliser des calculs. Voici quelques exemples.<\/p>\n<pre><code>X is 1 + 2.              --&gt; X=3\nA is 3 * 3, B is A + 1.  --&gt; A=9, B=10\n<\/code><\/pre>\n<p>L&rsquo;utilisation du mot-cl\u00e9 <code>is<\/code> est indispensable pour r\u00e9aliser un calcul arithm\u00e9tique, et un tel calcul n&rsquo;est r\u00e9alisable que si les valeurs de tous les op\u00e9randes sont connues.<\/p>\n<p>Par exemple&#8230;<\/p>\n<pre><code>10 is Y + 2.\n<\/code><\/pre>\n<p>&#8230;produit un message d&rsquo;erreur indiquant que certains op\u00e9randes ne sont pas instanci\u00e9s, autrement dit, que la variable <code>Y<\/code> n&rsquo;a pas de valeur.<\/p>\n<p>Voici deux autres buts qui utilisent une expression arithm\u00e9tique sans r\u00e9aliser de calcul :<\/p>\n<pre><code>X = 1 + 2.   --&gt; X = 1+2\nX == 1 + 2.  --&gt; false\n<\/code><\/pre>\n<p>Dans le premier cas, la variable <code>X<\/code> est instanci\u00e9e avec l&rsquo;expression <code>1+2<\/code>, qui est un terme fonctionnel, alias de <code>+(1,2)<\/code>. Comme le mot-cl\u00e9 <code>is<\/code> n&rsquo;est pas pr\u00e9sent, le calcul n&rsquo;est pas r\u00e9alis\u00e9.<\/p>\n<p>Dans le deuxi\u00e8me cas, la comparaison syntaxique de <code>X<\/code> et <code>1+2<\/code> \u00e9choue.<\/p>\n<p>Voici la d\u00e9finition d&rsquo;un pr\u00e9dicat permettant de calculer $2^n$ pour une valeur $n$ donn\u00e9e en entr\u00e9e.<\/p>\n<pre><code>pow2(0,1).\npow2(N,R) :- N&gt;0, \n             N1 is N-1, \n             pow2(N1,R1), \n             R is 2*R1.\n<\/code><\/pre>\n<p>Ce pr\u00e9dicat n&rsquo;est pas r\u00e9versible en raison de l&rsquo;utilisation de <code>is<\/code> pour r\u00e9aliser des calculs arithm\u00e9tiques. Le premier slot n&rsquo;est utilisable qu&rsquo;en entr\u00e9e et le deuxi\u00e8me en sortie.<\/p>\n<p>La premi\u00e8re clause dit que $2^0$ vaut 1.<\/p>\n<p>La deuxi\u00e8me clause permet de calculer r\u00e9cursivement $2^N$ pour $N&gt;0$.<\/p>\n<ul>\n<li>Le premier sous-but fait \u00e9chouer la clause si la valeur d&rsquo;entr\u00e9e <code>N<\/code> est n\u00e9gative ou nulle, pour \u00e9viter un bouclage infini.<\/li>\n<li>Le deuxi\u00e8me sous-but, <code>N1 is N-1<\/code>, calcule la valeur <code>N-1<\/code> avec r\u00e9sultat dans la variable <code>N1<\/code>.<\/li>\n<li>Le troisi\u00e8me sous-but <code>pow2(N1,R1)<\/code> calcule r\u00e9cursivement $2^{N-1}$ avec r\u00e9sultat dans <code>R1<\/code>.<\/li>\n<li>Le quatri\u00e8me sous-but <code>R is 2*R1<\/code> calcule le r\u00e9sultat final $2 \\cdot 2^{N-1} = 2^N$.<\/li>\n<\/ul>\n<p>Il faut reconnaitre que la syntaxe est lourde. C&rsquo;est d\u00fb au fait que Prolog ne permet pas l&rsquo;utilisation de fonctions avec valeurs de retours et que la composition de plusieurs \u00e9tapes de calcul n\u00e9cessite de faire remonter chaque r\u00e9sultat interm\u00e9diaire dans un slot de sortie ou dans une variable r\u00e9cup\u00e9rant le r\u00e9sultat d&rsquo;un calcul r\u00e9alis\u00e9 via <code>is<\/code>.<\/p>\n<h5>Exercice de d\u00e9couverte E.dec.x10<\/h5>\n<p>Compl\u00e9tez la d\u00e9finition du pr\u00e9dicat <code>pow\/3<\/code> qui a pour r\u00f4le de calculer $X^N$ pour une valeur $X$ et une valeur $N$ donn\u00e9es. Les deux premiers slots sont les entr\u00e9es correspondant \u00e0 $X$ et $N$. Le troisi\u00e8me slot est la sortie permettant de r\u00e9cup\u00e9rer le r\u00e9sultat.<\/p>\n<pre><code>pow(_,0,1).\npow(X,N,R) :- N &gt; 0,\n              N1 is N - 1,\n              pow(\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026),\n              P is \u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026 .\n<\/code><\/pre>\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<pre><code>pow(_,0,1).\npow(X,N,R) :- N &gt; 0,\n              N1 is N - 1,\n              pow(X,N1,R1),\n              R is X * R1 .\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<p>Compl\u00e9tez la d\u00e9finition du pr\u00e9dicat <code>long\/2<\/code> pour qu&rsquo;il permette de calculer la longueur d&rsquo;une liste donn\u00e9e en entr\u00e9e via le premier slot.<\/p>\n<pre><code>long([],\u2026\u2026).\nlong([_|Q],N) :- long(\u2026\u2026\u2026\u2026\u2026\u2026), N is \u2026\u2026\u2026\u2026\u2026 .\n<\/code><\/pre>\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<pre><code>long([],0).\nlong([_|Q],N) :- long(Q,N1), N is N1 + 1.\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h3>E.dec11 : Termes fonctionnels<\/h3>\n<p>On peut repr\u00e9senter des arbres, notamment, \u00e0 l&rsquo;aide de termes fonctionnels. Voici un exemple d&rsquo;arbre et une repr\u00e9sentation de cet arbre.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/03\/prolog5.png\" alt=\"prolog5\"><\/p>\n<p>Les symboles fonctionnels n et f sont tout \u00e0 fait arbitraires. On aurait pu utiliser n&rsquo;importe quels autres symboles pour d\u00e9signer les feuilles et les noeuds, comme par exemple <code>node<\/code> et <code>leaf<\/code>.<\/p>\n<p>Voici un pr\u00e9dicat qui v\u00e9rifie si une valeur est dans un arbre. Les deux slots sont des entr\u00e9es.<\/p>\n<pre><code>isIn(X, n(X,_,_)).\nisIn(X, n(_,G,_)) :- isIn(X,G).\nisIn(X, n(_,_,D)) :- isIn(X,D).\n<\/code><\/pre>\n<p>Voici deux exemples de buts et leur r\u00e9sultats :<\/p>\n<pre><code>isIn(7, n(5,n(7,f,f),n(6,f,f))). --&gt; true\nisIn(2, n(5,n(7,f,f),n(6,f,f))). --&gt; false\n<\/code><\/pre>\n<p>Revenons \u00e0 la d\u00e9finition du pr\u00e9dicat.<\/p>\n<ul>\n<li>La premi\u00e8re clause dit qu&rsquo;une valeur <code>X<\/code> est dans tout arbre s&rsquo;il elle est attach\u00e9e \u00e0 sa racine.<\/li>\n<li>La deuxi\u00e8me clause dit que si une valeur X est dans le fils gauche d&rsquo;un arbre, alors elle est dans cet arbre.<\/li>\n<li>La troisi\u00e8me clause dit que si une valeur X est dans le fils droit d&rsquo;un arbre, alors elle est dans cet arbre.<\/li>\n<\/ul>\n<p>On peut noter que la cas de l&rsquo;appartenance d&rsquo;une valeur \u00e0 une feuille n&rsquo;est pas couvert explicitement. En effet, un but du type&#8230;<\/p>\n<pre><code>isIn(X,f).\n<\/code><\/pre>\n<p>&#8230; retourne toujours <code>false<\/code> car aucune des clause ne permet d&rsquo;unifier <code>f<\/code> avec le terme apparaissant dans le deuxi\u00e8me slot du pr\u00e9dicat <code>isIn<\/code> : le terme <code>f<\/code> ne peut s&rsquo;unifier ni avec <code>n(X,_,_)<\/code>, ni avec <code>n(_,G,_)<\/code>, ni avec <code>n(_,_,D)<\/code>.<\/p>\n<h5>Exercice de d\u00e9couverte E.dec.x11<\/h5>\n<p>Compl\u00e9tez la d\u00e9finition suivante pour que le pr\u00e9dicat <code>somme\/2<\/code> permette le calcul de la somme des \u00e9tiquettes d&rsquo;un arbre donn\u00e9 en entr\u00e9e dans le premier slot.<\/p>\n<pre><code>somme(f,0).\nsomme(n(X,G,D), S) :- \u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026 ,\n                      \u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026 ,\n                      \u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026 .\n<\/code><\/pre>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code>somme(f,0).\nsomme(n(X,G,D), S) :- somme(G,S1),\n                      \u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026 ,\n                      \u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026 .\n<\/code><\/pre>\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\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code>somme(f,0).\nsomme(n(X,G,D), S) :- somme(G,S1),\n                      somme(D,S2),\n                      S is X + S1 + S2 .\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h3>E.dec12 : Coupe-choix<\/h3>\n<p>Le pr\u00e9dicat <code>isIn<\/code> de la section pr\u00e9c\u00e9dente ne  permet pas seulement de d\u00e9terminer si une valeur donn\u00e9e est dans un arbre donn\u00e9. Il permet aussi de produire toutes les valeurs qui sont dans un arbre donn\u00e9. Par exemple, le but&#8230;<\/p>\n<pre><code>isIn(E,n(5,n(7,f,f),n(6,f,f))).\n<\/code><\/pre>\n<p>&#8230;produit le r\u00e9sultat suivant :<\/p>\n<pre><code>E = 5\nE = 7\nE = 6\n<\/code><\/pre>\n<p>Il est possible d&rsquo;arr\u00eater l&rsquo;\u00e9num\u00e9ration \u00e0 la premi\u00e8re valeur trouv\u00e9e en utilisant un <strong>coupe-choi<\/strong>x, not\u00e9 <code>!<\/code>.<\/p>\n<pre><code>isIn(X, n(X,_,_)) :- !.\nisIn(X, n(_,G,_)) :- isIn(X,G), !.\nisIn(X, n(_,_,D)) :- isIn(X,D).\n<\/code><\/pre>\n<p>Cette version ne permet plus d&rsquo;\u00e9num\u00e9rer toutes les valeurs des \u00e9tiquettes d&rsquo;un arbre donn\u00e9 en entr\u00e9e mais s&rsquo;arr\u00eate \u00e0 la valeur racine. Elle reste utilisable pour d\u00e9terminer si une valeur donn\u00e9e est dans un arbre donn\u00e9 et est plus efficace que la version pr\u00e9c\u00e9dente dans cet usage.<\/p>\n<p>Mais comment \u00e7a fonctionne ?<\/p>\n<p>Sans coupe-choix, lors de l&rsquo;\u00e9valuation d&rsquo;un but bas\u00e9 sur un pr\u00e9dicat d\u00e9finit par plusieurs clauses, Prolog va successivement tenter de satisfaire le but avec chacune des clauses, qui sont consid\u00e9r\u00e9es comme autant de choix possibles.<\/p>\n<p>Si l&rsquo;\u00e9valuation de la premi\u00e8re clause r\u00e9ussi, le coupe choix est activ\u00e9, ce qui supprime les autres choix en attente. Les clauses suivantes ne seront pas prises en compte.<\/p>\n<p>Si l&rsquo;\u00e9valuation de la premi\u00e8re clause \u00e9choue, une tentative est faite avec la deuxi\u00e8me. Si elle r\u00e9ussit jusqu&rsquo;au sous-but situ\u00e9 avant le coupe choix, le choix en attente, correspondant \u00e0 la troisi\u00e8me clause, est annul\u00e9.<\/p>\n<p>Si l&rsquo;\u00e9valuation de la deuxi\u00e8me clause \u00e9choue avant que le coupe choix soit atteint, une tentative set faite avec la troisi\u00e8me clause.<\/p>\n<h5>Exercice de d\u00e9couverte E.dec.x12<\/h5>\n<p>Que se passe-t-il lors de l&rsquo;\u00e9valuation du but suivant ? L&rsquo;un des coupe choix est-il atteint ?<\/p>\n<pre><code>isIn(3, f).\n<\/code><\/pre>\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>Une tentative de satisfaire le but est faite avec chacune des trois clauses, avec \u00e0 chaque foi un \u00e9chec. Aucun coupe choix n&rsquo;est activ\u00e9.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<p>Expliquez dans quelle circonstance et pourquoi l&rsquo;\u00e9valuation peut \u00eatre plus rapide avec cette variante du pr\u00e9dicat <code>isIn<\/code>.<\/p>\n<pre><code>isIn(_, f) :- !, fail.\nisIn(X, n(X,_,_)) :- !.\nisIn(X, n(_,G,_)) :- isIn(X,G), !.\nisIn(X, n(_,_,D)) :- isIn(X,D).\n<\/code><\/pre>\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 l&rsquo;arbre donn\u00e9 en entr\u00e9e n&rsquo;est pas une feuille, la premi\u00e8re clause \u00e9choue avant d&rsquo;atteindre le coupe choix et le fonctionnement est similaire a celui observ\u00e9 avec la variante pr\u00e9c\u00e9dente \u00e0 trois clauses. Dans ce cas, l&rsquo;\u00e9valuation est un peu plus lente. (Ce n&rsquo;est pas perceptible en pratique.)<\/p>\n<p>Si l&rsquo;arbre est une feuille <code>f<\/code>, alors l&rsquo;\u00e9valuation de la t\u00eate de la premi\u00e8re clause r\u00e9ussi, le coupe choix est atteint, ce qui \u00e9limine les choix en attente, et le sous-but <code>fail<\/code> fait \u00e9chouer le but. Dans ce cas, l&rsquo;\u00e9valuation est un peu plus rapide car elle s&rsquo;arr\u00eate \u00e0 la premi\u00e8re clause.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<p>Que se passerait-il si on pla\u00e7ait le coupe choix de la troisi\u00e8me clause comme ceci ?<\/p>\n<pre><code>isIn(_, f) :- !, fail.\nisIn(X, n(X,_,_)) :- !.\nisIn(X, n(_,G,_)) :- !, isIn(X,G).\nisIn(X, n(_,_,D)) :- isIn(X,D).\n<\/code><\/pre>\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 l&rsquo;arbre d&rsquo;entr\u00e9e n&rsquo;est pas une feuille et si la valeur <code>X<\/code> n&rsquo;est pas son \u00e9tiquette racine, alors :<\/p>\n<ul>\n<li>Les deux premi\u00e8res clauses \u00e9chouent avant d&rsquo;atteindre le coupe choix.<\/li>\n<li>L&rsquo;\u00e9valuation de la t\u00eate de la troisi\u00e8me clause r\u00e9ussi (la variable <code>G<\/code> est instanci\u00e9e avec la sous-arbre gauche) et le coupe choix est activ\u00e9. La quatri\u00e8me clause ne sera donc jamais prise en consid\u00e9ration. La recherche se limitera au chemin partant de la racine de l&rsquo;arbre d&rsquo;entr\u00e9e et passant uniquement par les fils gauches.<\/li>\n<\/ul>\n<p>Cette variante est donc incorrecte. La position d&rsquo;un coupe choix dans la d\u00e9finition d&rsquo;une clause est importante et doit \u00eatre d\u00e9termin\u00e9e au cas par cas.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<p>Revenons succinctement sur le <code>false<\/code> parasite observ\u00e9 lors du r\u00e9sultat de certains buts, comme celui-ci&#8230;<\/p>\n<pre><code>jc(X,Y),cc(Y,dps).\n<\/code><\/pre>\n<p>qui utilise les pr\u00e9dicats d\u00e9finis dans la premi\u00e8re section&#8230;<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/03\/prolog1.png\" alt=\"prolog1\"><\/p>\n<p>&#8230;et fournit le r\u00e9sultat suivant :<\/p>\n<pre><code>X = anne, Y = voleur\nX = bart, Y = mage\nX = charlie, Y = druide\nfalse\n<\/code><\/pre>\n<p>Le <code>false<\/code> final est d\u00fb au fait que lorsque la troisi\u00e8me r\u00e9ponse est donn\u00e9e, il reste encore des choix en attente. Rappelons la d\u00e9finition du pr\u00e9dicat <code>jc<\/code> :<\/p>\n<pre><code>jc(anne,voleur).\njc(bart,mage).\njc(charlie,druide).\njc(dave,paladin).\njc(edouard,paladin).\n<\/code><\/pre>\n<p>La troisi\u00e8me r\u00e9ponse de l&rsquo;\u00e9valuation du but, <code>X = charlie<\/code>, <code>Y = druid<\/code>, est donn\u00e9e par la troisi\u00e8me clause du pr\u00e9dicat <code>jc<\/code>  c&rsquo;est \u00e0 dire <code>jc(charlie,druide)<\/code> et est confirm\u00e9e par le deuxi\u00e8me sous-but <code>cc(druide,dps)<\/code>. Mais apr\u00e8s avoir produit cette solution , Prolog continue \u00e0 en chercher d&rsquo;autres en essayant les deux clauses restantes du pr\u00e9dicat <code>jc<\/code>. Ces tentatives \u00e9chouent en raison du deuxi\u00e8me sous-but, et c&rsquo;est pourquoi la valeur <code>false<\/code> est finalement produite.<\/p>\n<p>On pourrait arr\u00eater la recherche d\u00e8s la premi\u00e8re solution trouv\u00e9e en utilisant un coupe-choix :<\/p>\n<pre><code>jc(X,Y),cc(Y,dps),!.\n--&gt; X = anne, Y = voleur\n<\/code><\/pre>\n<p>Il n&rsquo;y a plus de <code>false<\/code> parasite, mais une seule solution est produite.<\/p>\n<h2>Activit\u00e9 d&rsquo;entra\u00eenement E.ent<\/h2>\n<h3>E.ent1 : Exercices sur les listes<\/h3>\n<h4>Exercice d&rsquo;entrainement E.ent1.1<\/h4>\n<p>Vous devez d\u00e9finir le pr\u00e9dicat <code>isIn\/2<\/code> permettant de d\u00e9terminer si une valeur appartient \u00e0 une liste ou d&rsquo;\u00e9num\u00e9rer tous les \u00e9l\u00e9ments d&rsquo;une liste.<\/p>\n<p>Le but&#8230;<\/p>\n<pre><code>isIn(X_out, L_in).\n<\/code><\/pre>\n<p>&#8230;doit faire remonter dans la variable de sortie <code>X_out<\/code> tous les \u00e9l\u00e9ments de la liste d&rsquo;entr\u00e9e <code>L_in<\/code>.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice1&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<blockquote>\n<p>L&rsquo;\u00e9l\u00e9ment de t\u00eate d&rsquo;une liste appartient \u00e0 cette liste.<\/p>\n<\/blockquote>\n<blockquote>\n<p>Lorsqu&rsquo;une liste se d\u00e9compose en une t\u00eate quelconque et un reste <code>R<\/code>, tout \u00e9l\u00e9ment <code>X<\/code> de <code>R<\/code> appartient \u00e0 cette liste.<\/p>\n<\/blockquote>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code>isIn(X, [X|_]).\nisIn(X, [_|R]) :- \u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026 .\n<\/code><\/pre>\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\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code>isIn(X, [X|_]).\nisIn(X, [_|R]) :- isIn(X,R).\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h4>Exercice d&rsquo;entrainement E.ent1.2<\/h4>\n<p>D\u00e9finissez le pr\u00e9dicat <code>retire\/3<\/code> permettant de retirer d&rsquo;une liste donn\u00e9e toutes les occurrences d&rsquo;une valeur donn\u00e9e.<\/p>\n<p>Le but&#8230;<\/p>\n<pre><code>retire(X_in, L_in, R_out).\n<\/code><\/pre>\n<p>&#8230;doit faire remonter dans la variable de sortie <code>R_out<\/code> la liste obtenue en retirant de la liste <code>L_in<\/code> toutes les occurrences de la valeur <code>X_in<\/code>.<\/p>\n<p>Exemple :<\/p>\n<pre><code>retire(1, [1,2,1,1,7], R).  --&gt; R = [2,7]\n<\/code><\/pre>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice1&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>On distingue 3 cas :<\/p>\n<blockquote>\n<p>Retirer un \u00e9l\u00e9ment quelconque de la liste vide produit comme r\u00e9sultat la liste vide.<\/p>\n<\/blockquote>\n<blockquote>\n<p>Retirer toutes les occurrences de <code>X<\/code> d&rsquo;une liste <code>[X|Q]<\/code> a pour r\u00e9sultat la liste obtenue en retirant de la liste <code>Q<\/code> toutes les occurrences de <code>X<\/code>.<\/p>\n<\/blockquote>\n<blockquote>\n<p>Retirer toutes les occurrences de <code>X<\/code> d&rsquo;une liste <code>[T|Q]<\/code> dont la t\u00eate <code>T<\/code> n&rsquo;est n&rsquo;a pas la valeur <code>X<\/code> a pour r\u00e9sultat la liste ayant pout t\u00eate <code>T<\/code> et pour reste la liste obtenue en retirant de la liste <code>Q<\/code> toutes les occurrences de <code>X<\/code>.<\/p>\n<\/blockquote>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice2&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code>retire(_,[],\u2026\u2026).\nretire(X,[X|Q],R) :- \u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026 .\nretire(X,[T|Q],[T|\u2026\u2026]) :- X\\==T, \u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026 .\n<\/code><\/pre>\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\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code>retire(_,[],[]).\nretire(X,[X|Q],R) :- retire(X,Q,R).\nretire(X,[T|Q],[T|R]) :- X\\==T, retire(X,Q,R).\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<p>Donnez une autre d\u00e9finition du pr\u00e9dicat <code>retire\/3<\/code> n&rsquo;utilisant pas <code>\\==<\/code> mais utilisant des coupe-choix <code>!<\/code>.<\/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<pre><code>retire(_,[],[]) :- !.\nretire(X,[X|Q],R) :- !, retire(X,Q,R).\nretire(X,[T|Q],[T|R]) :- retire(X,Q,R).\n<\/code><\/pre>\n<p>Le premier coupe choix n&rsquo;est pas indispensable car les deux clauses suivantes \u00e9chouent si la liste d&rsquo;entr\u00e9e est vide. (La liste vide <code>[]<\/code> ne peut pas s&rsquo;unifier avec une liste <code>[_|_]<\/code> qui a au moins un \u00e9l\u00e9ment de t\u00eate.)<\/p>\n<p>Le deuxi\u00e8me coupe choix est atteint lorsque la liste d&rsquo;entr\u00e9e a pour t\u00eate une occurrence de la valeur \u00e0 retirer. Dans ce cas, la troisi\u00e8me n&rsquo;est pas invoqu\u00e9e. Elle n&rsquo;est invoqu\u00e9e que si l&rsquo;\u00e9valuation de la deuxi\u00e8me clause \u00e9choue, c&rsquo;est \u00e0 dire si la t\u00eate de la liste d&rsquo;entr\u00e9e n&rsquo;a pas la valeur <code>X<\/code>.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h4>Exercice d&rsquo;entrainement E.ent1.3<\/h4>\n<p>D\u00e9finissiez le pr\u00e9dicat <code>conc\/3<\/code> qui permet de concat\u00e9ner deux listes.<\/p>\n<p>Le but&#8230;<\/p>\n<pre><code>conc(A_in, B_in, C_out).\n<\/code><\/pre>\n<p>&#8230;doit faire remonter dans la variable de sortie <code>C_out<\/code> le r\u00e9sultat de la concat\u00e9nation des deux listes d&rsquo;entr\u00e9e <code>A_in<\/code> et <code>B_in<\/code>.<\/p>\n<p>Exemple :<\/p>\n<pre><code>conc([1,2],[3,4],L). --&gt; L = [1,2,3,4]\n<\/code><\/pre>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice1&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>On consid\u00e8re deux cas :<\/p>\n<blockquote>\n<p>Lorsque la premi\u00e8re liste d&rsquo;entr\u00e9e est vide, le r\u00e9sultat de la concat\u00e9nation est la deuxi\u00e8me liste d&rsquo;entr\u00e9e.<\/p>\n<\/blockquote>\n<blockquote>\n<p>Lorsque les listes d&rsquo;entr\u00e9e sont [T|R] et B, le r\u00e9sultat de la concat\u00e9nation est la liste ayant pour t\u00eate \u2026\u2026\u2026 et pour reste la concat\u00e9nation de \u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026 .<\/p>\n<\/blockquote>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice2&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code>conc([],B, \u2026\u2026).\nconc([T|R],B, \u2026\u2026\u2026\u2026\u2026 ) :- \u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026 .\n<\/code><\/pre>\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\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code>conc([],B,B).\nconc([T|R],B,[T|Q]) :- conc(R,B,Q).\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<p>Le pr\u00e9dicat <code>conc<\/code> illustre de mani\u00e8re magistrale la r\u00e9versibilit\u00e9 de Prolog. Il a \u00e9t\u00e9 con\u00e7u en consid\u00e9rant le seul cas ou les deux premiers slots sont des entr\u00e9es et le troisi\u00e8me une sortie, mais il peut toutefois \u00eatre utilis\u00e9 dans d&rsquo;autres situations telles que :<\/p>\n<pre><code>conc(A,[3,4],[1,2,3,4]).\n--&gt; A = [1,2]\n<\/code><\/pre>\n<pre><code>conc(A,B,[5,6]).\n--&gt; A=[], B=[5,6]\n--&gt; A=[5], B=[6]\n--&gt; A=[5,6], B=[]\n<\/code><\/pre>\n<h4>Exercice d&rsquo;entrainement E.ent1.4<\/h4>\n<p>D\u00e9finissiez le pr\u00e9dicat <code>ediff\/3<\/code> qui permet de produire la diff\u00e9rence entre deux listes. Plus pr\u00e9cis\u00e9ment, le but&#8230;<\/p>\n<pre><code>ediff(A_in, B_in, D_out).\n<\/code><\/pre>\n<p>&#8230;doit faire remonter dans la variable de sortie <code>D_out<\/code> la liste des \u00e9l\u00e9ments de <code>A_in<\/code> qui ne sont pas dans <code>B_in<\/code>.<\/p>\n<p>Exemple :<\/p>\n<pre><code>ediff([1,2,7,5],[7,3,2],R). --&gt; R = [1,5]\n<\/code><\/pre>\n<p>Vous devez utiliser le pr\u00e9dicat <code>retire\/3<\/code> d\u00e9fini dans l&rsquo;exercice E.ent1.2.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice1&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>On appelle <strong>liste initiale<\/strong> la premi\u00e8re liste d&rsquo;entr\u00e9e et <strong>liste \u00e0 soustraire<\/strong> la deuxi\u00e8me liste d&rsquo;entr\u00e9e.<\/p>\n<blockquote>\n<p>Lorsque la liste \u00e0 soustraire est vide, le r\u00e9sultat est la liste initiale.<\/p>\n<\/blockquote>\n<blockquote>\n<p>Lorsque la liste \u00e0 soustraire est de la forme <code>[T|Q]<\/code>, le r\u00e9sultat peut \u00eatre obtenu en deux \u00e9tapes :<\/p>\n<ol>\n<li>On retire <code>T<\/code> de la liste initiale.<\/li>\n<li>On soustrait <code>Q<\/code> de la liste obtenue.<\/li>\n<\/ol>\n<\/blockquote>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice2&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code>ediff(A,[], \u2026\u2026 ).\nediff(A,[T|Q],R) :- \u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026 .\n<\/code><\/pre>\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\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code>ediff(A,[],A).\nediff(A,[T|Q],R) :- retire(T,A,I), ediff(I,Q,R).\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h3>E.ent2 : Exercices sur les termes fonctionnels<\/h3>\n<h4>Exercice d&rsquo;entrainement E.ent2.1<\/h4>\n<p><strong>Insertion dans un arbre tri\u00e9.<\/strong><\/p>\n<p>On reprend la repr\u00e9sentation des arbres binaires \u00e9tiquet\u00e9s par des entiers vue dans la section E.dec11.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/03\/prolog5.png\" alt=\"prolog5\"><\/p>\n<p>On s&rsquo;int\u00e9resse aux <strong>arbres tri\u00e9s<\/strong>, qui ont les propri\u00e9t\u00e9s suivantes :<\/p>\n<ul>\n<li>Une feuille est un arbre tri\u00e9.<\/li>\n<li>Les fils d&rsquo;un arbre tri\u00e9s sont des arbres tri\u00e9s.<\/li>\n<li>Les \u00e9tiquettes situ\u00e9es dans le fils gauche d&rsquo;un arbre tri\u00e9 ont toute une valeur inf\u00e9rieure ou \u00e9gale \u00e0 celle de l&rsquo;\u00e9tiquette racine.<\/li>\n<li>Les \u00e9tiquettes situ\u00e9es dans le fils droit d&rsquo;un arbre tri\u00e9 ont toute une valeur sup\u00e9rieure \u00e0 celle de l&rsquo;\u00e9tiquette racine.<\/li>\n<\/ul>\n<p>D\u00e9finissez le pr\u00e9dicat <code>ins\/2<\/code> permettant d&rsquo;ins\u00e9rer une valeur dans un arbre tri\u00e9. Le but&#8230;<\/p>\n<pre><code>ins(X_in, T_in, R_out).\n<\/code><\/pre>\n<p>&#8230;doit produire dans la variable de sortie <code>R_out<\/code> l&rsquo;arbre tri\u00e9 obtenu en ins\u00e9rant la valeur <code>X_in<\/code> dans l&rsquo;arbre tri\u00e9 <code>T_in<\/code>.<\/p>\n<p>Exemple :<\/p>\n<pre><code>ins(4, n(5,n(3,f,f),n(6,f,f)), R).\n--&gt; R = n(5, n(3,f,n(4, f, f)), n(6,f,f))\n<\/code><\/pre>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/03\/prolog6.png\" alt=\"prolog6\"><\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice1&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code>ins(X, f, \u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026 ) :- !.\nins(X,n(Y,G,D),n(Y, \u2026\u2026\u2026 , \u2026\u2026\u2026)) :- X =&lt; Y,!, \u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026 .\nins(X,n(Y,G,D),n(Y, \u2026\u2026\u2026 , \u2026\u2026\u2026)) :- \u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026 . \n<\/code><\/pre>\n<p>On consid\u00e8re trois cas.<\/p>\n<blockquote>\n<p>Lorsque l&rsquo;arbre d&rsquo;entr\u00e9e est une feuille, l&rsquo;arbre de sortie est constitu\u00e9 d&rsquo;un unique noeud avec pour \u00e9tiquette la valeur \u00e0 ins\u00e9rer.<\/p>\n<\/blockquote>\n<blockquote>\n<p>Une deuxi\u00e8me clause doit r\u00e9aliser l&rsquo;insertion dans le cas o\u00f9 la valeur doit \u00eatre ins\u00e9r\u00e9e dans le fils gauche de l&rsquo;arbre d&rsquo;entr\u00e9e.<\/p>\n<\/blockquote>\n<blockquote>\n<p>Une troisi\u00e8me clause doit r\u00e9aliser l&rsquo;insertion dans le cas o\u00f9 la valeur doit \u00eatre ins\u00e9r\u00e9e dans le fils droit de l&rsquo;arbre d&rsquo;entr\u00e9e.<\/p>\n<\/blockquote>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice2&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code>ins(X, f, n(X,f,f)) :- !.\nins(X,n(Y,G,D),n(Y,G1,D)) :- X =&lt; Y,!, \u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026 .\nins(X,n(Y,G,D),n(Y,G,D1)) :- \u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026 .\n<\/code><\/pre>\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\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code>ins(X, f, n(X,f,f)) :- !.\nins(X,n(Y,G,D),n(Y,G1,D)) :- X =&lt; Y,!,ins(X,G,G1).\nins(X,n(Y,G,D),n(Y,G,D1)) :- ins(X,D,D1).       \n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h4>Exercice d&rsquo;entrainement E.ent2.2<\/h4>\n<p><strong>Extraction des valeurs d&rsquo;un arbre tri\u00e9.<\/strong><\/p>\n<p>Vous devez d\u00e9finir le pr\u00e9dicat <code>a2l\/2<\/code> permettant d&rsquo;extraire sous la forme d&rsquo;une liste tri\u00e9e les valeurs des \u00e9tiquettes d&rsquo;un arbre tri\u00e9. Le but&#8230;<\/p>\n<pre><code>a2l(T_in, L_out).\n<\/code><\/pre>\n<p>&#8230;doit faire remonter dans la variable <code>L_out<\/code> la liste tri\u00e9e des valeurs des \u00e9tiquettes de l&rsquo;arbre tri\u00e9 <code>T_in<\/code>.<\/p>\n<p>Exemple :<\/p>\n<pre><code>a2l(n(5,n(3,f,n(4, f, f)),n(6,f,f)),L).\n---&gt; L = [3, 4, 5, 6]\n<\/code><\/pre>\n<p>Vous pouvez utilisez le pr\u00e9dicat pr\u00e9d\u00e9fini <code>append\/3<\/code> qui r\u00e9alise la concat\u00e9nation de deux listes :<\/p>\n<pre><code>append([1,2],[3,4],C). --&gt; [1,2,3,4]\n<\/code><\/pre>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code>a2l(f,[]).\na2l(n(X,G,D),R) :- \u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026 ,\n                   \u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026 ,\n                   \u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026 .\n<\/code><\/pre>\n<p>La premi\u00e8re clause repr\u00e9sente le cas trivial (sans appel r\u00e9cursif) : une feuille ne contient aucune valeur. ce cas est tr\u00e8s important car il permet de terminer toutes les s\u00e9quences d&rsquo;appels r\u00e9cursifs du cas g\u00e9n\u00e9ral.<\/p>\n<p>La deuxi\u00e8me clause traite le cas g\u00e9n\u00e9ral dans lequel l&rsquo;arbre d&rsquo;entr\u00e9e a une \u00e9tiquette racine, un fils gauche et un fils droit. Pour produire le r\u00e9sultat, il faut produire la liste des valeurs du fils gauche, celle des valeur du fils droit, et combiner de mani\u00e8re appropri\u00e9e ces deux liste et la valeur de l&rsquo;\u00e9tiquette racine de l&rsquo;arbre d&rsquo;entr\u00e9e.<\/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\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code>a2l(f,[]).\na2l(n(X,G,D),R) :- a2l(G,L1),\n                   a2l(D,L2),\n                   append(L1,[X|L2],R).\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h4>Exercice d&rsquo;entrainement E.ent2.3<\/h4>\n<p><strong>Repr\u00e9sentation unaire des entiers.<\/strong><\/p>\n<p>On repr\u00e9sente les entiers naturels (0, 1, 2, &#8230;) par des termes fonctionnels :<\/p>\n<pre><code>z       repr\u00e9sente 0\ns(z)    repr\u00e9sente 1\ns(s(z)) repr\u00e9sente 2\netc.\n<\/code><\/pre>\n<p>D\u00e9finissez les pr\u00e9dicats <code>int2u\/2<\/code> et <code>u2int\/2<\/code> permettant de traduire la repr\u00e9sentation unaire en repr\u00e9sentation native et r\u00e9ciproquement.<\/p>\n<p>Le but&#8230;<\/p>\n<pre><code>int2u(N_in, U_out).\n<\/code><\/pre>\n<p>&#8230;fait remonter dans la variable de sortie <code>U_out<\/code> la repr\u00e9sentation unaire de l&rsquo;entier d&rsquo;entr\u00e9e <code>N_in<\/code>.<\/p>\n<p>Le but&#8230;<\/p>\n<pre><code>u2int(U_in, N_out).\n<\/code><\/pre>\n<p>&#8230;fait remonter dans la variable de sortie <code>N_out<\/code> l&rsquo;entier dont <code>U_in<\/code> est la repr\u00e9sentation unaire.<\/p>\n<p>Exemples :<\/p>\n<pre><code>int2u(3,U). --&gt; U = s(s(s(z)))\nu2int(s(s(z)),N). --&gt; N = 2\n<\/code><\/pre>\n<p>Le premier indice concerne <code>int2u<\/code>.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice1&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code>int2u(0,z) :- !.\nint2u(N,s(Y)) :- \u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026 .\n<\/code><\/pre>\n<p>La premi\u00e8re clause dit que 0 se traduit en <code>z<\/code>.<\/p>\n<p>La deuxi\u00e8me traite le cas o\u00f9 la valeur d&rsquo;entr\u00e9e est un entier <code>N<\/code> strictement positif. Dans ce cas, il va falloir calculer $N-1$, puis traduire cette valeur en repr\u00e9sentation unaire. Le r\u00e9sultat est utilis\u00e9 dans la construction du terme de sortie.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<p>Voici la d\u00e9finition compl\u00e8te de <code>int2u<\/code>.<\/p>\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<pre><code>int2u(0,z) :- !.\nint2u(N,s(Y)) :- N1 is N-1, int2u(N1,Y).\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<p>Voici maintenant un indice pour <code>u2int<\/code>.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice2&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code>u2int(z,0) :- !.\nu2int(s(Y),N) :- \u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026 .\n<\/code><\/pre>\n<p>La premi\u00e8re clause dit que <code>z<\/code> se traduit en 0.<\/p>\n<p>La deuxi\u00e8me traite le cas ou le terme d&rsquo;entr\u00e9e est de la forme <code>s(Y)<\/code>. La valeur de sortie devra \u00eatre 1 plus le r\u00e9sultat de la traduction de <code>Y<\/code>.<\/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<pre><code>u2int(z,0) :- !.\nu2int(s(Y),N) :- u2int(Y,N1), N is N1+1.\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h4>Exercice d&rsquo;entrainement E.ent2.4<\/h4>\n<p><strong>Mod\u00e9lisation de l&rsquo;addition unaire.<\/strong><\/p>\n<p>Ces deux axiomes de la th\u00e9orie de Peano mod\u00e9lisent l&rsquo;addition standard des entiers naturels :<\/p>\n<ol>\n<li>$\\forall X$ $X + z = X$<\/li>\n<li>$\\forall X \\forall Y$ $X + s(Y) = s(X + Y)$<\/li>\n<\/ol>\n<p>Les symbole $s$ et $z$ apparaissant dans ces axiomes sont ceux introduits dans l&rsquo;exercice pr\u00e9c\u00e9dent pour la repr\u00e9sentation unaire des entiers.<\/p>\n<p>D\u00e9finissez le pr\u00e9dicat <code>sum\/3<\/code> qui encode ces deux axiomes et permet de calculer la somme de deux entiers en repr\u00e9sentation unaire.<\/p>\n<p>Le but&#8230;<\/p>\n<pre><code>sum(A_in, B_in, R_out).\n<\/code><\/pre>\n<p>&#8230;produit dans la variable de sortie <code>R_out<\/code> la somme des deux entiers <code>A_in<\/code> et <code>B_in<\/code>.<\/p>\n<p>Exemple :<\/p>\n<pre><code>sum(s(z), s(s(z)), R). --&gt; R = s(s(s(z)))\n<\/code><\/pre>\n<p>Aucun coupe choix ni calcul arithm\u00e9tique r\u00e9alis\u00e9 avec <code>is<\/code> ne doit \u00eatre utilis\u00e9, de sorte que le pr\u00e9dicat sera r\u00e9versible, permettant par exemple d&rsquo;\u00e9valuer un but tel que celui-ci :<\/p>\n<pre><code>sum(s(z), B, s(s(s(z)))). --&gt; B = s(s(z))\n<\/code><\/pre>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code>sum(A,z,A).\nsum(A,s(B), \u2026\u2026\u2026\u2026\u2026 ) :- \u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026 .\n<\/code><\/pre>\n<p>Lorsque le premier terme est <code>A<\/code> et le second <code>s(B)<\/code>, comment exprimer le r\u00e9sultat en fonction de la somme de <code>A<\/code> et <code>B<\/code> ?<\/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\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code>sum(A,z,A).\nsum(A,s(B),s(R)) :- sum(A,B,R).\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h2>Activit\u00e9 E.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 capables de traiter sans difficult\u00e9 les exercices d&rsquo;assimilation.<\/p>\n<h3>E.top1<\/h3>\n<h4>Exercice de consolidation E.top1 ?\ufe0f?\ufe0f<\/h4>\n<p>D\u00e9finissez un pr\u00e9dicat <code>money\/3<\/code> tel que le but&#8230;<\/p>\n<pre><code>money(L_in, S_in, R_out).\n<\/code><\/pre>\n<p>&#8230;remonte dans <code>R_out<\/code> les listes de valeurs de la liste d&rsquo;entr\u00e9e <code>L_in<\/code> dont la somme est <code>S_in<\/code>.<\/p>\n<p>On suppose que la liste <code>L_in<\/code> contient des entiers positifs, qui repr\u00e9sentent des valeurs de pi\u00e8ces de monnaie, et que la variable d&rsquo;entr\u00e9e <code>S_in<\/code> a pour valeur un entier appel\u00e9 <strong>appoint<\/strong>.<\/p>\n<p>Exemple d&rsquo;utilisation :<\/p>\n<pre><code>money([1,1,1,2,5], 3, R).\n--&gt; R = [1,1,1]\n--&gt; R = [1,2]\n<\/code><\/pre>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<blockquote>\n<p>Lorsque l&rsquo;appoint vaut 0, le r\u00e9sultat est la liste vide, la liste d&rsquo;entr\u00e9e n&rsquo;ayant aucune importance.<\/p>\n<\/blockquote>\n<blockquote>\n<p>Dans le cas contraire, c&rsquo;est \u00e0 dire lorsque la liste d&rsquo;entr\u00e9e peut \u00eatre d\u00e9compos\u00e9e en <code>[T|Q]<\/code>, on doit consid\u00e9rer deux possibilit\u00e9s, qui seront chacune impl\u00e9ment\u00e9e par une clause :<\/p>\n<ul>\n<li>Produire l&rsquo;appoint en utilisant la valeur T (qui doit alors se retrouver dans la liste de sortie).<\/li>\n<li>Produire l&rsquo;appoint sans utiliser la valeur T.<\/li>\n<\/ul>\n<\/blockquote>\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\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code>money(_,0,[]).\nmoney([T|Q],S,[T|R]) :- S&gt;=T, S1 is S-T,\n                        money(Q,S1,R).\nmoney([_|Q],S,R) :- money(Q,S,R).\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h4>Exercice de consolidation E.top2 ?\ufe0f?\ufe0f<\/h4>\n<p>Dans le prolongement des exercices de la section E.ent2 sur l&rsquo;arithm\u00e9tique en repr\u00e9sentation unaire, vous devez d\u00e9finir un pr\u00e9dicat mod\u00e9lisant la multiplication et \u00e9crire un but permettant de donner en repr\u00e9sentation native (base 10) les solutions du syst\u00e8me d&rsquo;\u00e9quation suivant :<\/p>\n<p>$X + Y = 9$,    $X \\cdot 9 = 20$<\/p>\n<p>Les axiomes mod\u00e9lisant la multiplication sont les suivants :<\/p>\n<ol>\n<li>$\\forall X$ $X\\cdot 0 = 0$<\/li>\n<li>$\\forall X \\forall Y$ $X \\cdot s(Y) = (X \\cdot Y) + X$<\/li>\n<\/ol>\n<p>Commencez par d\u00e9finir le pr\u00e9dicat mod\u00e9lisant la multiplication en utilisant le pr\u00e9dicat <code>sum<\/code> de l&rsquo;exercice E.ent2.4.<\/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<pre><code>mul(_,z,z).\nmul(A,s(B),R) :- mul(A,B,M), sum(M,A,R).\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<p>R\u00e9digez le but codant l&rsquo;\u00e9quation \u00e0 r\u00e9soudre en utilisant les pr\u00e9dicats <code>int2u<\/code>, <code>sum<\/code>, <code>mul<\/code> et <code>u2int<\/code> d\u00e9finis dans la section E.ent2.<\/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<pre><code>int2u(9,Neuf), int2u(20,Vingt),\nsum(A,B,Neuf), mul(A,B,Vingt),\nu2int(A,X), u2int(B,Y).\n<\/code><\/pre>\n<p>En ex\u00e9cutant ce but, on obtient deux r\u00e9ponses :<\/p>\n<pre><code>X=5, Y=4\nX=4, Y=5\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h4>Exercice de consolidation E.top3 ?\ufe0f?\ufe0f?\ufe0f<\/h4>\n<p>Alice, Bob, Charlie et Dana sont les personnes participant \u00e0 une comp\u00e9tition de natation et une comp\u00e9tition de cyclisme.<\/p>\n<p>Utilisez Prolog pour d\u00e9duire le classement de ces 4 personnes \u00e0 chacune des comp\u00e9titions \u00e0 partir des informations suivantes :<\/p>\n<ol>\n<li>Alice n&rsquo;a gagn\u00e9 aucune des 2 comp\u00e9titions.<\/li>\n<li>La personne ayant gagn\u00e9 en natation est 3i\u00e8me en cyclisme.<\/li>\n<li>Alice a battu Bob en natation et Bob a battu Alice en cyclisme.<\/li>\n<li>Bob n&rsquo;est dernier \u00e0 aucune des deux comp\u00e9titions.<\/li>\n<li>Charlie a gagn\u00e9 la comp\u00e9tition de cyclisme et Dana l&rsquo;a battu en natation.<\/li>\n<\/ol>\n<p>La cl\u00e9 de la mod\u00e9lisation est un pr\u00e9dicat <code>score\/8<\/code>.<\/p>\n<pre><code>score(NA, CA, NB, CB, NC, CC, ND, CD).\n<\/code><\/pre>\n<p>Les 8 slots sont des sorties correspondant aux rangs des 4 personnes (1, 2, 3 ou 4) pour chacune des 2 comp\u00e9titions.<\/p>\n<ul>\n<li><code>NA<\/code> et <code>CA<\/code> repr\u00e9sentent les rangs d&rsquo;Alice en natation et cyclisme.<\/li>\n<li><code>NB<\/code> et <code>CB<\/code> repr\u00e9sentent les rangs de Bob en natation et cyclisme.<\/li>\n<li><code>NC<\/code> et <code>CC<\/code> repr\u00e9sentent les rangs de Charlie en natation et cyclisme.<\/li>\n<li><code>ND<\/code> et <code>CD<\/code> repr\u00e9sentent les rangs de Dana en natation et cyclisme.<\/li>\n<\/ul>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice1&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Voici une d\u00e9finition partielle du pr\u00e9dicat score :<\/p>\n<pre><code>score(NA, CA, NB, CB, NC, CC, ND, CD) :-\n  permut([1,2,3,4], [NA, NB, NC, ND]),\n  permut([1,2,3,4], [CA, CB, CC, CD]),\n  % \u00c0 compl\u00e9ter\n<\/code><\/pre>\n<p>Le pr\u00e9dicat <code>permut\/2<\/code> permet de produire toutes les permutations possibles d&rsquo;une liste. Par exemple, le but&#8230;<\/p>\n<pre><code>permut([1,2,3],P).\n<\/code><\/pre>\n<p>&#8230;a pour r\u00e9sultat :<\/p>\n<pre><code>P = [1, 2, 3]\nP = [2, 1, 3]\nP = [2, 3, 1]\nP = [1, 3, 2]\nP = [3, 1, 2]\nP = [3, 2, 1]\n<\/code><\/pre>\n<p>Les deux premiers sous-buts de la clause d\u00e9finissant le pr\u00e9dicat <code>score<\/code> vont produire toutes les combinaisons possibles des rangs des 4 personnes aux 2 comp\u00e9titions. Les sous-buts \u00e0 compl\u00e9ter doivent v\u00e9rifier si les valeurs de <code>NA<\/code>, <code>CA<\/code>, <code>NB<\/code>, <code>CB<\/code>, <code>NC<\/code>, <code>CC<\/code>, <code>ND<\/code>, <code>CD<\/code> respectent les propri\u00e9t\u00e9s 1 \u00e0 5 exprim\u00e9es dans l&rsquo;\u00e9nonc\u00e9 du probl\u00e8me.<\/p>\n<p>Avant de traiter cette partie, commencez par d\u00e9finir et tester le pr\u00e9dicat <code>permut\/2<\/code>.<\/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;Indice2&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Pour d\u00e9finir le pr\u00e9dicat <code>permut\/2<\/code>, vous pouvez utiliser un pr\u00e9dicat <code>ins\/3<\/code> permettant d&rsquo;ins\u00e9rer de toutes les mani\u00e8re possibles un \u00e9l\u00e9ment dans une liste. Le but&#8230;<\/p>\n<pre><code>ins(1,[3,3],R).\n<\/code><\/pre>\n<p>&#8230;produit le r\u00e9sultat :<\/p>\n<pre><code>R = [1, 3, 3]\nR = [3, 1, 3]\nR = [3, 3, 1]\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice3&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Voici la d\u00e9finition du pr\u00e9dicat <code>ins\/3<\/code> :<\/p>\n<pre><code>ins(E,L,[E|L]).\nins(E,[T|Q],[T|R]) :- ins(E,Q,R).\n<\/code><\/pre>\n<p>Terminez la d\u00e9finition du pr\u00e9dicat <code>permut\/2<\/code> en utilisant le pr\u00e9dicat <code>ins\/3<\/code>.<\/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;indice4&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Voici la d\u00e9finition du pr\u00e9dicat <code>permut\/2<\/code> :<\/p>\n<pre><code>permut([],[]).\npermut([T|Q],R) :- permut(Q,P), insert(T,P,R).\n<\/code><\/pre>\n<p>Vous pouvez maintenant terminer le d\u00e9finition du pr\u00e9dicat score\/8 en ajoutant les propri\u00e9t\u00e9s 1 \u00e0 5 :<\/p>\n<ol>\n<li>Alice n&rsquo;est premi\u00e8re ni en natation, ni en cyclisme.<\/li>\n<li>Le premier en natation est troisi\u00e8me en cyclisme.<\/li>\n<li>Alice bat Bob en natation, Bob bat Alice en cyclisme.<\/li>\n<li>Bob n&rsquo;est dernier ni en natation, ni en cyclisme.<\/li>\n<li>Charlie en premier en cyclisme mais Dana le bat en natation.<\/li>\n<\/ol>\n<p>Concentrez-vous d&rsquo;abord sur les propri\u00e9t\u00e9s 1 et 2.<\/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;Indice5&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>La propri\u00e9t\u00e9 1 s&rsquo;impl\u00e9mente sous la forme :<\/p>\n<pre><code>NA &gt; 1, CA &gt; 1\n<\/code><\/pre>\n<p>La propri\u00e9t\u00e9 2 est plus compliqu\u00e9e. Pour exprimer que la personne premi\u00e8re en natation est troisi\u00e8me en cyclisme, on peut utiliser un pr\u00e9dicat <code>prop2\/8<\/code> d\u00e9finit par les faits suivants :<\/p>\n<pre><code>prop2(1,3,_,_,_,_,_,_).\nprop2(_,_,1,3,_,_,_,_).\nprop2(_,_,_,_,1,3,_,_).\nprop2(_,_,_,_,_,_,1,3).\n<\/code><\/pre>\n<p>Il vous reste \u00e0 coder les propri\u00e9t\u00e9s 3 \u00e0 5.<\/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;Solution&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code>score(NA, CA, NB, CB, NC, CC, ND, CD) :-\n  permut([1,2,3,4], [NA, NB, NC, ND]),\n  permut([1,2,3,4], [CA, CB, CC, CD]),\n  NA&gt;1, CA&gt;1,\n  prop2(NA, CA, NB, CB, NC, CC, ND, CD),\n  NA&lt;NB, CB&lt;CA,\n  NB&lt;4, CB&lt;4,\n  CC==1, ND&lt;NC.\n<\/code><\/pre>\n<p>Le but suivant permet d&rsquo;obtenir la solution du probl\u00e8me :<\/p>\n<pre><code>score(NA, CA, NB, CB, NC, CC, ND, CD).\n<\/code><\/pre>\n<p>Le r\u00e9sultat est :<\/p>\n<pre><code>CA = NC, NC = 4,\nCB = NA, NA = 2,\nCC = ND, ND = 1,\nCD = NB, NB = 3\n<\/code><\/pre>\n<p>Ce qui nous donne l&rsquo;unique solution :<\/p>\n<table>\n<thead>\n<tr>\n<th><\/th>\n<th>1er<\/th>\n<th>2i\u00e8me<\/th>\n<th>3i\u00e8me<\/th>\n<th>4i\u00e8me<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td>Cyclisme ?\ufe0f<\/td>\n<td>Charlie<\/td>\n<td>Bob<\/td>\n<td>Dana<\/td>\n<td>Alice<\/td>\n<\/tr>\n<tr>\n<td>Natation ?\ufe0f<\/td>\n<td>Dana<\/td>\n<td>Alice<\/td>\n<td>Bob<\/td>\n<td>Charlie<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<\/div>\n","protected":false},"excerpt":{"rendered":"","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-354","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\/354","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=354"}],"version-history":[{"count":10,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/posts\/354\/revisions"}],"predecessor-version":[{"id":445,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/posts\/354\/revisions\/445"}],"wp:attachment":[{"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/media?parent=354"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/categories?post=354"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/tags?post=354"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}