Prolog
description
Transcript of Prolog
![Page 1: Prolog](https://reader035.fdocumento.com/reader035/viewer/2022062807/5681502a550346895dbe19e8/html5/thumbnails/1.jpg)
1
Un programa Prolog està format per un conjunt de fòrmules LP1 (claúsules de Horn) que representa un conjunt d’objectes i de relacions entre aquests objectes.
Fets : Regles : plou. mortal(X):-home(X). home(plato). avi(X,Y):-pare(X,Z),pare(Z,Y). pare(joan,pere). avi(X,joan).
Prolog
![Page 2: Prolog](https://reader035.fdocumento.com/reader035/viewer/2022062807/5681502a550346895dbe19e8/html5/thumbnails/2.jpg)
2
Un programa de càlcul de relacions de parentesc en prolog
anna
pere
joan
marc laura
maria
Imma xavi
![Page 3: Prolog](https://reader035.fdocumento.com/reader035/viewer/2022062807/5681502a550346895dbe19e8/html5/thumbnails/3.jpg)
3
home(joan).home(pere).home(marc).home(xavi).dona(anna).dona(maria).dona(laura).dona(imma).matrimoni(joan,anna).matrimoni(marc,laura).pro(joan,pere).pro(anna,pere).pro(joan,marc).pro(anna,marc).pro(maria,laura).pro(pere,imma).pro(marc,xavi).pro(laura,xavi).
pare(X,Y):-home(X),pro(X,Y).avi(X,Y):-pare(X,Z),pro(Z,Y).
avi(joan,Q).
pare(joan,Z)pro(Z,Y)
home(joan)pro(joan,Y’)pro(Y’,Y)
pro(joan,Y’)pro(Y’,Y)
pro(pere,Y)pro(marc,Y)
joan/X Q/Y
joan/X Z/Y’
Y’/pere
Y/immaY/xavi
![Page 4: Prolog](https://reader035.fdocumento.com/reader035/viewer/2022062807/5681502a550346895dbe19e8/html5/thumbnails/4.jpg)
4
home(joan).home(pere).home(marc).home(xavi).dona(anna).dona(maria).dona(laura).dona(imma).matrimoni(joan,anna).matrimoni(marc,laura).pro(joan,pere).pro(anna,pere).pro(joan,marc).pro(anna,marc).pro(maria,laura)./*pro(pere,imma).*/pro(marc,xavi).pro(laura,xavi).
pare(X,Y):-home(X),pro(X,Y).avi(X,Y):-pare(X,Z),pro(Z,Y).
avi(joan,Q).
pare(joan,Z)pro(Z,Y)
home(joan)pro(joan,Y’)pro(Y’,Y)
pro(joan,Y’)pro(Y’,Y)
pro(pere,Y)pro(marc,Y)
joan/X Q/Y
joan/X Z/Y’
Y’/pere
Y/xavi
FAIL
![Page 5: Prolog](https://reader035.fdocumento.com/reader035/viewer/2022062807/5681502a550346895dbe19e8/html5/thumbnails/5.jpg)
5
Termes
SimplesCompos-
tos
constants variables
àtoms nombres
àtoms : constants textuals. joan x23 ‘Johnnie Walker’
nombres : Reals o sencers -37 2.023E-14
variables : Comencen per una majúscula o un símbol ‘_’ X23 Joan _114
Sintaxi : Termes
![Page 6: Prolog](https://reader035.fdocumento.com/reader035/viewer/2022062807/5681502a550346895dbe19e8/html5/thumbnails/6.jpg)
6
Termes compostos: Formats per un nom de predicat (àtom) i una seqüència d’arguments, entre parèntesis i separats per comes. Aquests arguments són, a la seva vegada, termes.
pare(joan,jordi).persona(nom(joan,canals),edat(30).dom(carrer(nord),num(22))).
Sintaxi : Termes (II)
Exemple: Gestió d’una biblioteca. Tindrem dues classes de termes compostos o estructures:llibre(ref(11540), autor(‘Gabriel García Márquez’),titol(’100 años de soledad’),ed(anaya,any(1993))).
lector(id(202),nom(‘Pere Sala Güell’),dom(carrer(orient), num(1),mun(girona),tlf(972205674))).
prestec(llibre(11540), lector(202),dataini(2,11,2001), datafi(2,1,2002),tornat(no)).
Podem preguntar el telèfon de tots els lectors de Gabriel García Márquez que viuen al carrer Jaume I de Girona
![Page 7: Prolog](https://reader035.fdocumento.com/reader035/viewer/2022062807/5681502a550346895dbe19e8/html5/thumbnails/7.jpg)
7
r1 r2 r1+ r2
r_eq(X,X):-number(X).r_eq(s(X,Y),R):-r_eq(X,R1),r_eq(Y,R2),R is R1+R2.r_eq(p(X,Y),R):-r_eq(X,R1),r_eq(Y,R2),R is (R1*R2)/(R1+R2).
r2
r1(r1* r2) / (r1+ r2)
7
39
5
2
?- r_eq(s(p(s(p(7,3),9),3),2),R).
![Page 8: Prolog](https://reader035.fdocumento.com/reader035/viewer/2022062807/5681502a550346895dbe19e8/html5/thumbnails/8.jpg)
8
Unificació : Variables instanciades, lliures i lligades
Una variable és lliure quan no està instanciada.Una variable queda instanciada quan pren un valor :
?- major_dedat(Z)
persona(joan,23).persona(maria,19).major_dedat(X):-persona(X,Y),Y>=18.
persona(X,Y),Y>=18
23>=18
Z/X
X/joan , Y/23
Aquí Z està lliure
Aquí Z i X queden lligades
Aquí X i Y són lliures
Aquí s’instancien X, Y i Z
Z=joan
![Page 9: Prolog](https://reader035.fdocumento.com/reader035/viewer/2022062807/5681502a550346895dbe19e8/html5/thumbnails/9.jpg)
9
Unificació : Substitucions
Una substitució és un conjunt de parells X/T on X és una variable i T es un terme prolog qualsevol.
Per exemple : S = {X/pere, Y/p(Z,q(32)), K/T}
Les substitucions es poden aplicar als termes prolog.
Per exemple :
Sigui Q = r(X,Y,p(K)) llavors:
QS = r(pere, p(Z,q(32)), p(T))
![Page 10: Prolog](https://reader035.fdocumento.com/reader035/viewer/2022062807/5681502a550346895dbe19e8/html5/thumbnails/10.jpg)
10
Unificació : Definició
Donats dos termes prolog T1 i T2, una substitució S tal que T1S = T2S. es diu un unificador de T1 i T2
Donats dos termes prolog T1 i T2, unificar-los consisteix en trobar l’unificador més general tal que T1S = T2S.
Per exemple :
T1 és p(X) T2 és p(Y)
S={X/1, Y/1} és un unificador de T1 i T2,però S’={X/Y}és més general
Unificador més general (m.g.u.) de T1 i T2 : És l’unificador deT1 i T2 que té el mínim nombre de variables instanciades
![Page 11: Prolog](https://reader035.fdocumento.com/reader035/viewer/2022062807/5681502a550346895dbe19e8/html5/thumbnails/11.jpg)
11
Algorisme d’unificació.
Dos termes S i T s’unifiquen segons les següents regles:
a) Si S i T són constants o variables instanciades com a constants, s’unifiquen si i només si tenen el mateix valor.
b) Si S i T són variables lliures, s’unifiquen i queden lligades.c) Si S és una variable lliure i T un terme qualsevol, s’unifiquen
i S queda instanciada com a T.
d) Si S i T són estructures s’unifiquen només si• S i T tenen el mateix functor principal, (Defineixen el mateix
predicar), i el mateix nombre d’arguments.• Els arguments corresponent s’unifiquen dos a dos.
![Page 12: Prolog](https://reader035.fdocumento.com/reader035/viewer/2022062807/5681502a550346895dbe19e8/html5/thumbnails/12.jpg)
12
Unificació. Exemples
El símbol ‘ = ‘ és l’operador d’unificació. Donats dos termes T1 i T2 T1 = T2 és veritat si i només si T1 i T2 es poden unificar.
?- data(dia(2),X,any(Z))=data(Y,Z,any(99)).?- data(dia(X),mes(2),Z)=data(dia(3),mes(X),any(T)).?- data(dia(X),mes(2),any(Z))=data(Z,mes(X),T).?- X=2+3.?- X=p(X).
Exercici: Suposem que representem un punt (x,y) al pla com p(x,y) i un segment del punt p1 al p2 com s(p1,p2). Definir relacions per determinar quan un segment és vertical i quan tres segments formen un triangle.
![Page 13: Prolog](https://reader035.fdocumento.com/reader035/viewer/2022062807/5681502a550346895dbe19e8/html5/thumbnails/13.jpg)
13
Exemple : el mico i el plàtan
porta
finestra
caixa
plàtan
mico
Hi ha un mico a la porta d’una habitació. Hi ha un plàtan penjant del sostre i una caixa al costat de la finestra. El mico ha de trobar una seqüència d’accions que li permetin menjar-se el plàtan.
El mico pot fer quatre accions diferents : caminar a qualsevol punt de la cambra, pujar-se a la caixa, arrossegar la caixa i agafar el plàtan.
![Page 14: Prolog](https://reader035.fdocumento.com/reader035/viewer/2022062807/5681502a550346895dbe19e8/html5/thumbnails/14.jpg)
14
mov(estat(mig,asobre,mig,no),estat(mig,asobre,mig,si)).
mov(estat(P,aterra,P,T),estat(P,asobre,P,T)).
mov(estat(P,aterra,P,T),estat(P2,aterra,P2,T)).
mov(estat(P,aterra,PC,T),estat(P2,aterra,PC,T)).
pot_menjar(estat(_,_,_,si)).
pot_menjar(E):-mov(E,E2), pot_menjar(E2).
El mico i el plàtan (II).
Programa prolog que resol el problema del mico i el plàtan.Si ordenéssim les clàusules que defineixen els moviments de manera diferent, no funcionaria.
![Page 15: Prolog](https://reader035.fdocumento.com/reader035/viewer/2022062807/5681502a550346895dbe19e8/html5/thumbnails/15.jpg)
15
Operadors en prolog
Siguin T1 i T2 termes. Podem distingir diferents tipus d’operadors:
Operadors d’unificació :• T1= T2 sii T1 i T2 es poden unificar• T1\= T2 sii T1 i T2 no es poden unificar
Operadors aritmètics : + , - , * , / , // , mod.
L’operador is. Serveix per a forçar l’avaluació de les expressions aritmètiques. T1 is T2 és cert sii el resultat d’avaluar T2 es pot unificar amb T1.
Exemples : X is 2+3. 8 is 7+1. X=2+2,Y is 2*X SI
X is joan - 3. 5 is 2+2. X=4,X is 3*2. X is 2*Y NO
![Page 16: Prolog](https://reader035.fdocumento.com/reader035/viewer/2022062807/5681502a550346895dbe19e8/html5/thumbnails/16.jpg)
16
Operadors en prolog (II)
Operadors de comparació :
Siguin T1 i T2 termes.
T1 > (<) T2 sii el resultat d’avaluar T1 es major (menor) que el resultat d’avaluar T2.T1 >= (=<) T2 sii el resultat d’avaluar T1 es major (menor) o
igual que el resultat d’avaluar T2.
T1=:= (=\=) T2 sii el resultat d’avaluar T1 igual que el resultat d’avaluar T2.
T1== (\==) T2 sii T1 i T2 són (no són) exactament el mateix terme
![Page 17: Prolog](https://reader035.fdocumento.com/reader035/viewer/2022062807/5681502a550346895dbe19e8/html5/thumbnails/17.jpg)
17
Exemple.
/* pais(Nom, Població, Superfície) */
país(albania, 3000. 250).pais(alemania,80000 , 1000).pais(andorra,100 , 0.4).
mes_gran(X,Y):-pais(X,_,S1),pais(Y,_,S2), S1>S2.densitat(Pais,D):- pais(Pais,P,S), D is P/S.
![Page 18: Prolog](https://reader035.fdocumento.com/reader035/viewer/2022062807/5681502a550346895dbe19e8/html5/thumbnails/18.jpg)
18
Operadors en prolog (III). Precedències
:- op( 1200 , xfx , ’:-’ ).
:- op( 1200 , fx , [:-,?-]). :- op( 1100 , xfy , ’;’ ). :- op( 1000 , xfy , ’,’ ). :- op( 700 , xfx , [ = , is , < , > , =< , .>= , == , =\= , =:= ,\== ]). :- op( 500 , yfx , [ + , - ] ). :- op( 500 , fx , [ + , - , not ] ). :- op( 400 , yfx , [ * , / , div ] ). :- op( 300 , xfx , mod ).
El conjunt dels operadors predefinits en prolog, juntament amb les seves precedències i associativitats:
![Page 19: Prolog](https://reader035.fdocumento.com/reader035/viewer/2022062807/5681502a550346895dbe19e8/html5/thumbnails/19.jpg)
19
Operadors definits per l’usuari
:- op(900,xfx,te).:- op(890,xfy,i).:- op(900,xfx,es_troba_a).
joan te cotxe i moto i bici.pere te bici.anna te moto i vaixell.
X te Y :- X te Z, Y es_troba_a Z.
X es_troba_a X.X es_troba_a X i _.X es_troba_a Y i R :- X es_troba_a R.
Exemple
![Page 20: Prolog](https://reader035.fdocumento.com/reader035/viewer/2022062807/5681502a550346895dbe19e8/html5/thumbnails/20.jpg)
20
El “cut” ( ! )
Aquest operador predefinit es fa servir per a limitar el backtracking. Quan el prolog intenta fer servir un fet o regla per a demostrar un objectiu (goal), posa un punt de backtracking a aquest fet o regla per poder triar noves alternatives de demostració. Si en aquest procés de demostració el prolog troba un cut a la part dreta d’una regla, esborra tots els punts de backtracking establerts des del moment que s’ha intentat fer servir la regla que conté el cut per demostrar l’objectiu actual.
![Page 21: Prolog](https://reader035.fdocumento.com/reader035/viewer/2022062807/5681502a550346895dbe19e8/html5/thumbnails/21.jpg)
21
El “cut” ( ! )
p:-q,r,s.p:-t.q.r:-y.r:-x.x.t.
p:-q,r,!,s.p:-t.q.r:-y.r:-x.x.t.
tsrqp )( trqsrqp )()(
![Page 22: Prolog](https://reader035.fdocumento.com/reader035/viewer/2022062807/5681502a550346895dbe19e8/html5/thumbnails/22.jpg)
22
El “cut” ( ! )
max(X,Y,X):-X>=Y.max(X,Y,Y):-X<Y.
max(X,Y,X):-X>=Y,!.max(X,Y,Y).
x
x
x
xf
4 si 5
40 si 3
0 si 0
)(f(X,0):-X<=0.f(X,3):-0<X=<4.F(X,5):-4<X.
f(X,0):-X<=0,!.f(X,3):-X=<4,!.F(X,5).
member(X,[X|_]):-!.member(X,[_|R]):- member(X,R).
esborrar(X,[X|R],R):-!.esborrar(X, [Y|R], [Y|R2]):- esborrar(X,R,R2).
![Page 23: Prolog](https://reader035.fdocumento.com/reader035/viewer/2022062807/5681502a550346895dbe19e8/html5/thumbnails/23.jpg)
23
Els predicats predefinits fail i not
fail : el predicat fail mai es pot demostrar. Es fa servir sobre tot per forçar al prolog a fer backtracking. També existeix el predicat true.
Exemple : dues formes de definir un predicat per escriure per pantalla els elements d’una llista :
escriure([]).escriure([X|R]):-write(X), escriure(R).
escriure(L):-member(X,L), write(X),
fail.escriure(_).
![Page 24: Prolog](https://reader035.fdocumento.com/reader035/viewer/2022062807/5681502a550346895dbe19e8/html5/thumbnails/24.jpg)
24
Els predicats predefinits fail i not
not , \+ : Negation as failure. not p (\+ p) és cert si i només si p no es pot demostrar.
Exemple : not 4=3. not member(1,[2,3]). Cert not member(X,[2,3]). Fals
Es defineix així :
not P :- P,!,fail; true.
![Page 25: Prolog](https://reader035.fdocumento.com/reader035/viewer/2022062807/5681502a550346895dbe19e8/html5/thumbnails/25.jpg)
25
Entrada i Sortida en Prolog
En prolog hi ha en tot moment un canal (stream) actual de sortida i un canal actual d’entrada. Tota la sortida es fa al canal actual de sortida i tota l’entrada es fa desde el canal actual d’entrada. Per defecte tots dos canals són la consola del prolog (user).
Programa prolog
WVM
Input Stream Output Stream
![Page 26: Prolog](https://reader035.fdocumento.com/reader035/viewer/2022062807/5681502a550346895dbe19e8/html5/thumbnails/26.jpg)
26
Predicats E/S en Prolog.
Maneig dels canals
see(nomfitxer).tell(nomfitxer).seen.told.seeing(NomFitxer).telling(Nomfitxer).
![Page 27: Prolog](https://reader035.fdocumento.com/reader035/viewer/2022062807/5681502a550346895dbe19e8/html5/thumbnails/27.jpg)
27
Predicats E/S en Prolog.
Lectura i Escriptura
get0(CodiCaracter).get(CodiCaracter). Caracters imprimibles. eof=-1
put(CodiCaracter).write(Terme).read(Terme). end_of_file
![Page 28: Prolog](https://reader035.fdocumento.com/reader035/viewer/2022062807/5681502a550346895dbe19e8/html5/thumbnails/28.jpg)
28
Exemple. Processament d’un fitxer de notes.
aprovats:-see('alumnes.txt'),tell('aprovats.txt'),repeat,read(T),processar(T).
processar(end_of_file):-!, seen, told.processar(alumne(Nom,Nota)):-Nota>=5,
write(aprovat(Nom,Nota)), write('.'),nl, fail.
![Page 29: Prolog](https://reader035.fdocumento.com/reader035/viewer/2022062807/5681502a550346895dbe19e8/html5/thumbnails/29.jpg)
29
Exemple. Treure els espais en blanc de sobres.
blancs:-see('entrada.txt'),tell('sortida.txt'),get0(C),fora_blancs(C).
fora_blancs(-1):-!, seen, told.fora_blancs(C):-!, put(C),
(C=32->get(C2);get0(C2)), fora_blancs(C2).
![Page 30: Prolog](https://reader035.fdocumento.com/reader035/viewer/2022062807/5681502a550346895dbe19e8/html5/thumbnails/30.jpg)
30
Modificació dinàmica de programes en Prolog
assert(Term).assertz(Term).asserta(Term).retract(Term).retractall(Term).consult(nomfitxer).reconsult(nomfitxer).