Programació Lògica :- ProLog.


Save this PDF as:
 WORD  PNG  TXT  JPG

Tamaño: px
Comenzar la demostración a partir de la página:

Download "Programació Lògica :- ProLog."

Transcripción

1 Programació Lògica :- ProLog. Paradigmes i Llenguatges de Programació Grau en Informàtica - UdG Mateu Villaret

2 Guió Introducció Sintaxi Semàntica operacional del Prolog Llistes Aritmètica Arbre de cerca i tall

3 Introducció Prolog és un llenguatge de programació lògica que serveix per a validar fets en una teoria donada. L usuari defineix una base de dades de fets i regles i Prolog respon a les preguntes que es facin sobre la teoria. Surt dels camps del processat de llenguatge natural, de la demostració automàtica de teoremes en lògica de primer ordre i del problema de la planificació. Enlloc d escriure un algorisme per a resoldre un problema, podem especificar el problema en lògica de primer ordre i deixar que la màquina ens el resolgui...

4 Introducció Les especificacions de programes es poden descriure lògicament. Aquestes especificacions són independents de la màquina. Les regles de la lògica ens permeten demostrar la correctesa de les especificacions independentment de l existència dels programes. D altra banda existeixen mètodes per a poder fer gran part d aquestes demostracions automàticament. Així doncs, les especificacions i els programes són pràcticament el mateix... Eficiència i acabament Entrada/sortida

5 Exemple: Els Simpson Vegem un programa sobre els personatges dels Simpson. Tenim uns quants fets amb predicats unaris: nen(bart). home(abe). dona(marge). nen(milhouse). home(homer). dona(lisa). nen(lisa). home(bart). dona(maggie). nen(maggie). home(ned). dona(maude). nen(rod). home(rod). dona(mrs krabappel). nen(todd). home(todd). dona(ms hoover). nen(ralph). home(chief wiggum). dona(patty). home(ralph). dona(selma). home(milhouse). dona(jacqueline).... viu(homer, adr("evergreen Terrace", 742, "Springfield")). viu(ned, adr("evergreen Terrace", 744, "Springfield"))....

6 Exemple: Els Simpson Alguns fets amb relacions (o predicats) binaries: pare(abe, homer). pare(homer, bart). pare(homer, lisa). pare(homer, maggie). pare(ned, rod). pare(ned, todd). pare(chief wiggum, ralph). amic(bart, milhouse). amic(homer, ned). amic(marge, maude). mare(marge, bart). mare(marge, lisa). mare(marge, maggie). mare(jacqueline, marge). mare(jacqueline, patty). mare(jacqueline, selma). mare(maude, rod). mare(maude, todd). casat(homer, marge). casat(ned, maude). vei(ned, homer).

7 Exemple: Els Simpson Tenim les següents regles: X, Y. pare(x, Y ) progenitor(x, Y ) X, Y. ( mare(x, Y ) progenitor(x, Y ) ) X, Y, Z. progenitor(z, X ) progenitor(z, Y ) X Y germa(x, Y ) que en Prolog serien: progenitor(x,y):- pare(x,y). progenitor(x,y):- mare(x,y). germa(x,y):- progenitor(z,x), progenitor(z,y), X\=Y.

8 Exemple: Els Simpson SICStus (x86-win32-nt-4): Tue May 15 21:17:49 West 2007 Licensed to SP4ima.udg.edu?- :- consult( U:/paradigmes/els\_simpson.pl ). % consulting u:/paradigmes/els_simpson.pl... % consulted u:/paradigmes/els_simpson.pl... in module user, 0 ms?- nen(bart). yes?- pare(x,bart). X = homer? ; no?- germa(bart,x). X = lisa? ; X = maggie? ;...

9 Sintaxi Els Termes ens serviran per a referir-nos als objectes sobre els que definirem la teoria: persones, llocs, valors, etc. terme ::= variables simbol constant simbol funcio(termes) termes ::= terme terme, termes Les variables comencen amb majúscules i els símbols (funcions i constants) amb minúscules. Exemples de termes: adr("evergreen Terrace", 742, "Springfield"), homer, Algu, 742,...

10 Sintaxi Els predicats ens serviran per a establir fets i regles sobre els termes de la nostra teoria: atom ::= simbol proposicio simbol predicat(termes) Els símbols de proposició i predicats comencen amb minúscules. Exemples d atoms: viu(ned,adr("evergreen Terrace",744,"Springfield")), home(homer), germa(x,y),...

11 Sintaxi Els programes Prolog consten de: Fets, ens permeten assertar atoms a la teoria. fet ::= atom. Per exemple: home(homer)., amic(bart, milhouse).,... Regles, ens permeten assertar fórmules condicionals amb premises i una conclusió, a la teoria. regla ::= atom :- atoms. atoms ::= atom atoms, atom on :- representa el condicional ( ), i les comes les conjuncions ( ). Les variables estan quantificades universalment. Per exemple: germa(x,y):- progenitor(z,x), progenitor(z,y), X\=Y.

12 Sintaxi Les queries o objectius que preguntem a l intèrpret Prolog, són la conjunció d àtoms que volem demostrar o refutar segons la teoria carregada. query ::= atoms. En les queries, les variables estan quantificades existencialment. Es pregunta si existeix algun valor per a les variables que ens faci certa aquella conjunció d atoms d acord amb la teoria. Per exemple:?- germa(bart,x).?- home(ned). Si al donar-nos una resposta ens apareix un interrogant, tenim l opció de demanar que segueixi buscant altres solucions: ;. Les solucions són yes, amb assignacions de variables..., no, o esperar-se.

13 Exercicis d els Simpson Penseu com definirieu les relacions: avantpassat avi, avia oncle, tia

14 Semàntica operacional Q: germa(bart,lisa) per la regla de germà G: {progenitor(z,bart), progenitor(z,lisa), bart\=lisa} per regla progenitor {pare(z,bart), progenitor(z,lisa), bart \= lisa} pel fet pare(homer, bart) {progenitor(homer,lisa), bart \= lisa} per regla progenitor {pare(homer,lisa), bart \= lisa} pel fet pare(homer, lisa) {bart \= lisa} pel significat \= { } qed

15 Semàntica operacional Aquest exemple ens mostra una linea d execució però en realitat tenim un arbre. Cada vegada que tenim més d una opció de resoldre un objectiu, tenim una possible bifurcació. Si per alguna de les opcions (branques) triades quedem amb algun objectiu que no sabem resoldre, mirarem de recular backtracking per l arbre fins a trobar una alternativa que ens dongui opcions a resoldre tots els objectius. Si finalment hem explorat totes les branques i no hem pogut resoldre tots els objectius, és que la query no era demostrable. quan trobem una solució (hem resolt tots els objectius) i apretem ; li estem demanant a Prolog que faci backtracking i segueixi explorant l arbre.

16 Llistes Considerant ja predicats, els arguemnts dels predicats siguent termes qualsevols, n hi ha uns de molt especials, les llistes: Les llistes van sempre dins de: [ i ]. La llista buida és [ ] [X L], denota llistes amb X com a cap i L com a cua. [X,Y L], X i Y són els dos primers elements i L la cua. [X,Y,Z], denota una llista amb 3 elements. Per exemple:?- [1,2,3]=[X,Y L]. L=[3], X=1, Y=2?- [1,2,3]=[X,Y,Z L]. L=[], X=1, Y=2, Z=3?- [1,2,3]=[X,Y,Z,T]. no

17 Predicats bàsics sobre llistes (i) Alguns predicats clàssics: % member(x,l) => X apareix a la llista L. member(x,[x ]). member(x,[ XS]):-member(X,XS). Què ens respondrà Prolog a:?- member(x,[1,2,3]).?- member(1,x). I si canviem l ordre de les definicions dels predicats? % treu(x,l1,l2) => L2 es L1 sense X. treu(x,[],[]). treu(x,[x L1],L2):-treu(X,L1,L2). treu(x,[y L1],[Y L2]):-treu(X,L1,L2). Compte, que passa si demanem més solucions a?- treu(1, [1,2,1],L).

18 Predicats bàsics sobre llistes (ii) % append(l1,l2,l) => L es la concatenacio de L1 i L2. append([],ys,ys). append([x Xs],Ys,[X Zs]):-append(Xs,Ys,Zs). L append és molt útil, per exemple podem redefinir member i definir permutacio així: % member(x,l) => X apareix a la llista L. member(x,l):-append(,[x ],L). % permutacio(l1,l2) => L2 es una permutacio d L1. permutacio([],[]). permutacio(l,[x Xs]):- append(v,[x P],L), append(v,p,w), permutacio(w,xs).

19 Predicats bàsics sobre llistes (iii) Com veiem es poden fer molts predicats sobre llistes amb append. % invers(l,in) => In es la llista L girada. invers([],[]). invers([x Xs],In):-invers(Xs,Ps), append(ps,[x],in). % prefix(p,l) => P es un prefix de la llista L. prefix(p,l):- append(p,,l). % sufix(s,l) => S es un sufix de la llista L. sufix(s,l):- append(,s,l). % subllista(lp,l) => Lp es una subllista (elements % consecutius) de la llista L. subllista(lp,l) :-...

20 Aritmètica (i) Els nombres: 33, -2, i les expressions aritmètiques: 3+3, 33*3+1,... també són termes. Per tant:?- 4 = 2+2.?- X = 2+2. no X = 2+2 Per avaluar expressions aritmètiques s ha de fer servir el predicat predefinit is: % E1 is E2 => E1 unifica amb el valor aritmetic d E2, % E2 ha de ser avaluable aritmeticament.?- 4 is 2+2.?- X is 2+2. yes X = 4?- 2+2 is 4.?- 4 is X.?-4 is 2+X. no Inst. error. Inst. error.

21 Aritmètica (ii) Els predicats relacionals com <, =<, >, >=, =:= i =\= si que avaluen els dos costats (sempre que siguin avaluables):?- 2+2 =:= 9/2.?- 2+2 =:= 9//2. no yes?- 4 mod 2 >= 2+X.?- 2+2 =\= 3+1. Inst. error no Compte, els operadors = i == (i els seus negats \= i \==) signifiquen: % E1 = E2 => E1 unifica E2. % E1 == E2 => E1 i E2 son el mateix terme.?- 2+X=2+Y.?- 2+X == 2+Y. X=Y no

22 Aritmètica (iii) El predicat del Factorial % fact(+n,f) => F és el factorial del natural N. fact(0,1). fact(n,f):- N>0, Np is N-1, fact(np,f1), F is F1 * N. El predicat, no va en totes dues direccions ja que +N ha de ser un número degut a l us de is:?- fact(3,6).?- fact(3,f)?- fact(n,6). yes F=6 Int. error.

23 Llistes i aritmètica % llargada(l,n) => N es la llargada de L. llargada([],0). llargada([ Xs],N):- llargada(xs,np), N is Np+1. % conta(l,x,n) => N es quants cops apareix X a L. conta([],,0). conta([x Xs],X,N):- conta(xs,x,np), N is Np+1. conta([y Xs],X,N):- X\=Y, conta(xs,x,n). % nessim(l,n,x) => X ocorre a la posicio N de L. nessim([x ],0,X). nessim([ Xs],N,X):- N>0, Np is N-1, nessim(xs,np,x).

24 Ordenació % parteix(x,l,men,maj) => Men son els elements de L % menors que X, Maj els majors parteix(,[],[],[]). parteix(x,[y L],[Y Mn],Mj):- Y =< X, parteix(x,l,mn,mj). parteix(x,[y L],Mn,[Y Mj]):- Y > X, parteix(x,l,mn,mj). % quicksort(l1,l2) => L2 es la llista L1 ordenada. quicksort([],[]). quicksort([x Xs],L):- parteix(x,xs,men,maj), quicksort(men,menord), quicksort(maj,majord), append(menord,[x Majord],L).

25 Exemple de les torres de Hanoi El famós problema de les torres de Hanoi. % hanoi(n,a,b,c,m) => M son els moviments per passar % N discos de A a B usant C. hanoi(s(0),a,b,c,[de a (A, B)]). hanoi(s(n),a,b,c,mov):- hanoi(n,a,c,b,mov1), hanoi(n,c,b,a,mov2), append(mov1,[de a (A,B) Mov2],Mov).

26 L arbre de cerca Pel següent codi representare el corresponent arbre de cerca: q(x):- p(x). q(0). q(x) [X 0] p(x):-a(x),b(x). p(1). p(x) [X 1] X = 0 a(2). a(3). a(x),b(x) [X 2] [X 3] X = 1 b(2). b(2). b(3). X = 2 b(2) X = 2 b(3) X = 3 Les solucions s enumerarien d esquerra a dreta, és a dir: X = 2, X = 2, X = 3, X = 1, X = 0.

27 Control sobre l arbre de cerca L ordre de les clàusules i les repeticions de clàusules poden donar lloc a redundàncies en les respostes i en les fallades. ineficiència comportament no especificat És interesant coneixer l arbre de cerca i poder-lo controlar. Prolog ens proporcions un predicat anomenat tall:!, que serveix per a podar l arbre de cerca.

28 El tall! Donada una clàusula: A:- B 1,...,B k,!,b k+1,...,b n. tal que A unifica amb l objectiu G que es vol resoldre, i B 1,...,B k es satisfan, l efecte de! és: Qualsevol altra clàusula que es pogués aplicar per resoldre G és ignorada. Si a l intentar satisfer algun B i d entre B k+1,...,b n es fracassa, només es fa BACKTRAKING fins al tall. Si s arriba a haver de refer el tall, es torna fins a l elecció anterior de G i es fa BACKTRAKING a partir d allà.

29 L arbre de cerca i el tall Canviant lleugerament el codi anterior...les solucions són: X = 2, X = 2, X = 0. La part grisa s ha tallat! q(x):- p(x). q(0). p(x):-a(x),!, b(x). p(1). a(2). a(3). a(x),!,b(x) p(x) [X 2] [X 3]!,b(2)!,b(3) q(x) [X 1] X = 1 [X 0] X = 0 b(2). b(2). b(3). X = 2 b(2) X = 2 b(3) X = 3

30 Exemple amb el factorial i el tall % nums(x) => X és un número natural. Comenca per 0. nums(0). nums(x):- nums(xp), X is Xp+1. % trobaf(x,+y) => El factorial d X és més gran que Y. trobaf(x,y):- nums(x), fact(x,z), Z>Y. % fact(+n,f) => F és el factorial del natural N. fact(0,1). fact(0,1):-!. fact(n,f):- Np is N-1, fact(np,f1), F is F1 * N. fact(n,f):- Np is N-1, fact(np,f1), F is F1 * N. La query:?- trobaf(x,6). utilitzant el factorial de l esquerra es penjarà, mentre que usant el de la dreta no.

31 Exemple d ordenació i el tall % ordenada(l) => L es una llista ordenada creixent. ordenada([]). ordenada([x]). ordenada([x,y Zs]):- X=<Y, ordenada([y Zs]). % ordena(x,y) => Y es la llista X ordenada creixentment. ordena(xs,xs):- ordenada(xs),!. ordena(xs,ys):- append(as,[x,y Ns],Xs), X>Y,!, append(as,[y,x Ns],Xs1), ordena(xs1,ys). El primer tall ens diu d ordenació només n hi ha una, per tant no cal mirar si puc ordenar d una manera diferent. El segon tall ens diu, si trobes un parell d element desordenats, segur que s han d ordenar, per tant no cal que provis de deixar-los per més tard.

32 La negació La negació en ProLog és \+(P) on P és un predicat. Funciona segons la CWA, assumpció del mon tancat : el literal es satisfà quan no pot demostrar P (i acaba és clar). q(a). q(b):- q(a).?- \+(q(c)). yes?- \+(q(b)). no?- \+(q(x)). no

33 Termes, programar amb unificació Prolog no ens permet definir tipus nous. Per a usar altres tipus, hem de crear una definició del comportament dels termes: % arrela(n,a,b,t) => T es l arbre de node N, fe A i fd B. arrela(n, A1, A2, arbre(n, A1, A2)). % node(t,n) => N es l arrel de l arbre T. node( arbre(n,, ), N). % fe(t,te)/fd(t,td) => TE/TD es fill esquerra/dret de T. fe(arbre(,ae, ), AE). fd(arbre(,, AD), AD). % preordre(t,l) => L es el preordre de l arbre T. preordre(arbre(n, A1, A2),[N L]):- preordre(a1,l1), preordre(a2,l2), append(l1,l2,l). preordre(abuit,[]).

34 Exemple d entrada/sortida, tall i aritmètica. % repeat => un predicat que es satisfa sempre. repeat. repeat:- repeat. % llegeix(x) => X es un numero entrat per teclat. llegeix(x):- repeat, write(numeret), read(x), number(x),!. % tracta(x) => Si X es 0 es satisfa i talla, % si no, en calcula el quadrat, el mostra i falla. tracta(0):-!. tracta(x):- R is X*X, writeln([x, ^ 2=, R]), fail. % quadrats => Llegeix enters i en mostra el quadrat % fins que s entra un 0. quadrats:- repeat, llegeix(x), tracta(x),!.