IA et logique : Prologrobillia/IA-L3/prolog.pdf · IA et logique : Prolog ... eux, peut être vraie ou fausse, et s’écrit comme un foncteur ex : siege(’ULCO’, adresse ... argument

IA et logique : Prolog

Denis Robilliard

2014-2015, revisé mars 2018

Denis Robilliard IA et logique : Prolog 2014-2015, revisé mars 2018 1 / 25

Présentation

PROLOG : “PROgrammer en LOGique”

Alain Colmerauer, Univ. Marseille, 1972

Plusieurs dialectes et langages dérivés (ex : Datalog)

Dans ce cours : SWI Prolog, commande “swipl”.

I manuel de référence :http://www.swi-prolog.org/pldoc/man?section=quickstart

I un site de Christine Solnon, chercheuse au LIRIS et professeur à l’INSA deLyon, plus maintenu mais intéressant :http://liris.cnrs.fr/csolnon/prolog.html


http://www.swi-prolog.org/pldoc/man?section=quickstart

http://liris.cnrs.fr/csolnon/prolog.html

IntroductionOrganisation d’une session

Éditer un fichier .pl, ex : monprog.pl

Note : un commentaire commence par % et s’étend jusqu’en fin de ligne.

Lancer swipl dans un terminal.

Au prompt | ?-, charger et compiler votre programme [’monprog’].(attention pas de .pl derrière le nom de fichier).

Corriger si nécessaire les erreurs de compilation.

Utile : trace. et notrace. active et désactive le débogueur avec trace,nodebug. quitte le débogueur.

Principe général de la programmation prologProgrammation déclarative : on liste des faits et des règles, formant la"database".

On pose une requête (query ) et le "moteur" Prolog cherche si cetterequête peut se déduire de la database.


Éléments de base

DéfinitionsTerme : tout élément de base du langage, se décomposent en :

I les variables : chaînes alphanumériques commençant par une lettremajuscule, non typées, pouvant représenter tout objet, immutables une foisaffectées (mais voir plus loin) ;

I les termes élémentaires : objets simples ("atomiques") comme nombresentiers, flottants, identificateurs commençant par une minuscule, chaînesde caractères entre ’ ’ ou " ".

I les termes composés (structurés), représentés par des foncteurs,identifiants commençant par une minuscule suivi d’arguments entreparenthèses : foncteur(t1, . . ., tn) le nombre d’arguments est appelé l’aritédu foncteur. Exemple : adresse(1, ’place de l’Yser’, 59375,’Dunkerque’)

les relations (ou atomes logiques) : une relation lie des termes entreeux, peut être vraie ou fausse, et s’écrit comme un foncteur ex :siege(’ULCO’, adresse(1, ’place de l’Yser’, 59375,’Dunkerque’))


Éléments de base – suite

PrincipeUn programme est une liste de clauses

Un fait est une clause de la forme : corps.

Une règle est une clause de la forme : tête :- corps. (notez le pointfinal)

Exemples de faitsbleu(ciel).

mammifere(lapin).

parent(paul, theo).

egal(X,X).

Prolog est un langage symbolique : pas besoin de " " ou de ’ ’ autour deciel ou lapin (on peut en mettre si on veut explicitement des chaînes).

Ici, ciel ou lapin sont des constantes, bleu ou parent sont des prédicats.



Exemples de règlesvertebre(lapin):-mammifere(lapin).

vertebre(X):-mammifere(X).

vertebre(X):-oiseau(X).

gdparent(X, Y):-parent(X,Z),parent(Z,Y).

On peut lire le connecteur :- comme un "si" : la tête est vraie si tous lesatomes du corps sont vrais.

Une variable apparaissant en tête de règle est quantifiée ∀ , en corps derègle est quantifiée ∃ .

Attention, une variable ne peut changer de valeur au cours d’un calcul.

Deux clauses avec même tête correspondent à un ou logique : règle 2 et3, X est un vertebre si X est un mammifere ou si X est un oiseau.

La virgule dans un corps de clause correspond au et logique : règle 4, Xest grand parent de Y si X est parent de Z et Z est parent de Y.



parent(X,Y) :- ( pere(X,Y) ; mere(X,Y) ).On peut introduire un ou aussi dans un corps de clause avec lepoint-virgule : bien parenthéser les limites du "ou".

orphelin(X) :- \+ parent(_,X).La négation se note \+ en prolog. Notez la variable anonyme _ : on nel’utilise pas ailleurs dans cette clause, donc on n’a pas besoin de gaspillerun identifiant (warning: singleton variables sinon).

La sémantique de la négation est la “négation par l’échec” : est faux cequi ne peut pas être prouvé vrai avec la database (on parle “d’hypothèsedu monde clos”).

bonjour :- write(’votre nom : ’), read(N),write(’Bonjour ’), write(N), nl.Le prédicat read/1 à 1 argument, saisit une donnée de l’entrée standard,qui doit obligatoirement finir par un point. Le prédicat write/1 écrit sonargument sur l’entrée standard.


Exécution d’un programme Prolog

Au prompt on pose une requête :| ?- parent(paul, X). se lit quels sont les X tels que parent(paul,X) estvrai ?

Prolog affichera tous les X correspondant, et le prédicat vaut "true" si uneréponse existe comme une conséquence “logique” du programme, "false” sinon| ?- parent(paul, X).X = theo| ?- parent(paul, theo).true.| ?- parent(paul, yoda).false.

| ?- parent(paul, X), parent(X, Y). répondra de même par tous lescouples X, Y tels que la conjonction des 2 atomes de la question soient vraie.

On passe d’une réponse à la suivante en tapant ; (ou espace), et a ou RETURNpour arrêter l’énumération des réponses s’il y en a plusieurs).

On quitte l’interpréteur prolog avec halt.


Principe de la sémantique Prolog

Substitution et unificationUne substitution s est une fonction de l’ensemble des variables dansl’ensemble des termes. Par exemple : s = {X <- Y, Z <- f(a,Y)}

Une substitution peut être appliquée à un atome logique :s(p(X,f(Y,Z))) = p(s(X),f(s(Y),s(Z))) = p(Y,f(Y,f(a,Y)))

Une instance d’un atome logique A est le résultat de l’application d’unesubstitution : parent(paul,theo) est une instance de parent(paul,X)via la substitution {X <- theo}

Un unificateur des atomes logiques A et B est une substitution s telle ques(A) = s(B) : A = p(X,f(X,Y)), B = p(a,Z) ont pour unificateurs ={X<-a, Z<-f(a,Y)}, mais aussi s′ ={X<-a, Y<-g(b,c),Z<-f(a,g(b,c))}

Un unificateur s de A et B est unificateur le plus général (upg) si pourtout autre unificateur s′ de A et B, il existe une substitution s′′ non videtelle que s′ = s′′(s). Ci-dessus : s′′ ={Y <- g(b,c)}.


Exemples d’unification

Unification possible? Si oui, quelle substitution?a = a.

a = b.

X = Y.

foo(a,Y) = foo(X,b).

foo(a,b) = foo(X,X).

2*3+4 = X+Y.

k(s(g), Y) = k(X, t(k)).

k(s(g), t(k)) = k(X, t(Y)).

k(s(g),Y) = k(X,t(X)).

k(t(s(X)), g(Y)) = k(t(Y),g(X)).



Unification possible? Si oui, quelle substitution?a = a. oui, subst. vide.

a = b.

X = Y.



2*3+4 = X+Y.

k(s(g), Y) = k(X, t(k)).

k(s(g), t(k)) = k(X, t(Y)).

k(s(g),Y) = k(X,t(X)).

k(t(s(X)), g(Y)) = k(t(Y),g(X)).




a = b. non.

X = Y.



2*3+4 = X+Y.

k(s(g), Y) = k(X, t(k)).

k(s(g), t(k)) = k(X, t(Y)).

k(s(g),Y) = k(X,t(X)).

k(t(s(X)), g(Y)) = k(t(Y),g(X)).




a = b. non.

X = Y. oui, X<-Y.



2*3+4 = X+Y.

k(s(g), Y) = k(X, t(k)).

k(s(g), t(k)) = k(X, t(Y)).

k(s(g),Y) = k(X,t(X)).

k(t(s(X)), g(Y)) = k(t(Y),g(X)).




a = b. non.

X = Y. oui, X<-Y.

foo(a,Y) = foo(X,b). oui, X<-a, Y<-b.


2*3+4 = X+Y.

k(s(g), Y) = k(X, t(k)).

k(s(g), t(k)) = k(X, t(Y)).

k(s(g),Y) = k(X,t(X)).

k(t(s(X)), g(Y)) = k(t(Y),g(X)).




a = b. non.

X = Y. oui, X<-Y.


foo(a,b) = foo(X,X). non.

2*3+4 = X+Y.

k(s(g), Y) = k(X, t(k)).

k(s(g), t(k)) = k(X, t(Y)).

k(s(g),Y) = k(X,t(X)).

k(t(s(X)), g(Y)) = k(t(Y),g(X)).




a = b. non.

X = Y. oui, X<-Y.



2*3+4 = X+Y. oui, X<-2*3, Y<-4.

k(s(g), Y) = k(X, t(k)).

k(s(g), t(k)) = k(X, t(Y)).

k(s(g),Y) = k(X,t(X)).

k(t(s(X)), g(Y)) = k(t(Y),g(X)).




a = b. non.

X = Y. oui, X<-Y.



2*3+4 = X+Y. oui, X<-2*3, Y<-4.

k(s(g), Y) = k(X, t(k)). oui, X<-s(g), Y<-t(k).

k(s(g), t(k)) = k(X, t(Y)).

k(s(g),Y) = k(X,t(X)).

k(t(s(X)), g(Y)) = k(t(Y),g(X)).




a = b. non.

X = Y. oui, X<-Y.



2*3+4 = X+Y. oui, X<-2*3, Y<-4.


k(s(g), t(k)) = k(X, t(Y)). oui, X<-s(g), Y<-k.

k(s(g),Y) = k(X,t(X)).

k(t(s(X)), g(Y)) = k(t(Y),g(X)).




a = b. non.

X = Y. oui, X<-Y.



2*3+4 = X+Y. oui, X<-2*3, Y<-4.



k(s(g),Y) = k(X,t(X)). oui, X<-s(g), Y<-t(s(g)).

k(t(s(X)), g(Y)) = k(t(Y),g(X)).




a = b. non.

X = Y. oui, X<-Y.



2*3+4 = X+Y. oui, X<-2*3, Y<-4.



k(s(g),Y) = k(X,t(X)). oui, X<-s(g), Y<-t(s(g)).

k(t(s(X)), g(Y)) = k(t(Y),g(X)). non ! X<-Y, Y<-s(Y) : impossiblel’erreur sur le dernier n’est pas forcément vue par prolog...


Algorithme d’unificationfonction upg(t1, t2: termes) // rend l’upg de t1 et t2 ou echecsi t1 = t2 alors rendre(substitution vide) finsisi t2 est une variable alors permuter t1 et t2 finsisi t1 est une variable alorssi t2 contient t1 alors rendre(echec) /* test d’occurrence */sinon rendre(t1 <- t2 ) finsi

sinonsi t1 et t2 sont 2 structures de symbole != ou d’arité !=alors rendre(echec)sinon soit t1 = symb(u1, ..., un) et t2 = symb(v1, ..., vn)s <- substitution videpour i de 1 a n faires’ <- upg(s(ui), s(vi))si s’ = echec alors rendre(echec) finsis <- s’(s)

finfairerendre(s)

finsifinsi


Principe de la résolution Prolog

Chaînage arrière

Pour prouver un but composé d’une suite d’atomes logiques | ?- A1,A2, ..., An., Prolog cherche à prouver d’abord A1 en trouvant uneclause dont la tête s’unifie avec A1, par exemple B0 :-B1, B2, ...,Bm. avec l’upg(A1,B0)=s.

On remplace A1 dans le but par la substitution du corps associé à B0, lebut devient : | ?- s(B1), s(B2), ..., s(Bm), s(A2), ...,s(An).

On continue à appliquer cette méthode jusqu’à ce que le but soit vide : lebut initial est prouvé et s’il contenait des variables on affiche leur valeur enappliquant les substitutions successives qui ont mené au but vide.

Comme il est possible que plusieurs têtes de clauses puissent s’unifieravec un atome, Prolog essaie successivement tous les cas possibles etpeut donc trouver plusieurs réponses.


Illustration de la résolution

p(a). /* 1 */p(X) :- q(X), r(X). /*2 */p(X) :- u(X). /* 3 */q(X) :- s(X). /* 4 */r(a). /* 5 */r(b). /* 6 */s(a). /* 7 */s(b). /* 8 */s(c). /* 9 */u(d). /* 10 */

Descente récursive à gauche d’abord (de haut en bas pour les règles duprogramme), en profondeur d’abord (le 1er sous-but de la clause) : attentionaux branches infinies !


Résolution prolog – branches infinies

naturel(X):- Y is X-1, naturel(Y).naturel(0).

| ?- naturel(2).

Fatal Error: global stack overflow (size: 32768 Kb, env...

Visualiser en mode trace (taper c pour dérouler la trace pas à pas).

Logiquement valide mais branche infinie



naturel(0).naturel(X):- Y is X-1, naturel(Y).

| ?- naturel(2).

true ? ;Fatal Error: global stack overflow (size: 32768 Kb, env...


Logiquement valide mais branche infinie si appelé pour un négatif

Donne vrai pour un positif, mais si on demande tous les résultats alorsbranche infinie aussi !



naturel(X):- X < 0, !, fail.naturel(0).naturel(X):- Y is X-1, naturel(Y).

| ?- naturel(2).

true ? ;false.


Le "cut" ! force cette branche étant comme la dernière.

Plus de branche infinie, et la dernière branche de la requête se terminepar un échec (aucune importance, il y a eu un succès)



naturel(X):- X < 0, !, fail.naturel(0):-!.naturel(X):- Y is X-1, naturel(Y).

| ?- naturel(2).

yes.


Le "cut" ! force cette branche étant comme la dernière.

En coupant dès le succès sur 0, on ne voit pas l’échec de la dernièrebranche.


Compléments sur le langage

La coupure ou cut...Le cut ! (ou coupure) : prédicat sans signification logique (ni vrai ni faux),toujours traversé, qui coupe l’ensemble des branches en attente crééesdepuis la tête de la clause qui contient le cut, jusqu’au moment où onpasse le cut.

... à consommer avec modérationRisque de perte du résultat à chaque coupe !

Exemple :

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

Quelle réponse pour la requête a(X).


Compléments sur le langage

La coupure ou cut...Le cut ! (ou coupure) : prédicat sans signification logique (ni vrai ni faux),toujours traversé, qui coupe l’ensemble des branches en attente crééesdepuis la tête de la clause qui contient le cut, jusqu’au moment où onpasse le cut.

... à consommer avec modérationRisque de perte du résultat à chaque coupe !

Exemple :

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

Quelle réponse pour la requête a(X). rien ! (il ne considère que X<-1).


Exemples de cut (coupure)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).

Position du cut :(X,Y) :- q(X), r(X,Y), !.solution 1 etcoupe de b112, b12, b2.p(X,Y) :- q(X), !, r(X,Y).solutions 1 et 2,coupe de b12 et b2.p(X,Y) :- !, q(X), r(X,Y).solutions 1, 2, 3, 4 et 5,coupe de b2.

L’arbre de recherche construit par Prolog pour le but p(Z,T) est :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([],[p(a,a1)] –> solution1 = Z=a, T=a1b112 : 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=b1b122 : s = Y <- b2—— prouver([]) –> solution4 = Z=b, T=b2b123 : s = Y <- b3—— prouver([]) –> solution5 = Z=b, T=b3

b2 : s = Z <- c, T <- c1—- prouver([]) –> solution6 = Z=c, T=c1


Exemples de cut (suite)

p(X) :- r(X).p(X) :- s(X)r(X) :- write(’*’), s(X), !.s(a).s(b).s(c).

requete : p(X).*X = a ? ;X = a ? ;X = b ? ;X = cyes

Notez que les branches en attentes sur p(X) ne sont pas coupées par le cutdans la définition de r(X).


Compléments : unification, arithmétique, comparaisons.

t1 = t2, t1 \= t2 : vrai ssi t1 unifiable/non unifiable avec t2 en appliquantles substitution/assignations nécessaires aux variables

t1 == t2, t1 \== t2 identité/différence des deux termes : f( a, b ) == f(a,b)est vrai (espaces non significatifs)

Expr1 = := Expr2, Expr1 =\= Expr2 : vrai si les 2 expressions ontmêmes/différentes valeurs résultat (indépendamment de leur forme)

?- 1+2=2+1.false.?- 1+2=X.X = 1+2.?- 1+2= 1 + 2.true.?- 1+2==2+1.false.?- 1+2== X.false.?- 1+2== 1 + 2.true.

?- 1+2=:= 1 + 2.true.?- 1+2=:=2+1.true.?- 1+2=:=X.erreur (X non instancié).?- 2+1=X, 1+2=:=X.X = 2+1.?- 2+3=X, 1+2=:=X.false.


Compléments : unification, arithmétique, comparaisons.

Unification, arithmétique, comparaison

t1 \= t2 : vrai si t1 non unifiable avec t2, faux si unifiable ;

Var is expression : unifie (assigne) à la variable Var le résultat del’expression (ex : X is 2+3) ;

Inégalités : <, >, =<, >= comparent des nombres ; @<, @>, @=<, @>=peuvent aussi comparer des chaînes


Compléments : listes

Liste

Une variable de type liste se construit entre crochets [] comme la donnée de npremiers éléments (n=1,2,3,...), séparés par des virgules, suivi facultativementpar une barre | qui précède la liste des éléments restants (liste qui peut êtrevide). Exemples :



Liste


I liste vide : [ ]I liste à 1 élément a : [ a ] ou [a | [ ] ]I liste à 3 éléments a,b,c : [a, b, c] ou [a, b | [c]] ou [a | [b, c]] ou [a | [b | [ c ]]].I ne pas confondre virgule et barre : [[a], [b]] (liste de deux listes) et [a | [b]]

(liste égale à [a, b], ne contenant aucune liste comme élément).



Liste




Unification de liste :

I [X|L]=[1,2,3] → Subst :{X=1, L=[2,3]}I [X,Y|L]=[1,2,3] → Subst :{X=1, Y=2, L=[3]}I [X,Y,Z|L]=[1,2] → Fail ! (Z pas unifiable)



Liste




Unification de liste :

I [X|L]=[1,2,3] → Subst :{X=1, L=[2,3]}I [X,Y|L]=[1,2,3] → Subst :{X=1, Y=2, L=[3]}I [X,Y,Z|L]=[1,2] → Fail ! (Z pas unifiable)

Rien pour accèder aux derniers (... donc récursivité).


Compléments : exemples de listes

/* récupère le premier d’une liste */prem(L,X) :- L = [X|_].?- prem([1,2],C).C = 1.?- prem([],C).false.?- prem([[1,2]],C).C = [1, 2]./* ajoute toto en tête d’une liste */ajouttoto(L1,L2) :- L2 = [toto|L1].?- ajouttoto([1,2], L).L = [toto , 1, 2]./* afficher récursivement une liste */affiche([]).affiche([X|L]) :- write(X), nl, affiche(L)./* concatène 2 listes (clone de ’append’ prédéfini) */concat([], L2, L2).concat([X|L1], L2, [X|L3]):- concat(L1, L2, L3).


Clauses dynamiques

Idée : ajouter des faits ou règles dynamiquement en cours d’exécutiond’un programme.

dynamic(predicat/arite) : déclare predicat comme étant unpredicat dynamique d’arité arite (voir exemple ci-dessous).

asserta(clause) : ajoute la clause au début de la database ;

assertz(clause) : ajoute la clause en fin de la database ;

retract(clause) : retire la 1ère clause de la database qui s’unifie avecla clause argument – ce doit être une clause dynamique ;

retractall(tete) : retire toutes les clauses de la database quis’unifient avec la tete – ce doit être des clauses dynamiques.

Exemple :

:-dynamic(toto/1). /* toto est un predicat dyn. a 1 argument */goal(X) :- retractall(toto),/* efface tout eventuel toto(...) */

asserta(toto(a)), /* declare dynamiquement un fait */toto(X). /* verifie que toto(a) est connu */


Divers

true, fail : true est toujours vrai, fail toujours faux (déclenche lebacktracking).

halt :- predicat sans argument qui met fin au programme (et àl’interpréteur).

member(X, L) : prédicat qui unifie successivement X à chaque élémentde la liste L. Donc équivalent à un "ou" (X=L1 ; X=L2 ; ... ; X=Ln)avec L1, L2, ..., Ln les éléments de L. Exemple :chiffre(X):-member(X,[0,1,2,3,4,5,6,7,8,9]).

findall(X, pred(...,X, ...), L) : crée dans L une liste descopies de chacune des valeurs qui peuvent être unifiées avec X enappelant pred(...,X, ...). Exemple : findall(X,member(X,[a,b,c]), L) construit L = [a,b,c].


Divers (suite)

Note : swi-prolog tronque l’affichage des listes “trop grandes”, c’est parfoisagaçant... Astuce : ajouter un point de choix artificiel ; true et taper w (pourwrite) à la console.

?- findall(X, member(X,[0,1,2,3,4,5,6,7,8,9]),L).L = [0, 1, 2, 3, 4, 5, 6, 7, 8|...].?- findall(X, member(X,[0,1,2,3,4,5,6,7,8,9]),L); true.L = [0, 1, 2, 3, 4, 5, 6, 7, 8|...] [write]L = [0, 1, 2, 3, 4, 5, 6, 7, 8, 0] .


Divers (suite)

Lister le contenu de la database : | ?- listing.

Exécuter automatiquement une requête au démarrage ::-initialization(goal).

On peut encore :I Créer des scripts Prolog sous Unix/Wind*wsI Lier Prolog avec du C++, du Java


Documents

IA et logique : Prologrobillia/IA-L3/prolog.pdf · IA et logique : Prolog ... eux, peut être vraie ou fausse, et s’écrit comme un foncteur ex : siege(’ULCO’, adresse ... argument