ProLog

Partie 2 : Unification, Arbre, Récursion, Coupure, Négation

Mathieu Vidal

Université Grenoble Alpes

Année 2015-2016

L2 - MIASHS

Grenoble - France

Planl Unification l Arbre de Recherchel Récursionl Coupure (Cut)l Négation

Partie 1-

Unification

Unification : Idée de base

l Exemple :l Base de connaissance : elfe(galadriel).l Question :?- elfe(X). l Comment fait Prolog pour dire que galadriel est une

valeur possible pour X ? l Unification : procédé par lequel on essaie de rendre

deux formules identiques en donnant des valeurs aux variables qu’elles contiennent.

l Unification réussie : substitution possible

Unification dans les Clauses

l L'unification réussie dans la tête se propage aux clauses

frere(X,Y) :- homme(X), enfant(X,Z), enfant(Y,Z), X\=Y.

frere(patrick,Qui).

homme(patrick)enfant(patrick,Z)enfant(Y,Z)patrick\=Y

Unification avec frere(X,Y)

X=patrick et Qui=Y

Définition Précise

l Si t1 et t2 sont des constantes, t1 et t2 unifient ssi ils sont le même atome ou le même nombre.

l Si t1 est une variable et t2 quelconque, t1 et t2 unifient ssi t1 est instanciable en t2.

l Si t1 et t2 sont des termes complexes, t1 et t2 unifient ssi :

l Ils ont le même foncteur et arité l Tous leurs arguments correspondants unifientl Les instanciations de variables sont compatibles

Conséquence

l L’unification peut réussir ou échouer.l e(X) et e(2) peuvent être unifiés.

l e(3) et e(2) ne peuvent être unifiés

l Le résultat n’est pas forcément unique : ensemble de solutions

l Prédicat d’unification : « = ». Teste si l'unification a réussie. Ecriture 1 : =(a,b). Ecriture 2 : a=b.

l Unification optimiste : pere(X)=X unifiel Unification pessimiste :n'unifie pas

unify_with_occurs_check(pere(X),X).

Exercice

l Dire si les expressions suivantes unifient et comment :l ?- sam = sam.l ?- sam = lea.l ?- 'sam' = sam.l ?- '1' = 1l ?- X = Y.l ?- X = sam, X = lea.l ?- k(s(g),Y) = k(X,t(k)).l ?- k(s(g), t(k)) = k(X,t(Y)).l ?- aime(X,X) = aime(sam,lea).

Partie 2-

Arbre de Recherche

Démonstration Prolog

l Pour répondre à une question, Prolog cherche à l'unifier, soit avec un fait, soit avec la tête d'une règle

l Unification avec la tête d'une Règlel Si l’unification réussit : substitution des

variables de la queue par les valeurs correspondantes dans la tête.

l L'algorithme est appelé SLDNF résolution (Selective Linear Definite Negation as Failure)

Résultat Final

l Prolog continue à unifier jusqu'à vérification de la requête initiale

l Si l’unification échoue : Prolog répond faux (false)l Si l’unification réussit : Prolog répond soit vrai

(true), soit donne la valeur des variables (expl : X=lea) s'il y en avait dans la requête.

l On demande à Prolog de chercher d'autres valeurs en appuyant sur « ; » ou « Espace »

l A la fin de la démonstration, Prolog a construit une liste de couples valeur-variable

Parcours

l Parcours de la base du haut vers le basl Parcours des clauses de gauche à droitel Quand il y a plusieurs manières d'unifier, on a un

point de choix. Cas possibles :l Différentes règles définissant un même prédicat

l Disjonction de prédicats dans une queue

l Instanciation d'une variable

Arbre de recherche

l Pour résoudre une question, Prolog construit l’arbre de recherche de la question

l Construction de l'arbrel Racine : la question initiale l Nœud : point de choixl Passage d’un nœud vers son fils en effectuant

une unification

Stratégie de Prolog

l Parcours en profondeur d’abordl nœud de succès : c’est une solution, Prolog

l’affiche et peut chercher d’autres solutionsl nœud d'échec : remontée dans l’arbre jusqu'à

un point de choix possédant des branches non explorées

l Puis parcours de gauche à droite dans l'ordre des conditions

Backtracking

l Remontée dans l'arbre jusqu'au point de choix : backtrack. Si un tel nœud de choix n’existe pas, la démonstration est terminée, il n’y a pas d’autre solution.

l Bactrack : toutes les unifications faites depuis le dernier point de choix sont défaites

l Possibilité de branche infinie et donc de recherche sans terminaison… Attention à :l L’ordre des littéraux dans la queue de clausel L’ordre des clauses

Exemple d'Arbre de rechercheExemple de programme:pere(charlie, david). (p1)pere(henri, charlie). (p2)papi(X,Y) :- pere(X,Z), pere(Z,Y). (p3)

Question :?- papi(X,Y).

Résolution versus SLDNF

Résolutionl Théorie Mathématiquel Clauses de Horn

SLDNFl Algorithme effectifl Unification

Expl : Base = {p, q si p} et Question = {q?}

Base = {p,q v ¬p}. Qu. = {¬q}

[p] [q, ¬p] [¬q]

[q] [¬q]

[]

Base = {p,q:- p}. Qu. = {q}

?- q

?- p

OK

Equivalent

Exercice

rectangle(a).

rectangle(b).

losange(b).

carre(X) :- rectangle(X),losange(X).

?- carre(X).

l Soit la base de connaissance et la requête suivante. Construire l'arbre de recherche Prolog

Partie 3-

Récursion

Programmation récursive

l Rappel : un programme récursif est un programme qui s’appelle lui-même

l Exemple : factoriellel factorielle(0) = 1 (Cas de base)l factorielle(n) = n * factorielle(n-1) si n≠0

l En Prolog, un prédicat est récursif si au moins une de ses règles associées réfère à lui-même

Exemple deRécursion simple

digere(X,Y) :- vientDeManger(X,Y).

digere(X,Y) :- vientDeManger(X,Z), digere(Z,Y).

vientDeManger(moustique,sang(marie)).

vientDeManger(grenouille,moustique).

vientDeManger(marie,grenouille).

?- digere(marie,moustique).true.?- digere(grenouille,marie)false?- digere(marie,sang(marie)).true.

Intérêt de la récursion

l Permet d'exprimer de manière succincte un processus réitéré n fois

l Expl : Exprimer la relation de descendance

l Non récursif : Nombre infini de règlesdescend(X,Y):- enfant(X,Y).descend(X,Y):- enfant(X,Z), enfant(Z,Y).descend(X,Y):- enfant(X,Z), enfant(Z,A), enfant(A,Y). ...

l Récursif : Deux règles

descend(X,Y):- enfant(X,Y).descend(X,Y):- enfant(X,Z), enfant(Z,Y).descend(X,Y):- enfant(X,Z), enfant(Z,A), enfant(A,Y). ...

descend(X,Y):- enfant(X,Y).descend(X,Y):- enfant(X,Z), descend(Z,Y).

Le cas de base

p :-p.

?- p.

l Sans cas de base, la récursion ne s'arrête pas

l Il faut placer le cas de base avant la relation de récurrence dans la règle, sinon pas d'arrêt

descend(X,Y):- descend(X,Z), enfant(Z,Y).

descend(X,Y):- enfant(X,Y).

enfant(marie,paul).

?- descend(marie,paul).ERROR : Out of local stack

Exercice

l Trouvez-vous problématique la réécriture suivante du prédicat descend ?

descend(X,Y):- enfant(X,Y).descend(X,Y):- descend(X,Z), descend(Z,Y).

Solution

l Donne les bonnes solutionsl Mais finit par une erreur : Out of local stack

Partie 4-

Coupure

Notion de coupure (1)

l La recherche systématique de toutes les solutions possibles est une caractéristique importante de Prolog.

l Mais elle constitue également son talon d’Achille car elle conduit parfois à une explosion combinatoire qu’il est nécessaire de couper si l’on veut voir son programme se terminer.

Notion de coupure (2)

l Différents noms utilisés: coupure, cut ou coupe choix

l Introduit un contrôle du programmeur sur l'exécution de ses programmesl en élaguant les branches de l’arbre de recherchel rend les programmes plus simples et efficaces

l Notation: ! l Le coupe choix est un prédicat prédéfini qui

réussit toujours.

Notion de coupure (3)

l Le coupe choix permet de signifier à Prolog qu’on ne désire pas conserver les points de choix en attente

l Les autres solutions possibles à l'unification ne sont donc pas examinées

Coupure dans une règle

l Le coupe-choix ne conserve que les unifications faites avant la suppression des points de choix.

a(1). b(1). a(2). b(2).p(X):- a(X),b(X).

?- p(X).X =1 ;X=2.

a(1). b(1). a(2). b(2).p(X):- a(X), !,b(X).

?- p(X).X =1.

Arbre de Recherche

?-a(X),b(X).

X=2

?-b(1). ?-b(2).

OK

X=1

?-p(X).

OK

?-a(X), !,b(X).

?- !,b(1).

X=1

?-p(X).

?-b(1).

OK

Sans Coupure Avec Coupure

Exemples d'utilisation

l Pour prouver que x est un élément d’une liste, on peut s'arrêter dès que la première occurrence de x a été trouvée.

l Pour calculer min(a,b) :

min(A, B, A) :- A=<B. min(A, B, A) :- A=<B, !.min(A, B, B) :- A >B. min(A, B, B) :- A =B.

l Exprimer des clauses exclusives :humain(X) :- homme(X). humain(X) :- homme(X), !.

humain(X) :- femme(X). humain(X) :- femme(X), !.

Danger

l Dangers du coupe-choix : on peut perdre des solutions. Expl :

achete(helene, journal). achete(helene, journal) :- !.

achete(corinne, timbres). achete(corinne, timbres) :- !.

achete(X, pain). achete(X, pain).

l et l’interrogation achete(helene, N).

l Sans coupure : N=journal et N=painl Avec coupure : N=journal

Notion de coupure (fin)

l En résumé, les utilités du coupe-choix sont :l éliminer les points de choix menant à des

échecs certainsl supprimer certains tests d’exclusion mutuelle

dans les clausesl permettre de n’obtenir que la première solution

de la démonstrationl assurer la terminaison de certains programmesl contrôler et diriger la démonstration

Exercice

l Etant donné la base de connaissance suivante, quel sera la réponse de Prolog à la question ?

a(1). a(2). b(2). c(3).p(X):- c(X).p(X):- a(X), !, b(X).

?- p(X).

Partie 5-

Négation

La négation

l Négation par l'échec l Si F est une formule, sa négation est notée \+(F).

Dans d'autres implémentations, noté not(F)l Prolog pratique la négation par l'échec, c’est-à-dire

que pour démontrer \+(F) Prolog va tenter de démontrer F. Si la démonstration de F échoue, Prolog considère que \+(F) est démontrée.

l Pour Prolog, \+(F) signifie que la formule F n’est pas démontrable, et non que c’est une formule fausse. C’est ce que l’on appelle l'hypothèse du monde clos.

La négation

l \+(X) ne veut pas dire que X est faux mais que X ne peut pas être prouvé.

l Elle est utilisée pour vérifier qu’une formule n’est pas vraie.

l La négation par l'échec ne doit être utilisée que sur des prédicats dont les arguments sont déterminés et à des fins de vérification.l Son utilisation ne détermine jamais la valeur d’une

variable

La négation

l Dangers :l Considérez le programme suivant :

p(a).

l Et interrogez Prolog avec :?- X = b, \+ p(X).

YES { X = b }

l Prolog répond positivement car p(b) n’est pas démontrable.

La négation

l Par contre, interrogez le avec :?- \+ p(X), X=b.No

l Prolog répond négativement car p(X) étant démontrable avec X = a, \+ p(X) est considéré comme faux.

=> Incohérence qui peut être corrigée si l’on applique la règle vue précédemment : n’utiliser la négation que sur des prédicats dont les arguments sont déterminés.

La différence

l La différence est définie comme le contraire de l’unificationl Elle est notée : X \= Y. Elle signifie que X et Y ne

sont pas unifiables, et non qu’ils sont différents.

Ex : Z \= 3. Sera faux car Z et 3 sont unifiables.

l Elle peut être définie comme :X \= Y :- \+ (X = Y).

Le prédicat fail

l fail signale à Prolog l'échec de la branche courante

l Prolog effectue alors un backtrack (retour arrière jusqu'au dernier point de choix)

Combinaison cut-fail

l Enchaînement :?- …,!,fail.l Le cut a supprimé tous les points de choixl Le fail essaye de retourner au dernier point de

choixl Leur combinaison termine donc la démonstrationl Permet d'exprimer une exception à une règle

l vole(X):- autruche(X), !,fail.

l vole(X):- oiseaux(X).

Exercice

l Définir la base de connaissance décrivant qu'en Europe, les voitures roulent à droite, sauf au Royaume-Uni et en Irlande.