1

Le langage Prolog(DemoII)

Atefeh Farzindar

2

Table des matières

Demo 2

• Unification

• Les listes

• Arithmétique et opérateurs

• Quelques prédicats prédéfinis

• Backtracking

3

Unification

Def. Le but de l’unification est de déterminerles substitutions sur des variables pour quel’arbre de deux termes soient identiques.

Exemple:aime(paul,marie) = aime(paul,X)Si X=marie aime = aime paul marie paul X

4

Formellement, t1 est une instance de t2 s’il existe unesubstitution s telle que t2 s = t1.

Par exemple :élève(jean, info, adresse(parkAve,montreal))

est une instance de : élève(jean, X, Y)avec la substitution :s = {(X, info), (Y, adresse(parkAve,montreal)}

On définit l’unification comme l’instance communela plus générale de deux termes. L’opérateurProlog de l’unification est « = ».

5

Exemple 1.

?- élève(jean,info,Z) = élève(X,info,adresse(parkAve,montreal).

X=jean, Z=adresse(parkAve,montreal) ?- élève(jean,info,adresse(Z1,Z2))=élève(Y,info,adresse(parkAve,montreal).Y=jean, Z1=parkAve, Z2=montreal

6

Exemple 2.

a(X,b(X,Y) ) = a(fred,b(Z,Z))

a a

X b fred b

X Y Z Z

a

fred b

fred fred

7

Règles Unification

Deux termes sont unifiables si:1. Un terme est libre. ex. X = a(1,2)2. Deux constates identiques. ex. 1 = 13. Deux termes fonctionnels si

i. Même foncteurii. Même aritéiii. Tous les arguments sont uni fiables ex. aime(paul,marie) = aime(paul,X)

8

Les listes

Une liste est une structure de la forme :[a, b][a, X, adresse(X, montréal)] [] est la liste vide.La notation des listes est un raccourci. Le foncteur

« . » est le foncteur de liste .(a,.(b,[])). Il est équivalent à [a, b]. La notation « | » est prédéfinie et permet d’extraire

la tête et la queue. La tête est le 1er élément ; laqueue est la liste restante sans le premier élément.

9

Exemple:| ?- [H|T]=[head,s,u,i,t,e].H = head,T = [s,u,i,t,e] | ?- [H|T]=[head].H = head,T = [] ?- [a, [b]] = [X | Y].X = a, Y = [[b]] | ?- [_,A|B]=[marie,jean,paul,claud].A = jean,B = [paul,claud]

10

Le prédicat member/2Appartenance d’un élément à une liste :Règle1 member(X, [X | Y]).Règle2 member(X, [Y | YS]) :-

member(X, YS).

Exemples d’utilisation:?- member(X, [a, b, c]).X = a ;X = b ;X = c ;No.

11

Le prédicat append/3Concaténer deux listes Règle1 append([], L2, L2).Règle2 append([H1|T1], L2, [H1|T3]) :-

append(T1,L2,T3).

% trace| ?- append([a,b],[c,d,e],L). 1 1 Call: append([a,b],[c,d,e],_543) ? 2 2 Call: append([b],[c,d,e],_1152) ? 3 3 Call: append([],[c,d,e],_1724) ? 3 3 Exit: append([],[c,d,e],[c,d,e]) ? 2 2 Exit: append([b],[c,d,e],[b,c,d,e]) ? 1 1 Exit: append([a,b],[c,d,e],[a,b,c,d,e]) ?L = [a,b,c,d,e]

12

Utilisation de append/3

?- append([a, b], [c, d], L).L = [a, b, c, d]?- append(L, [c, d], [a, b, c, d]).L = [a, b] ?- append(L1, L2, [a, b]).L1 = [], L2 = [a, b] ;L1 = [a], L2 = [b] ;L1 = [a,b], L2 = []

13

Le prédicat delete/3Efface un élément d’une liste.delete(Élément,Liste,ListeSansÉlément).

delete(_,[],[]). %Cas trivial%Cas où Élément est en tête de listedelete(Élément, [Élément| Liste],ListeSansÉlément):-delete(Élément, Liste,ListeSansÉlément).

%Cas où Élément n’est pas en tête de liste (filtrage avec les règlesprécédentes.)

delete(Élément, [T|Liste],[T|ListeSansÉlément]):-delete(Élément, Liste,ListeSansÉlément).

14

trace et notrace| ?-trace.| ?- delete(marie,[paul,marie,claud],ListeSansÉlément).

1 1 Call: delete(marie,[paul,marie,claud],_518) ? 2 2 Call: delete(marie,[marie,claud],_1057) ? 3 3 Call: delete(marie,[claud],_1057) ? 4 4 Call: delete(marie,[],_2025) ?? 4 4 Exit: delete(marie,[],[]) ?? 3 3 Exit: delete(marie,[claud],[claud]) ?? 2 2 Exit: delete(marie,[marie,claud],[claud]) ?? 1 1 Exit:

delete(marie,[paul,marie,claud],[paul,claud]) ?

ListeSansÉlément = [paul,claud]| ?-notrace. % Switched off

15

le prédicat length/2La longueur d’une liste :?- length([a, [a, b], c], N).N = 3

length([],0).length([X | XS], N) :-length(XS, N1), N is N1 + 1.

L’évaluation par le is est essentielle car Prolog ne comprendpas 1 + 2 comme une expression arithmétique:

?- L = 1 + 2 ?- L is 1+2 L = +(1, 2) L = 3

16

Arithmétique et opérateurs

• Chaque Prolog dispose d’opérateurs infixés,préfixés et postfixés : + , - , * , / .L’interprète les considère comme desfoncteurs et transforme les expressions entermes : 2 * 3 + 4 * 2 est un termeidentique à +(*(2, 3), *(4, 2))).

17

Opérateurs et Prédicats de base

Nombres TermesOpérateur d’arithmatique +, -, *, / Opérateur d’égalité =:= ==Opérateur d’inégalité =\= \==Plus petit < @<Plus petit ou égal =< @=<Unifiable = =Évaluation is

18

Opérateurs

• Si :-

• Et ,

• Ou ;

• Unification =• Toujours vrai true• Toujours faux fail• (sicstus)if then else +P->+Q;+R

If(+P,+Q,+R)

19

Exemple 1.- 1 + 2 =:= 2 + 1. % égalité pour les NombresYes.?- 1 + X =:= 1 + 2.Erreur.?- 1 + 2 = 2 + 1. % unificationNo. ?- 1 + X = 1 + 2.X = 2.?- 1 + a == 1 + a. % identiqueYes.?- 1 + X == 1 + 2.No.

20

Exemple 2.

?- X = 1 + 1 + 1.X = 1 + 1 + 1 (ou X = +(+(1, 1), 1)). ?- X = 1 + 1 + 1, Y is X.X = 1 + 1 + 1, Y = 3.

?- Z = 2, X is 1 + 1 + Z.Z = 2X = 4

21

Quelques prédicats prédéfinis1. Prédicats de type:integer/1 : est-ce un entier??- integer(3).Yes.number/1 : est-ce un nombre??- number(3.14).Yes.float/1 : est-ce un flottant?atom/1 : est-ce un atome??- atom(toto).Yes.?- atom(3).No

22

var/1 : est-ce une variable non instanciée?nonvar/1. Le contraire de var/1.?- nonvar(X).Nocompound/1. Est-ce que le terme est composé??- compound(f(X, Y)).Yesground/1. Est-ce que le terme est fondé??- ground(f(a, b)).Yes?- ground(f(a, Y)).No

(voir liste complète des prédicats dansle manuel)

23

2. Prédicats de manipulation de termes

functor(Terme, Foncteur, Arité). Mode?- functor(père(jean, isa), F, A).F = père, A = 2. ?- functor(T, père, 2).T = père(X, Y).

arg(N, Terme, X). Unifie X à l’argument numéro Nde Terme.

?- arg(1, père(jean, isa), X).X = jean.

24

Le prédicat univ Terme =.. Liste. Transforme unterme en une liste :

?- père(jean, isa) =.. L.L = [père, jean, isa]. ?- T =.. [a, b, c].T = a(b, c).

name/2. Transforme un atome en une liste de ses codesASCII.

?- name(toto, L).L = [116, 111, 116, 111]. ?- name(A, [116, 111, 116, 111]).A = toto.

25

Exemples d’utilisation% Addition plus(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.

26

backtracking

Quand un terme est évalué à FAUX, Prolog utiliseun autre “match” (une autre unification) pour leterme précédent et essaie de nouveau de prouver lebut initial.

Exemple:?- b(X), b(Y). B. de C.X = 1,Y = 1 ?; b(1).X = 1,Y = 2 ? ; b(2).X = 2,Y = 1 ? ;X = 2,Y = 2

27

Exercices1. Effacer un element d'une liste

args: terme, liste, liste2. Le dernier d'une liste non vide

args: liste, terme3. Somme les elements d'une liste

args: liste de nombres, nombre4. Reverse d'une liste

args: liste, liste5. Trie d'une liste

args: liste de nombres, listeTriée