PREMIERS PAS EN PROLOG

Fonctionnement
Utilisation pour des bases de connaissances
Listes
PROGRAMMATION LOGIQUE

¢ Origines :
— 1970, Marseille, Colmerauer
— Edimbourg, Warren
¢ Bibliographie

— L. Sterling, E. Shapiro, L’art de Prolog, Masson

— Clocksin, Mellish, Programmer en Prolog, Eyrolles

Licence Lyon1 - UE LIFprolog N. Guin

LE LANGAGE PROLOG

¢ Langage d’expression des connaissances fondé

sur le langage des prédicats du premier ordre

¢ Programmation déclarative :
— L’utilisateur définit une base de connaissances
— L’interpréteur Prolog utilise cette base de
connaissances pour répondre à des questions

Licence Lyon1 - UE LIFprolog N. Guin

CONSTANTES ET VARIABLES

¢ Constantes
— Nombres : 12, 3.5
— Atomes
¢ Chaînes de caractères commençant par une minuscule
¢ Chaînes de caractères entre " "

¢ Liste vide []

¢ Variables
¢ Chaînes de caractères commençant par une majuscule
¢ Chaînes de caractères commençant par _

¢ La variable « indéterminée » : _

Licence Lyon1 - UE LIFprolog N. Guin

TROIS SORTES DE CONNAISSANCES :
FAITS, RÈGLES, QUESTIONS

¢ Faits : P(…). avec P un prédicat

pere(jean, paul).
pere(albert, jean).
Clause de Horn réduite à un littéral positif
¢ Règles : P(…) :- Q(…), …, R(…).
papy(X,Y) :- pere(X,Z), pere(Z,Y).
Clause de Horn complète
¢ Questions : S(…), …, T(…).
pere(jean,X), mere(annie,X).
Clause de Horn sans littéral positif
5

Licence Lyon1 - UE LIFprolog N. Guin

RÉFUTATION PAR RÉSOLUTION

¢ Programme P
— P1 : pere(charlie, david).
— P2 : pere(henri, charlie).
— P3 : papy(X,Y) :- pere(X,Z), pere(Z,Y).
¢ Appel du programme P
— A: papy(X,Y).
¢ Réponse : X=henri, Y=david

Licence Lyon1 - UE LIFprolog N. Guin

GRAPHE DE RÉSOLUTION
A : ¬papy(X,Y) P3 : ¬pere(X1,Z1)Ú¬pere(Z1,Y1)Úpapy(X1,Y1)

X|X1
Y|Y1

¬pere(X,Z1)Ú¬pere(Z1,Y) P2 : pere(henri, charlie)

henri|X
charlie|Z1
charlie|X
david|Z1
P1 : pere(charlie, david) ¬pere(charlie, Y)

P1 : pere(charlie, david)
david|Y

¬pere(david, Y)
échec : retour arrière succès de la réfutation
7

Licence Lyon1 - UE LIFprolog N. Guin

INTERPRÉTATION PROCÉDURALE : ARBRE ET-OU

papy(X,Y)
P3
et

pere(X,Z) pere(Z,Y)
ou pere(david,Y) pere(charlie,Y)
P1 P2
ou ou
P1 P2 P1 P2
X=charlie X=henri
Z=david Z=charlie
échec échec Y=david
succès
8

Licence Lyon1 - UE LIFprolog N. Guin

 MON PREMIER PROGRAMME (1)
pere(charlie,david).
pere(henri,charlie).
papy(X,Y) :- pere(X,Z), pere(Z,Y).
lirispc1$ swiprolog
Welcome to SWI-Prolog (Version 3.3.0)
Copyright (c) 1993-1999 University of Amsterdam.
All rights reserved.
For help, use ?- help(Topic). or ?-apropos(Word).
?- [pere].
% pere compiled 0.00 sec, 824 bytes
true.
?- listing.
pere(charlie, david).
pere(henri, charlie).
papy(A, B) :-
pere(A, C),
pere(C, B).
true. 9

Licence Lyon1 - UE LIFprolog N. Guin

 MON PREMIER PROGRAMME (2)
?- pere(charlie,david). ?- papy(x,y).
true. false.
?- pere(charlie,henri). ?- papy(X,Y).
false. X = henri
?- pere(X,Y). Y = david
X = charlie
Y = david ?- papy(henri,X).
true. X = david
?- pere(X,Y). true.
X = charlie ?- halt.
Y = david ; lirispc1$
X = henri
Y = charlie

10

Licence Lyon1 - UE LIFprolog N. Guin

ORDRE DES RÉPONSES
pere(charlie, david). ?- parents(X,Y,Z).
pere(henri, charlie).
pere(david, luc). X = david
Y = charlie
mere(sophie, charlie). Z = anne ;
mere(anne, david).
X = charlie
parents(E, P, M) :- Y = henri
pere(P, E), Z = sophie ;
mere(M, E).
false.

Prolog parcourt le paquet de clauses de haut en bas,

chaque clause étant parcourue de gauche à droite
11

Licence Lyon1 - UE LIFprolog N. Guin

EXERCICES

¢ Construire l’arbre ET-OU permettant à Prolog de

donner l’ensemble des réponses satisfaisant la
requête parents(X,Y,Z).

¢ On définit le programme suivant :

b(1). b(2). c(3). c(4). d(5). d(6).
a(X,Y,Z) :- b(X), c(Y), d(Z).
— Donner toutes les réponses à la requête a(X,Y,Z) dans
l’ordre où Prolog les fournit.

12

Licence Lyon1 - UE LIFprolog N. Guin

L’ÉNIGME POLICIÈRE EN PROLOG

¢ On dispose des informations suivantes :

— La secrétaire déclare qu’elle a vu l’ingénieur dans le
couloir qui donne sur la salle de conférences
— Le coup de feu a été tiré dans la salle de conférences,
on l’a donc entendu de toutes les pièces voisines
— L’ingénieur affirme n’avoir rien entendu

¢ On souhaite démontrer que si la secrétaire dit

vrai, alors l’ingénieur ment

13

Licence Lyon1 - UE LIFprolog N. Guin

L’ÉNIGME POLICIÈRE EN PROLOG

¢ Ordre 1 : un individu entend un bruit s’il se trouve

dans une pièce voisine de celle où le bruit a été
produit
entend(Ind,Bruit) :- lieu(Ind,Piece1), lieu(Bruit,Piece2),
voisin(Piece1,Piece2).

¢ Faits relatifs à l’énigme :

voisin(couloir,salle_de_conf).
lieu(coup_de_feu,salle_de_conf).
lieu(ingenieur,couloir) :- secretaire_dit_vrai.
ingenieur_ment :- entend(ingenieur,coup_de_feu).
14

Licence Lyon1 - UE LIFprolog N. Guin

L’ÉNIGME POLICIÈRE EN PROLOG

¢ Hypothèse
secretaire_dit_vrai.
¢ Pour la démonstration, on pose la requête :
ingenieur_ment.

15

Licence Lyon1 - UE LIFprolog N. Guin

SYMBOLES FONCTIONNELS

¢ La fonction « femme de Jean » est différente du

prédicat femme(marie,jean).
nom(femme(jean),marie).
age(femme(jean),25).
¢ On peut parler de la femme de jean, mais pas la
« calculer »

16

Licence Lyon1 - UE LIFprolog N. Guin

PROGRAMMATION RÉCURSIVE

¢ Un programme récursif est un programme qui

s’appelle lui-même

¢ Exemple : factorielle
— factorielle(1) = 1 (Cas d’arrêt)
— factorielle(n) = n * factorielle(n-1) si n≠1

Appel récursif

17

Licence Lyon1 - UE LIFprolog N. Guin

POUR ÉCRIRE UN PROGRAMME RÉCURSIF

¢ Il faut :
— Choisir sur quoi faire l’appel récursif
— Choisir comment passer du résultat de l’appel récursif
au résultat que l’on cherche
— Choisir le(s) cas d’arrêt

18

Licence Lyon1 - UE LIFprolog N. Guin

BOUCLAGE
maries(jean, sophie). maries(jean, sophie).
maries(philippe, maries(philippe,
stephanie). stephanie).
maries(A, B) :- sont_maries(A, B) :-
maries(B, A). maries(A, B).
sont_maries(A, B) :-
?- maries(jean,sophie). maries(B, A).
true.
?- maries(sophie,jean).
true.
?- sont_maries(X,Y).
?- maries(X,Y).
X = jean
X = jean
Y = sophie ;
Y = sophie ;
X = philippe
X = philippe
Y = stephanie ;
Y = stephanie ;
X = sophie
X = sophie
Y = jean ;
Y = jean ;
X = stephanie
X = stephanie
Y = philippe ;
Y = philippe ;
false.
X = jean
?-
Y = sophie ; 19
...
Licence Lyon1 - UE LIFprolog N. Guin
ARITHMÉTIQUE

¢ Comparaisons : =:=, =\=, >, <, >=, =<

¢ Affectaction : is
?- X is 3+2.
X=5
¢ Fonctions prédéfinies : -, +, *, /, ^, mod, abs, min,
max, sign, random, sqrt, sin, cos, tan, log, exp, ...

20

Licence Lyon1 - UE LIFprolog N. Guin

 UN EXEMPLE : FACTORIELLE (1)
?- trace, fact(3,R).
fact(1, 1). Call: (8) fact(3, _G237) ? creep
^ Call: (9) _G308 is 3-1 ? creep
fact(N, R) :- ^ Exit: (9) 2 is 3-1 ? creep
Nm1 is N-1, Call: (9) fact(2, _G306) ? creep
^ Call: (10) _G311 is 2-1 ? creep
fact(Nm1, Rnm1), ^ Exit: (10) 1 is 2-1 ? creep
R is Rnm1*N. Call: (10) fact(1, _G309) ? creep
Exit: (10) fact(1, 1) ? creep
^ Call: (10) _G314 is 2*1 ? creep
^ Exit: (10) 2 is 2*1 ? creep
Exit: (9) fact(2, 2) ? creep
^ Call: (9) _G237 is 3*2 ? creep
?- fact(5,R). ^ Exit: (9) 6 is 3*2 ? creep
R = 120 ; Exit: (8) fact(3, 6) ? creep
R = 6 ;
ERROR: Out of local Redo: (10) fact(1, _G309) ? creep
stack ^ Call: (11) _G314 is 1-1 ? creep
^ Exit: (11) 0 is 1-1 ? creep
Exception: (36,276) Call: (11) fact(0, _G312) ? creep
_G4661 is-36263-1 ? ^ Call: (12) _G317 is 0-1 ? creep
abort ^ Exit: (12) -1 is 0-1 ? creep
Call: (12) fact(-1, _G315) ? creep
% Execution Aborted ^ Call: (13) _G320 is-1-1 ? creep
^ Exit: (13) -2 is-1-1 ? creep

21
Il faut faire des cas exclusifs
Licence Lyon1 - UE LIFprolog N. Guin
 UN EXEMPLE : FACTORIELLE (2)
fact(1, 1).
fact(N, R) :- ?- 5 is X-1.
fact(Nm1, Rnm1), ERROR: Arguments
are not
Nm1 is N-1, sufficiently
R is Rnm1*N. instantiated
% Execution
Aborted
?- fact(3,R).
?- plus(3,2,5).
ERROR: Arguments are not
sufficiently instantiated true.
^ Exception: (9) 1 is ?- plus(X,2,5).
_G241-1 ? creep X = 3
Exception: (8) true.
fact(_G241, _G255) ? creep
Exception: (7) fact(3,
_G195) ? creep
% Execution Aborted
22

Licence Lyon1 - UE LIFprolog N. Guin

EXERCICE

¢ Définir un prédicat calculant le nième terme de la

suite : u0 = 2, un = 2un-1+3

23

Licence Lyon1 - UE LIFprolog N. Guin

 UNE FACTORIELLE AVEC ACCUMULATEUR
^ Call: (9) _G308 is 3-1 ? creep
fact(N,R) :- fact(N,1,R).
^ Exit: (9) 2 is 3-1 ? creep
Call: (9) fact(2, 3, _G234) ?
fact(1,R,R). creep
fact(N,I,R) :- N>1, Call: (10) 2>1 ? creep
Nm1 is N-1, Exit: (10) 2>1 ? creep
NewI is N*I, ^ Call: (10) _G311 is 3*2 ?
fact(Nm1,NewI,R). creep
^ Exit: (10) 6 is 3*2 ? creep
^ Call: (10) _G314 is 2-1 ?
?- trace, fact(3,N). creep
Call: (7) fact(3, _G234) ? ^ Exit: (10) 1 is 2-1 ? creep
creep Call: (10) fact(1, 6, _G234) ?
Call: (8) fact(3, 1, _G234) creep
? creep Call: (11) 1>1 ? creep
Call: (9) 3>1 ? creep Fail: (11) 1>1 ? creep
Exit: (9) 3>1 ? creep Redo: (10) fact(1, 6, _G234) ?
^ Call: (9) _G305 is 1*3 ? creep
creep Exit: (10) fact(1, 6, 6) ?
^ Exit: (9) 3 is 1*3 ? creep creep
24
N = 6
Licence Lyon1 - UE LIFprolog N. Guin
COMPARAISON ET UNIFICATION DE TERMES

¢ Vérifications de type : var, nonvar, integer, float,

number, atom, string, …

¢ Comparer deux termes :

T1==T2 réussit si T1 est identique à T2
T1\==T2 réussit si T1 n’est pas identique à T2
T1=T2 unifie T1 avec T2
T1\=T2 réussit si T1 n’est pas unifiable à T2

25

Licence Lyon1 - UE LIFprolog N. Guin

DIFFÉRENTS PRÉDICATS DE COMPARAISON
=:= =\= == \== = \=
?- A is 3, A=:=3. ?- A is 3, A==3.
A = 3. A = 3.
?- A is 3, A=:=2+1. ?- A is 3, A==2+1.
A = 3. false.

?- a=\=b. ?- a\==b.
ERROR true.

?- A==3. ?- A=3.
false. A = 3.
?- p(A)\==p(1). ?- p(A)\=p(1).
true. false.
26

Licence Lyon1 - UE LIFprolog N. Guin

LISTES

¢ Liste vide : [ ]

¢ Cas général : [Tete|Queue]

[a,b,c] º [a|[b|[c|[ ]]]]

27

Licence Lyon1 - UE LIFprolog N. Guin

EXEMPLES

¢ [X|L] = [a,b,c] ® X = a, L = [b,c]

¢ [X|L] = [a] ® X = a, L = []
¢ [X|L] = [] ® échec
¢ [X,Y]=[a,b,c] ® échec
¢ [X,Y|L]=[a,b,c] ® X = a, Y = b, L = [c]
¢ [X|L]=[X,Y|L2] ® L=[Y|L2]

28

Licence Lyon1 - UE LIFprolog N. Guin

SOMME DES ÉLÉMENTS D’UNE LISTE DE NOMBRES

/* somme(L, S) L liste de nb donnée, S nb résultat */

somme([],0).
somme([X|L],N) :- somme(L,R), N is R+X.

?- somme([1,2,3,5],N).
N = 11

29

Licence Lyon1 - UE LIFprolog N. Guin

EXERCICE

¢ Définir un prédicat ajoute1(L,L1) où L est une

liste de nombres, et L1 une liste identique où
tous les nombres sont augmentés de 1.

30

Licence Lyon1 - UE LIFprolog N. Guin

VARIABLE INDÉTERMINÉE (1)

/* ieme(L,I,X) L liste donnée, I entier donné,

X elt res */
ieme([X|L],1,X).
ieme([X|L],I,R) :- I>1, Im1 is I-1, ieme(L,Im1,R).

[ieme].
Warning: (/Users/nath/Enseignement/Option Prolog/ieme:2):
Singleton variables: [L]
Warning: (/Users/nath/Enseignement/Option Prolog/ieme:3):
Singleton variables: [X]
% ieme compiled 0.01 sec, 736 bytes
true. 31

Licence Lyon1 - UE LIFprolog N. Guin

VARIABLE INDÉTERMINÉE (2)

/* ieme(L,I,X) L liste donnée, I entier donné,

X elt res */
ieme([X|_],1,X).
ieme([_|L],I,R) :- I>1, Im1 is I-1, ieme(L,Im1,R).

?- ieme([a,b,c,d],2,N).
N=b;
false.

32

Licence Lyon1 - UE LIFprolog N. Guin

TEST OU GÉNÉRATION
/* appart(X,L) X elt donné,
Redo: (7) appart(_G284, [b, a,
L liste donnée */ c]) ? creep
appart(X,[X|_]). Call: (8) appart(_G284, [a,
appart(X,[_|L]) :- appart(X,L). c]) ? creep
Exit: (8) appart(a, [a, c]) ?
?- appart(a,[b,a,c]). creep
true. X = a ;
?- appart(d,[b,a,c]). Redo: (8) appart(_G284, [a,
c]) ? creep
false. Call: (9) appart(_G284, [c])
?- appart(X,[b,a,c]). ? creep
X = b ; Exit: (9) appart(c, [c]) ?
X = a ; creep
X = c ;
X = c ;
Redo: (9) appart(_G284, [c])
false. ? creep
?- trace, appart(X,[b,a,c]). Call: (10) appart(_G284, [])
Call: (7) appart(_G284, [b, a, c]) ? creep
? creep Fail: (10) appart(_G284, [])
Exit: (7) appart(b, [b, a, c]) ? ? creep
creep false.
X = b ; 33

Licence Lyon1 - UE LIFprolog N. Guin

LE PRÉDICAT MEMBER

¢ Le prédicat appart est prédéfini en Prolog

¢ Il est très utile :
— ?- member(c,[a,z,e,c,r,t]).
true
— ?- member(X,[a,z,e,r,t]).
X = a ; X = z ; X = e ; X = r ; X = t.
— ?- member([3,V],[[4,a],[2,n],[3,f],[7,g]]).
V=f.

34

Licence Lyon1 - UE LIFprolog N. Guin

UTILISATION DU PRÉDICAT APPEND
Append est le prédicat prédéfini pour la concaténation
de listes
?- append([a,b,c],[d,e],L).
L = [a, b, c, d, e]
Il est complètement symétrique et peut donc être utilisé
pour
• Trouver le dernier élément d’une liste :
?- append(_,[X],[a,b,c,d]).
X=d
• Couper une liste en sous-listes :
?- append(L1,[a|L2],[b,c,d,a,e,t]).
L1 = [b, c, d],
L2 = [e, t]

35

Licence Lyon1 - UE LIFprolog N. Guin

DÉFINITION D’UN PRÉDICAT : QUESTIONS À SE
POSER

¢ Comment vais-je l’utiliser ?

¢ Quelles sont les données ?
¢ Quels sont les résultats ?
¢ Est-ce souhaitable qu’il y ait plusieurs solutions ?

¢ Si l’on veut une seule solution, il faut faire des

cas exclusifs

36

Licence Lyon1 - UE LIFprolog N. Guin

EXERCICE

¢ Définir le prédicat renverse(L1,L2) satisfait si la

liste L2 est miroir de la liste L1.
¢ Construire l’arbre de résolution des requêtes
suivantes :
— renverse([a,b,c],L)
— renverse(L,[a,z,e]).
¢ Définirune version avec accumulateur du
prédicat renverse.
¢ Construire l’arbre de résolution des deux
requêtes précédentes.
37

Licence Lyon1 - UE LIFprolog N. Guin