Programmation logique et fonctionnelle – partie E
Par O. Bailleux, Maître de conférences HDR à l'université de Bourgogne.
Le langage PROLOG
Les activités #.dec (dec pour Découverte) consistent à étudier des présentations explicatives et à traiter tous les exercices de découverte proposés. Si vous ne répondez pas correctement à un exercice de découverte, revenez en arrière pour relire les explications et identifier la cause de votre erreur.
Les activités #.ent (ent pour Entrainement) consistent à traiter des exercices d’entraînement. Vous devez d’abord tenter de traiter ces exercices sans dévoiler d’indice ni regarder la solution. Vous pouvez remonter dans le document pour relire certaines explications ou consulter les solutions des exercices de découverte ou d’entraînement précédemment traités.
Activité de découverte E.dec
Introduction
Prolog est un langage de programmation déclaratif basé sur la logique du premier ordre. Il permet d’écrire en quelques lignes des programmes qui nécessiterait des pages de codes avec les langages impératifs tels que Python, Java, C ou C++ par exemple.
Mais il est difficile de parler de ce langage sans le pratiquer, donc je vous propose de commencer tout de suite à le découvrir avec les exemples.
E.dec1 : Faits et buts
Voici un exemple de relations entre des joueurs, des classes et des compétence dans un jeu de rôle.

La relation jc relie des joueurs et des classes. La relation cc relie des classes et des compétences. Voici comment ces relations peuvent être définies en Prolog.
jc(anne,voleur).
jc(bart,mage).
jc(charlie,druide).
jc(dave,paladin).
jc(edouard,paladin).
cc(voleur,dps).
cc(mage,dps).
cc(druide,dps).
cc(druide,soigneur).
cc(paladin,soigneur).
cc(paladin,tank).
cc(guerrier,tank).
Des lettres minuscules ont été utilisées pour les prénoms car en Prolog les identificateurs commençant par une majuscule représentent des variables. Il est possible d’utiliser des chaines de caractères en les mettant entre guillemets doubles.
Exercice de découverte E.dec.x1
Quels joueurs ont la compétence soigneur ?
Quels joueurs peuvent tanker et soigner ?
Charlie, Dave et Edouard sont soigneurs.
Dave et Edouard peuvent tanker et soigner.
E.dec2 : Requêtes sur des faits
En Prolog, une requête est appelée but. Voici un exemple de but avec le prédicat jc défini précédemment :
jc(X,voleur).
La réponse produite parle d’elle-même :
X = anne
Prolog recherche toutes les valuations des variables concernées qui satisfont le but. Lorsqu’il n’y a pas de variable, la réponse est true ou false :
jc(anne,voleur). --> true
jc(dave,voleur). --> false
jc(olivier,voleur). --> false
On peut formuler des buts composés de plusieurs sous-buts, comme par exemple…
jc(X,Y),cc(Y,dps).
…qui recherche les joueurs X dont la classe Y leur donne la compétence dps. On obtient la réponse :
X = anne, Y = voleur
X = bart, Y = mage
X = charlie, Y = druide
false
La valeur false à l’issue de l’énumération des solutions est un effet de bord du mécanisme d’évaluation de Prolog, que nous n’aborderons pas tout de suite. Elle peut être ignorée.
Voici une représentation graphique des solutions :

Exercice de découverte E.dec.x2
Donnez le but permettant de savoir quelles sont les compétences de Dave.
jc(dave,Classe), cc(Classe,Comp).
N’oubliez pas que les identificateurs commençant par une majuscule sont des variables. La réponse obtenue est :
Classe = paladin, Comp = soigneur
Classe = paladin, Comp = tank
Donnez le but permettant de savoir quelles sont les classes ayant la compétence dps.
cc(Classe,dps).
On obtient la réponse :
Classe = voleur
Classe = mage
Classe = druide
Quelle est la réponse donnée au but ci-dessous, et pourquoi ?
jc(anne,X),cc(X,soigneur).
La réponse est false, car il n’y a aucune valeur X telle que les 2 sous-buts jc(anne,X) et cc(X,soigneur) sont satisfaits.
Le but…
jc(anne,X),cc(X,soigneur).
…peut être formulé de la manière suivante en logique du premier ordre :
$\exists X$ $(\text{jc}(\text{anne}, X) \wedge \text{cc}(X, \text{soigneur}))$
Les identificateurs jc et cc sont des symboles relationnels et les identificateurs anne et soigneur sont des termes fonctionnels, plus précisément des constantes fonctionnelles.
E.dec3 : Clauses
Les fait ne sont pas la seule manière de définir des prédicats. On peut également le faire avec des clauses, comme dans cet exemple :
peut(J,A) :- jc(J,X), cc(X,A).
Un nouveau prédicat peut est définit. Le prédicat peut(J,A), est satisfait si et seulement si il existe une valeur X telle que jc(J,X) et cc(X,A) soient satisfaits.
Le symbole :- représente le connecteur logique implique écrit à l’envers, c’est à dire $\leftarrow$. La clause définissant le prédicat peut correspond à la formule du premier ordre suivante :
$\exists X (\text{jc}(J,X) \wedge \text{cc}(X,A))$ $\to$ $\text{peut}(J,A)$
En français, on peut définir le prédicat ainsi :
Si
Ja la classeXet siXa la compétenceA, alorsJa la compétenceA.
L’expression peut(J,A) est appelée tête de la clause, et les expressions jc(J,X) et cc(X,A) sont appelées les sous-buts de la clause.
On peut utiliser notre nouveau prédicat dans un but, tel que par exemple…
peut(charlie,A).
…qui donne la réponse :
A = dps
A = soigneur
Exercice de découverte E.dec.x3
Sans utiliser d’interpréteur Prolog, donnez les résultats du but :
peut(J, soigneur).
J = charlie
J = dave
J = edouard
Sans utiliser d’interpréteur Prolog, donnez les résultats du but :
peut(anne, tank).
false
Sans utiliser d’interpréteur Prolog, donnez les résultats du but :
peut(dave, soigneur).
true
En exécutant le but sur machine, on constate qu’un false est affiché après le true. Il ne faut pas en tenir compte. Cet affichage "parasite" est lié au mécanisme d’évaluation de Prolog, comme mentionné précédemment.
E.dec4 : Prédicats définis par plusieurs clauses
Un prédicat peut être défini par plusieurs clauses, comme le montre l’exemple suivant :
polyvalent(J) :- peut(J, tank), peut(J,soigneur).
polyvalent(J) :- peut(J,dps), peut(J,soigneur).
Chacune des clauses spécifie une façon de satisfaire le prédicat polyvalent :
- Si
Jpeut tanker et siJpeut soigner alorsJest polyvalent. - Si
Jpeut faire des dégâts (dps) et siJpeut soigner alorsJest polyvalent.
Le but…
polyvalent(J).
…donne comme résultat :
J = dave
J = edouard
J = charlie

Exercice de découverte E.dec.x4
Pour que deux joueurs puissent former un duo, il faut respecter l’une ou l’autre des conditions suivantes :
- L’un des joueurs peut tanker et un des joueurs peut soigner.
- L’un des joueurs peut faire des dégâts (
dps) et l’autre peut soigner.
Définissez un prédicat duo/2 tel que le but duo(X,Y) soit satisfait si et seulement si X et Y peuvent former un duo. Vous devez utiliser le prédicat peut/2 défini précédemment :
peut(J,A) :- jc(J,X), cc(X,A).
duo(X,Y) :- peut(X,tank), peut(Y,soigneur).
duo(X,Y) :- peut(X,dps), peut(Y,soigneur).
Parmi les nombreuses réponses du but…
duo(X,Y).
…il y a :
X = Y, Y = dave
X = Y, Y = edouard
X = Y, Y = charlie
Proposez une explication.
Dave peut tanker et soigner, ce qui permet de satisfaire la première clause. Edouard est dans le même cas. Charlie peut faire des dégâts et soigner, ce qui permet de satisfaire le deuxième clause.
On peut éviter ce problème en ajoutant le but X\==Y à la fin de chacune des deux clauses.
E.dec5 : Slots d’entrée et de sortie
Dans la suite du cours, le mot slot désignera la position d’une variable ou d’un terme fonctionnel dans un prédicat. Le nombre de slots d’un prédicat est donc égal à son arité.
Par exemple, dans le but…
duo(anne,dave).
…le premier slot reçoit la valeur anne et le deuxième la valeur dave. Ces deux slots sont utilisés comme des entrées, dans le sens ou leurs valeurs sont connues au moment de l’invocation du prédicat dans un but.
Dans ce deuxième exemple…
duo(anne,P).
…le premier slot est utilisé en entrée et le deuxième en sortie, dans le sens ou il est occupé par une variable non instanciée. Si le but peut être satisfait, son exécution va faire remonter dans cette variable les valeurs qui permettent de le satisfaire. On récupérera dans cette variable les résultats, donc en quelques sorte les données de sortie.
Exercice de découverte E.dec.x5
Quels sont les slots d’entrée et de sortie de chacun des prédicats du but suivant, sachant que le premier sous-but est d’abord évalué, puis que le deuxième sous-but est ensuite évalué pour chaque réponse du premier sous-but ?
duo(X,dave),peut(X,soigneur).
Le premier slot de duo est utilisé en sortie, car X n’est pas instanciée (n’a pas de valeur) au moment de l’exécution de ce premier sous-but. Le deuxième slot de duo est utilisé en entrée.
Les deux slots de peut sont utilisés en entrées. En effet, après chaque exécution réussie de duo(X,dave), la variable X est instanciée avec un joueur pouvant faire un duo avec dave. Donc au moment d’invoquer le prédicat peut, si applicable, la variable X a une valeur. Le premier slot de peut est donc utilisé en entrée, tout comme le deuxième puisqu’il contient une valeur et non une variable.
Que est le résultat de ce but ?
X = edouard
X = charlie
E.dec6 : Principe d’évaluation
Nous allons tenter d’élucider partiellement le fonctionnement de Prolog lors de l’évaluation d’un but.
Pour ce faire, nous reprenons le prédicat duo/2 dans sa variante qui oblige à ce que les joueurs d’un duo soient différents :
duo(X,Y) :- peut(X,tank), peut(Y,soigneur), X\==Y.
duo(X,Y) :- peut(X,dps), peut(Y,soigneur), X\==Y.
Considérons le but :
duo(charlie,P).
Prolog va d’abord chercher à satisfaire le but avec la première clause en substituant aux variables apparaissant dans la tête de la clause les arguments du but, c’est à dire charlie et P.
duo(charlie,P) :- peut(charlie,tank), peut(P,soigneur), charlie\==P.
Le premier sous-but peut(charlie,tank) est d’abord évalué, avec résultat false. Comme le premier sous-but échoue, l’évaluation de la première clause échoue.
Prolog va alors tenter dés satisfaire le but avec la deuxième clause. Il le ferait également si des solutions avaient été trouvée avec la première clause, car par défaut, toutes les solutions sont recherchées.
duo(X,Y) :- peut(X,dps), peut(Y,soigneur), X\==Y.
La variable d’entrée est remplacée par sa valeur :
duo(charlie,P) :- peut(charlie,dps), peut(P,soigneur), charlie\==P.
Cette fois-ci, le premier sous-but peut(charlie,dps) réussit. Le deuxième sous-but peut(P,soigneur) est donc évalué.
Pour chaque solution de ce deuxième sous-but, respectivement P=charlie, P= dave et P=edouard, le troisième sous-but charlie\==P est évalué. La première des trois évaluations échoue, car le symbole \== réussit si et seulement les deux valeurs comparées sont identiques. Les deux autres évaluations réussissent, ce qui donne produit les deux solutions du but :
P = dave
P = edouard
L’exemple que nous venons de donner est un cas simple. L’évaluation des buts par Prolog repose sur un mécanisme plus complexe appelé unification, qui consiste à rechercher les valeurs des variables apparaissant dans deux termes fonctionnel permettant, si applicable, de rendre ces termes identiques.
L’unification des termes duo(charlie,P) (le but à évaluer) et duo(X,Y) (la tête de la première clause du prédicat duo), conduit à remplacer X par charlie et Y par P, ce qui revient à une simple substitution, mais parfois c’est plus compliqué. Par exemple l’unification des deux termes…
t(A,f(B))
t(g(X,B),f(alpha))
… a pour résultat…
B = alpha
A = g(X,alpha)
…qui unifie les deux termes en :
t(g(X,alpha),f(alpha))
Nous ne rentrerons pas dans le détail du principe d’unification. Les exemples suivants permettent de faire la différence entre comparaison avec == et unification avec = .
Commençons par la comparaison :
anne == anne. --> true
anne == charlie. --> false
anne == X. --> false
X == Y. --> false
Et regardons maintenant les résultats en remplaçant le symbole de comparaison == par le symbole d’unification = :
anne = anne. --> true
anne = charlie. --> false
anne = X. --> X = anne
X = Y. --> X = Y
La comparaison est purement syntaxique. Elle a pour résultat true ou false. L’unification tente d’assigner aux variables des valeurs qui permettent de rendre les termes identiques.
La négation du symbole de comparaison est notée \==. Le résultat est la négation logique de celui de ==.
La négation du symbole d’unification est notée \=. Son résultat est true si l’unification échoue, false si l’unification est possible.
Exercice de découverte E.dec.x6
Quel est le résultat du but suivant :
peut(X,tank), peut(Y,soigneur), X=Y.
X = Y, Y = dave
X = Y, Y = edouard
Quel est le résultat du but suivant :
peut(X,tank), peut(Y,soigneur), X==Y.
X = Y, Y = dave
X = Y, Y = edouard
Quel est le résultat du but suivant :
peut(X,tank), peut(Y,soigneur), X\=Y.
X = dave, Y = charlie
X = dave, Y = edouard
X = edouard, Y = charlie
X = edouard, Y = dave
Quel est le résultat du but suivant :
peut(X,tank), peut(Y,soigneur), X\==Y.
X = dave, Y = charlie
X = dave, Y = edouard
X = edouard, Y = charlie
X = edouard, Y = dave
Quel est le résultat du but suivant :
X=Y, peut(X,tank), peut(Y,soigneur).
X = Y, Y = dave
X = Y, Y = edouard
Quel est le résultat du but suivant :
X==Y, peut(X,tank), peut(Y,soigneur).
false
La comparaison entre deux variables différentes échoue, ce qui fait échouer le but, alors que dans l’exemple précédent, l’unification réussit et fait en sorte que X et Y représentent la même variable.
Quel est le résultat du but suivant :
X\=Y, peut(X,tank), peut(Y,soigneur).
false
Comme X s’unifie avec Y, X\=Y échoue et le reste du but n’est pas évalué.
Récrivez plus simplement le but suivant, sans utiliser = :
X=Y, peut(X,tank), peut(Y,soigneur).
peut(X,tank), peut(X,soigneur).
D’une manière générale, on a jamais besoin d’utiliser une expression du type X=Y en Prolog parce qu’elle se simplifie en remplaçant toutes les occurrences de X par Y, ou réciproquement.
E.dec7 : Récursivité
On introduit une nouvelle relation qui décrit une hiérarchie entre joueurs. Cette relation est définie par le prédicat mentor/2.

Dans le code Prolog, ce prédicat est défini par les faits suivants :
mentor(anne,charlie).
mentor(charlie,dave).
mentor(dave,edouard).
mentor(anne,bart).
On définit un prédicat sup, représentant le concept de supérieur hiérarchique, de la manière suivante :
sup(S,J) :- mentor(S,J).
sup(S,J) :- mentor(S,T), sup(T,J).
Ce prédicat est récursif. Il est définit par deux clauses qui pourraient être traduite en français de la manière suivante.
Première clause :
Si
Sest un mentor deJ, alorsSest un supérieur hiérarchique deJ.
Deuxième clause :
Si
Sest un mentor deTet siTest un supérieur hiérarchique deJ, alorsSest un supérieur hiérarchique deJ.
Par exemple, le but…
sup(S,edouard).
…a pour résultat :
S = dave
S = anne
S = charlie
Exercice de découverte E.dec.x7
Sans utiliser d’interpréteur Prolog, déterminez le résultat du but suivant :
sup(charlie,J).
J = dave
J = edouard
On dit que deux joueurs sont condisciples s’ils ont au moins un supérieur hiérarchique commun. Spécifiez un prédicat cond/2 tel que cond(A,B) est satisfait si et seulement si A et B sont condisciples.
cond(A,B) :- sup(S,A), sup(S,B).
Dans un Prolog idéal, on devrait pouvoir donner les sous-buts d’une clause dans n’importe quel ordre, et écrire par exemple :
sup(S,J) :- mentor(S,J).
sup(S,J) :- sup(T,J), mentor(S,T).
Mais en pratique, une telle implémentation va conduire à des bouclages infinis lors de l’exécution de certains buts.
La bonne pratique à respecter est de faire les appels récursifs le plus tardivement possible dans la liste des sous-buts des clauses récursives.
E.dec8 : Négation et jokers
On dit qu’un joueur L est leader d’un joueur J si et seulement si L est un supérieur hiérarchique de J et n’a lui-même aucun supérieur hiérarchique.
Pour définir le prédicat leader exprimant cette propriété, nous utilisons une négation et une variable joker :
leader(L,J) :- sup(L,J), not(mentor(_,L)).
Le premier sous-but étant évident, intéressons-nous au deuxième :
- Dans
mentor(_,L), le symbole_représente une variable dont la valeur n’est pas réutilisée et n’a pas d’importance. Le butmentor(_,L)est satisfait siLa au moins un mentor, dont le nom est sans importance. - La négation
not(mentor(_,L))a pour résultat la négation logique de l’évaluation dementor(_,L).
L’évaluation d’une négation ne peut pas assigner de variable. Son résultat est juste une valeur de vérité, true ou false. En d’autres termes, les variables situées dans un not ne peuvent être utilisées comme sorties. Si elle ne sont pas instanciées (n’ont pas de valeur) au moment de l’évaluation du not, elle sont considérées comme des variables joker.
Par exemple, le but…
not(leader(L,charlie)).
…a pour résultat false. Ce but ne permet pas de récupérer touts les joueurs qui ne sont pas leader de Charlie, comme on aurait pu l’espérer. C’est une limitation de la négation en Prolog.
Si on veut déterminer les joueurs qui ne sont pas leader de Charlie, on peut utiliser le but suivant :
jc(J,_), not(leader(J,charlie)).
On obtient la réponse :
J = bart
J = charlie
J = dave
J = edouard
Le premier sous-but permet d’instancier J, utilisée en sortie, successivement avec tous les joueurs. Pour chaque valeur de J remontée, le deuxième sous-but réussi si et seulement si la valeur de J, qui est utilisée en entrée, n’est pas leader de Charlie.
Exercice de découverte E.dec.x8
Donnez le but permettant de rechercher les joueurs qui ont au moins un supérieur hiérarchique et ne sont supérieur hiérarchique de personne. (Le résultat devrait être edouard et bart.)
sup(_,J), not(sup(J,_)).
On veut afficher les joueurs qui ne sont pas paladin. Le but suivant ne permet pas de réaliser cette requête car son exécution retourne false.
not(jc(J,paladin)).
Proposez un moyen de produire le résultat attendu.
jc(J,_), not(jc(J,paladin)).
E.dec9 : Listes
Prolog permet de construire et exploiter des listes représentée de la manière suivante. Une liste est :
- soit vide (on note
[]), - soit composée d’un élément de tête
Tet d’un resteR, qui est une liste pouvant être vide (on note[T|R]).
Par exemple, le but…
[7,5,3] = [T|R].
…donne comme résultat :
R = [5, 3], T = 7
Ou encore, par exemple…
[a|[]] = L.
… produit le résultat :
L = [a]
Cette représentation permet définir des prédicats exploitant des listes, tels que par exemple le prédicat dernier qui permet de récupérer le dernier élément d’une liste :
dernier([D],D).
dernier([_|R],D) :- dernier(R,D).
La première clause représente le cas trivial (ne nécessitant pas d’appel récursif) dans lequel la liste comporte un unique élément.
Le dernier élément d’une liste qui contient un seul élément est cet élément.
La deuxième clause représente le cas général d’une liste de plusieurs éléments.
Si D est le dernier élément de la liste
R, alorsDest le dernier élément de toute liste ayant pour resteR.
Une chose intéressante avec ce prédicat est que son deuxième slot peut être utilisé en entrée ou en sortie. Voici deux exemples de buts qui illustrent ces deux situations :
dernier([1,2,3],D). --> D=3
dernier([1,2,3],2). --> false
Dans les deux buts, le premier slot est utilisé en entrée. Le deuxième slot est utilisé en sortie dans le premier but et en entrée dans le deuxième. Le prédicat peut donc permettre de tester si un élément donné est le dernier élément d’une liste et de produire le dernier élément d’une liste.
Dans le cas où la liste d’entrée est vide, le résultat est toujours false :
dernier([],D). --> false
Exercice de découverte E.dec.x9
On veut définir un prédicat addFin tel que si L est une liste connue, F un élément connu, ce qui suppose que les deux premiers slots sont utilisé en entrées, et R est une variable de sortie (non instanciée), alors le but…
addFin(L,F,R)
…fait remonter dans R la liste obtenue en ajoutant F à la fin de L.
Par exemple,
addFin([1,2,3],4,L).
…a pour résultat :
L = [1, 2, 3, 4]
voici la définition du prédicat addFin à compléter.
addFin([],F,[F]).
addFin([T|Q],F,[T|R]) :- ……………………………………… .
La première clause dit :
Ajouter un élément
Fà la fin d’une liste vide revient à produire la liste[F].
La deuxième clause dit :
La liste de sortie (troisième slot) obtenue en ajoutant l’élément
F(entrée, deuxième slot)) à la fin d’une liste[T|Q](entrée, premier slot) a pour têteTet pour reste la listeRobtenue en…
La liste de sortie (troisième slot) obtenue en ajoutant l’élément
F(entrée, deuxième slot)) à la fin d’une liste[T|Q](entrée, premier slot) a pour têteTet pour reste la listeRobtenue en ajoutantFà la fin deQ.
addFin([],F,[F]).
addFin([T|Q],F,[T|R]) :- addFin(Q,F,R).
Bien que, lors de la conception du prédicat, nous ayant raisonné en considérant que le premier et le deuxième slots étaient des entrées et le troisième des sorties, il est parfaitement possible d’utiliser le prédicat de manière différente.
Donnez le but permettant de récupérer dans une variable D le dernier élément de la liste [1,2,3] et dans une variable L tous les éléments de cette même liste sauf le dernier.
addFin(L,D,[1,2,3]).
Le résultat obtenu est :
D = 3, L = [1, 2]
Donnez la définition d’un prédicat der équivalent au prédicat dernier de la section E.dec9 avec une seule clause faisant appel au prédicat addFin.
der(L,D) :- addFin(_,D,L).
E.dec10 : Arithmétique
Prolog n’est pas un as de l’arithmétique, mais il est capable de réaliser des calculs. Voici quelques exemples.
X is 1 + 2. --> X=3
A is 3 * 3, B is A + 1. --> A=9, B=10
L’utilisation du mot-clé is est indispensable pour réaliser un calcul arithmétique, et un tel calcul n’est réalisable que si les valeurs de tous les opérandes sont connues.
Par exemple…
10 is Y + 2.
…produit un message d’erreur indiquant que certains opérandes ne sont pas instanciés, autrement dit, que la variable Y n’a pas de valeur.
Voici deux autres buts qui utilisent une expression arithmétique sans réaliser de calcul :
X = 1 + 2. --> X = 1+2
X == 1 + 2. --> false
Dans le premier cas, la variable X est instanciée avec l’expression 1+2, qui est un terme fonctionnel, alias de +(1,2). Comme le mot-clé is n’est pas présent, le calcul n’est pas réalisé.
Dans le deuxième cas, la comparaison syntaxique de X et 1+2 échoue.
Voici la définition d’un prédicat permettant de calculer $2^n$ pour une valeur $n$ donnée en entrée.
pow2(0,1).
pow2(N,R) :- N>0,
N1 is N-1,
pow2(N1,R1),
R is 2*R1.
Ce prédicat n’est pas réversible en raison de l’utilisation de is pour réaliser des calculs arithmétiques. Le premier slot n’est utilisable qu’en entrée et le deuxième en sortie.
La première clause dit que $2^0$ vaut 1.
La deuxième clause permet de calculer récursivement $2^N$ pour $N>0$.
- Le premier sous-but fait échouer la clause si la valeur d’entrée
Nest négative ou nulle, pour éviter un bouclage infini. - Le deuxième sous-but,
N1 is N-1, calcule la valeurN-1avec résultat dans la variableN1. - Le troisième sous-but
pow2(N1,R1)calcule récursivement $2^{N-1}$ avec résultat dansR1. - Le quatrième sous-but
R is 2*R1calcule le résultat final $2 \cdot 2^{N-1} = 2^N$.
Il faut reconnaitre que la syntaxe est lourde. C’est dû au fait que Prolog ne permet pas l’utilisation de fonctions avec valeurs de retours et que la composition de plusieurs étapes de calcul nécessite de faire remonter chaque résultat intermédiaire dans un slot de sortie ou dans une variable récupérant le résultat d’un calcul réalisé via is.
Exercice de découverte E.dec.x10
Complétez la définition du prédicat pow/3 qui a pour rôle de calculer $X^N$ pour une valeur $X$ et une valeur $N$ données. Les deux premiers slots sont les entrées correspondant à $X$ et $N$. Le troisième slot est la sortie permettant de récupérer le résultat.
pow(_,0,1).
pow(X,N,R) :- N > 0,
N1 is N - 1,
pow(…………………………),
P is ………………………… .
pow(_,0,1).
pow(X,N,R) :- N > 0,
N1 is N - 1,
pow(X,N1,R1),
R is X * R1 .
Complétez la définition du prédicat long/2 pour qu’il permette de calculer la longueur d’une liste donnée en entrée via le premier slot.
long([],……).
long([_|Q],N) :- long(………………), N is …………… .
long([],0).
long([_|Q],N) :- long(Q,N1), N is N1 + 1.
E.dec11 : Termes fonctionnels
On peut représenter des arbres, notamment, à l’aide de termes fonctionnels. Voici un exemple d’arbre et une représentation de cet arbre.

Les symboles fonctionnels n et f sont tout à fait arbitraires. On aurait pu utiliser n’importe quels autres symboles pour désigner les feuilles et les noeuds, comme par exemple node et leaf.
Voici un prédicat qui vérifie si une valeur est dans un arbre. Les deux slots sont des entrées.
isIn(X, n(X,_,_)).
isIn(X, n(_,G,_)) :- isIn(X,G).
isIn(X, n(_,_,D)) :- isIn(X,D).
Voici deux exemples de buts et leur résultats :
isIn(7, n(5,n(7,f,f),n(6,f,f))). --> true
isIn(2, n(5,n(7,f,f),n(6,f,f))). --> false
Revenons à la définition du prédicat.
- La première clause dit qu’une valeur
Xest dans tout arbre s’il elle est attachée à sa racine. - La deuxième clause dit que si une valeur X est dans le fils gauche d’un arbre, alors elle est dans cet arbre.
- La troisième clause dit que si une valeur X est dans le fils droit d’un arbre, alors elle est dans cet arbre.
On peut noter que la cas de l’appartenance d’une valeur à une feuille n’est pas couvert explicitement. En effet, un but du type…
isIn(X,f).
… retourne toujours false car aucune des clause ne permet d’unifier f avec le terme apparaissant dans le deuxième slot du prédicat isIn : le terme f ne peut s’unifier ni avec n(X,_,_), ni avec n(_,G,_), ni avec n(_,_,D).
Exercice de découverte E.dec.x11
Complétez la définition suivante pour que le prédicat somme/2 permette le calcul de la somme des étiquettes d’un arbre donné en entrée dans le premier slot.
somme(f,0).
somme(n(X,G,D), S) :- ……………………………………… ,
……………………………………… ,
……………………………………… .
somme(f,0).
somme(n(X,G,D), S) :- somme(G,S1),
……………………………………… ,
……………………………………… .
somme(f,0).
somme(n(X,G,D), S) :- somme(G,S1),
somme(D,S2),
S is X + S1 + S2 .
E.dec12 : Coupe-choix
Le prédicat isIn de la section précédente ne permet pas seulement de déterminer si une valeur donnée est dans un arbre donné. Il permet aussi de produire toutes les valeurs qui sont dans un arbre donné. Par exemple, le but…
isIn(E,n(5,n(7,f,f),n(6,f,f))).
…produit le résultat suivant :
E = 5
E = 7
E = 6
Il est possible d’arrêter l’énumération à la première valeur trouvée en utilisant un coupe-choix, noté !.
isIn(X, n(X,_,_)) :- !.
isIn(X, n(_,G,_)) :- isIn(X,G), !.
isIn(X, n(_,_,D)) :- isIn(X,D).
Cette version ne permet plus d’énumérer toutes les valeurs des étiquettes d’un arbre donné en entrée mais s’arrête à la valeur racine. Elle reste utilisable pour déterminer si une valeur donnée est dans un arbre donné et est plus efficace que la version précédente dans cet usage.
Mais comment ça fonctionne ?
Sans coupe-choix, lors de l’évaluation d’un but basé sur un prédicat définit par plusieurs clauses, Prolog va successivement tenter de satisfaire le but avec chacune des clauses, qui sont considérées comme autant de choix possibles.
Si l’évaluation de la première clause réussi, le coupe choix est activé, ce qui supprime les autres choix en attente. Les clauses suivantes ne seront pas prises en compte.
Si l’évaluation de la première clause échoue, une tentative est faite avec la deuxième. Si elle réussit jusqu’au sous-but situé avant le coupe choix, le choix en attente, correspondant à la troisième clause, est annulé.
Si l’évaluation de la deuxième clause échoue avant que le coupe choix soit atteint, une tentative set faite avec la troisième clause.
Exercice de découverte E.dec.x12
Que se passe-t-il lors de l’évaluation du but suivant ? L’un des coupe choix est-il atteint ?
isIn(3, f).
Une tentative de satisfaire le but est faite avec chacune des trois clauses, avec à chaque foi un échec. Aucun coupe choix n’est activé.
Expliquez dans quelle circonstance et pourquoi l’évaluation peut être plus rapide avec cette variante du prédicat isIn.
isIn(_, f) :- !, fail.
isIn(X, n(X,_,_)) :- !.
isIn(X, n(_,G,_)) :- isIn(X,G), !.
isIn(X, n(_,_,D)) :- isIn(X,D).
Si l’arbre donné en entrée n’est pas une feuille, la première clause échoue avant d’atteindre le coupe choix et le fonctionnement est similaire a celui observé avec la variante précédente à trois clauses. Dans ce cas, l’évaluation est un peu plus lente. (Ce n’est pas perceptible en pratique.)
Si l’arbre est une feuille f, alors l’évaluation de la tête de la première clause réussi, le coupe choix est atteint, ce qui élimine les choix en attente, et le sous-but fail fait échouer le but. Dans ce cas, l’évaluation est un peu plus rapide car elle s’arrête à la première clause.
Que se passerait-il si on plaçait le coupe choix de la troisième clause comme ceci ?
isIn(_, f) :- !, fail.
isIn(X, n(X,_,_)) :- !.
isIn(X, n(_,G,_)) :- !, isIn(X,G).
isIn(X, n(_,_,D)) :- isIn(X,D).
Si l’arbre d’entrée n’est pas une feuille et si la valeur X n’est pas son étiquette racine, alors :
- Les deux premières clauses échouent avant d’atteindre le coupe choix.
- L’évaluation de la tête de la troisième clause réussi (la variable
Gest instanciée avec la sous-arbre gauche) et le coupe choix est activé. La quatrième clause ne sera donc jamais prise en considération. La recherche se limitera au chemin partant de la racine de l’arbre d’entrée et passant uniquement par les fils gauches.
Cette variante est donc incorrecte. La position d’un coupe choix dans la définition d’une clause est importante et doit être déterminée au cas par cas.
Revenons succinctement sur le false parasite observé lors du résultat de certains buts, comme celui-ci…
jc(X,Y),cc(Y,dps).
qui utilise les prédicats définis dans la première section…

…et fournit le résultat suivant :
X = anne, Y = voleur
X = bart, Y = mage
X = charlie, Y = druide
false
Le false final est dû au fait que lorsque la troisième réponse est donnée, il reste encore des choix en attente. Rappelons la définition du prédicat jc :
jc(anne,voleur).
jc(bart,mage).
jc(charlie,druide).
jc(dave,paladin).
jc(edouard,paladin).
La troisième réponse de l’évaluation du but, X = charlie, Y = druid, est donnée par la troisième clause du prédicat jc c’est à dire jc(charlie,druide) et est confirmée par le deuxième sous-but cc(druide,dps). Mais après avoir produit cette solution , Prolog continue à en chercher d’autres en essayant les deux clauses restantes du prédicat jc. Ces tentatives échouent en raison du deuxième sous-but, et c’est pourquoi la valeur false est finalement produite.
On pourrait arrêter la recherche dès la première solution trouvée en utilisant un coupe-choix :
jc(X,Y),cc(Y,dps),!.
--> X = anne, Y = voleur
Il n’y a plus de false parasite, mais une seule solution est produite.
Activité d’entraînement E.ent
E.ent1 : Exercices sur les listes
Exercice d’entrainement E.ent1.1
Vous devez définir le prédicat isIn/2 permettant de déterminer si une valeur appartient à une liste ou d’énumérer tous les éléments d’une liste.
Le but…
isIn(X_out, L_in).
…doit faire remonter dans la variable de sortie X_out tous les éléments de la liste d’entrée L_in.
L’élément de tête d’une liste appartient à cette liste.
Lorsqu’une liste se décompose en une tête quelconque et un reste
R, tout élémentXdeRappartient à cette liste.
isIn(X, [X|_]).
isIn(X, [_|R]) :- ………………………… .
isIn(X, [X|_]).
isIn(X, [_|R]) :- isIn(X,R).
Exercice d’entrainement E.ent1.2
Définissez le prédicat retire/3 permettant de retirer d’une liste donnée toutes les occurrences d’une valeur donnée.
Le but…
retire(X_in, L_in, R_out).
…doit faire remonter dans la variable de sortie R_out la liste obtenue en retirant de la liste L_in toutes les occurrences de la valeur X_in.
Exemple :
retire(1, [1,2,1,1,7], R). --> R = [2,7]
On distingue 3 cas :
Retirer un élément quelconque de la liste vide produit comme résultat la liste vide.
Retirer toutes les occurrences de
Xd’une liste[X|Q]a pour résultat la liste obtenue en retirant de la listeQtoutes les occurrences deX.
Retirer toutes les occurrences de
Xd’une liste[T|Q]dont la têteTn’est n’a pas la valeurXa pour résultat la liste ayant pout têteTet pour reste la liste obtenue en retirant de la listeQtoutes les occurrences deX.
retire(_,[],……).
retire(X,[X|Q],R) :- ……………………………………… .
retire(X,[T|Q],[T|……]) :- X\==T, ……………………………………… .
retire(_,[],[]).
retire(X,[X|Q],R) :- retire(X,Q,R).
retire(X,[T|Q],[T|R]) :- X\==T, retire(X,Q,R).
Donnez une autre définition du prédicat retire/3 n’utilisant pas \== mais utilisant des coupe-choix !.
retire(_,[],[]) :- !.
retire(X,[X|Q],R) :- !, retire(X,Q,R).
retire(X,[T|Q],[T|R]) :- retire(X,Q,R).
Le premier coupe choix n’est pas indispensable car les deux clauses suivantes échouent si la liste d’entrée est vide. (La liste vide [] ne peut pas s’unifier avec une liste [_|_] qui a au moins un élément de tête.)
Le deuxième coupe choix est atteint lorsque la liste d’entrée a pour tête une occurrence de la valeur à retirer. Dans ce cas, la troisième n’est pas invoquée. Elle n’est invoquée que si l’évaluation de la deuxième clause échoue, c’est à dire si la tête de la liste d’entrée n’a pas la valeur X.
Exercice d’entrainement E.ent1.3
Définissiez le prédicat conc/3 qui permet de concaténer deux listes.
Le but…
conc(A_in, B_in, C_out).
…doit faire remonter dans la variable de sortie C_out le résultat de la concaténation des deux listes d’entrée A_in et B_in.
Exemple :
conc([1,2],[3,4],L). --> L = [1,2,3,4]
On considère deux cas :
Lorsque la première liste d’entrée est vide, le résultat de la concaténation est la deuxième liste d’entrée.
Lorsque les listes d’entrée sont [T|R] et B, le résultat de la concaténation est la liste ayant pour tête ……… et pour reste la concaténation de ………………………… .
conc([],B, ……).
conc([T|R],B, …………… ) :- ………………………… .
conc([],B,B).
conc([T|R],B,[T|Q]) :- conc(R,B,Q).
Le prédicat conc illustre de manière magistrale la réversibilité de Prolog. Il a été conçu en considérant le seul cas ou les deux premiers slots sont des entrées et le troisième une sortie, mais il peut toutefois être utilisé dans d’autres situations telles que :
conc(A,[3,4],[1,2,3,4]).
--> A = [1,2]
conc(A,B,[5,6]).
--> A=[], B=[5,6]
--> A=[5], B=[6]
--> A=[5,6], B=[]
Exercice d’entrainement E.ent1.4
Définissiez le prédicat ediff/3 qui permet de produire la différence entre deux listes. Plus précisément, le but…
ediff(A_in, B_in, D_out).
…doit faire remonter dans la variable de sortie D_out la liste des éléments de A_in qui ne sont pas dans B_in.
Exemple :
ediff([1,2,7,5],[7,3,2],R). --> R = [1,5]
Vous devez utiliser le prédicat retire/3 défini dans l’exercice E.ent1.2.
On appelle liste initiale la première liste d’entrée et liste à soustraire la deuxième liste d’entrée.
Lorsque la liste à soustraire est vide, le résultat est la liste initiale.
Lorsque la liste à soustraire est de la forme
[T|Q], le résultat peut être obtenu en deux étapes :
- On retire
Tde la liste initiale.- On soustrait
Qde la liste obtenue.
ediff(A,[], …… ).
ediff(A,[T|Q],R) :- …………………………………………………… .
ediff(A,[],A).
ediff(A,[T|Q],R) :- retire(T,A,I), ediff(I,Q,R).
E.ent2 : Exercices sur les termes fonctionnels
Exercice d’entrainement E.ent2.1
Insertion dans un arbre trié.
On reprend la représentation des arbres binaires étiquetés par des entiers vue dans la section E.dec11.

On s’intéresse aux arbres triés, qui ont les propriétés suivantes :
- Une feuille est un arbre trié.
- Les fils d’un arbre triés sont des arbres triés.
- Les étiquettes situées dans le fils gauche d’un arbre trié ont toute une valeur inférieure ou égale à celle de l’étiquette racine.
- Les étiquettes situées dans le fils droit d’un arbre trié ont toute une valeur supérieure à celle de l’étiquette racine.
Définissez le prédicat ins/2 permettant d’insérer une valeur dans un arbre trié. Le but…
ins(X_in, T_in, R_out).
…doit produire dans la variable de sortie R_out l’arbre trié obtenu en insérant la valeur X_in dans l’arbre trié T_in.
Exemple :
ins(4, n(5,n(3,f,f),n(6,f,f)), R).
--> R = n(5, n(3,f,n(4, f, f)), n(6,f,f))

ins(X, f, ………………………… ) :- !.
ins(X,n(Y,G,D),n(Y, ……… , ………)) :- X =< Y,!, ……………………………………… .
ins(X,n(Y,G,D),n(Y, ……… , ………)) :- ……………………………………… .
On considère trois cas.
Lorsque l’arbre d’entrée est une feuille, l’arbre de sortie est constitué d’un unique noeud avec pour étiquette la valeur à insérer.
Une deuxième clause doit réaliser l’insertion dans le cas où la valeur doit être insérée dans le fils gauche de l’arbre d’entrée.
Une troisième clause doit réaliser l’insertion dans le cas où la valeur doit être insérée dans le fils droit de l’arbre d’entrée.
ins(X, f, n(X,f,f)) :- !.
ins(X,n(Y,G,D),n(Y,G1,D)) :- X =< Y,!, ……………………………………… .
ins(X,n(Y,G,D),n(Y,G,D1)) :- ……………………………………… .
ins(X, f, n(X,f,f)) :- !.
ins(X,n(Y,G,D),n(Y,G1,D)) :- X =< Y,!,ins(X,G,G1).
ins(X,n(Y,G,D),n(Y,G,D1)) :- ins(X,D,D1).
Exercice d’entrainement E.ent2.2
Extraction des valeurs d’un arbre trié.
Vous devez définir le prédicat a2l/2 permettant d’extraire sous la forme d’une liste triée les valeurs des étiquettes d’un arbre trié. Le but…
a2l(T_in, L_out).
…doit faire remonter dans la variable L_out la liste triée des valeurs des étiquettes de l’arbre trié T_in.
Exemple :
a2l(n(5,n(3,f,n(4, f, f)),n(6,f,f)),L).
---> L = [3, 4, 5, 6]
Vous pouvez utilisez le prédicat prédéfini append/3 qui réalise la concaténation de deux listes :
append([1,2],[3,4],C). --> [1,2,3,4]
a2l(f,[]).
a2l(n(X,G,D),R) :- ………………………… ,
………………………… ,
……………………………………… .
La première clause représente le cas trivial (sans appel récursif) : une feuille ne contient aucune valeur. ce cas est très important car il permet de terminer toutes les séquences d’appels récursifs du cas général.
La deuxième clause traite le cas général dans lequel l’arbre d’entrée a une étiquette racine, un fils gauche et un fils droit. Pour produire le résultat, il faut produire la liste des valeurs du fils gauche, celle des valeur du fils droit, et combiner de manière appropriée ces deux liste et la valeur de l’étiquette racine de l’arbre d’entrée.
a2l(f,[]).
a2l(n(X,G,D),R) :- a2l(G,L1),
a2l(D,L2),
append(L1,[X|L2],R).
Exercice d’entrainement E.ent2.3
Représentation unaire des entiers.
On représente les entiers naturels (0, 1, 2, …) par des termes fonctionnels :
z représente 0
s(z) représente 1
s(s(z)) représente 2
etc.
Définissez les prédicats int2u/2 et u2int/2 permettant de traduire la représentation unaire en représentation native et réciproquement.
Le but…
int2u(N_in, U_out).
…fait remonter dans la variable de sortie U_out la représentation unaire de l’entier d’entrée N_in.
Le but…
u2int(U_in, N_out).
…fait remonter dans la variable de sortie N_out l’entier dont U_in est la représentation unaire.
Exemples :
int2u(3,U). --> U = s(s(s(z)))
u2int(s(s(z)),N). --> N = 2
Le premier indice concerne int2u.
int2u(0,z) :- !.
int2u(N,s(Y)) :- ……………………………………… .
La première clause dit que 0 se traduit en z.
La deuxième traite le cas où la valeur d’entrée est un entier N strictement positif. Dans ce cas, il va falloir calculer $N-1$, puis traduire cette valeur en représentation unaire. Le résultat est utilisé dans la construction du terme de sortie.
Voici la définition complète de int2u.
int2u(0,z) :- !.
int2u(N,s(Y)) :- N1 is N-1, int2u(N1,Y).
Voici maintenant un indice pour u2int.
u2int(z,0) :- !.
u2int(s(Y),N) :- ……………………………………… .
La première clause dit que z se traduit en 0.
La deuxième traite le cas ou le terme d’entrée est de la forme s(Y). La valeur de sortie devra être 1 plus le résultat de la traduction de Y.
u2int(z,0) :- !.
u2int(s(Y),N) :- u2int(Y,N1), N is N1+1.
Exercice d’entrainement E.ent2.4
Modélisation de l’addition unaire.
Ces deux axiomes de la théorie de Peano modélisent l’addition standard des entiers naturels :
- $\forall X$ $X + z = X$
- $\forall X \forall Y$ $X + s(Y) = s(X + Y)$
Les symbole $s$ et $z$ apparaissant dans ces axiomes sont ceux introduits dans l’exercice précédent pour la représentation unaire des entiers.
Définissez le prédicat sum/3 qui encode ces deux axiomes et permet de calculer la somme de deux entiers en représentation unaire.
Le but…
sum(A_in, B_in, R_out).
…produit dans la variable de sortie R_out la somme des deux entiers A_in et B_in.
Exemple :
sum(s(z), s(s(z)), R). --> R = s(s(s(z)))
Aucun coupe choix ni calcul arithmétique réalisé avec is ne doit être utilisé, de sorte que le prédicat sera réversible, permettant par exemple d’évaluer un but tel que celui-ci :
sum(s(z), B, s(s(s(z)))). --> B = s(s(z))
sum(A,z,A).
sum(A,s(B), …………… ) :- ……………………………………… .
Lorsque le premier terme est A et le second s(B), comment exprimer le résultat en fonction de la somme de A et B ?
sum(A,z,A).
sum(A,s(B),s(R)) :- sum(A,B,R).
Activité E.top
Cette activité propose des exercices de consolidation qui ne doivent être abordés que par les personnes apprenantes capables de traiter sans difficulté les exercices d’assimilation.
E.top1
Exercice de consolidation E.top1 ?️?️
Définissez un prédicat money/3 tel que le but…
money(L_in, S_in, R_out).
…remonte dans R_out les listes de valeurs de la liste d’entrée L_in dont la somme est S_in.
On suppose que la liste L_in contient des entiers positifs, qui représentent des valeurs de pièces de monnaie, et que la variable d’entrée S_in a pour valeur un entier appelé appoint.
Exemple d’utilisation :
money([1,1,1,2,5], 3, R).
--> R = [1,1,1]
--> R = [1,2]
Lorsque l’appoint vaut 0, le résultat est la liste vide, la liste d’entrée n’ayant aucune importance.
Dans le cas contraire, c’est à dire lorsque la liste d’entrée peut être décomposée en
[T|Q], on doit considérer deux possibilités, qui seront chacune implémentée par une clause :
- Produire l’appoint en utilisant la valeur T (qui doit alors se retrouver dans la liste de sortie).
- Produire l’appoint sans utiliser la valeur T.
money(_,0,[]).
money([T|Q],S,[T|R]) :- S>=T, S1 is S-T,
money(Q,S1,R).
money([_|Q],S,R) :- money(Q,S,R).
Exercice de consolidation E.top2 ?️?️
Dans le prolongement des exercices de la section E.ent2 sur l’arithmétique en représentation unaire, vous devez définir un prédicat modélisant la multiplication et écrire un but permettant de donner en représentation native (base 10) les solutions du système d’équation suivant :
$X + Y = 9$, $X \cdot 9 = 20$
Les axiomes modélisant la multiplication sont les suivants :
- $\forall X$ $X\cdot 0 = 0$
- $\forall X \forall Y$ $X \cdot s(Y) = (X \cdot Y) + X$
Commencez par définir le prédicat modélisant la multiplication en utilisant le prédicat sum de l’exercice E.ent2.4.
mul(_,z,z).
mul(A,s(B),R) :- mul(A,B,M), sum(M,A,R).
Rédigez le but codant l’équation à résoudre en utilisant les prédicats int2u, sum, mul et u2int définis dans la section E.ent2.
int2u(9,Neuf), int2u(20,Vingt),
sum(A,B,Neuf), mul(A,B,Vingt),
u2int(A,X), u2int(B,Y).
En exécutant ce but, on obtient deux réponses :
X=5, Y=4
X=4, Y=5
Exercice de consolidation E.top3 ?️?️?️
Alice, Bob, Charlie et Dana sont les personnes participant à une compétition de natation et une compétition de cyclisme.
Utilisez Prolog pour déduire le classement de ces 4 personnes à chacune des compétitions à partir des informations suivantes :
- Alice n’a gagné aucune des 2 compétitions.
- La personne ayant gagné en natation est 3ième en cyclisme.
- Alice a battu Bob en natation et Bob a battu Alice en cyclisme.
- Bob n’est dernier à aucune des deux compétitions.
- Charlie a gagné la compétition de cyclisme et Dana l’a battu en natation.
La clé de la modélisation est un prédicat score/8.
score(NA, CA, NB, CB, NC, CC, ND, CD).
Les 8 slots sont des sorties correspondant aux rangs des 4 personnes (1, 2, 3 ou 4) pour chacune des 2 compétitions.
NAetCAreprésentent les rangs d’Alice en natation et cyclisme.NBetCBreprésentent les rangs de Bob en natation et cyclisme.NCetCCreprésentent les rangs de Charlie en natation et cyclisme.NDetCDreprésentent les rangs de Dana en natation et cyclisme.
Voici une définition partielle du prédicat score :
score(NA, CA, NB, CB, NC, CC, ND, CD) :-
permut([1,2,3,4], [NA, NB, NC, ND]),
permut([1,2,3,4], [CA, CB, CC, CD]),
% À compléter
Le prédicat permut/2 permet de produire toutes les permutations possibles d’une liste. Par exemple, le but…
permut([1,2,3],P).
…a pour résultat :
P = [1, 2, 3]
P = [2, 1, 3]
P = [2, 3, 1]
P = [1, 3, 2]
P = [3, 1, 2]
P = [3, 2, 1]
Les deux premiers sous-buts de la clause définissant le prédicat score vont produire toutes les combinaisons possibles des rangs des 4 personnes aux 2 compétitions. Les sous-buts à compléter doivent vérifier si les valeurs de NA, CA, NB, CB, NC, CC, ND, CD respectent les propriétés 1 à 5 exprimées dans l’énoncé du problème.
Avant de traiter cette partie, commencez par définir et tester le prédicat permut/2.
Pour définir le prédicat permut/2, vous pouvez utiliser un prédicat ins/3 permettant d’insérer de toutes les manière possibles un élément dans une liste. Le but…
ins(1,[3,3],R).
…produit le résultat :
R = [1, 3, 3]
R = [3, 1, 3]
R = [3, 3, 1]
Voici la définition du prédicat ins/3 :
ins(E,L,[E|L]).
ins(E,[T|Q],[T|R]) :- ins(E,Q,R).
Terminez la définition du prédicat permut/2 en utilisant le prédicat ins/3.
Voici la définition du prédicat permut/2 :
permut([],[]).
permut([T|Q],R) :- permut(Q,P), insert(T,P,R).
Vous pouvez maintenant terminer le définition du prédicat score/8 en ajoutant les propriétés 1 à 5 :
- Alice n’est première ni en natation, ni en cyclisme.
- Le premier en natation est troisième en cyclisme.
- Alice bat Bob en natation, Bob bat Alice en cyclisme.
- Bob n’est dernier ni en natation, ni en cyclisme.
- Charlie en premier en cyclisme mais Dana le bat en natation.
Concentrez-vous d’abord sur les propriétés 1 et 2.
La propriété 1 s’implémente sous la forme :
NA > 1, CA > 1
La propriété 2 est plus compliquée. Pour exprimer que la personne première en natation est troisième en cyclisme, on peut utiliser un prédicat prop2/8 définit par les faits suivants :
prop2(1,3,_,_,_,_,_,_).
prop2(_,_,1,3,_,_,_,_).
prop2(_,_,_,_,1,3,_,_).
prop2(_,_,_,_,_,_,1,3).
Il vous reste à coder les propriétés 3 à 5.
score(NA, CA, NB, CB, NC, CC, ND, CD) :-
permut([1,2,3,4], [NA, NB, NC, ND]),
permut([1,2,3,4], [CA, CB, CC, CD]),
NA>1, CA>1,
prop2(NA, CA, NB, CB, NC, CC, ND, CD),
NA<NB, CB<CA,
NB<4, CB<4,
CC==1, ND<NC.
Le but suivant permet d’obtenir la solution du problème :
score(NA, CA, NB, CB, NC, CC, ND, CD).
Le résultat est :
CA = NC, NC = 4,
CB = NA, NA = 2,
CC = ND, ND = 1,
CD = NB, NB = 3
Ce qui nous donne l’unique solution :
| 1er | 2ième | 3ième | 4ième | |
|---|---|---|---|---|
| Cyclisme ?️ | Charlie | Bob | Dana | Alice |
| Natation ?️ | Dana | Alice | Bob | Charlie |