View
3
Download
0
Category
Preview:
Citation preview
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.
Recommended