PROLOG (suite)

1
 N. Doggaz
RÉCURSIVITÉ
ARITHMÉTIQUE ÉLÉMENTAIRE
36

2
ARITHMÉTIQUE
En plus de : +, -, *, /, nous disposons des fonctions
suivantes:
 X mod Y calcule le reste de la division

N. Doggaz
entière de X par Y
 X div Y calcule le quotient de la division
entière de X par Y
 abs(X) valeur absolue

 cos(X), sin(X), tan(X) fonctions

trigonométriques, X doit être en radians.
 arctan(X), exp(X), ln(X), log(X), sqrt(X)
fonctions usuelles (ln: logarithme en base e;
log: logarithme en base 10; sqrt: racine
carrée). 3
ARITHMÉTIQUE
Les opérateurs suivants permettent de
manipuler les expressions

N. Doggaz
arithmétiques
➢ X is Y évalue Y et le résultat est
unifié avec X.
➢ Expr1 =:= Expr2 réussit si les
valeurs des deux expressions sont
égales.
Exemple 2*3 =:= 1+5 réussit mais
2*3 =:= 5 échoue. 4
ARITHMÉTIQUE

Le signe = signifie l’unification.

N. Doggaz
Par exemple 2*3 = 6 échoue parce que les
deux termes ne sont pas unifiables.

Le terme 2*3 est un terme composé. Il

correspond au terme *(2, 3) alors que 6
est un entier.

5
 Que donne la question suivante :
?- 2 + 3 = 5
?- 2+3 = 5.
false.

N. Doggaz
 Le signe = signifie l’unification.

 Il faut utiliser l’opérateur is pour forcer l’évaluation

numérique (avec l’absence de toute inconnue dans la
partie droite du is).
?- X is 2+3.
X = 5.
?- X = 5.
X = 5.
?- X = 2+3.
X = 2+3.
6
ARITHMÉTIQUE

 Expr1 =\= Expr2 réussit si les valeurs des

deux expressions sont différentes.

N. Doggaz
 Expr1 < Expr2 réussit si la valeur de Expr1
est strictement inférieure à celle de Expr2.
 Expr1 =< Expr2 réussit si la valeur de Expr1
est inférieure ou égale à celle de Expr2.
 Expr1 > Expr2 réussit si la valeur de Expr1
est strictement supérieure à celle de Expr2.
 Expr1 >= Expr2 réussit si la valeur de Expr1
est supérieure ou égale à celle de Expr2.

7
EXERCICE

Définir les prédicats suivants :

N. Doggaz
➢ Pair(x): vrai si x pair.

➢ Abs(x, y) : « x est la valeur absolue de y ».

➢ cube(x, y) : « x est le cube de y ».

➢ min(x, y, z): « z est le minimum de x et y ».

➢ min3(x, y, z, m): « m est le minimum de x, y et z ».

➢ Factoriel(n, m): « n est le factoriel m ».

8
 N. Doggaz
LES LISTES

9
➢ La liste (séquence ordonnée d'éléments de
longueur variable) est la principale

N. Doggaz
structure en Prolog.

➢ Les éléments peuvent être des constantes

(atomes ou nombres) ou des termes
composés.

10
Pour l’interpréteur Prolog, la liste peut être :
 une liste vide notée [] ou .()

 une liste composée d’un élément de

tête et d’un reste comprenant la liste

N. Doggaz
sans le premier élément qu’on note
[T|R].
La barre verticale est l’opérateur « cons »
de constructions de listes.

Les élémentsd’une liste sont séparés par

une virgule « , ».
11
EXEMPLES DE LISTES
Objet formel Notation couple cons Syntaxe
.(a, [ ]) [a|[ ]] [a]
.(a, .(b, [ ])) [a | [b | [ ]]] [a, b]

N. Doggaz
.(a,.(b,.(c, [ ]))) [a | [b | [c | [ ]]]] [a, b, c]
.(a, X) [a | X] [a | X]

La première colonne présente les listes avec le

foncteur point et c’est la façon dont les listes sont
considérées comme termes par les programmes
logiques.

La deuxième colonne donne l’équivalent en crochets

de la syntaxe point. 12
FONCTIONS PRÉDÉFINIES SUR LES LISTES
 Length(l, n) : vraie si n est la longueur de la
liste l.

N. Doggaz
length([a, b, 1, 2], N). → N = 4.
length([q], 2). → false.
 member(term, list) réussit si le premier
argument est membre de la liste passée en
deuxième argument.
member(q, [a, n, m]). → false.
member(a, [q, w, a]). → true.
member(X, [a, mn]). → X=a;
X = mn
13
FONCTIONS PRÉDÉFINIES SUR LES LISTES
 append(l1, l2, l3): réussit si la troisième liste
est la concaténation de la première et de la
deuxième.

N. Doggaz
append([a,b], [c,d], [a,b,c,d]). → true.
append([a], [b], [a,d]). → false.
append([a,b], [c,d], L). → L = [a, b, c, d].
 reverse(l1, l2): réussit si la deuxième liste est
l'inverse de la première.
reverse([a,m,n,b,c], L). → L = [c, b, n, m, a].
 last(l, term): réussit si le deuxième argument
est le dernier élément.
last([a,m, n], X). → X = n.
14
FONCTIONS PRÉDÉFINIES SUR LES LISTES
 permutation(L1, L2) : réussit si la deuxième
liste est une permutation de la première.

N. Doggaz
permutation([a, b, c], L).
L = [a, b, c] ;
L = [a, c, b] ;
L = [b, a, c] ;
L = [b, c, a] ;
L = [c, a, b] ;
L = [c, b, a] .

15
EXERCICES

1. Définir le prédicat appartenance qui

teste si un élément appartient ou non à

N. Doggaz
une liste.
2. Définir le prédicat l ongueur qui calcule
la longueur d’une liste.

3. Définir le prédicat nb_occ qui calcule le

nombre d’apparition d’un élément dans
une liste.
16
Correction

appartient(X, [X|L]).
appartient(X, [Y|L]) :- X =\= Y, appartient(X,L).

longueur([],0).
longueur([X|L], N) :- longueur(L, N1), N is N1+1.

nb_occ(X, [], 0).

nb_occ(X, [X|L], N):- nb_occ(X, L, N1), N is 1+N1.
nb_occ(X, [Y|L], N):- X =\= Y, nb_occ(X, L, N).

17
EXERCICES

1. Définir un prédicat dernier qui

récupère le dernier élément d’une

N. Doggaz
liste.
2. Définir un prédicat qui calcule le
maximum d’une liste d’entiers.
3. Définir un prédicat de concaténation
de listes: concat (l1,l2,l3), qui rend
vrai si l3 est la concaténation de l1 et
l2.
18
Correction

dernier([X], X).
dernier([X|L], Y) :- dernier(L, Y).

max([X], X).
max([X|L], X) :- max(L, N1), X >= N1.
max([X|L], N) :- max(L, N), X < N.

concat([], L1, L1).

concat(L1, [], L1).
concat([X|L1], L2, [X|L]) :- concat(L1, L2, L).

19
 N. Doggaz
LA COUPURE
50

20
LA NOTION DE COUPURE
 La recherche systématique de toutes les solutions
possibles est une caractéristique importante de
Prolog.
 Mais elle constitue également un inconvénient

car elle conduit parfois à une explosion

combinatoire qu’il est nécessaire de couper.
 Prolog fournit un prédicat système unique appelé
coupure, cut ou coupe choix (noté !) dont la
fonction principale est de réduire l’espace de
recherche des calculs Prolog en élaguant de façon
dynamique l’arbre de recherche.

21
DEFINITION [J.P. DELAHAYE]

Le CUT est toujours satisfait (vrai).

N. Doggaz
Definition1: Dans le parcours de l’arbre de
raisonnement Prolog si lors d’une remontée on
tombe sur une liste de buts commençant par un
CUT, il faut remonter directement jusqu’à la liste
des buts au-dessus du but qui a introduit ce CUT
(c.a.d. il faut remonter deux niveaux au-dessus de
la première apparition du CUT dans l’arbre de
raisonnement).

22
DÉFINITIONS [J.P. DELAHAYE]
Definition2:
Le CUT doit être considéré comme un but
satisfait, mais lorsque le CUT s’efface toutes les

N. Doggaz
instanciations faites depuis l’appel du but qui a
introduit le CUT sont figées et ne peuvent donc
plus être remises en cause lors de retours en
arrière ( par contre les instanciations faites avant
l’appel de ce but ou après l’effacement du CUT
sont remises en cause normalement).
Definition3:
Lorsque le CUT s’efface, il coupe tous les choix en
suspens portant sur le but qui a introduit le CUT
et sur tous les buts effacés depuis.
23
EXEMPLE [J.P. DELAHAYE]
A :- B, C.
A :- D. A
A :- E.

N. Doggaz
B :- F, !.
B :- H. B,C. D. E.
B :- I.
F :- G. F,!,C. H,C. I,C.
F :- J.
F :- K.
G. G,!,C. J,!,C. K,!,C.

G :- L.
G :- M.
!,C. L,!,C. M,!,C.
24
COMMENTAIRES SUR L’EXEMPLE
 Le but A introduit la liste de buts B, C ( il y a alors 2
choix en suspens pour A qui sont D et E).
 Le but B introduit la liste de buts F, ! Ce qui donne
donc F, !, C ( pour B il y a 2 choix en suspens qui sont
H et I).
 Le but F introduit G ce qui donne G, !, C ( pour F il y
a 2 choix en suspens qui sont J et K).
 Le but G s’efface ce qui donne !, C. (pour G il y a 2
choix en suspens qui sont L et M).
 En dessous le CUT s’efface et provoque à ce moment
là, la suppression des choix en suspens pour B, F, et G
( mais pas pour A). → Lors d’une remontée en !,C il
faut aller directement essayer les choix en suspens en
A sans s’arrêter à ceux de B, F et G.
25
REMARQUES
 Une coupure élague toutes les solutions
alternatives pour la conjonction des buts qui
apparaissent à sa gauche dans la clause, c.à.d. un
but conjonctif suivi d’une coupure produira au
plus une solution.
 La coupure n’affecte nullement les buts à sa
droite dans la clause. Ils peuvent produire plus
d’une solution en cas de remontée.
 « ! » signifie donc que la première solution
trouvée sur sa gauche suffira, mais que Prolog
cherchera toutes les solutions aux prédicats sur
la droite de « ! ».
26
EXEMPLE
Considérons le programme Prolog suivant:

p(X,Y) :- q(X), r(X,Y).

p(c,c1).

q(a).
q(b).
r(a,a1).
r(a,a2).
r(b,b1).
r(b,b2).
r(b,b3).

 Donner l’arbre de recherche pour le prédicat

p(Z, T).
27
L'ARBRE DE RECHERCHE CONSTRUIT PAR
PROLOG POUR LE BUT P(Z,T)
Prouver([p(Z,T)])
b1 : s = {Z  X, T  Y}
---- prouver([q(X),r(X,Y)])
b11 : s = {X  a}
----- prouver([r(a,Y)])
b111 : s = {Y  a1}
------ prouver([]] → solution1 = {Z=a, T=a1}
b112 : s = {Y  a2}
------ prouver([]) → solution2 = {Z=a, T=a2}
b12 : s = {X  b}
----- prouver([r(b,Y)])
b121 : s = {Y  b1}
------ prouver([]) → solution3 = {Z=b, T=b1}
b122 : s = {Y  b2}
------ prouver([]) → solution4 = {Z=b, T=b2}
b123 : s = {Y  b3}
------ prouver([]) → solution5 = {Z=b, T=b3}
b2 : s = {Z  c, T  c1}
---- prouver([]) → solution6 = {Z=c, T=c1}

28
UTILISATION DE LA COUPURE
 Cas1: On définit p par: p(X,Y) :- q(X), r(X,Y), !.
p(c,c1).
 Cas2: On définit p par: p(X,Y) :- q(X), !, r(X,Y).
p(c,c1).
 Cas3: On définit p par: p(X,Y) :- !, q(X), r(X,Y).
p(c,c1).

q(a).
q(b).
r(a,a1).
r(a,a2).
r(b,b1).
r(b,b2).
r(b,b3).
 Donner l’arbre de recherche pour le prédicat p(Z, T).
29
UTILISATION DE LA COUPURE
En fonction de l'endroit ou l'on place une coupure dans la définition
de p, cet arbre de recherche est plus ou moins élagué, et certaines
solutions supprimées :
 si on définit p par:
p(X,Y) :- q(X), r(X,Y), !.
p(c,c1).
Prolog donne la solution 1 puis coupe toutes les branches en
attente
(b112, b12 et b2).
 si on définit p par:
p(X,Y) :- q(X), !, r(X,Y).
p(c,c1).
Prolog donne les solutions 1 et 2 puis coupe les branches en
attente
(b12 et b2).
 si on définit p par:
p(X,Y) :- !, q(X), r(X,Y).
p(c,c1).
Prolog donne les solutions 1, 2, 3, 4 et 5 puis coupe la
branche en attente (b2).
30
EXERCICE COUPURE
Soit le programme Prolog suivant:
s(X,Y) :- q(X,Y).
s(0,0).

q(X,Y) :- i(X),!,j(Y).

i(1).
i(2).
j(1).
j(2).
j(3).

Donnez l’arbre de resolution de s(X, Y).

31
LE COUPE-CHOIX POUR OBTENIR UNE
SOLUTION UNIQUE

 Il arrive qu’un prédicat donne plusieurs solutions

alors qu’on voudrait n’obtenir que la première. Le
CUT permet facilement d’arriver à ce résultat.
 Soit le prédicat solution(X) qui dans un
programme donne les solutions à un problème.
Poser la question:
Solution(X), !.
provoque la recherche et l’affichage de la
première solution uniquement.
Les choix en suspens correspondants aux autres
solutions sont coupés par l’effacement du CUT
dès qu’une solution est obtenue.
32
LE COUPE-CHOIX POUR SÉLECTIONNER UNE
RÈGLE ET ÉVITER DES CALCULS INUTILES

Exemple: Le maximum

Calculer le maximum de 2 nombres.

max(N1,N2,M) :- N1 >= N2, M is N1.
max(N1, N2,M) :- N1 < N2, M is N2.

Max avec Cut:

max(N1,N2, M) :- N1 >= N2, !, M is N1.
max(N1, N2, M) :- N1 < N2, M is N2.

33
EXERCICE
Ecrire un prédicat appréciation(X, A) qui pour une
note fixée X, entre 0 et 20, donne l’appréciation
correspondante. On veut obtenir:
 Très-bien pour 16, 17, 18, 19 et 20.
 Bien pour 11, 12, 13, 14, et 15.
 Passable pour 7, 8, 9 et 10.
 Mauvais pour 0, 1, 2, 3, 4, 5 et 6.

Ecrire deux versions du prédicat:

1. Une version logique n’utilisant pas le CUT,

2. Une version efficace avec utilisation du CUT.

34
 N. Doggaz
LA NÉGATION EN PROLOG

35
LA NÉGATION EN PROLOG
 La négation de Prolog n’est pas la négation
générale de la logique.
 L’usage du NOT en Prolog a deux limitations:
 Le NOT ne peut intervenir que dans le corps d’une
règle et ne peut pas intervenir dans sa tête.
Exemple: a(X) :- s(X), not(p(X)). est une règle permise
alors que not(a(X)) :- p(X). ne l’est pas.
 Lorsque le raisonnement Prolog tombe sur un but de
la forme NOT(P), il faut que toutes les variables de P
soient liées (c.a.d aient été substituées par des
constantes ou des objets construits à partir de
constantes).

36
CLAUSES ET BUTS DISJONCTIFS
La disjonction est une abréviation en PROLOG.

La clause:
tete :- p_1 ; p_2 ; .... ; p_n .
est équivalente à la séquence de clauses:
tete :- p_1 .
tete :- p_2 .
….
tete :- p_n .

L’ordre des clauses d’une disjonction est important.

37