Prédicats prédéfinisPrédicats de type : Le type d ’un terme peut être une variable, une constante (atome, nombre), une structure.

Un terme de type variable peut être instancié ou non.

integer(X) <=> est-ce que X est un entier? ?- integer(4).> Yes.?- integer(X).> No.

float(X) <=> est-ce que X est un flottant? ?- float(3.14).> Yes.

number(X) <=> est-ce que X est un nombre?

Prédicats prédéfinis atom(X) <=> est-ce un atome?

?- atom(toto).> Yes.?- atom(3).> No.

atomic(X) <=> est-ce un atome ou un nombre? var(X) <=> est-ce une variable non instanciée??- var(X).> Yes.?- X= f(Z), var(X).> No.

nonvar(X) <=> (le contraire de var) <=> X est un terme autre qu’une variable, ou une variable instancié.?- nonvar(X).> No.

Prédicats prédéfinis

compound(X) <=> est-ce un terme composé??- compound(X).> No.?- compound(f(X,Y)).> Yes.

ground(X) <=> est-ce un terme fondé??- ground(f(a,b)).> Yes.?- ground(f(a,Y)).> No.

Prédicats prédéfinisPrédicats de manipulation de termes functor(Terme, Foncteur, Arité).

?- functor(pere(jean,isa), F, A).> F = pere, A = 2.?- functor(T, pere, 2).> T = pere(X,Y).

arg(N, Terme, X). <=> unifie X à l ’argument numéro N de terme.?- arg(1, pere(jean, isa), X).> X = jean.

Terme = ..L. <=> transforme un terme en une liste.?- pere(jean,isa) = ..L.> L= [pere, jean, isa].?- T= ..[a,b,c].> T= a(b, c).

Prédicats prédéfinis

name(atome, Liste). <=> transforme un atome en une liste de ses codes ASCII. ?- name(toto, L).> L = [116, 111, 116, 111].?- name(A, [116, 111, 116, 111]).> A = toto.

Prédicats prédéfinis

Exemples: ?- var(Z), Z=2. > Z=2 ?- Z=2, var(Z). > no ?- integer(Z), Z=2. > no ?- var(Z), Z=2, integer(Z), nonvar(Z). > Z=2 ?- atom(22). > no ?- atomic(22). > yes ?- atom( date(1, mars, 2003) ). > no

Prédicats prédéfinisUtilisation: integer(X), integer(Y), Z is X+Y;

Que faire en cas d’échecs ... count(A,L,N) <=> A apparaît N fois dans L

count(_,[],0). count(A, [A|L], N) : !, count(A, L, N1), N is N1 + 1.

count(A, [_|L],N) : count(A, L, N).

Mais alors: ?- count(a, [a,b,X,Y], N). > N = 3 ?-count(b, [a,b,X,Y], N). > N = 3 X et Y ont été instancié à a (b)

Prédicats prédéfinis Nouvelle solution:

count(_, [], 0). count(A, [B|L], N) : atom(B), A = B, !, %B est un atome A? count(A, L, N1), %compter nombre de A dans L N is N1 + 1; count(A, L, N). %sinon compter dans L

Additionplus(X,Y,Z) :-nonvar(X), nonvar(Y),Z is X +Y.

plus(X,Y,Z) :-nonvar(Y), nonvar(Z),X is Z - Y.

plus(X,Y,Z) :-nonvar(X), nonvar(Z),Y is Z - X.

Prédicats prédéfinis Algorithme d ’unification: (version simplifiée) unify(Terme1,Terme2) <=> est-ce unifiable?

unify(X,Y) : var(X), var(Y), X=Y.

unify(X,Y) : var(X), nonvar(Y), X=Y.

unify(X,Y) : nonvar(X), var(Y), Y=X.

unify(X,Y) : nonvar(X), nonvar(Y),compound(X), compund(Y),termUnify(X,Y).

termUnify(X,Y):-functor(X, F, N),functor(Y, F, N),argUnify(N, X, Y).

Prédicats prédéfinis

argUnify(N,X,Y):-N>0,

argUnify1(N, X, Y),

Ns is N-1,

argUnify(Ns, X, Y).

argUnify(0,X,Y).

argUnify1(N, X, Y):-

arg(N, X, ArgX),

arg(N, Y, ArgY),

unify(ArgX, ArgY).

Prédicats de méta-programmation

Ajout et suppression de clauses (règles) en cours d’exécution :

Clause(Tete, Corps) <=> renvoie les corps des clauses pour une tête donnée.personne(jean).Personne(isa).Personne(X,Y):-fils(Y,X),masculin(X).

?- clause(pere(X,Y), C).> C= (fils(Y,X), masculin(X)).?- clause(personne(X), C).> X = jean, C = true;> X = isa, C = true;

Prédicats de méta-programmation

Exemple d ’application : les méta-interpréteurs pour prouver un but :

prove(But):-call(But). Ou bien simplement :

prove(But):- But. On peut aussi descendre dans le code et écrire :

prove(true).prove((But1, Buts2)) :-prove(But1),prove(Buts2).

prove(But):-clause(But, Corps),prove(Corps).

Prédicats de méta-programmation

Le méta-interpréteur le plus connu (vanilla):solve(true).

solve((But, Reste)):-

solve(But),

solve(Reste).

solve(But):-

clause(But, Corps),

solve(Corps).

Prédicats de méta-programmation

Le méta-interpréteur le plus connu (vanilla):solve(true).solve((But, Reste)):- solve(But),solve(Reste).

solve(But):-clause(But, Corps), solve(Corps).

assert(C) <=> ajout de la clause C à la base de données.?- assert(personne(françois)). ajoute le fait personne(françois). au programme.

Autres variantes : Asserta(C) ajout au début du programme assertz(C) ajout en fin du programme

Prédicats de méta-programmation

abolish(Terme, Arité) <=> permet de retirer tous les termes Terme d’arité Arité

consult(Terme, Arité) <=> Réalise un assert des faits et des règles du fichier.

retract(Terme) <=> retract(P) permet de retirer P de la base de donnée.? retract(personne(X)).

> X= jean, X= francois;

retractall(Tete) <=> Tous les faits et toutes les clauses dont la tête s’unifie avec Tete sont retirés.

Prédicats du 2nd ordre

findall/3, bagof/3, setof/3 : La résolution Prolog peut toutes les solutions

satisfaisant un ensemble de buts. Mais lorsqu ’une nouvelle solution est générée, la solution précédente est perdue.

Les prédicats bagof,setof et findall permettent de collecter ses solutions dans une liste.

Prédicats du 2nd ordre

Le prédicat findall :Exemple :

eleve(françois, 2, info).

eleve(isa, 2, info).

eleve(françois, 3, math).

?- findall(X, eleve(X, 2, info), B).

> B = [françois, isa].

?- findall(X, eleve(X,Y,Z),B).

> B = [françois, isa, françois].

Prédicats du 2nd ordre Le prédicat bagof :

Exemple :

eleve(françois, info, 2).

eleve(isa, info, 2).

eleve(françois, info, 3).

eleve(paul, math, 3).

masculin(françois).

masculin(paul).

feminin(isa).

?-bagof(X, eleve(X, info, 2), B).

> B = [francois, isa].

?-bagof(X, eleve(X, info, Y), B).

> B = [françois, isa], Y=2;

> B = [françois], Y=3;

Prédicats du 2nd ordre Utilisation d ’un quantificateur (^) :

?-bagof(X, Y^eleve(X, info, Y), B).

> B = [françois, isa, françois].

?-bagof(X, eleve(X, Y, Z), B).

> B = [françois, isa], Y = info, Z=2.

> (etc … )

?-bagof(X, Z^Y^eleve(X, Y, Z), B).

> B = [françois, isa, françois,paul].

?-bagof(X, Z^Y^(eleve(X, Y, Z), masculin(X)), B).

> B = [françois, françois, paul].

Le prédicat setof/3 :idem que bagof/3, sauf que la liste est triée et les doublons exclus

Prédicats repeat

Repeat Le prédicat repeat est toujours vrai (succès) et à chaque fois qu ’il est rencontré, une nouvelle branche d ’exécution est générée.

Repeat peut être définie par : repeat.

repeat : repeat.

Exemple d’utilisation: carre :

repeat,

read(X),

(X = stop, !; Y is X*X, write(Y), fail ).

Entrées / sorties

Le prolog standard ne connaît que l ’ASCII. Les entrées sorties sont primitives.

Lire et écrire des caractères : ?- get0(X).

a

> X= 65.

?- put0(65).

>a.

?- get0(X).

^D

> X= -1.

Entrées / sorties Lire et écrire des termes :

?- read(X).pere(françcois, isa).> X= pere(françcois, isa). Read renvoie end_of_file en fin de fichier.?- T = pere(françois, isa), write(T).pere(francois, isa).?- nl. Insère une nouvelle ligne.

Ouvrir et fermer des fichiers see(fichier).

Ouverture en lecture du fichier fichier. Le fichier devient le flux d ’entrée courant.

see(user).Le flux courant redevient l ’utilisateur - le clavier

Entrées / sorties see(fichier).

Rappelle fichier à l ’endroit où il était s ’il n ’a pas été fermé. Et il redevient le flux courant.

seen.Fermeture du fichier ouvert en lecture. L ’utilisateur devient le flux courant.

seeing(F).F s ’unifie au fichier en cours

tell(fichier).Ouverture en écriture du fichier. Le fichier devient le flux de sortie courant.

telling(F).F s ’unifie au fichier en cours

Entrées / sorties tell(user).

Le flux courant de sortie redevient l ’utilisateur - le clavier.

told.Fermeture du fichier ouvert en écriture.

Exemples : lecture d ’un fichierread_file(File, List):-see(F),read_list(List),seen,!.

Read_list([X|L]):-get0(X), X =\= -1, ! , read_list(L).

Read_list([]).

Entrées / sorties Copie d ’un fichier dans un autre (supposés correctement ouvert)copie:-repeat,ecrire(X),X== end_of_file,!.ecrire(end_of_file).ecrire(X):-write(X), nl.

Découpage de phrases en mots :?- tokenise(X).le petit chat.> X= [le, petit, chat, ‘.’].

Termes préfixés et N-uplets

Termes préfixés Codage Exemple du calcul booléen

Codage des termes préfixés (1)

Donnons-nous une suite de propositions : Il fait beau. Jean habite Lens. Pierre est le père de Marie...

Associons leur des variables P, Q, R, … Si on les relie à l’aide de connecteurs et, ou,

non, on obtient des formules de logiques.

Codage des termes préfixés (2)

Ces formules sont de la forme : P et Q, P ou Q, non P, …

On peut alors construire : (P et Q) ou (R et S) P et (Q ou (R et non(S)))

Ce qui donne en notation préfixée (préférable) ou(et(P, Q), et(R, S))

Codage des termes préfixés (3)

Ces formules sont représentées par des arbres.

Exercice : dessiner les arbres des 2 formules précédentes.

Ces structures sont appelées des termes préfixés. Cette notation est utilisée pour représenter :

des relations : parle(louis, chinois) des fonctions.

Codage des termes préfixés (4)

Le nombre d’arguments ne dépend que de la relation ou de la fonction utilisées.

La seule restriction est que le terme qui sert à préfixer doit être un identificateur, il ne peut s’agir d’une variable.

Calcul booléen (1)

Illustration de l’utilisation des termes préfixés. Attribuons :

la valeur 1 à une proposition vraie la valeur 0 à une proposition fausse. Exercice : écrire les règles du calcul booléen associées

aux propositions suivantes : et(P, Q), ou(P, Q), non(P).

Calcul booléen (2)

Problème : écrire les règles qui calculent la valeur booléenne d’une formule.

Nous allons travailler sur l’exemple : et(ou(0, non(1)), et(1, non(0))) Exercice : représenter l’arbre associé à cette formule.

Calcul booléen (3)

Approche naturelle : appeler les règles valeur-booleenne y faire figurer 2 arguments : la formule à évaluer et le

résultat de l'évaluation. Il y a deux types de formules au sein de l’arbre

représentatif : les nœuds en et, ou, non les feuilles 0 et 1

Calcul booléen (4)

Règles relatives aux feuilles : R1: valeur-booleenne(0, 0). R2: valeur-booleenne(1, 1).

Examinons les regles relatives à une formule et(P, Q) :

R3: valeur-booleenne(et(P, Q), B) :-

valeur-booleenne(P, U),

valeur-booleenne(Q, V),

combiner-et(U, V, B).

Calcul booléen (5)

Avec : R6: combiner-et(1, 1, 1). R7: combiner-et(1, 0, 0). R8: combiner-et(0, 1, 0). R9: combiner-et(0, 0, 0).

Exercice : écrire les autres règles R4: valeur-booleenne(ou(P, Q), B) R5 : valeur-booleenne(non(P), B) R10 à R15 : règles combiner-ou et combiner-non

Calcul booléen (6)

Commentaires : Le programme est conçu de façon purement

déclarative. Chacune des règles correspond à un cas spécifique, il

n’y a pas de remontée possible. R3, R4, et R5 sont des règles récursives. R1 et R2 sont

les règles d'arrêt.

Calcul booléen (7)

Améliorations du programme : N’est-il pas possible d’arranger les règles ?

1) remarque sur le et(0, _) et modification de valeur-booléenne

2) introduction de coupure 3) comment supprimer la coupure ? 4) introduction de poursuivre-et 5) simplification des règles 6) adaptation du raisonnement à ou

Calcul booléen (8)

Amélioration 1 : et(0, Q) donne toujours la valeur faux. Il n’est donc pas

nécessaire d'évaluer Q. D’où la règle : S1: valeur-booleenne(et(P, Q), 0) :-

valeur-booleenne(P, 0). S2: valeur-booleenne(et(P, Q), B) :-

valeur-booleenne(P, U),

valeur-booleenne(Q, V),

combiner-et(U, V, B).

Calcul booléen (9)

Amélioration 2 : L’amélioration 1 n’a rien apportée car si P vaut 0, S1

s’applique, et le programme se poursuit. Lors de la remontée, il applique S2 !!

S1: valeur-booleenne(et(P, Q), 0) :-

valeur-booleenne(P, 0) !.

S2: valeur-booleenne(et(P, Q), B) :-

valeur-booleenne(P, U), valeur-booleenne(Q, V),

combiner-et(U, V, B).

Calcul booléen (10)

Amélioration 3: Problème du cut : détruit l’aspect déclaratif du

programme en introduisant un contrôle sur l’exécution. Pour le supprimer, il suffit de réserver S2 aux cas où P est vraie.

S1: valeur-booleenne(et(P, Q), 0) :-

valeur-booleenne(P, 0). S2: valeur-booleenne(et(P, Q), B) :-

valeur-booleenne(P, 1), valeur-booleenne(Q, V),

combiner-et(1, V, B).

Calcul booléen (11)

Amélioration 4 : On n’a pas progressé car P est toujours évalué 2 fois.

Le programme est toujours inefficace. C’est S1 la source du problème.

S1: valeur-booleenne(et(P, Q), B) :-

valeur-booleenne(P, U), poursuivre-et(U, Q, B). S2: poursuivre-et(0, Q, 0). S3: poursuivre-et(1, Q, B):- valeur-booleenne(Q, V),

combiner-et(1, V, B).

Calcul booléen (12)

Amélioration 5: La règle S2 prend en compte le cas où la valeur

booléenne de P est nulle. On peut donc supprimer des déclarations dans combiner-et.

combiner-et(1, 1, 1).

combiner-et(1, 0, 0). Mais si on efface combiner-et(1, V, B) sur ces deux

règles, V et B prendront la même valeur. On peut donc supprimer combiner-et en identifiant V et B.

Calcul booléen (13)

On a donc les règles :

valeur-booleenne(et(P, Q), B) :-

valeur-booleenne(P, U), poursuivre-et(U, Q, B).

poursuivre-et(0, Q, 0).

poursuivre-et(1, Q, B) :- valeur-booleenne(Q, B). Exercice : écrire de la même façon les règles de ou(P,

Q) et de non(P). La première version était plus lisible, mais nous avons

supprimé 4 règles et gagné énormément en efficacité.

Conclusion - termes préfixés

Nous avons généralisé la structure de liste en définissant les termes préfixés, ou encore des arbres dont le nœuds ne sont pas seulement des « . », mais des identificateurs. Nous allons maintenant voir des arbres dont les nœuds peuvent être des variables, et plus seulement des identificateurs.