Prolog (suite)
Données Prolog
• Une Donnée Prolog:
– Donnée élémentaire:
• Nombre,
• Chaîne de caractères
• Identificateur de constante
• Booléen
– Donnée composée:
• Terme/Prédicat
• Liste
– Variable
Données Prolog
• Un Terme est un identificateur de constante
suivi généralement d’une liste d’arguments qui
sont des données Prolog
• Une Liste est généralement une suite de
données Prolog entre crochet […] et séparées
par des virgules:
– [4, [bo, ba], X, toto, frere(hassan, hicham), ‘‘sas’’]
Liste en Prolog
• Enumération complète d’une Liste vs
Enumération partielle: le constructeur « | »
– [5, ‘‘bon jour’’, X, add(Y,T)]
– [5, X, Y|Z]
• Unification des listes
– [5, ‘‘bon jour’’, X, add(Y,T), 45] = [5, X, Y|Z].
Liste en Prolog
• Avec l’unification, le constructeur permet
de décomposer ou de composer une liste
?- [4, 5, 6] = [X|Y].
{X = 4, Y = [5, 6]}
data([4, 5, 6]). // dans un programme
?- data([X|Y]).
{X = 4, Y = [5, 6]}
Composition d’une liste
?- X = 7, Y = [8, 9], Z = [X|Y].
{X = 7, Y = [8, 9], Z = [7, 8, 9]}
?- [X, 3, Y|Z] = [[7, 8], 3, 10, bonjour, 34, 9].
X = [7, 8]
Y = 10
Z = [bonjour, 34, 9]
Traitement procédural ou
fonctionnel en PROLOG
Définition fonctionnelle de factoriel (fac):
fac(0) = 1
fac(N) = N * fac(N - 1), pour N > 0
fac(M) => V, fac(M, V).
En Prolog: ??
X is Expression.
Remarques
• Un prédicat n’est pas une fonction:
– Le résultat de la fonction devrait être un
argument du prédicat. Ex:
– fac(0) -> 1 fac(0, 1).
• Et au lieu de :
– fac(N) = N * fac(N - 1)
= Y telque Y = N * fac(N - 1)
– fac(N, Y) :- …
Remarques (suite)
• En général, les arguments d’un prédicat
ne peuvent pas être des expressions.
• Il faut d’abord « évaluer » l’expression et
associer sa valeur à une variable V avec
le but prédéfini « is » et ensuite fournir V
comme argument au prédicat. Ex:
– fac(N – 1) M is N – 1, fac(M) …
– ET puisque le prédicat fac n’est pas une
fonction … : fac(M) fac(M, R).
Remarques (suite)
• Par ailleurs et dans le même sens, on ne
peut pas avoir ceci:
N * fac(N - 1),
fac(N, Y) :- M is N – 1, Y is N * fac(M, R).
fac(N, Y) :- M is N – 1, fac(M, R), Y is N * R.
Résultat des transformations
précédentes
Définition fonctionnelle de factoriel (fac):
fac(0) = 1
fac(N) = N * fac(N - 1), pour N > 0
En Prolog:
fac(0,1).
fac(N,F) :- N > 0, M is N - 1,
fac(M, F1),
F is N * F1.
Remarque
• Pourquoi on ne peut pas utiliser une seule
variable, comme dans :
fac(N, F) :- N > 0, N is N - 1,
fac(N, F),
F is N * F. N can’t be = to N – 1
• Parce que « is » n’est pas une opération
d’affectation; l’ancienne valeur de N (idem
pour F) n’est pas écrasée par la nouvelle
valeur.
Dernière remarque
• On ne peut pas écrire ceci:
fac(0,1).
fac(N, N * F1) :- N > 0, M is N - 1,
fac(M, F1).
Pourquoi ?
• Parce qu’un prédicat ne peut pas avoir
une expression comme argument.
Exercices
• Définir la fonction Puissance en Prolog
• Définir la fonction Fibonnacci en Prolog
Définition du but membre(E, L)
Définition en LISP:
(defun membre (E L)
(cond ((null L) L)
((equal E (car L)) L)
(t (membre E (cdr L))) ))
En Prolog:
membre(E, L) :- L = [X|Y], E = X.
membre(E, L) :- L = [X|Y], membre(E, Y).
?- membre(3, [4, 5, 3, 6]).
yes
?- membre(3, [4, 5, 6]).
no
? membre(3, []).
no
Amélioration progressive de
l’écriture du but membre
membre(E, L) :- L = [X|Y], E = X.
membre(E, [X|Y]) :- E = X.
membre(E, [E|Y]).
membre(E, [E|_]).
// Idem pour la seconde règle:
membre(E, [_|Y]) :- membre(E, Y).
L’autre utilisation du but membre(E, L)
?- membre(E, [4, 5, 6]).
{E = 4};
{E = 5};
{E = 6};
No
// la même définition joue le rôle aussi
d’énumération
Remarques
• En Prolog, comme en LISP, le traitement
des listes implique la
décomposition/composition des listes (en
utilisant l’opérateur | ) et la récursivité.
Exercices sur les Listes
• Ecriver un but Prolog qui affirme qu’un élément e est le
dernier élément de la liste L
• Ecriver un but Prolog qui affirme qu’une liste L1 est
l’inverse d’une liste L2
• Ecriver un but Prolog qui affirme que n est le nombre
d’éléments d’une liste L
• Ecriver un but Prolog qui affirme que les éléments d’une
liste L1 se trouve dans la liste L2
• Ecriver un but Prolog qui calcule la moyenne d’une liste
d’entiers.
• Ecriver un but Prolog qui affirme que la liste L2 est le
résultat de la substitution, dans la liste L1, de l’élément
e1 par l’élément e2.