# data[].attributes.body
Pour tester immédiatement vos programmes.

# data[].attributes.body
⚠️ Site en version beta

# data[].attributes.headline
Enseignement en ligne d'initiation à PROLOG

# data[].attributes.subject
Enseignement en ligne d'initiation à PROLOG

# data[].attributes.body
Cet enseignement en ligne est un initiative personnelle proposée dans le cadre du 50ième anniversaire de PROLOG.

# data[].attributes.body
Pour poser vos questions et bénéficier de l'aide d'une personne enseignante, vous devez avoir un compte Discord depuis au moins 5 minutes, puis :

https://discord.gg/NeCUVt9njE

# data[].attributes.body
Le matériel pédagogique de cette étape n'est pas encore disponible.

# data[].attributes.attachment_link.readable_text
Par O. Bailleux, Maître de conférences HDR à l'université de Bourgogne.

Les activités d'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. Si vous avez besoin d'indices ou si vos solutions sont erronées, analysez les causes de vos erreurs - au besoin, demandez des explications à une personne qualifiée - et refaites les exercices concernés après un délai d'au moins une journée et au plus quelques jours.

Activité d'entraînement C.ent

C.ent1

Vous devez définir un prédicat sum permettant de produire toutes les valeurs pouvant être obtenues en additionnant des nombres donnés dans une liste d'entrée.

Par exemple, l'évaluation du but...

sum([1,10,100],S).

...doit avoir pour résultat :

S = 111 S = 11 S = 101 S = 1 S = 110 S = 10 S = 100 S = 0

On considère que la valeur 0 est correcte. Elle représente le cas où aucune des valeurs de la liste d'entrée n'est utilisée.

On peut considérer trois possibilités, dont chacune sera décrite par une clause.

1. La liste d'entrée est vide. Dans ce cas, la seule valeur calculable est 0.

2. La liste d'entrée n'est pas vide. Elle se décompose en [T|R]. On s'intéresse aux sommes réalisables en utilisant la première valeur.

3. La liste d'entrée n'est pas vide. Elle se décompose en [_|R]. On s'intéresse aux sommes réalisables sans utiliser la première valeur.

sum([],0). % clause 1 sum([T|R],S) :- .................... . % clause 2 sum([_|R],S) :- .................... . % clause 3

La clause 2 dit que S est réalisable en ajoutant T et une somme de valeurs de R.

La clause 3 dit que S est une somme de valeurs de R.

C.ent2

Nous avons vu dans la partie découverte sur les listes la définition d'un prédicat pref qui permet d'obtenir tous les préfixes non vide d'une liste.

pref([T],[T|_]). pref([T|P],[T|R]) :- pref(P,R).

Par exemple, le but...

pref(P,[1,2,3]).

...produit le résultat :

P = [1] P = [1, 2] P = [1, 2, 3]

On appelle sous-liste d'une liste $L$ toute suite non vide de valeurs consécutives apparaissant dans $L$. Par exemple, les sous-listes de [1,2,3] sont :

[1] [1, 2] [1, 2, 3] [2] [2, 3] [3]

Vous devez définir un prédicat sl tel que sl(S,L) spécifie que S est une sous-liste de L. Ce prédicat doit permettre de produire toutes les sous-listes d'une liste ou de déterminer si une liste est sous-liste d'une autre. Vous pouvez raisonner de manière constructive sur le premier cas d'utilisation ou de manière plus déclarative sur le deuxième.

Par exemple, le but...

sl(P,[1,2,3]).

...devra produire le résultat :

S = [1] S = [1, 2] S = [1, 2, 3] S = [2] S = [2, 3] S = [3]

Vous pouvez vous appuyer sur cette propriété :

Soit une liste non vide L ayant pour tête T et pour reste R. Toute sous-liste de L est soit un préfixe de L, soit une sous-liste de R.

sl(S,L) :- ............... . %clause 1 sl(S,[_|R]) :- ............... . %clause 2

La clause 1 dit que tout préfixe d'une liste L est une sous-liste de L.

La clause 2 dit que toute sous liste d'une liste R est une sous liste de toute liste de la forme [_|R].

C.ent3

Vous devez définir un prédicat dec permettant de décomposer une liste en un de ses éléments et un reliquat qui est la liste de tous les autres éléments.

Plus précisément, dec(L,E,R) dit que E est un élément de L et que le reliquat R est la liste des autres éléments de L (dans l'ordre où ils apparaissant dans L).

Par exemple, le but...

dec([1,2,3],E,A).

...doit produire le résultat :

A = [2,3], E = 1 A = [1,3], E = 2 A = [1,2], E = 3

Une première manière évidente de décomposer une liste [T|R] est de considérer son premier élément et son reste. La clause correspondante est :

dec([T|R],T,R).

Comment décrire les autres décompositions ?

dec([T|R],T,R). dec([T|R],E,[T|Q]) :- .......... .

La deuxième clause dit que [T|R] peut être décomposée en un élément E et un reliquat [T|Q]. Comment exprimer la relation entre R, E et Q ?

dec([T|R],T,R). dec([T|R],E,[T|Q]) :- dec(R,E,Q).

Voici une illustration de la deuxième clause.

On appelle anagramme d'une liste L toute les listes ayant les mêmes éléments dans un ordre quelconque.

Vous devez, en utilisant notre prédicat dec, définir un prédicat ana permettant de produire les anagrammes d'une liste. Par exemple, le but...

ana([a,b,c],A).

...devra produire le résultat :

A = [a, b, c] A = [a, c, b] A = [b, a, c] A = [b, c, a] A = [c, a, b] A = [c, b, a]

Le seul anagramme d'une liste ayant un seul élément est la liste elle-même.

Tout anagramme d'une liste L plus grande est constitué d'un élément de L suivi d'un anagramme du reliquat de la décomposition de cette liste telle que définie par le prédicat dec.

ana([E],[E]). ana(L,[T|Q]) :- ............... .

La deuxième clause dit qu'un anagramme [T|Q] de L est constitué d'un élément T issu de la décomposition de L par dec et d'un anagramme Q du reliquat de cette décomposition.

On peut utiliser le prédicat ana pour produire les anagramme d'une chaîne de caractères. Pour ce faire, on dispose d'un prédicat string_chars qui établit une relation entre une chaine et une liste de caractères. Voici deux buts utilisant ce prédicat et leur résultats :

string_chars("Tim",L). --> L = ['T', i, m] string_chars(S,['T', i, m]). --> S = "Tim"

Les caractères représentant des majuscules sont entre cotes pour les différencier des variables. Ces cotes sont facultatives pour les lettres minuscules.

Définissez un prédicat anagramme permettant de produire sous forme de chaines les anagrammes d'une chaine. Par exemple, le but...

anagramme("Tomy",A).

...produit tous les anagrammes du mot "Tomy".

A = "Tomy" A = "Toym" A = "Tmoy" A = "Tmyo" A = "Tyom" A = "Tymo" etc. (18 autres réponses)

C.ent4

Vous devez définir un prédicat sd permettant de supprimer les doublons (valeurs ayant plusieurs occurrences) dans une liste.

Si L_in est une liste connue et S_out est une variable non instanciée, alors le but...

sd(L_in, S_out).

Fait remonter dans la variable S_out une liste contenant exactement une occurrence de chaque valeur de L_in.

Par exemple, l'évaluation de...

sd([2,1,2,3,1,1,3],F).

...produit le résultat :

F = [2, 1, 3]

Vous pouvez utiliser le prédicat standard member qui permet de vérifier si une valeur est dans une liste. Voici deux exemples de buts construits avec ce prédicat et leur résultats :

member(1,[2,1,1,3,2]). --> true member(4,[2,1,1,3,2]). --> false

Quant la liste d'entrée et vide, la liste de sortie l'est aussi.

Si le premier élément T de la liste d'entrée est aussi dans le reste Q de cette liste, alors la liste de sortie est obtenue en supprimant les doublons de Q.

Si le premier élément T de la liste d'entrée n'est pas dans le reste Q de cette liste, alors la liste de sortie est constituée de T et de la liste obtenue en supprimant les doublons de Q.

sd([],[]). sd([T|R],.....) :- member(T,R),!, .......... . sd([T|R],.....) :- .......... .

La première clause concerne le cas où le premier élément T de la liste d'entrée apparait également dans le reste R de cette liste. On ne conservera pas cette première occurrence et la liste de sortie sera obtenue en supprimant les doublons de R. En raison de la présence du coupe-choix, la troisième clause ne sera prise en compte que si T n'est pas dans R.

Activité d'approfondissement

Vous commencez à avoir une certaine aisance avec la manipulation des listes ? Je vous propose maintenant de résoudre des problèmes avec Prolog.

C.top1

Nous allons utiliser Prolog pour résoudre le problème suivant :

Un berger est sur la rive gauche d'une rivière en présence d'un loup, d'une chèvre et d'une salade. Il peut traverser la rivière soit seul, soit avec la chèvre, soit avec la salade, soit avec le loup.

Il ne doit en aucun cas laisser la chèvre seule avec le loup ou avec la salade sur une des rives.

Il faut trouver un scénario permettant, en un nombre donné de traversées, d'emmener la chèvre, le loup, le berger et la salade sur la rive droite.

Pour résoudre un tel problème, nous devons trouver un moyen de représenter les données. Il y a de nombreuses possibilités et j'en ai choisi une, mais vous pouvez en chercher d'autres.

On appelle état une donnée représentant les positions respectives du berger, du loup, de la chèvre et de la salade. Un état sera représenté par une liste de 4 éléments pouvant prendre deux valeurs possibles : g pour rive gauche et d pour rive droite.

Par exemple :

[g,g,d,d] représente l'état dans lequel le berger et le loup sont sur la rive gauche et la chèvre et la salade sont sur la rive droite.

[d,g,d,g] représente l'état dans lequel le berger est sur la rive droite, le loup sur la rive gauche, la chèvre sur la rive droite et la salade sur la rive gauche.

On définit le prédicat op qui définit la notion de rives opposées :

op(d,g). op(g,d).

Dans un premier temps, je vous propose de définir un prédicat bad qui détermine les états interdits. Plus précisément, bad(E) soit être satisfait si et seulement si l'état E correspond à une situation dans laquelle la chèvre et le loup ou la chèvre et la salade sont sur la même rive sans le berger.

Pourquoi les états interdits et pas les états autorisés ? Parce-qu'on peut modéliser les états interdits de manière plus concise.

Une première solution consiste à définir bad en 4 faits comme ceci :

bad([g,d,d,_]). % berger à gauche, loup et chèvre à droite bad([g,_,d,d]). % berger à gauche, chèvre et salade à droite bad([d,g,g,_]). % berger à droite, loup et chèvre à gauche bad([d,_,g,g]). % berger à droite, chèvre et salade à gauche

Proposez une définition plus concise en deux clauses, en utilisant le prédicat op.

Maintenant, vous devez définir un prédicat trav permettant de déterminer si une traversée est réalisable, c'est à dire si elle correspond à une de ces 4 possibilités :

1. Le berger traverse seul.

2. Le berger traverse avec le loup.

3. Le berger traverse avec la chèvre.

4. Le berger traverse avec la salade.

Plus précisément, trav(E1,E2,T) est satisfait si et seulement si une traversée réalisable permet de passer de l'état E1 à l'état E2, T étant ce qui change de rive avec le berger. Les valeurs possibles de T sont loup, chevre, salade et rien.

Par exemple, l'évaluation du but...

trav([g,g,g,g],S,T).

...a pour résultats :

S = [d, d, g, g], T = loup S = [d, g, d, g], T = chevre S = [d, g, g, d], T = salade S = [d, g, g, g], T = rien

La première solution dit que le berger et le loup ont changé de rive, puisque le nouvel état est [d,d,g,g]. La quatrième solution dit que le berger traverse seul. Le nouvel état, [d,g,g,g] indique que le loup, le chèvre et la salade sont restés sur la rive gauche.

On peut définir trav en 4 clauses correspondant respectivement aux cas où le berger traverse seul, avec le loup, avec la chèvre et avec la salade. Voici la première clause correspondant au cas où le berger traverse seul :

trav([D,L,C,S],[A,L,C,S],rien) :- op(D,A).

Les positions L, C et S, du loup, de la chèvre et de la salade, ne changent pas de valeur entre l'état avant la traversée (premier slot) et l'état après la traversée (deuxième slot). Par contre, la position du berger (premier slot) passe de g à d ou de d à g. (La variable D représente la rive de départ et la variable A la rive d'arrivée.)

À vous trouver les trois clauses restantes.

Il vous reste à définir le prédicat transp tel que transp(I,F,N,L) qui produise, si applicable, la liste L des traversées permettant de passer d'un état initial I à un état final F en N étapes.

Par exemple, l'évaluation du but...

transp([g,g,g,g],[d,d,d,d],7,Plan).

...doit produire les listes :

Plan = [chevre, rien, loup, chevre, salade, rien, chevre] Plan = [chevre, rien, salade, chevre, loup, rien, chevre]

...qui sont les deux solutions du problème en 7 étapes.

La première liste s'interprète de la manière suivante :

1. Le berger traverse avec la chèvre.

2. Il revient seul sur la rive gauche.

3. Il retourne sur la rive droite avec le loup.

4. Il revient sur la rive gauche avec la chèvre.

5. Il retourne sur la rive droite avec la salade.

6. Il revient seul sur la rive gauche.

7. Il traverse une dernière fois de gauche à droite avec la chèvre.

Si l'état initial et l'état final sont identiques, le transport nécessite 0 étapes et la liste des traversées est vide, ce qui correspond à la clause :

transp(F,F,0,[]).

Il reste à écrire la clause récursive qui permet de passer d'un état initial à un état final avec un nombre N de traversées supérieur à 0.

Voici le début de le deuxième clause :

transp(I,F,N,[E|S]) :- N>0, .............................. .

Voici une version à compléter de la deuxième clause

transp(I,F,N,[E|S]) :- N>0, trav(I,J,E), not(bad(J)), .............................. .

Passer de l'état I à l'état F en un nombre N>0 d'étapes suppose :

de faire une traversée E permettant de passer de l'état I à un état J,

que J soit un état autorisé,

...

transp(F,F,0,[]). transp(I,F,N,[E|S]) :- N>0, trav(I,J,E), not(bad(J)), N1 is N-1, transp(J,F,N1,S).

La solution complète est donc :

op(d,g). op(g,d). bad([A,B,B,_]) :- op(A,B). bad([A,_,B,B]) :- op(A,B). trav([D,D,C,S],[A,A,C,S],loup) :- op(D,A). trav([D,L,D,S],[A,L,A,S],chevre) :- op(D,A). trav([D,L,C,D],[A,L,C,A],salade) :- op(D,A). trav([D,L,C,S],[A,L,C,S],rien) :- op(D,A). transp(F,F,0,[]). transp(I,F,N,[E|S]) :- N>0, trav(I,J,E), not(bad(J)), N1 is N-1, transp(J,F,N1,S).

Ce qui est remarquable, c'est que ce programme de résolution comporte moins de caractères que l'énoncé du problème à résoudre ! Sans compter les espaces, l'énoncé comporte 402 caractères alors que le programme complet en comporte 319.

Nous avons donc là une illustration de la puissance d'expression de Prolog. Certes, le passage de l'énoncé au programme est loin d'être évident et nécessite une certaine expérience, mais une fois maîtrisée, une même approche peut être utilisée pour résoudre de nombreux problèmes.

Dans cet exercice, nous avons traité un problème de planification. Dans le suivant, nous abordons un casse-tête célèbre.

C.top2

Nous allons maintenant nous attaquer à un casse-tête très célèbre : le problème du zèbre. Voici une variante moderne de l'énoncé :

On considère cinq maisons, toutes de couleurs différentes (rouge, bleu, jaune, blanc, vert), dans lesquelles logent cinq personnes de professions différentes (peintre, sculpteur, diplomate, médecin et violoniste) et de nationalités différentes (anglaise, espagnole, japonaise, norvégienne et italienne) ayant chacun une boisson favorite (thé, jus de fruits, café, lait et vin) et un animal favori (chien, escargots, renard, cheval et zèbre).

On dispose des faits suivants :

1. Le norvégien habite la première maison à gauche.

2. On boit du lait dans la maison du milieu.

3. L'Anglais habite la maison rouge.

4. L'Espagnol possède un chien.

5. Le Japonais est peintre.

6. L'Italien boit du thé.

7. Le propriétaire de la maison verte boit du café.

8. Le sculpteur élève des escargots.

9. Le diplomate habite la maison jaune.

10. Le violoniste boit du jus de fruit.

11. La maison verte est a droite de la blanche.

12. Le Norvégien habite a cote de la maison bleue.

13. Le renard est dans une maison voisine de celle du médecin.

14. Le cheval est à coté de la maison du diplomate.

On veut savoir quelle est la couleur, la nationalité, la boisson, l'animal et la profession associés à chacune des maisons.

Il nous faut une représentation des informations à rechercher. Il existe plusieurs approches possibles, plus ou moins efficaces. Je vous propose de représenter chacune des lignes apparaissant sur la figure précédente par une liste.

La définition du prédicat permettant la résolution du problème commence ainsi :

sol(C,N,B,A,P) :- C=[_,_,_,_,_], N=[norvege,_,_,_,_], B=[_,_,lait,_,_], A=[_,_,_,_,_], P=[_,_,_,_,_], % À compléter

La variable C représente la liste des couleurs dans l'ordre des maisons dans le rue, en partant de la gauche.

La variable N représente la liste des nationalités dans le même ordre.

La variable B représente la liste des boissons dans le même ordre.

La variable A représente la liste des animaux dans le même ordre.

La variable P représente la liste des professions dans le même ordre.

À ce stade, les seules informations qui sont données est que chaque liste contient 5 valeurs, que le norvégien habite la première maison (premier indice de l'énoncé) et que la personne qui boit du lait habite la maison centrale (deuxième indice de l'énoncé).

Il faut ajouter les autres indices de l'énoncé sous une forme exploitable par Prolog.

Commençons par le troisième indice de l'énoncé du problème :

L'anglais habite la maison rouge.

Cet indice concerne la liste C des couleurs et la liste N des nationalités. Il nous dit que anglais est dans la même position dans la liste des nationalités que rouge dans la liste des couleurs.

Pour le traduire en Prolog, nous allons définir un prédicat memePos tels que si L1, L2 sont des listes et E1, E2 des éléments, alors le but...

memePos(E1,L1,E2,L2).

...est satisfait si et seulement si la position de E1 dans L1 est la même que celle de E2 dans L2.

Voici deux exemples de buts et les résultats de leurs évaluations :

memePos(b,[a,b,c],c,[d,c,a]). --> true memePos(a,[a,b,c],c,[d,c,a]). --> false

Donnez la définition de memePos.

Les deux éléments apparaissant en tête de chaque liste sont dans la même position (cas trivial).

Si deux éléments apparaissent en même position dans les restes de deux listes alors ils apparaissent en même positions dans ces deux listes (clause récursive).

Continuez à compléter la définition du prédicat sol en y ajoutant les indices 3 à 10 de l'énoncé.

L'indice n°3 s'exprime de cette manière :

memePos(anglais,N,rouge,C)

Le symbole anglais apparait en même position dans le liste des nationalité que le symbole rouge dans la liste des couleurs.

sol(C,N,B,A,P) :- C=[_,_,_,_,_], N=[norvegien,_,_,_,_], % indice 1 B=[_,_,lait,_,_], % indice 2 A=[_,_,_,_,_], P=[_,_,_,_,_], memePos(anglais,N,rouge,C), % indice 3 memePos(chien,A,espagnol,N), % indice 4 memePos(japonais,N,peintre,P), % indice 5 memePos(italien,N,the,B), % indice 6 memePos(verte,C,cafe,B), % indice 7 memePos(sculpteur,P,escargots,A), % indice 8 memePos(diplomate,P,jaune,C), % indice 9 memePos(violoniste,P,jus,B), % indice 10

À ce stade, il peut être intéressant de tester la résolution du but...

sol(C,N,B,A,P).

...pour voir si Prolog peut faire des déductions à partir des indices donnés.

Il s'avère que oui. Cette évaluation produit de nombreuses réponses compatibles aves les données fournies, telle que :

A = [escargots, _1840, chien, _1852, _1858], B = [café, jus, lait, _1942, the], C = [verte, rouge, jaune, _1818, _1824], N = [norvegien, anglais, espagnol, japonais, italien], P = [sculpteur, violoniste, diplomate, peintre, _656]

Les variables commençant par le caractère _ sont non instanciées. Attention, le fait que escargots soit associé à la première maison dans cette réponse n'implique pas que ce soit le cas dans la solution du problème complet. Parmi les nombreuses solutions du problème partiel, certaines associent l'escargot à d'autres maisons.

Intéressons nous maintenant à l'indice n° 11 :

La maison verte est a droite de la blanche.

l'expression "à droite" est ici à prendre au sens strict. La maison verte immédiatement après la blanche.

Vous devez définir un prédicat apres tel que si L, est une liste et X, Y des éléments, alors le but...

apres(X,Y,L).

...est satisfait si et seulement si Y apparait immédiatement après X dans L.

Voici la première clause qui concerne le cas trivial où X et Y sont en début de liste :

apres(X,Y,[X,Y|_]).

Il reste à écrire la clause récursive.

Donnez maintenant le but exprimant l'indice n°11, qui sera à ajouter dans la définition du prédicat sol.

Il nous reste 3 indices à encoder :

Le norvégien habite a cote de la maison bleue.

Le renard est dans une maison voisine de celle du médecin.

Le cheval est à coté de la maison du diplomate.

Dans les trois cas, on exprime qu'un élément X apparait dans une liste L1 à une position située immédiatement avant ou après la position d'un élément Y dans une liste L2.

Vous devez définir un prédicat contigu pour exprimer cette contrainte par le but :

contigu(X,L1,Y,L2).

Voici les deux clauses non récursives :

contigu(X,[X|_],Y,[_,Y|_]). contigu(X,[_,X|_],Y,[Y|_]).

Il vous reste à écrire la clause récursive.

Ajoutez à la définition du prédicat sol les trois derniers indices.

En lançant le but...

sol(C,N,B,A,P).

...on obtient une seule réponse, mais incomplète :

A = [renard, cheval, escargots, chien, _1858], B = [_1924, the, lait, jus, café], C = [jaune, bleu, rouge, blanche, verte], N = [norvegien, italien, anglais, espagnol, japonais], P = [diplomate, medecin, sculpteur, violoniste, peintre]

La raison est qu'on à oublié de dire que quelqu'un boit du vin et qu'il y a un zèbre dans l'une des maisons. Vous pouvez vérifier que les symboles vin et zebre n'apparaissent pas dans le programme.

Il vous reste donc un dernier défit à relever : trouver un moyen simple d'ajouter l'information manquante.

Le prédicat standard member permet de spécifier qu'un élément E appartient à une liste L avec le but member(E,L).

Nous obtenons enfin l'unique solution du problème :

A = [renard, cheval, escargots, chien, zebre], B = [vin, the, lait, jus, café], C = [jaune, bleu, rouge, blanche, verte], N = [norvegien, italien, anglais, espagnol, japonais], P = [diplomate, medecin, sculpteur, violoniste, peintre]

Ici encore, le programme qui résout le problème est plus court que l'énoncé du problème ! Sans compter les espaces, l'énoncé contient 1128 caractères alors que le programme en contient 559, soit presque deux fois moins. On peut évidemment réduire la taille de l'énoncé (et du programme), mais sans changer le fait que les tailles de l'énoncé et du programme de résolution ont le même ordre de grandeur.

# data[].attributes.attachment_link.title
PROLOG : étape C - entrainement - Activités d'apprentissages

# data[].attributes.attachment_link.description
Par O. Bailleux, Maître de conférences HDR à l'université de Bourgogne. Les activités d'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.

# data[].attributes.attachment_link.readable_text
Par O. Bailleux, Maître de conférences HDR à l'université de Bourgogne.
Les activités de 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.

Activité de découverte C.dec

Introduction

Nous allons découvrir comment représenter des listes, ce qui ouvre la voie à la modélisation et à la résolution de nombreux problèmes, et comment limiter le nombre de possibilités explorées par Prolog lors de l'évaluation d'un but.

C.dec1 : Représentation des listes

Prolog permet de construire et exploiter des listes représentée de la manière suivante. Une liste est :

Par exemple, le but...

...donne comme résultat :

Ou encore, par exemple...

... produit le résultat :

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 d'une liste de plusieurs éléments.

Si D est le dernier élément de la liste R, alors D est le dernier élément de toute liste ayant pour reste R.

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 C.x1

On veut définir un prédicat addFin tel que si L est une liste connue, F un élément connu et R est une variable de sortie (non instanciée), alors le but...

...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 :

voici la définition du prédicat addFin à compléter.

addFin([],F,[F]). addFin([T|Q],F,[T|R]) :- ............................................. .

La première clause dit :

La liste obtenue en ajoutant F à la fin d'une liste vide est [F].

La deuxième clause dit :

La liste obtenue (troisième slot) en ajoutant l'élément F à la fin d'une liste [T|Q] a

et pour reste la liste R obtenue en... (Tentez de compéter cette phrase.)

La liste obtenue (troisième slot) en ajoutant l'élément F à la fin d'une liste [T|Q] a

et pour reste la liste R obtenue en ajoutant F à la fin de Q.

addFin([],F,[F]). addFin([T|Q],F,[T|R]) :- addFin(Q,F,R).

Bien que, lors de la conception du prédicat, nous ayons raisonné en considérant que le premier et le deuxième slots étaient des entrées et le troisième une sortie, 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 :

C.dec2 : quelques mots sur l'unification

Dans un esprit de simplification, on peut dire que l'unification est un processus permettant de rendre deux termes identiques en remplaçant toutes les occurrences d'une ou plusieurs variables par des termes. Parce que la définition formelle du concept nous entraînerait au delà des objectifs de cette initiation, nous limiterons à des exemples.

Deux termes sans variable ne s'unifient que s'ils sont identiques. Ceci s'applique aux listes, qui sont des cas particuliers de termes. Par exemple :

Une variable s'unifie avec elle même et avec n'importe quel terme qui ne la contient pas. Par exemple :

Dans le cas de deux termes contenant des variables, on doit rechercher s'il est possible de les rendre identiques en réalisant des substitutions de variables par des termes. Voici quelques exemples :

[1,X] ne s'unifie pas avec [1,2,3] car les listes ne comportent pas le même nombre d'éléments.

[1|X] s'unifie avec [1,2] par la substitution X=[2]. (Et pas avec X=2. ne confondez pas la virgule qui sépare les éléments d'une liste et le caractère | qui la décompose en un élément de tête et une liste.

Exercice de découverte C.x2

Les termes [T|Q] et [1,2] s'unifient-ils ? Si oui, par quelle substitution ?

Les termes [T|Q] et [7] s'unifient-ils ? Si oui, par quelle substitution ?

Les termes [T|Q] et [] s'unifient-ils ? Si oui, par quelle substitution ?

Les termes [1,2|Q] et [1|R] s'unifient-ils ? Si oui, par quelle substitution ?

C.dec3 : Coupe choix

Le coupe choix est une entorse au caractère déclaratif de Prolog. Il permet de limiter l'exploration des solutions lors de l'évaluation d'un prédicat. Pour comprendre son fonctionnement, examinons un exemple basé sur les deux prédicats suivants :

val(1). val(2). p([X,Y]) :- val(X), val(Y). p([X]) :- val(X).

Pour évaluer le but...

...Prolog recherche tous les moyens de satisfaire p(L) avec chacune des deux clauses définissant le prédicat p. Examinons d'abord les étapes de cette recherche avec la première clause, à savoir :

p([X,Y]) :- val(X), val(Y).

Dans un premier temps, Prolog vérifie si la tête de la clause, p([X,Y]) peut s'unifier avec le but p(L). Cette unification réussi et a pour résultat L=[X,Y].

Ensuite, Il recherche toutes les valeurs de X permettant de satisfaire le premier sous-but val(X), puis pour chacune d'elles toutes les valeurs de Y permettant de satisfaire le deuxième sous-but val(Y). Pour représenter de manière plus lisible les quatre cheminement conduisant aux quatre solutions, on peut représenter la clause sous la forme...

$\text{val}(X) \wedge \text{val}(Y) \to \text{p}([X,Y])$

...dans laquelle le symbole $\to$ représente l' implication logique et le symbole $\wedge$ représente le et logique.

Si $\text{val}(X)$ est vrai et si $\text{val}(Y)$ est vrai alors $\text{p}([X,Y])$ est vrai.

Les résultat du but p(L) issu de la première clause sont :

L = [1, 1] L = [1, 2] L = [2, 1] L = [2, 2]

Ces résultats sont complétés par ceux obtenus à l'aide de la deuxième clause, qui sont :

Le coupe choix, noté !, permet d'annuler les explorations qui n'ont pas encore été réalisées au moment où il est atteint. Si par exemple on le place à la fin de la première clause de p, comme ceci...

p([X,Y]) :- val(X), val(Y), !. p([X]) :- val(X).

...alors le coupe choix est atteint au moment où la première solution issue de la première clause est produite. Toutes les explorations en attente sont annulées :

celles relatives aux autres manières de satisfaire les buts de la première clause,

et celles relatives à la deuxième clause.

Le résultat du but p(L) est :

Si on place le coupe choix ici...

p([X,Y]) :- val(X), !, val(Y). p([X]) :- val(X).

...alors il annule :

les autres possibilités en attente de satisfaire le but val(X) situé avant le coupe choix,

et les explorations exploitant la deuxième clause.

Par contre, les deux manières de satisfaire le but val(Y), situé après le coupe choix dans la première clause, sont explorées.

Le résultat du but p(L) est :

Si on place le coupe choix ici...

p([X,Y]) :- val(X), val(Y). p([X]) :- val(X), !.

...alors il annule les choix en attente après la production du premier résultat issu de la deuxième clause. Le but p(L) a donc pour résultat :

L = [1, 1] L = [1, 2] L = [2, 1] L = [2, 2] L = [1]

Exercice de découverte C.x3

Cet exercice doit être traité sans utiliser d'interpréteur Prolog.

On place de coupe choix ici :

p([X,Y]) :- !, val(X), val(Y). p([X]) :- val(X).

Quel sera le résultat du but p(L) ? Pourquoi ?

Le résultat est :

L = [1, 1] L = [1, 2] L = [2, 1] L = [2, 2]

On définit le prédicat p de la manière suivante :

p([X,Y]) :- val(X), val(Y), Y\==X. p([X]) :- val(X).

Donnez le résultat du but p(L).

L = [1, 2] L = [2, 1] L = [1] L = [2]

On ajoute un coupe choix ici :

p([X,Y]) :- val(X), val(Y), !, Y\==X. p([X]) :- val(X).

Quelle est le résultat du but p(L) ?

Rappelez vous bien que les possibilités non explorées situées avant le coupe choix (ainsi que les clauses suivantes du prédicat) sont annulées lorsque le coupe choix est atteint.

Pensée récursive

Avant d'aller un peu plus loin avec les listes, je vous propose de faire le point sur l'approche récursive de la résolution de problèmes.

Nous appellerons problème tout ensemble d' instances ayant chacune ayant une, plusieurs, ou aucune solution(s).

Quelques exemples :

Le problème concat_v1 :

Instances : couples de deux listes.

Solution d'une instance $(A,B)$ : la liste constituée des éléments de $A$ suivis des éléments de $B$, appelée concaténation de $A$ et $B$.

Le problème concat_v2 :

Instances : triplets de trois listes.

Solution d'une instance $(A,B,C)$ : oui si $C$ est constituée des éléments de $A$ suivis de ceux de $B$, non dans le cas contraire.

Le problème somme :

Instances : couples $(L,v)$ où $L$ est une liste d'entiers positifs et $v$ un entier naturel.

Solution d'un instance $(L,v)$ : toute liste d'éléments de $L$ dont la somme est égale à $v$. Chaque élément de $L$ peut être utilisé au plus une fois.

Pour résoudre récursivement un problème, il faut associer (de manière implicite ou explicite) à chaque instance un nombre que nous appellerons difficulté. Par souci de simplification, nous allons considérer que la difficulté d'une instance est un entier naturel.

Nous avons aussi besoin de deux ingrédients :

1. Un moyen de résoudre immédiatement toute instance de difficulté inférieure ou égale à un certain entier $d_\text{triv}$. De telles instances seront dites triviales.

2. Un moyen de résoudre toute instance de difficulté $d>d_\text{triv}$ en utilisant des solutions d'instances de difficultés inférieures à $d$.

Par exemple, dans le cas du problème concat_v1, on peut définir la difficulté d'une instance $(A,B)$ comme étant le nombre d'élément de la liste $A$ et fixer le seuil $d_\text{triv}$ à 0. Ce choix peut paraitre arbitraire, mais il permet d'obtenir facilement les deux ingrédients nécessaires à une résolution récursive du problème :

1. La concaténation de la liste vide [] avec une liste $B$ est la liste $B$.

2. Soit une instance non triviale $([T|R],B)$. Si $Q$ est la solution de l'instance $(R,B)$, alors la solution de l'instance $(A,B)$ est $[T|Q]$.

Le deuxième ingrédient vous paraît indigeste ? En voici une illustration.

En ajoutant l'élément $T$ en tête de la concaténation de $R$ et $B$, on obtient la concaténation de $A$ et $B$.

Nous avons les ingrédients pour définir un prédicat concat permettant de résoudre notre problème.

Une première clause décrit le cas trivial correspondant à notre premier ingrédient : la concaténation d'une liste vide et d'une liste B est la liste B.

Le deuxième ingrédient sera exploité par la clause récursive suivante :

concat([T|R],B,[T|Q]) :- concat(R,B,Q).

Littéralement :

Ou encore, dans une interprétation plus constructive :

Le bon fonctionnement du prédicat concat - et de tout prédicat défini récursivement - repose sur le principe de récurrence, très utilisé en mathématiques. Je ne le développerai pas ici, mais vous pouvez vous documenter sur le sujet. Si vous faites confiance à ce principe, alors vous pouvez concevoir des prédicats récursifs sans vous soucier de la manière dont Prolog évalue les buts utilisant ces prédicats.

Le prédicat concat permet aussi de résoudre le problème concat_v2, c'est à dire de vérifier si une liste connue est la concaténation de deux listes connues. Il permet également de résoudre d'autres problèmes, tels que :

Soient deux listes $B$ et $C$. Trouver la liste $A$ telle que la concaténation de $A$ et $B$ est $C$.

Soient deux listes $A$ et $C$. Trouver la liste $B$ telle que la concaténation de $A$ et $B$ est $C$.

Soit une liste $C$. Trouver toutes les listes $A$ et $B$ telles que la concaténation de $A$ et $B$ est $C$.

Exercice de découverte C.x4

Si une liste $L$ est la concaténation d'une liste $P$ avec une liste quelconque (possiblement vide), on dit que $P$ est un préfixe de $L$. Par exemple, les préfixes de [1,2,3] sont les listes [], [1], [1,2], [1,2,3].

Donnez un but permettant de produire tous les préfixes de la liste [1,2,3,4] avec le prédicat concat.

On veux maintenant définir un prédicat pref dédié à la production des préfixes non vides d'une liste.

Par exemple, le but...

....doit produire le résultat :

P = [1] P = [1, 2] P = [1, 2, 3] P = [1, 2, 3, 4]

Les deux ingrédients permettant de traiter ce problème récursivement sont les suivants :

1. Une liste comportant un seul élément a pour seul préfixe elle-même.

2. Soit une liste [T|R]. Les préfixes de cette liste sont : 2.1 d'une part[T] , 2.2 et d'autre part, si applicable, toutes les listes obtenues en ajoutantT au début des préfixes non vides de R.

Pour simplifier la définition du prédicat pref, on peut utiliser deux clauses, une non récursive et une récursive, ayant les rôles suivants :

La clause non récursive produit tous les préfixes de taille 1, quelle que soit la taille de la liste d'entrée. Cette clause exploite donc l'ingrédient 1 et l'ingrédient 2.1.

La clause récursive produit tous les préfixes de tailles supérieures à 1 en utilisant l'ingrédient 2.2.

Voici une illustration de ce que dit la clause non récursive.

Complétez cette définition du prédicat pref (la liste d'entrée occupe le deuxième slot, les préfixes produits remontent dans le premier slot) :

pref([T],[T|_]). pref(..... , [T|R]) :- pref(..... , .....).

pref([T],[T|_]). pref([T|P],[T|R]) :- pref(P,R).

La clause récursive peut se décrire de manière déclarative de la façon suivante :

Mais s'il est relativement facile de rédiger une telle description après avoir écrit la clause, il me semble plus difficile de rédiger une telle description comme étape préalable à l'écriture de la clause. C'est la raison pour laquelle je privilégie l'approche constructive lors de la conception de la définition d'un prédicats.

Toutefois, je ne saurais prétendre que cette approche est la meilleure pour tout le monde. C'est à vous de trouver votre propre voie.

C.dec4 : Un peu plus loin avec les listes

Je vous propose une étude de cas : résoudre le problème de la somme, c'est à dire rechercher s'il est possible de produire un entier $s$ appelé valeur cible en additionnant certains des éléments d'une liste $L$.

Par exemple, si $L$ est la liste $[3,5,11,13,17]$ et $s$ vaut 26, alors il n'y a aucune solution. Avec la même liste, si la valeur cible est 27 alors il y a une solution : 3+11+13= 27.

Pour résoudre ce problème, nous allons définir un prédicat somme tel que si L_in est une liste d'entiers positifs , X_in un entier positif ou nul, et S_out une variable non instanciée, alors le but...

somme(L_in, X_in, S_out).

...fait remonter dans S_out les listes d'éléments de L_in dont la somme est X_in.

Par exemple, l'évaluation du but...

somme([1,3,5,11,13,17],25,S).

...produira les solutions :

S = [1, 11, 13] S = [3, 5, 17]

Pour résoudre le problème récursivement, nous allons considérer que la difficulté d'une instance est la taille de la liste d'entrée. Commençons par chercher nos deux ingrédients. Pour mémoire, le premier ingrédient doit permettre de construire ou de décrire les solutions des instances dont la difficulté est sous un certain seuil. Le deuxième argument doit nous permettre de construire ou de décrire les solutions d'une instance à partir de celles d'une ou plusieurs instances moins difficiles.

Pour le problème de la somme, le premier ingrédient est que si la liste d'entrée est vide (instances de difficulté 0, qu'on appellera instances triviales), la seule valeur réalisable avec une somme d'éléments de la liste d'entrée est 0. Il permet d'écrire la clause non récursive suivante :

somme([],0,[]). % Cas trivial

Notre deuxième ingrédient doit nous permettre de produire (ou décrire) les solutions d'une instance non triviales en exploitant des solutions d'instances basées sur les listes de valeurs plus petites. Je vous propose d'y réfléchir en faisant l'expérience de pensée suivante :

Vous voulez résoudre une instance de difficulté 5.

Vous disposez d'un moyen de résoudre des instances de difficulté 4.

Exercice de découverte C.x5

On considère l'instance suivante du problème de la somme.

La liste d'entrée est [2,3,4,10,11].

La valeur cible est 25.

On suppose qu'on dispose d'un prédicat somme_ capable de résoudre le problème de la somme, mais seulement avec des listes d'entrée d'au plus 4 éléments.

En utilisant le prédicat somme_, donnez deux buts permettant d'obtenir des informations à partir desquelles on peut immédiatement déterminer les solutions de l'instance du problème de la somme décrite plus haut. Déduisez-en les solutions.

somme_([3,4,10,11],23,S). somme_([3,4,10,11],25,S).

En généralisant le principe utilisé dans l'exercice précédent, nous obtenons notre deuxième ingrédient, qui peut être exploité par les deux clauses récursives suivantes :

somme([T|R],S,[T|Q]) :- T=<S, S1 is S-T, somme(R,S1,Q). somme([_|R],S,Q) :- somme(R,S,Q).

La première clause récursive permet de rechercher les solutions utilisant le premier élément de la liste d'entrée, à condition que sa valeur ne soit pas plus grande que la valeur cible.

La deuxième clause récursive permet de rechercher les solutions n'utilisant pas le premier élément de la liste d'entrée.

La définition complète du prédicat somme est la suivante :

somme([],0,[]). somme([T|R],S,[T|Q]) :- T=<S, S1 is S-T, somme(R,S1,Q). somme([_|R],S,Q) :- somme(R,S,Q).

Faisons un petit essai pour le fun. Comment obtenir 301 avec 14, 25, 32, 47, 59, 61, 78, 83, 96 ?

somme([14,25,32,47,59,61,78,83,96],301,S).

Solutions :

S = [14, 47, 61, 83, 96] S = [32, 47, 61, 78, 83]

# data[].attributes.attachment_link.title
PROLOG : étape C - Activités d'apprentissages

# data[].attributes.attachment_link.description
Par O. Bailleux, Maître de conférences HDR à l'université de Bourgogne. Les activités de 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.

# data[].attributes.attachment_link.readable_text
Par O. Bailleux, Maître de conférences HDR à l'université de Bourgogne.

Règles complexes

Les activités d’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. Si vous avez besoin d’indices ou si vos solutions sont erronées, analysez les causes de vos erreurs – au besoin, demandez des explications à une personne qualifiée – et refaites les exercices concernés après un délai d’au moins une journée et au plus quelques jours.

Activité d’entraînement B.ent

B.ent1

On travaille avec une base de connaissances représentant trois types de plats utilisables dans des menus.

plat(entree, "pâté", 200, 6).
plat(entree, "salade", 120, 1).
plat(princ, "poulet frites", 360, 35).
plat(princ," couscous", 280, 18).
plat(dessert, "sorbet", 180, 0).
plat(dessert, "cake", 150, 4).

Les slots du prédicat plat représentent respectivement :

Le type d’un plat : entree pour une entrée, princ pour un plat principal, et dessert pour un dessert.

Son nom.

Son apport énergétique en kilocalories.

Son apport en protéines, exprimé en grammes.

Vous devez définir un prédicat repas permettant de composer un repas avec un nombre maximum donné de kilocalories et une quantité minimum donnée de protéines.

Par exemple, le but…

repas(700, 30, E, P, D).

…doit produire tous les repas constitués d’une entrée E, d’un plat principal P et d’un dessert D, ayant un apport énergétique inférieur ou égal à 700 kilocalories et comportant au moins 30 grammes de protéines.

Pour chaque résultat du but, le nom de l’entrée doit remonter dans la variable de sortie E, le nom du plat principal doit remonter dans la variable de sortie P et le nom du dessert doit remonter dans la variable de sortie D.

Les réponses produites par l’évaluation du but donné en exemple doivent être :

D = "sorbet", E = "salade", P = "poulet frites"
D = "cake", E = "salade", P = "poulet frites"

Remarque : pour exprimer que A est inférieur ou égal à B, on écrit A=<B et non A<=B. Cette syntaxe a pour but d’éviter de confondre l’opérateur de comparaison avec le symbole d’implication logique (bien que ce symbole s’écrive :- et non <=).

"Indice1"

Ce prédicat peut s’écrire avec une seule clause. Voici une solution partielle à compléter :

repas(CalMax, ProtMin, E, P, D) :-
    plat(entree, E, Cal1, Prot1),
    % À compléter

Le premier but de la clause dit que Le plat de nom E est une entrée qui apporte Cal1 kilocalories et Prot1 grammes de protéines.

Il reste à exprimer les deux plat restant (plat principal et dessert), et leurs apports en protéines et kilocalories, puis calculer l’apport total en énergie et protéines, puis exprimer les contraintes sur la quantité d’énergie de de calories.

"Indice2"

repas(CalMax, ProtMin, E, P, D) :-
    plat(entree, E, Cal1, Prot1),
    plat(princ, P, Cal2, Prot2),
    plat(dessert, D, Cal3, Prot3),
    Cal is ....., Prot is .....,
    % À compléter

Les variables Cal et Prot permettent de récupérer le nombre total de kilocalories et la quantité totale de protéines.

"Réponse"

repas(CalMax, ProtMin, E, P, D) :-
    plat(entree, E, Cal1, Prot1),
    plat(princ, P, Cal2, Prot2),
    plat(dessert, D, Cal3, Prot3),
    Cal is Cal1+Cal2+Cal3, Prot is Prot1+Prot2+Prot3,
    Cal=<CalMax, Prot>=ProtMin.

B.ent2

Le graphe suivant représente les liens de parenté entre plusieurs personnes dont les noms ont été remplacés par des numéros pour des raisons de protection des données personnelles (RGPD). Une flèche d’un sommet $A$ vers un sommet $B$ indique que $A$ est le père biologique ou la mère biologique de $B$.

Ces liens de parenté directs sont modélisés par le prédicat parent.

parent(1,4). parent(1,5). parent(2,4). parent(2,5).
parent(3,8). parent(3,9). parent(4,8). parent(4,9).
parent(5,10). parent(6,10). parent(6,11). parent(7,11).
parent(8,12). parent(10,12). parent(9,13). parent(11,13).

Question 1

On définit le prédicat siblings tel que siblings(A,B) est satisfait si et seulement si A est le frère ou la soeur de B dans le sens où :

1. il existe deux personnes distinctes qui sont toutes les deux parents directs de A et de B,

2. A et B sont deux personnes distinctes (on ne considère pas qu’une personne est son propre frère ou sa propre soeur.

siblings(A,B) :-
    parent(P1,A), % une personne P1 est père ou mère de A
    parent(P2,B), % une personne P2 est père ou mère de B
    P1\==P2,      % P1 et P2 sont deux personnes distinctes
    A\==B,        % A et B sont deux personnes distinctes
    parent(P1,B), % P1 est le père ou la mère de B
    parent(P2,A). % P2 est le père ou la mère de B

L’ordre dans lequel sont placé les but de la clause peut paraitre étrange. Il se justifie par les deux critères suivant :

1. Une condition telle que X\==Y échoue si au moins l’un des deux termes comparés est une variable non instanciée (n’ayant pas de valeur). Pour qu’une telle condition soit pertinente, il faut donc qu’au moment où elle est évaluée, les deux valeurs à comparer soient connues.

2. Pour des raisons d’efficacité, on a intérêt à placer ce genre de condition le plus tôt possible dans l’ordre des buts d’une clause car cela limitera la combinatoire de la recherche de solutions.

Mais il y a un problème avec ce prédicat. Si on évalue le but…

siblings(8,S).

…on obtient deux fois la même réponse :

S = 9
S = 9

…car les deux variable P1 et P2 sont en quelque sorte interchangeables. Le but a été satisfait deux fois :

Une fois avec P1=3 et P2=4.

Une fois avec P1=4 et P2=3.

Cherchez un moyen d’éviter ce petit problème en modifiant la définition du prédicat. N’hésitez pas à faire des essais sur machine.

"Indice"

On peut modifier la condition P1\==P2 en la remplaçant par une autre, plus restrictive, sachant que les valeurs P1 et P2 sont des entiers.

"Réponse"

On remplace P1\==P2 par P1<P2.

siblings(A,B) :-
    parent(P1,A), parent(P2,A), P1<P2,
    parent(P1,B), parent(P2,B), A\=B.

Question 2

On évalue le but…

siblings(X,Y).

…et on obtient le résultat :

X = 4, Y = 5
X = 5, Y = 4
X = 8, Y = 9
X = 9, Y = 8

Pourquoi obtient-on deux fois chacune des deux fratries ?

"Réponse"

Parce-que les rôles des variables A et B sont interchangeables et qu’il y a donc deux manières de satisfaire le but pour chaque fratrie.

Comment pourrait-on éviter cette redondance en modifiant le but, sans changer la définition du prédicat ?

Si on incorporait la nouvelle condition dans la définition du prédicat, cela pourrait-il poser problème pour certains buts ? Donnez un exemple.

"Réponse"

Si on remplace A\==B par A<B dans la clause qui définit le prédicat siblings, comme ceci…

siblings(A,B) :-
    parent(P1,A), parent(P2,B),
    P1<P2, A<B,
    parent(P1,B), parent(P2,A).

…alors le fonctionnement avec un but tel que…

siblings(X,Y).

…sera correct, mais par exemple le but…

siblings(9,S).

…va échouer car la condition A<B impose que la valeur S soit le plus petite que 9.

Question 3

Une personne A est un ancêtre d’une personne B si et seulement si une des deux propositions suivantes est vraie :

1. A est parent direct de B.

2. A est ancêtre d’un parent direct de B.

Définissez le prédicat ancetre tel que ancetre(A,B) soit satisfait si et seulement si A est une personne ancêtre de B.

"Indice1"

Il faut deux clauses :

Une clause qui concerne la cas où l’ancêtre est un parent direct.

Une clause récursive qui concerne l’autre cas.

"Indice2"

ancetre(A,B) :- parent(A,B).
ancetre(A,B) :- parent(..... , .....), ancetre(..... , .....).

"Réponse"

ancetre(A,B) :- parent(A,B).
ancetre(A,B) :- parent(P,B), ancetre(A,P).

Donnez le but permettant de rechercher tous les ancêtre de la personne numéro 12.

Donnez un but permettant de rechercher une personne dont les deux parents biologiques ont au moins un ancêtre commun.

"Réponse"

ancetre(A,P1), ancetre(A,P2), P1<P2, parent(P1,X), parent(P2,X).

C’est la valeur de X qui nous intéresse dans les résultats, qui sont :

A = 1, P1 = 8,  P2 = 10, X = 12
A = 2, P1 = 8,  P2 = 10, X = 12

Le résultat révèle que les deux parents de la personne 12 ont deux ancêtres communs, qui sont les personnes 1 et 2.

En utilisant la condition P1\==P2 au lieu de P1<P2, on obtient 4 résultats qui désignent tous (de manière redondante) que la personne 12 a deux parents directs ayant les mêmes ancêtres, à savoir les personnes 1 et 2.

Question 4

On définit ainsi la notion d’ancêtre de rang $r$ d’une personne X :

Les ancêtres de rang 1 de X sont ses parents biologiques.

Pour tout $r>1$, toute personne P est ancêtre de rang $r$ de X si et seulement si elle est ancêtre de rang $r-1$ d’un parent direct de X.

Quels sont les ancêtres de rang 2 de la personne numéro 13 ?

"Réponse"

Les personnes 3, 4, 6 et 7.

Définissez le prédicat ancetre tel que le but ancetre(A_out,R_out,B_in) permette de rechercher tous les ancêtres d’une personne B_in donnée. Ce prédicat doit être utilisable avec son dernier slot en entrée. Les deux autres slots, utilisés en sortie, permettent de récupérer le numéro et le rang d’un ancêtre de B_in.

Par exemple, le but…

ancetre(A,Rang,9).

…doit produire la réponse…

A = 3, Rang = 1
A = 4, Rang = 1
A = 1, Rang = 2
A = 2, Rang = 2

…qui donne les quatre ancêtres connus de la personne numéro 9 et les rangs correspondants. La personne 3 est ancêtre de rang 1 de la personne 9, etc.

"Indice1"

Le prédicat s’écrit en deux clauses :

La première clause indique simplement qu’un ancêtre de rang 1 est un parent direct.

La deuxième dit que si une certaine personne P est ancêtre de rang N d’un parent direct d’une personne B, alors elle est ancêtre de rang N+1 de B.

ancetre(A,1,B) :- parent(A,B).
ancetre(A,R,B) :- .......... .

"Indice2"

Détaillons la structure de la deuxième clause :

ancetre(A,R,B) :- % Conclusion
    .......... ,  % Prémisse 1
    .......... ,  % Prémisse 2
    .......... .  % Prémisse 2

Si P est un parent direct de B (Prémisse 1)

et si A est un ancêtre de rang N de P (Prémisse 2)

et si R vaut N+1 (Prémisse 3)

alors A est un ancêtre de rang R de B. (Conclusion)

"Réponse"

ancetre(A,R,B) :-   % Conclusion
    parent(P,B),    % Prémisse 1
    ancetre(A,N,P), % Prémisse 2
    R is N+1.       % Prémisse 2

Question 5

Donnez un but permettant de rechercher tous les ancêtres de rang au moins égal à deux de la personne 12. Ce but peut comporter plusieurs sous-buts.

Donnez le but permettant de rechercher toutes les personnes ayant pour ancêtre la personne 4 et les rangs auxquels ses personnes sont ancêtres de la personne 4. La réponse attendue est :

B = 8, Rang = 1
B = 9, Rang = 1
B = 12, Rang = 2
B = 13, Rang = 2

Question 6

Comme pour les questions précédentes, on considère uniquement la base de connaissances suivante :

parent(1,4). parent(1,5). parent(2,4). parent(2,5).
parent(3,8). parent(3,9). parent(4,8). parent(4,9).
parent(5,10). parent(6,10). parent(6,11). parent(7,11).
parent(8,12). parent(10,12). parent(9,13). parent(11,13).

Donnez un but permettant de rechercher toutes les personnes apparaissant dans cette base de connaissance qui n’ont aucun enfant.

"Réponse"

parent(_,X), not(parent(X,_)).

Prêt pour la suite ?

Les notions qui ont été introduites dans cette étape permettent de réaliser des choses intéressantes, mais c’est à l’étape suivante (Étape C) que toute la puissance de Prolog va être révélée.

Si vous avez eu des difficultés à traiter certains exercices, si certaines de vos solutions ne correspondaient pas à celles données, je vous conseille de traiter à nouveau ces exercices après au moins une nuit de sommeil et au plus quelques jours.

Si certains points ne sont pas limpides, posez des questions aussi précises que possible à une personne maitrisant parfaitement les notions concernées.

Un petit challenge ?

Je préfère réserver les challenges aux parties suivantes, dans lesquelles nous pourrons utiliser des structures de données telles que des listes et des arbres. Voici toutefois deux problèmes intéressants qui peuvent vous aider à développer votre "pensée Prolog".

Ne traitez ces problème que si vous avez une certaine aisance avec les compétences entrainées dans la section B.ent et que vous souhaitez approfondir ces compétences. Dans le cas contraire, je vous conseille de passer directement à l’étape C.

Les solutions ne sont pas données. Faites des essais sur machine jusqu’à ce que vous parveniez à les trouver vous-même.

B.top1

Vous devez définir un prédicat range permettant de produire les entiers compris entre deux bornes.

Par exemple, le but…

range(3,6,X).

…doit produire le résultat :

X = 3
X = 4
X = 5
X = 6

"Indice"

Un nombre $x$ appartient à l’intervalle $[\text{min}..\text{max}]$ si et seulement si une des deux conditions suivantes est satisfaite :

1. $x = \text{min}$

2. $\text{max}>\text{min}$ et $x$ appartient à l’intervalle $[\text{min+1}..\text{max}]$

B.top2

On rappelle que les termes de rang 0 et 1 de la suite de Fibonacci ont la valeur 1 et qu’ensuite chaque terme est la somme des deux précédents.

rang | 0 | 1 | 2 | 3 | 4 | 5 | 6
valeur | 1 | 1 | 2 | 3 | 5 | 8 | 13

Un des exercices de découverte consistait à définir le prédicat fibo permettant de calculer le terme d’un rang N donné de la suite de Fibonacci.

fibo(0,1).
fibo(1,1).
fibo(N,F) :- N>1, N1 is N-1, N2 is N-2,
    fibo(N1,F1), fibo(N2,F2), F is F1+F2.

Ce prédicat est peu efficace car il comporte deux invocations récursives. Par exemple, lors du calcul du terme de rang 7, le calcul du terme de rang 2 est réalisé 8 fois, ce qui n’est pas très raisonnable.

Votre mission, si vous l’acceptez, est de définir un prédicat fibo permettant de calculer, pour un entier $n$ donné en entrée, les termes de rangs $n$ et $n-1$ de la suite de Fibonacci. Par exemple, le but..

fibo(6, P, N)

…doit produire le résultat…

N = 13, P = 8

…parce que le terme de rang 6 est 13 et que le terme précédent est 8.

La définition de ce prédicat doit comporter une seule invocation récursive et non deux comme la variante traitée en exercice de découverte.

# data[].attributes.attachment_link.title
PROLOG : étape B – entrainement – Activités d’apprentissages

# data[].attributes.attachment_link.description
Par O. Bailleux, Maître de conférences HDR à l’université de Bourgogne.

# data[].attributes.attachment_link.readable_text
Par O. Bailleux, Maître de conférences HDR à l'université de Bourgogne.
Cette activité de découverte consiste à é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.

Activité de découverte B.dec

Introduction

Nous allons découvrir comment et pourquoi écrire des règles récursives, mais aussi quelques briques de constructions permettant d'enrichir la puissance d'expression des prédicats, telles que la négation, les variables anonymes, et le moyen de réaliser des calculs arithmétiques.

B.dec1 : 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.

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 :

Deuxième clause :

Par exemple, le but...

sup(S,edouard).

...a pour résultat :

S = dave S = anne S = charlie

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.

Exercice de découverte B.x1

Sans utiliser d'interpréteur Prolog, déterminez le résultat du but suivant :

sup(charlie,J).

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.

B.dec2 : Négation et variables anonymes

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 anonyme :

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 but mentor(_,L) est satisfait si L a 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 de mentor(_,L).

L'évaluation d'une négation ne peut pas instancier 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 anonymes.

Par exemple, le but...

not(leader(L,charlie)).

...a pour résultat false. Ce but ne permet pas de récupérer tous 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 B.x2

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.)

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.

B.dec3 : Arithmétique

Les entiers naturels peuvent être représentés par des termes fonctionnels, comme les autres données pouvant être traitées par Prolog, mais cette approche, bien que très puissante (elle permet à Prolog de de résoudre des équations), est inefficace pour beaucoup d'applications pratiques, lorsque les valeurs manipulées dépassent quelques centaines d'unités.

Cette limitation peut être contournée avec des extensions de Prolog permettant de spécifier et résoudre des contraintes arithmétiques sur des entiers ou des réels. On entre alors dans le domaine, très vaste, de la programmation logique avec contraintes.

Mais en Prolog de base, l'instruction is est le seul moyen d'évaluer le résultat d'un calcul arithmétique. Par exemple, le but...

...a pour résultat :

Si on remplace is par le symbole =, appelé symbole d'unification, comme ceci...

...on obtient :

Il n'y a pas d'erreur de syntaxe, mais l'expression arithmétique n'est pas évaluée. La variable X est instanciée avec l'expression elle-même, qui a le statut de terme fonctionnel, et non avec le résultat. L'évaluation peut d'ailleurs être différée. Le but...

...produit le résultat :

L'instruction is ne fonctionne que si toutes les valeurs de l'expression à évaluer sont connues au moment de l'évaluation. Elle n'est pas réversible. Par exemple, le but...

...échoue. Il ne permet pas de trouver la valeur X telle que 7 + X vaut 12.

Voici un prédicat permettant de calculer une factorielle. C'est un exemple complètement bateau, mais qui permet de comprendre certains points importants.

fact(0,1). fact(N,F) :- N>0, N1 is N-1, fact(N1,F1), F is N*F1.

Voici un exemple d'utilisation de ce prédicat pour calculer la factorielle de 5.

Le résultat est :

Le prédicat fact est défini de manière récursive. Il s'appuie sur la définition par récurrence de la fonction factorielle :

Si vous êtes habitué à un langage de programmation procédural, objet ou même fonctionnel, la définition du prédicat fact peut vous paraître déroutante, mais elle est en fait facile à comprendre si on tient compte de deux faits :

1. Un prédicat Prolog ne retourne pas de valeur. Il peut juste réussir ou échouer. Mais il peut permettre de produire une ou plusieurs valeurs en les faisant remonter dans une variable non instanciée située dans un slot utilisé en sortie.

2. Tout calcul arithmétique doit être réalisé en utilisant l'instruction is.

Le premier slot de fact ne peut être utilisé qu'en entrée en raison des limitations de l'instruction is. Le deuxième slot peut être utilisé en entrée, mais nous allons raisonner uniquement sur la cas où il est utilisé en sortie, pour récupérer le résultat du calcul d'une factorielle, ce qui est la vocation première du prédicat.

Cette figure illustre les différentes étapes de calcul dans le cas où N a une valeur supérieure à 0 et montre le cheminement des résultats intermédiaires successifs.

Nous sommes assez loin de l'idéal déclaratif de Prolog, mais pour utiliser ce langage en pratique, il ne faut pas s'enfermer dans un dogmatisme rigide.

Supposons donc qu'une valeur d'entrée N supérieure à 0 soit placée dans le premier slot. Voici les différentes étapes d'évaluation de cette clause, qui correspondent au buts numérotés de 1 à 4.

1. Le but N>0 réussit seulement si N est strictement positif. Dans le cas contraire, c'est la première clause qui aura fournit le résultat.

2. Le but N1 is N-1 calcule la valeur $N-1$ et place le résultat dans la variable N1.

3. Le but fact(N1,F1) invoque récursivement le prédicat fact pour calculer la factorielle de $N-1$ et faire remonter le résultat dans la variable F1.

4. Le but F is N*F1 calcule le résultat en multipliant factorielle de $N-1$ par $N$ et le place dans la variable de sortie F.

On peut aussi décrire cette clause de manière déclarative :

Cette description est toutefois un peu trompeuse dans le cas de ce prédicat pour lequel l'ordre des buts est critique (alors qu'en logique, le connecteur et est commutatif) et qui utilise l'instruction is qui n'est pas déclarative, mais impérative : elle décrit un calcul et non une relation.

Exercice de découverte B.x3

Définissez le prédicat fibo tel que le but...

fibo(N_in,R_out).

..., où N_in est une valeur d'entrée et R_out une variable de sortie, produise dans la variable R_out le terme de rang N_in de la suite de Fibonacci.

La suite de Fibonacci est définie de la manière suivante :

Les termes de rang 0 et 1 ont la valeur 1.

Chacun des autres termes a pour valeur la somme des deux termes précédents.

Voici le début de cette suite.

Par exemple, le but...

...produit le résultat R=5.

Dans cet exercice, vous ne devez pas vous soucier de l'efficacité de l'implémentation, mais opter pour la solution la plus simple.

Prêt pour la suite ?

Si vous n'avez pas bien compris certaines explications, ou des exemples, ou des solutions proposées pour les exercices de découverte, vous devez poser à une personne maîtrisant bien Prolog des questions précises qui ciblent vos difficultés.

Vous avez compris les notions et principes qui viennent d'être introduits ? Vous devez maintenant continuer votre apprentissage en réalisant les activités d'entrainement B.ent.

# data[].attributes.attachment_link.title
PROLOG : étape B - Activités d'apprentissages

# data[].attributes.attachment_link.description
Par O. Bailleux, Maître de conférences HDR à l'université de Bourgogne. Cette activité de découverte consiste à é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.

# data[].attributes.headline
Activités de découverte et d'entrainement

# data[].attributes.subject
Activités de découverte et d'entrainement

# data[].attributes.attachment_link.readable_text
Par O. Bailleux, Maître de conférences HDR à l'université de Bourgogne.

Interroger une base de connaissances

Les activités de 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 d’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. Si vous avez besoin d’indices ou si vos solutions sont erronées, analysez les causes de vos erreurs – au besoin, demandez des explications à une personne qualifiée – et refaites les exercices concernés après un délai d’au moins une journée et au plus quelques jours.

Activité de découverte A.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écessiteraient des pages de code 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.

A.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 attribue des classes à des joueurs et des joueuses. 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 A.x1

Quels personnes ont la compétence soigneur ?

Quels personnes peuvent tanker et soigner ?

"Réponse"

Charlie, Dave et Edouard sont soigneurs.

Dave et Edouard peuvent tanker et soigner.

A.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 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

Pour essayer ces requêtes, vous pouvez utiliser un interpréteur Prolog. Le plus connu est swiProlog. Il existe une version utilisable en ligne via un navigateur WEB : SWISH.

Les faits et autres éléments du programme doivent être écrits dans le panneau de gauche. Le but doit être écrit dans le panneau situé en bas à droite. Les résultats apparaissent dans le panneau situé en haut à droite.

On peut formuler des buts composés de plusieurs sous-buts, comme par exemple…

jc(X,Y),cc(Y,dps).

…qui est satisfait par toute personne X dont la classe Y est associée à 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 A.x2

Donnez le but permettant de savoir quelles sont les compétences de Dave.

"Réponse"

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.

"Réponse"

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).

"Réponse"

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.

A.dec3 : Clauses

Les faits 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.

En français, on peut définir le prédicat ainsi :

Si J a la classe X et si X a la compétence A, alors J a la compétence A.

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 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 A.x3

Sans utiliser d’interpréteur Prolog, donnez les résultats du but :

peut(J, soigneur).

"Réponse"

J = charlie
J = dave
J = edouard

Sans utiliser d’interpréteur Prolog, donnez les résultats du but :

peut(anne, tank).

Sans utiliser d’interpréteur Prolog, donnez les résultats du but :

peut(dave, soigneur).

"Réponse"

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.

A.dec4 : 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 appelé arité.

Par exemple, dans le but…

peut(anne,tank).

…le premier slot reçoit la valeur anne et le deuxième la valeur tank. 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…

peut(anne,A).

…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 A.x4

Déterminez 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, si ce premier sous-but réussit, le deuxième sous-but est ensuite évalué pour chaque réponse du premier sous-but.

peut(X,dps),peut(X,soigneur).

"Réponse"

Le premier slot du premier sous-but 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 du premier sous-but est utilisé en entrée puisqu’il est garni par une valeur (techniquement, une constante fonctionnelle) et non une variable.

Les deux slots du deuxième sous-but sont utilisés en entrée. En effet, au moment où ce sous-but est évalué (si applicable) , la variable X est instanciée.

Que est le résultat de ce but ?

A.dec5 : 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 :

1. Si J peut tanker et si J peut soigner alors J est polyvalent.

2. Si J peut faire des dégâts (dps) et si J peut soigner alors J est polyvalent.

Le but…

polyvalent(J).

…donne comme résultat :

J = dave
J = edouard
J = charlie

Il est possible de regrouper ces deux clauses en une même règle (qui n’est plus une clause) en utilisant le point virgule ; pour exprimer une disjonction, aussi appelée ou logique.

polyvalent(J) :- (peut(J,tank); peut(J,dps)), peut(J,soigneur).

Exercice de découverte A.x5

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 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 défini précédemment :

peut(J,A) :- jc(J,X), cc(X,A).

"Réponse"

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.

"Réponse"

Dave peut tanker et soigner, ce qui permet de satisfaire la première clause lorsque X et Y ont toutes les deux la valeur dave. Edouard est dans le même cas. Charlie peut faire des dégâts et soigner, ce qui permet de satisfaire la deuxième clause lorsque X et Y ont toutes les deux la valeur charlie.

On peut éviter ce problème en ajoutant le but X\==Y à la fin de chacune des deux clauses.

Soient les deux prédicats suivants :

duo_v1(X,Y) :- peut(X,tank), peut(Y,soigneur), X\==Y.
duo_v1(X,Y) :- peut(X,dps), peut(Y,soigneur), X\==Y.

duo_v2(X,Y) :- (peut(X,tank) ; peut(X,dps)) , peut(Y,soigneur), X\==Y.

Les deux buts suivants produisent-ils les mêmes réponses ?

duo_v1(X,Y).
duo_v2(X,Y).

"Réponse"

Oui. Les deux clauses de la première version ont été regroupées en une seule règle dans la deuxième version grâce à l’utilisation du point virgule qui représente une disjonction. Les deux prédicats sont équivalents.

Soit le prédicat suivant :

duo_v3(X,Y) :- peut(Y,soigneur) , (peut(X,tank) ; peut(X,dps)), X\==Y.

Les deux buts suivants produisent-ils les mêmes réponses ?

duo_v2(X,Y).
duo_v3(X,Y).

"Réponse"

Oui, car les connecteurs logiques et (,) et ou (;) sont commutatifs. (Mais l’ordre des réponses est différent en raison du mécanisme d’évaluation de Prolog qui tente de satisfaire les buts d’une règle en les parcourant de gauche à droite.)

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 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ées 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 utilise un mécanisme plus complexe appelé unification, que nous n’aborderons pas pour l’instant.

Activité d’entraînement A.ent

A.ent1

On considère les trois prédicats définis ci-dessous.

vehicule(v100, b, essence).
vehicule(v101, b, electrique).
vehicule(v102, a, essence).
vehicule(v103, a, essence).
vehicule(v104, c, diesel).
vehicule(v105, c, diesel).

Ce prédicat établit une relation entre les identifiants des véhicules d’une entreprise de livraison, les types de permis requis pour les conduire et le type d’énergie qui les fait fonctionner.

personne(c310, "Paul").
personne(c311, "Anne").
personne(c312, "Fred").
personne(c317, "Rory").

Ce prédicat établit une relation entre les identifiants et les noms des personnes pouvant conduire les véhicules.

qualif(c310,b).
qualif(c311,b).
qualif(c311,a).
qualif(c312,a).
qualif(c312,b).
qualif(c312,c).
qualif(c317,b).

Ce prédicat établit une relation entre les identifiants des personnes pouvant conduire des véhicules et le type de permis de conduire que possèdent ces personnes.

Les réponses aux questions posées doivent être valables pour des bases de connaissances définies avec les mêmes prédicats mais ayant des contenus différents.

Question 1

Donnez un but permettant de connaître les identifiants des véhicules à essence et les types de permis requis pour les conduire.

Question 2

Donnez un but permettant de connaître les noms des personnes ayant un permis de type a.

"Réponse"

personne(I,Nom),qualif(I,a).

Les noms des personnes recherchées seront remontés dans la variable N. Les identifiants de ces personnes seront également remontés dans la variable I. Le résultat sera :

I = c311, Nom = "Anne"
I = c312, Nom = "Fred"

Question 3

Donnez un but permettant de connaître les noms des personnes pouvant conduire un véhicule électrique.

"Indice"

vehicule(Iv,.....,electrique),qualif(.....,.....),personne(.....,Nom).

"Réponse"

vehicule(Iv,Permis,electrique),qualif(Ip,Permis),personne(Ip,Nom).

La variable Ip, qui représente un identifiant de personne, permet de faire le lien entre le nom d’une personne et les types de permis qu’elle possède. La variable Iv, qui représente un identifiant de véhicule, n’a pas d’intérêt particulier dans cette requête. On pourrait la remplacer par une "variable joker", notée _.

vehicule(_,Permis,electrique),qualif(Ip,Permis),personne(Ip,Nom).

Question 4

Définissez le prédicat qualif_bc tel que qualif_bc(P) soit satisfait par tout identifiant P d’une personne titulaire d’un permis b ou d’un permis c.

"Indice"

qualif_bc(I) :- ..... .
qualif_bc(I) :- ..... .

"Réponse"

qualif_bc(I) :- qualif(I,b).
qualif_bc(I) :- qualif(I,c).

On aurait put également écrire…

qualif_bc(I) :- qualif(I,b) ; qualif(I,c).

…en faisant bien attention à utiliser un point virgule (disjonction) et non une virgule (conjonction) pour séparer les deux sous-buts.

Question 5

Donnez un but permettant de connaître les noms des personnes pouvant conduire le véhicule v101 et le véhicule v102.

"Indice"

vehicule(v101,P1,E1), vehicule(v102,P2,E2),
qualif(Ip,.....), qualif(Ip,.....), personne(.....,Nom).

"Réponse"

vehicule(v101,P1,E1), vehicule(v102,P2,E2),
qualif(Ip,P1), qualif(Ip,P2), personne(Ip,Nom).

Ici, il faut bien comprendre que le but parle d’une même personne, d’identifiant Ip, ayant un permis de type P1 permettant de conduire le véhicule v101 et un permis de type P2 permettant de conduire le véhicule v102.

Prêt pour la suite ?

Les notions qui ont été introduites dans cette étape ne permettent pas de faire des choses vraiment passionnantes, mais il est nécessaire de les maîtriser avant passer à la suite.

Si vous avez eu des difficultés à traiter certains exercices, si certaines de vos solutions ne correspondaient pas à celles données, je vous conseille de traiter à nouveau ces exercices après au moins une nuit de sommeil et au plus quelques jours.

Si certains points ne sont pas limpides, posez des questions aussi précises que possible à une personne maitrisant parfaitement les notions concernées.

# data[].attributes.attachment_link.title
PROLOG : étape A – Activités d’apprentissages

# data[].attributes.attachment_link.description
Par O. Bailleux, Maître de conférences HDR à l’université de Bourgogne.

# data[].attributes.body
représentation, prédicats exploitant ds listes, pensée récursive, coupe-choix

# data[].attributes.body
récursivité, négation, variables jokers, arithmétique

# data[].attributes.body
faits, clauses, règles, disjonction, buts

# data[].attributes.body
À toute personne, même débutante, intéressée par la découverte d'une approche originale, puissante, étonnante, de  la programmation, qui, une fois maîtrisée, permet de réaliser en quelques lignes des applications qui nécessitent des pages de code avec d'autres langages tels que C, C++, Java, ou même Python.

# data[].attributes.attachment_link.readable_text
Le langage de programmation Prolog a vu le jour il y a cinquante ans.

Pour célébrer cet anniversaire, nous déclarons 2022 Année Prolog !

Au programme des festivités figurera un concours pour un Prix Alain Colmerauer remis par un jury international.

Voici le texte complet de l'annonce :

et la liste de ses signataires au 24 janvier 2022 :

Célestin Sedogbo

Jean Rohmer

Bob Kowalski

Colette Colmerauer

Guy A. Narboni

Henry Kanoui

Marc Bergman

Pascal Van Hentenryck

Laurent Chaudron

Laurent Cervoni

Veronica Dahl

Philippe Roussel

Mirek Truszczynski

Thomas Eiter

Jean-François Perrot

Philipp Körner

Jan Wielemaker

David S. Warren

Gopal Gupta

Actualités : février 2022

Constitution d'un Comité scientifique international pour le Prix Alain Colmerauer, présidé par Robert Kowalski, Professeur émérite et Distinguished Research Fellow de l' Imperial College de Londres.

Les membres de ce comité sont :

# data[].attributes.attachment_link.keywords[]
programmation en logique par contraintes

# data[].attributes.attachment_link.description
Le langage de programmation Prolog a vu le jour il y a cinquante ans. Pour célébrer cet anniversaire, nous déclarons 2022 Année Prolog ! Au programme des festivités figurera un concours pour un Prix Alain Colmerauer remis par un jury international.

# data[].attributes.body
Pour chaque étape, faites d'abord l'activité de découverte, puis l'activité d'entrainement.
Si vous ne réussissez pas à résoudre un exercice ou si vous avez besoin de révéler certains indices, tentez de le traiter à nouveau après au moins une nuit de sommeil.
Ne traitez les exercices challenges que lorsque les exercices d'entraînement ne vous posent plus de problème.
En cas de difficultés, vous pouvez demander de l'aide sur le serveur Discord dédié.

# data[].attributes.body
Olivier Bailleux est maître de conférences habilité à diriger des recherche à l'Université de Bourgogne (laboratoire LIB). Il enseigne la programmation objet, la programmation par contraintes, la programmation logique, la programmation fonctionnelle et la programmation de bas niveau en langages C et C++. Son domaine de recherche est l'IA symbolique, et plus spécifiquement la résolution des problèmes NP-complets, le problème SAT et la traduction de contraintes.

# data[].attributes.body
Vous faire découvrir un langage et un paradigme de programmation d'une rare puissance expressive et complètement différent de l'approche classique, dite "impérative".

Promouvoir une approche pédagogique permettant à chaque personne apprenante de progresser à son propre rythme, aussi vite que le permettent le temps et les efforts investis dans les activités d'apprentissage.

# data[].attributes.body
Un langage de programmation déclaratif (on spécifie le problème à résoudre sans détailler les étapes de calcul) basé sur la logique du premier ordre.
Prolog est une porte d'entrée dans l'univers de l'IA symbolique, mais son champ d'application est beaucoup plus large.