Cours2 Prolog1

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

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 » : _

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

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

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

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

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

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

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

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

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

¢ 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Cours2 Prolog1

Transféré par

Droits d'auteur :

Formats disponibles

Cours2 Prolog1

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Cours2 Prolog1

Transféré par

Droits d'auteur :

Formats disponibles

PREMIERS PAS EN PROLOG

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

Licence Lyon1 - UE LIFprolog N. Guin

¢ Langage d’expression des connaissances fondé

Licence Lyon1 - UE LIFprolog N. Guin

Licence Lyon1 - UE LIFprolog N. Guin

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

Licence Lyon1 - UE LIFprolog N. Guin

Licence Lyon1 - UE LIFprolog N. Guin

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

Licence Lyon1 - UE LIFprolog N. Guin

Licence Lyon1 - UE LIFprolog N. Guin

Licence Lyon1 - UE LIFprolog N. Guin

Licence Lyon1 - UE LIFprolog N. Guin

Prolog parcourt le paquet de clauses de haut en bas,

Licence Lyon1 - UE LIFprolog N. Guin

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

¢ On définit le programme suivant :

Licence Lyon1 - UE LIFprolog N. Guin

¢ On dispose des informations suivantes :

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

Licence Lyon1 - UE LIFprolog N. Guin

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

¢ Faits relatifs à l’énigme :

Licence Lyon1 - UE LIFprolog N. Guin

Licence Lyon1 - UE LIFprolog N. Guin

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

Licence Lyon1 - UE LIFprolog N. Guin

¢ Un programme récursif est un programme qui

Licence Lyon1 - UE LIFprolog N. Guin

Licence Lyon1 - UE LIFprolog N. Guin

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

Licence Lyon1 - UE LIFprolog N. Guin

Licence Lyon1 - UE LIFprolog N. Guin

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

Licence Lyon1 - UE LIFprolog N. Guin

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

¢ Comparer deux termes :

Licence Lyon1 - UE LIFprolog N. Guin

Licence Lyon1 - UE LIFprolog N. Guin

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

Licence Lyon1 - UE LIFprolog N. Guin

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

Licence Lyon1 - UE LIFprolog N. Guin

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

Licence Lyon1 - UE LIFprolog N. Guin

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

Licence Lyon1 - UE LIFprolog N. Guin

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

Licence Lyon1 - UE LIFprolog N. Guin

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

Licence Lyon1 - UE LIFprolog N. Guin

Licence Lyon1 - UE LIFprolog N. Guin

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

Licence Lyon1 - UE LIFprolog N. Guin

Licence Lyon1 - UE LIFprolog N. Guin

¢ Comment vais-je l’utiliser ?

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

Licence Lyon1 - UE LIFprolog N. Guin

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