Le langage Prolog

Partie 2

Faculté de sciences et de génie

Département d’informatique et de génie logiciel
IFT-2003 Intelligence artificielle I
Laurence Capus
 Plan
1. La variable anonyme
2. Les opérateurs
3. Les assertions
4. Les listes
5. La programmation récursive avec les
listes
6. Les prédicats ensemblistes

2
 La variable anonyme
• Notée « _ »
• Unification comme n’importe quelle
variable / Ne donne aucune valeur
• à utiliser lorsque la valeur d’une variable n’a pas
d’impact sur le reste du programme
– Exemple :
parent(pierre, sébastien).
parent(nathalie, sébastien).
parent(marie, nathalie).
parent(robert, nathalie).

Est-ce que Sébastien a des parents ?

?- parent( _, sébastien).
true .

3
 Les opérateurs
• Catégorie A - fonctions arithmétiques : +, -,
*, /, //, mod, ^, abs(X), acos(X), asin(X), atan(X),
cos(X), log(X), max(X,Y), min(X,Y), sqrt(X),
tan(X), etc.
– Exemple :
?- A is max(2+1,sqrt(5)/tan(10)).
A = 3.448801782585935.
• Catégorie B - Opérateurs de comparaison
d’expressions arithmétiques : </2, =:=/2, =\=/2,
=</2, >/2, >=/2
– Exemple :
?- 3 =< 4.
true.
4
 Les opérateurs
• Catégorie C - Opérateurs de comparaison de
termes : ==/2, \==/2, @</2, @=/2, @=</2,
@>/2, @>=/2, @\=/2 (@ pour les termes
ordonnés)
– Exemple :
?- b @< a.
false.
• Catégorie D - Opérateur d’unification : =/2
– Exemple :
?- A = a + b.
A = a+b.
• Catégorie E - Opérateur d’évaluation
d’expression arithmétique : is/2
– Exemple :
?- A is 1 + 1.
A = 2.
5
 Les opérateurs
unification identité égalité
= \= == \== =:= =\=
| ?- 1+1=2. | ?- 1+1\=2. | ?- 1+1==2. | ?- 1+1\==2. | ?- 1+1=:=2. | ?- 1+1=\=2.
false. true. false. true. true. false.
| ?- 1 = 1. | ?- 1 \= 1. | ?- 1 == 1. | ?- 1 \== 1. | ?- 1 =:= 1. | ?- 1 =\= 1.
true. false. true. false. true. false.
| ?- 1 = 2. | ?- 1 \= 2. | ?- 1 == 2. | ?- 1 \== 2. | ?- 1 =:= 2. | ?- 1 =\= 2.
false. true. false. true. true. true.
| ?- a = a. | ?- a \= a. | ?- a == a. | ?- a \== a. | ?- a =:= a. | ?- a =\= a.
true. false. true. false. Erreur de type Erreur de type
| ?- a = b. | ?- a \= b. | ?- a == b. | ?- a \== b. | ?- a =:= b. | ?- a =\= b.
false. true. false. true. Erreur de type Erreur de type
| ?- A = A. | ?- A \= A. | ?- A == A. | ?- A \== A. | ?- A =:= A. | ?- A =\= A.
true. false. true. false. Err. d’instanciation Err. d’instanciation
| ?- A = B. | ?- A \= B. | ?- A == B. | ?- A \== B. | ?- A =:= B. | ?- A =\= B.
A = B. false. false. true. Err. d’instanciation Err. d’instanciation
6
 Les opérateurs
• Opérateurs dans SWI-PROLOG
– Précédence de 0 (forte) à 1200 (faible)
• Exemple: la précédence du « non » est plus forte
que celle du « et »
• Associativité : à droite, à gauche, non-associatif
– Exemple d’associativité à droite :
» a et b et c  a et (b et c).
» non non a  non (non a).
– Types
• Préfixe (fx, fy) , postfixe (xf, yf) , infixe (xfx, xfy)
– Exemple
» préfixe : non a.
» postfixe : a est_vrai.
» infixe : a ou b.

7
 Les opérateurs
• Opérateurs dans SWI-PROLOG
– Pour connaître les opérateurs prédéfinis :
current_op/3

?- current_op(PREC,ASSOC,NOM).
…
PREC = 500, ASSOC = yfx, NOM = (-) ;
PREC = 400, ASSOC = yfx, NOM = (mod) ;
PREC = 700, ASSOC = xfx, NOM = (==) ;
...
PREC = 700, ASSOC = xfx, NOM = (is) ;
PREC = 700, ASSOC = xfx, NOM = (=) ;
PREC = 1000, ASSOC = xfy, NOM = (',') ;
…

8
 Les opérateurs
• Opérateurs dans SWI-PROLOG
– Il est possible de définir un nouvel opérateur
avec op/3
• Exemple
% sans opérateurs définis % avec opérateurs définis
:- op(200,xfy,et).
a.
b. a.
et( A, B ):- A, B. b.
A et B :- A, B.

?- et(a,b). ?- et(a,b).
true. true.
?- a et b. ?- a et b.
Erreur de syntaxe true.
9
 Les assertions
• On peut ajouter de nouvelles clauses dans la mémoire de
travail sans les ajouter dans le fichier programme :
assert/1, asserta/1, assertz/1
Pour supprimer ces nouvelles clauses :
retract/1 ou retractall/1
NB : À utiliser pour avoir une structure temporaire par exemple.

?- parent(X, pierre).
Exemple :
false.
parent(pierre, sébastien). ?- assert( parent(marc, pierre) ).
parent(nathalie, sébastien). true.
parent(marie, nathalie). ?- parent(X, pierre).
parent(robert, nathalie). X=marc.
?- retract( parent(marc, pierre) ).
true.
?- parent(marc, pierre).
false.
10
 Les listes
• Seule structure de données prédéfinie
• Exemples de listes :
[ a, b, 3, c, pomme, ‘a b c’]
[]
• Il y a 2 manières d’accéder aux éléments d’une
liste :
– « , » : accéder élément par élément
• Exemple :
?- [ A, B, C ] = [ 30, 20, 50 ].
A =30, B=20,C=50.
– « | » : accéder au premier élément et au reste de la
liste (soit la liste privée de son premier élément)
• Exemple
?- [ X | Y ] = [ 30, 20, 50 ].
X=30, Y = [20,50].
11
La programmation récursive avec les listes
• Exemple : la relation d’appartenance à un ensemble
peut être définie par le prédicat membre/2
membre(X,L) signifie que X appartient à L

• Cette relation existe déjà dans Swi-Prolog :

member/2 (member(X,L) est vrai si X appartient à L)

• Définition : membre(X, [A|B])

– Il est plus facile de représenter la liste L par [A|B] pour
déterminer tous les cas possibles
– 2 cas possibles :
1) X est le premier élément de L, donc X=A
2) X se trouve dans le reste de L (L privée de son premier
élément), donc X appartient à B
Le cas (1) correspond à la condition d’arrêt et (2) est récursif.
12
La programmation récursive et les listes
• Illustrations de la relation :
?- membre(a, [a,b,c]). ?- membre(X, [a,b,c]).
true. X=a;
?- membre(d, [a,b,c]). X=b;
false. X=c.
?- membre(a, []). ?- membre([a,b], [c,d,[a,b]]).
false. true.
• Implantation en langage Prolog :
% condition d’arrêt : X est membre d’une liste qui
% contient X comme premier élément.
membre(X,[X|_]).
% appel récursif : X n’est pas le premier élément de la liste
% [Y|R] mais appartient au reste de cette liste R
membre(X,[Y|R]):- not(X=Y), membre(X,R).

13
La programmation récursive avec les listes
• Exemple : la relation de concaténation de deux listes
peut être définie par le prédicat membre/2
conc(L1,L2,L3) signifie que L3 est la liste contenant les éléments
de L1 suivis des éléments de L2

• Cette relation existe déjà dans Prolog :

append/3 (append(L1,L2,L3) est vrai
si L3 est la concaténation des listes L1 et L2)

• Définition : conc(L1,L2,L3)
– 2 cas possibles :
1) L1 est vide donc L3 reçoit la valeur de L2
2) On écrit L1=[X|R1], dans ce cas L1 n’est pas vide. On met
X en première position de la liste L3 ([X|R3]) et on
continue à concaténer R1 avec L2 dans R3.
Le cas (1) correspond à la condition d’arrêt et (2) est récursif.
14
La programmation récursive et les listes
• Illustrations de la relation :
?- conc([a], [b,c], [a,b,c]). ?- conc([a], [], K).
true. K=[a].
?- conc([d], [a,b,c], X). ?- conc([d], K, [d,a,b,c]).
X=[d,a,b,c]. K=[a,b,c].
?- conc([], [a,b,c], L). ?- conc(K, [a,b,c], [X,a,b,c]).
L=[a,b,c]. K=[X].
• Implantation en langage Prolog :
% condition d’arrêt : la première liste est vide, donc le
résultat est la deuxième liste
conc([], L, L).
% appel récursif : la première liste n’est pas vide, on met
% son premier élément dans le résultat, puis on continue à
% concaténer le reste R1 avec L2 dans R3
conc([X|R1], L2, [X|R3]):- conc(R1, L2, R3).

15
La programmation récursive avec les listes
• Exemple : calculer la longueur d’une liste par le prédicat
longueur/2
longueur(L, N) signifie que N est la longueur de la liste L

• Cette relation existe déjà dans Prolog :

length/2 (length(L,N) est vrai
si N correspond au nombre total d’élément de L)

• Définition : longueur(L, N)
– 2 cas possibles :
1) L est vide donc N a la valeur 0
2) On écrit L=[X|R], dans ce cas L n’est pas vide. On ajoute 1
à N et continue à calculer la longueur de R, placée dans
une nouvelle variable N1.
Le cas (1) correspond à la condition d’arrêt et (2) est récursif.

16
La programmation récursive et les listes
• Illustrations de la relation :
?- longueur([a], N). ?- longueur(K, 0).
N=1. K=[].
?- longueur([], X).
X=0.
?- longueur([a,b,c], X).
X=3.
• Implantation en langage Prolog :
% condition d’arrêt : la première liste est vide, donc le
résultat est la deuxième liste
longueur([], 0).
% appel récursif : la liste n’est pas vide, on calcule la
% longueur de R qu’on place dans N1 et on y ajoute 1 pour
% obtenir 1 (toutes les variables de la partie droite de is/2
% doivent avoir une valeur)
longueur([X|R], N):- longueur(R, N1), N is N1+1.
17
 Les prédicats ensemblistes
• Ces prédicats sont prédéfinis en langage Prolog.
• Leur but est de produire une liste d’éléments à
partir de faits ou affirmations connus
• Il existe 3 prédicats ensemblistes : bagof/3,
setof/3, findall/3
• Particularités :
• bagof/3 et setof/3 tiennent compte de la valeur de
tous les arguments
• findall/3 ne s’occupent pas des arguments non
demandés pour la liste
• setof/3 construit des listes triées

18
Les prédicats ensemblistes
• findall/3 : findall(A,B,C) trouve tous les A
tels que B est vrai et met le résultat dans
la liste C.
• Exemple :
auto( julie, honda, rouge ).
auto( jean, honda, rouge ).
auto( marc, chrysler, rouge ).
auto( nathalie, honda, noire ).

?- findall( P, auto(P, M, C), R ).

R= [julie, jean, marc, nathalie].
?- findall( M, auto(P,M,C), R).
R = [honda, honda, chrysler, honda].

19
Les prédicats ensemblistes
• Bagof/3 : tient compte de tous les arguments
• Exemple :
auto( julie, honda, rouge ).
auto( jean, honda, rouge ).
auto( marc, chrysler, rouge ).
auto( nathalie, honda, noire ).

?- bagof( P, auto(P, M, C), R).

M = chrysler, C = rouge, R = [marc] ;
M = honda, C = noire, R = [nathalie] ;
M = honda, C = rouge, R = [julie, jean].

20
Les prédicats ensemblistes
• bagof/3 : si on utilise le prédicat ^/2, on peut
s’affranchir des valeurs des autres arguments
?- bagof( P, C^auto(P, M, C), R).
M= chrysler, R=[marc] ;
M=honda, R=[julie, jean, nathalie].
?- bagof( P, M^auto(P, M, C), R). ^/2
C = noire , R = [nathalie] ; quantification
C = rouge ,R = [julie,jean,marc]. existentielle
?- bagof( P, C^M^auto(P, M, C), R).
R = [julie,jean,marc,nathalie].

• Remarque : les listes sont affichées en tenant

compte de l’ordre alphabétique des autres
arguments n’appartenant pas à la liste
21
Les prédicats ensemblistes
• setof/3 : produire une liste triée exempte
de doublons
• Exemple
auto( julie, honda, rouge ).
auto( jean, honda, rouge ).
auto( marc, chrysler, rouge ).
auto( nathalie, honda, noire ).

?- setof( P, auto(P, M, C), R).

M = chrysler, C = rouge, R = [marc] ;
M = honda, C = noire, R = [nathalie] ;
M = honda, C = rouge, R = [jean, julie].
?- setof( P, M^C^auto(P, M, C), R).
R = [jean, julie, marc, nathalie].

22
 Conclusion

●
Attention à utiliser le bon opérateur, plusieurs
catégories existent en langage Prolog.
●
Les listes et la programmation récursive sont un
défi intellectuel mais sont très utiles pour
programmer rapidement.
●
La meilleur manière de relever le défi est de
s’entraîner à programmer diverses relations
récursives.
●
Beaucoup de prédicats récursifs sur les listes
sont prédéfinis (voir Aide de Swi-Prolog). Utiliser
un autre nom pour programmer ces relations.
23