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 ?
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.
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.
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
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 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).
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.
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).
- Le premier slot du premier sous-but est utilisé en sortie, car
Xn’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
Xest instanciée.

Que est le résultat de ce but ?
X = charlie
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 :
- 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

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).
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 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).
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).
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.
vehicule(I,P,essence).
Question 2
Donnez un but permettant de connaître les noms des personnes ayant un permis de type a.
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.
vehicule(Iv,.....,electrique),qualif(.....,.....),personne(.....,Nom).
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.
qualif_bc(I) :- ..... .
qualif_bc(I) :- ..... .
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.
vehicule(v101,P1,E1), vehicule(v102,P2,E2),
qualif(Ip,.....), qualif(Ip,.....), personne(.....,Nom).
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.