limbaj prolog

29
Limbaj Prolog Prelegerea 1 Pastramă Emil 1 PROLOG Prolog reprezintă o prescurtare de la “Programming în logic”. Este un limbaj conceput pentru programarea logică (deci un limbaj declarativ). A fost elaborat în cursul anilor 1970 în Europa (mai ales în Franţa şi Scoţia). Primul compilator de Prolog a fost creat în 1972 de către Philippe Roussel, la Universitatea din Marsilia. Prologul este un limbaj compilat, care utilizează, în locul relaţiilor matematice, relaţii logice între mulţimi de date. Exista limbaje algoritmice, orientate obiect si logice. Limbajele programării logice (Prolog) sunt limbaje declarative. Un limbaj de programare declarativ scuteşte programatorul de a mai menţiona procedura exactă pe care trebuie să o execute calculatorul pentru a realiza o funcţie. Programatorii folosesc limbajul pentru a descrie o mulţime de fapte şi de relaţii astfel încât utilizatorul să poată interoga apoi sistemul pentru a obţine un anumit rezultat. - Programele Prolog opereaza cu obiecte si cu relatii intre obiecte (fapte si/sau clauze). - Negatia joaca un rol foarte important in programarea in acest limbaj, deoarece orice proprietate care nu se poate deduce din entitatile programului este considerata falsa, deci negatia ei este adevarata. - Prolog foloseste un model de rationament minimal numit ipoteza lumii inchise . Conform acestui model, tot ceea ce nu este stiut de program, deci afirmat explicit ca fiind adevarat in program, este considerat fals. - Prologul modeleaza negatia ca esec al satisfacerii unui scop (negatia ca insucces), aceasta fiind de fapt o particularizare a ipotezei lumii inchise. O clauza Prolog sau regula este de forma: H :- B1, B2, … , Bn. unde: H este capul regulii , iar membrul drept constituie corpul regulii (care este o conjunctie sau o disjunctie de scopuri ). Sensul clauzei Prolog anterioare este:

Upload: pastrama-emil

Post on 10-Jun-2015

4.565 views

Category:

Documents


6 download

TRANSCRIPT

Page 1: Limbaj Prolog

Limbaj Prolog – Prelegerea 1 Pastramă Emil 1

PROLOG

Prolog reprezintă o prescurtare de la “Programming în logic”.

Este un limbaj conceput pentru programarea logică (deci un limbaj declarativ).

A fost elaborat în cursul anilor 1970 în Europa (mai ales în Franţa şi Scoţia).

Primul compilator de Prolog a fost creat în 1972 de către Philippe Roussel, la

Universitatea din Marsilia.

Prologul este un limbaj compilat, care utilizează, în locul relaţiilor matematice,

relaţii logice între mulţimi de date.

Exista limbaje algoritmice, orientate obiect si logice.

Limbajele programării logice (Prolog) sunt limbaje declarative. Un limbaj de

programare declarativ scuteşte programatorul de a mai menţiona procedura exactă

pe care trebuie să o execute calculatorul pentru a realiza o funcţie. Programatorii

folosesc limbajul pentru a descrie o mulţime de fapte şi de relaţii astfel încât

utilizatorul să poată interoga apoi sistemul pentru a obţine un anumit rezultat.

- Programele Prolog opereaza cu obiecte si cu relatii intre obiecte (fapte si/sau

clauze).

- Negatia joaca un rol foarte important in programarea in acest limbaj, deoarece

orice proprietate care nu se poate deduce din entitatile programului este

considerata falsa, deci negatia ei este adevarata.

- Prolog foloseste un model de rationament minimal numit ipoteza lumii inchise.

Conform acestui model, tot ceea ce nu este stiut de program, deci afirmat explicit

ca fiind adevarat in program, este considerat fals.

- Prologul modeleaza negatia ca esec al satisfacerii unui scop (negatia ca

insucces), aceasta fiind de fapt o particularizare a ipotezei lumii inchise.

O clauza Prolog sau regula este de forma:

H :- B1, B2, … , Bn.

unde: H este capul regulii, iar membrul drept constituie corpul regulii (care este o

conjunctie sau o disjunctie de scopuri).

Sensul clauzei Prolog anterioare este:

Page 2: Limbaj Prolog

Limbaj Prolog – Prelegerea 1 Pastramă Emil 2

If B1 & B2 & … & Bn then H

In Prolog constantele se scriu cu litera mica, iar variabilele cu litera

mare.

Simbol…………………………..Sens

:- daca

, conjunctie

; disjunctie

_ variabila universala

(semnifica orice)

O fapta Prolog este o clauza fara corp, adica de forma H. Ea reprezinta

o clauza care este tot timpul adevarata, deoarece nu este conditionata.

Structura unui program Prolog:

definitii constante

tipuri de obiecte definite de utilizator

declaratiile predicatelor

reguli

Un program Prolog contine urmatoarele entitati:

fapte despre obiecte si relatiile existente intre aceste obiecte;

reguli despre obiecte si relatiile dintre ele, care permit deducerea

(inferarea) de noi fapte pe baza celor cunoscute;

intrebari, numite si scopuri, despre obiecte si relatiile dintre ele, la care

programul raspunde pe baza faptelor si regulilor existente.

Baza de cunostinte Prolog:

Multimea faptelor unui program Prolog formeaza baza de cunostinte Prolog. In

baza de cunostinte a unui program Prolog sunt incluse si regulile Prolog.

Scopuri:

Scopurile sunt predicate pentru care se doreste aflarea valorii de adevar, in

contextul faptelor existente in baza de cunostinte.

Page 3: Limbaj Prolog

Limbaj Prolog – Prelegerea 1 Pastramă Emil 3

Rezultatul unui program Prolog:

Obtinerea consecintelor sau a rezultatului unui program Prolog se face prin

fixarea unor scopuri care pot fi adevarate sau false, in functie de continutul bazei

de cunostinte. Cum scopurile pot fi vazute ca intrebari, rezultatul unui program

Prolog este raspunsul la o intrebare sau la o conjunctie de intrebari.

O regula Prolog exprima un fapt care depinde de alte fapte si este de forma

S :- S1, S2, … , Sn.

cu S reprezentand capul sau antetul regulii, iar membrul drept reprezentand corpul

regulii.

Constantele se mai numesc atomi simbolici si denumirile lor incep cu litera mica.

Numele de variabile incep cu litera mare; o variabila poate fi instantiata sau

legata daca exista un obiect asociat acestei variabile sau neinstantiata, respectiv

nelegata, respectiv libera daca nu se stie inca ce obiect va desemna variabila.

La fixarea unui scop Prolog care contine variabile, acestea sunt neinstantiate, iar

sistemul incearca satisfacerea acestui scop cautand printre faptele din baza de cunostinte

un fapt care poate identifica cu scopul, printr-o instantiere adecvata a variabilelor din

scopul dat. Este vorba de fapt de un proces de unificare a predicatului scop cu unul din

predicatele fapte existente in baza de cunostinte. La incercarea de satisfacere a scopului,

cautarea se face intotdeauna pornind de la inceputul bazei de cunostinte. Exista atatea

solutii cate unificari diferite exista. Obtinerea primei solutii este numita satisfacerea

scopului, iar obtinerea altor solutii resatisfacerea scopului. La satisfacerea unui scop

cautarea se face intotdeauna de la inceputul bazei de cunostinte. La resatisfacerea unui

scop cautarea se face incepand de la marcajul stabilit de satisfacerea anterioara a acelui

scop.

Obtinerea solutiilor atunci cand baza de cunostinte Prolog contine si reguli:

In acest caz, unificarea scopului se incearca atat cu fapte din baza de cunostinte,

cat si cu antetul regulilor din baza.

La unificarea unui scop cu antetul unei reguli, pentru a putea satisface acest scop

trebuie satisfacuta regula. Aceasta revine la a satisface toate faptele din corpul regulii,

Page 4: Limbaj Prolog

Limbaj Prolog – Prelegerea 1 Pastramă Emil 4

deci conjunctia de scopuri. Scopurile din corpul regulii devin subscopuri a caror

satisfacere se va incerca printr-un mecanism similar cu cel al satisfacerii scopului initial.

Comportarea sistemului Prolog in care se incearca in mod repetat satisfacerea si

resatisfacerea scopurilor din conjunctia de scopuri se numeste backtracking.

Un exemplu de program Prolog (definirea unor relatii de familie):

- faptul ca Tom este parinte al lui Bob se poate scrie in Prolog astfel:

parinte(tom, bob).

Aici parinte este numele relatiei, iar tom si bob sunt argumentele sale.

Program Prolog care defineste relatii de familie:

parinte(pam, bob).

parinte(tom, bob).

parinte(tom, liz).

parinte(bob, ann).

parinte(bob, pat).

parinte(pat, jim).

Programul consta din 6 clauze. Fiecare dintre aceste clauze declara un fapt despre

relatia parinte. Spre exemplu, parinte(tom, bob) este o instantiere particulara a relatiei

parinte. In general, o relatie se defineste ca fiind multimea tuturor instantierilor sale.

Obs.: Acest program simplu nu contine (inca) regului (ci doar fapte).

Interogarea Prologului:

Ex.: Vrem sa aflam daca Bob este parinte al lui Pat. Aceasta intrebare este comunicata

sistemului Prolog tastandu-se la terminal:

?- parinte(bob, pat).

Raspunsul Prologului va fi

yes

Alte exemple de interogari:

?-parinte(liz, pat).

no

Page 5: Limbaj Prolog

Limbaj Prolog – Prelegerea 1 Pastramă Emil 5

?-parinte (tom, ben).

no

Cine este parintele lui Liz?

?-parinte(X, liz).

X = tom

Cine sunt copiii lui Bob?

?-parinte (bob, X).

X = ann;

X= pat;

no

Cine este parinte al cui?

?-parinte(X, Y).

X = pam

Y = bob;

X = tom

Y = bob;

X = tom

Y = liz;

Cine este un bunic al lui Jim? i.e.

(1) Cine este parinte al lui Jim? Presupunem ca acesta este un Y.

(2) Cine este parinte al lui Y? Presupunem ca acesta este un X.

(1) si (2) necesita urmatoarea interogare compusa:

?- parinte(Y, jim), parinte(X, Y).

Page 6: Limbaj Prolog

Limbaj Prolog – Prelegerea 1 Pastramă Emil 6

Raspunsul Prologului este:

X = bob

Y = pat

Obs.: Interogarea

?- parinte(X, Y), parinte(Y, jim).

va produce acelasi rezultat.

Cine sunt nepotii lui Tom?

?- parinte(tom, X), parinte (X, Y).

X = bob

Y = ann;

X = bob

Y = pat

Ann si Pat au un parinte comun?

?-parinte(X, ann), parinte(X, pat).

X = bob

Extinderea programului cu reguli:

Introducem, mai intai, urmatoarele fapte noi:

feminin(pam).

masculin(tom).

masculin(bob).

feminin(liz).

feminin(pat).

feminin(ann).

masculin(jim).

si

sex(pam, feminin).

sex(tom, masculin).

Page 7: Limbaj Prolog

Limbaj Prolog – Prelegerea 1 Pastramă Emil 7

sex(bob, masculin).

si

urmas(liz, tom).

Obs.: Relatia urmas poate fi definita intr-un mod mult mai elegant prin folosirea

relatiei deja definite parinte.

Pentru toti X si toti Y,

Y este urmas al lui X daca

X este parinte al lui Y.

Aceasta interpretare genereaza o clauza Prolog reprezentata de urmatoarea regula:

urmas(Y, X) :- parinte(X, Y).

Interogarea Prologului cand baza de cunostinte contine si aceasta regula:

?- urmas(liz, tom).

Cum lucreaza Prologul acum: Intrucat nu exista fapte referitoare la urmasi, trebuie

folosita regula, astfel: variabilele X si Y vor fi instantiate in felul urmator

X = tom si Y = liz

Continuare:

- Dupa instantiere se obtine un caz particular al regulii generale. Acest caz

particular este:

urmas(liz, tom) :- parinte(tom, liz).

- Corpul regulii reprezinta partea de conditie, iar antetul ei partea de concluzie.

Prolog incearca sa determine daca partea de conditie este adevarata i.e. daca

parinte(tom, liz) este adevarat. In acest moment, scopul initial, urmas(liz,tom), a

fost inlocuit cu subscopul parinte(tom, liz).

- Noul scop este imediat satisfacut intrucat el reprezinta o fapta Prolog (din baza de

cunostinte).

- Aceasta inseamna ca partea de concluzie este, de asemenea, adevarata, iar Prolog

va raspunde la intrebare cu yes.

Page 8: Limbaj Prolog

Limbaj Prolog – Prelegerea 2 Pastramă Emil 1

Introducem acum relatii de familie suplimentare:

relatia mama, definita astfel:

mama (X, Y) :- parinte (X,Y), feminin (X).

relatia bunic, definita astfel:

bunic (X, Z) :- parinte (X, Y), parinte(Y, Z).

relatia sora, definita astfel:

sora (X, Y) :-

parinte (Z, X),

parinte (Z, Y),

feminin (X).

Interogarea Prologului:

daca ann si pat sunt surori

?- sora (ann, pat).

yes

cine este sora lui Pat

?- sora (X, pat).

X = ann;

X = pat

Obs.: Relatia sora ar trebui sa fie definita dupa cum urmeaza

sora (X, Y) :-

parinte (Z, X),

parinte (Z, Y),

feminin (X),

diferit (X, Y).

unde predicatul diferit (X,Y) trebuie definit astfel incat el sa fie satisfacut daca si numai

daca X e diferit de Y.

Reguli recursive

relatia predecesor: un predecesor poate fi direct (parinte)

predecesor (X, Z) :- parinte (X, Z).

Page 9: Limbaj Prolog

Limbaj Prolog – Prelegerea 2 Pastramă Emil 2

sau indirect

predecesor (X, Z) :-

parinte (X, Y),

parinte (Y, Z).

predecesor (X, Z):-

parinte (X, Y1),

parinte (Y1, Y2),

parinte(Y2, Z).

OBS.: Pentru ca relatia predecesor sa lucreze corect in cazul predecesorilor aflati la orice

adancime, definitia ei trebuie gandita in felul urmator:

Pentru toti X si Z,

X este predecesor al lui Z daca

Exista un Y astfel incat

(1) X este parinte al lui Y si

(2) Y este un predecesor al lui Z.

Clauza Prolog corespunzatoare (recursiva) este:

Predecesor (X,Z) :-

parinte (X,Y),

predecesor (Y,Z).

Definirea relatiei predecesor:

- consta din doua reguli, una care se refera la predecesori directi si cealalta la

predecesori indirecti. Definitia completa este urmatoarea:

predecesor (X, Z) :-

parinte (X,Z).

predecesor (X, Z) :-

parinte (X, Y),

predecesor (Y, Z).

Exemplu de interogare a Prologului (care sunt succesorii lui Pam):

?- predecesor (pam, X).

X = bob;

X = ann;

X = pat;

X = jim

Page 10: Limbaj Prolog

Limbaj Prolog – Prelegerea 2 Pastramă Emil 3

Semnificatia declarativa si procedurala a programelor Prolog

Semnificatia declarativa a unui program Prolog se refera la interpretarea strict

logica a clauzelor acelui program, rezultatul programului fiind reprezentat de toate

consecintele logice ale acestuia. Semnificatia declarativa determina daca un scop este

adevarat (poate fi satisfacut) si, in acest caz, pentru ce instante de variabile este adevarat

scopul.

Semnificatia procedurala a unui program Prolog se refera la modul in care

sistemul incearca satisfacerea scopurilor, deci la strategia de control utilizata.

Diferenta dintre semnificatia declarativa si cea procedurala este aceea ca cea de-a

doua defineste, pe langa relatiile logice specificate de program, si ordinea de satisfacere

a scopurilor si subscopurilor.

OBS.1: Datorita semnificatiei procedurale a limbajului Prolog, trebuie urmarit cu

atentie modul de definire a unui predicat, atat din punctul de vedere al ordinii clauzelor,

cat si din punctul de vedere al ordinii scopurilor in corpul regulilor.

OBS. 2: Ceea ce este neobisnuit in raport cu alte limbaje de programare este

faptul ca semnificatia declarativa a programului este corecta, indiferent de ordonarea

clauzelor, in timp ce programul este procedural incorect, avand comportari diferite in

functie de aceasta ordonare.

Satisfacerea clauzelor in Prolog (Backtracking)

Presupunem ca programul nu contine reguli, ci numai fapte

Presupunem ca avem un program ce contine si reguli

1. Programul nu contine reguli, ci numai fapte:

Daca scopul are forma p1, p2, … , pn, se incearca satisfacerea lui de la stanga la

dreapta. Atunci cand acesta nu contine variabile, daca baza de fapte satisface intreg

scopul, Prolog raspunde cu YES, altfel cu NO. Daca scopul contine variabile, atunci

obiectivul este acela de a gasi toate legaturile posibile pentru variabile, care sa satisfaca

scopul (deci de a da toate solutiile). Mai precis, se parcurge baza de fapte si se satisface o

data p1. Se trece apoi la satisfacerea lui p2. Daca p2 este satisfacut, atunci se trece la p3.

Page 11: Limbaj Prolog

Limbaj Prolog – Prelegerea 2 Pastramă Emil 4

Daca p2 nu se satisface, atunci se dezleaga variabilele lui p1 si se inspecteaza baza de

fapte pentru a gasi alte valori care legate de variabilele lui p1 sa resatisfaca p1, apoi se

reincearca satisfacerea lui p2 cu noile legaturi. Blocarea acestui proces de Backtracking se

poate face cu predicatul ! (“cut”), asezat intre doua clauze consecutive pi si pi+1 ale

scopului. In acest caz, nu se incearca resatisfacerea lui pi.

Daca programul contine si reguli:

Satisfacerea scopului se realizeaza in urmatorii pasi:

a) Presupunem: clauzele p1,…, pi au fost satisfacute.

b) In vederea satisfacerii lui pi+1 se inspecteaza mai intai baza de fapte. Daca pi+1

se satisface cu o fapta, se trece la pi+2. Daca nu exista elemente in baza de fapte

care sa satisfaca pe pi+1, se inspecteaza baza de reguli si se identifica prima

dintre regulile neluate in consideratie pana in prezent, al carei cap se poate

unifica cu pi+1 : se intra in corpul regulii identificate, considerand clauzele care

il compun drept componente ale scopului. Daca una din clauzele corpului nu

poate fi satisfacuta, se identifica o alta regula al carei cap sa se unifice cu pi+1.

In cazul in care nu exista o asemenea regula, se incearca resatisfacerea

clauzelor pi, pi-1, …

Unificare: Satisfacerea unui scop de tipul X = Y se face prin incercarea de a unifica X cu

Y. Din aceasta cauza, dandu-se un scop de tipul X = Y, regulile de decizie care indica

daca scopul se indeplineste sau nu sunt:

1. Daca X este variabila neinstantiata, iar Y este instantiata la orice obiect Prolog,

atunci scopul reuseste. Ca efect lateral, X se va instantia la aceeasi valoare cu cea

a lui Y.

2. Daca atat X cat si Y sunt variabile neinstantiate, scopul X = Y reuseste, variabila

X este legata la Y si reciproc, i.e.: ori de cate ori una dintre cele doua variabile se

instantiaza la o anumita valoare, cealalta variabila se va instantia la aceeasi

valoare.

3. Atomii si numerele sunt intotdeauna egali cu ei insisi.

Page 12: Limbaj Prolog

Limbaj Prolog – Prelegerea 2 Pastramă Emil 5

4. Doua structuri (a se vedea sintaxa limbajului) sunt egale daca au acelasi functor,

acelasi numar de componente si fiecare componenta dintr-o structura este egala

cu componenta corespunzatoare din cealalta structura.

Sintaxa limbajului Prolog

Constantele definesc:

Obiecte particulare

Relatii particulare

Constantele sunt de urmatoarele tipuri:

atomi – constante simbolice (desemneaza predicate Prolog sau argumente

ale predicatelor)

numere

Atomii pot fi construiti in 3 moduri; ei pot constitui:

1) siruri de litere, cifre si caracterul “underscore”, „_‟, siruri care incep cu o litera

mica;

2) siruri de caractere speciale;

3) siruri de caractere incluse intre paranteze simple (ex.: „South_America‟).

Numerele: majoritatea implementarilor admit o gama de valori cuprinse intre –

16383 si +16383, dar gama poate fi si mai larga.

Variabilele:

au denumiri care incep cu litere mari; numele de variabila poate incepe si

cu simbolul “_”, ceea ce indica o variabila anonima;

utilizarea unei variabile anonime semnifica faptul ca nu intereseaza

valoarea la care se va instantia acea variabila;

scopul lexical al unui nume de variabila il constituie o unica clauza. (Daca,

spre exemplu, numele X15 intervine in doua clauze diferite, atunci el

semnifica doua variabile diferite. Fiecare ocurenta a lui X15 in interiorul

aceleiasi clauze semnifica insa o aceeasi variabila).

Page 13: Limbaj Prolog

Limbaj Prolog – Prelegerea 2 Pastramă Emil 6

Structurile sunt obiecte ce desemneaza o colectie de obiecte corelate logic, care

formeaza componentele structurii.

Ex: poseda(mihai, carte(prolog, clocksin, 1981))

Sunt folosite la reprezentarea structurilor de date (liste, arbori)

O structura se defineste prin specificarea:

numelui structurii (functorul structurii);

elementelor sau componentelor structurii.

Desi alcatuite din mai multe componente, sunt tratate de program ca obiecte

unice. Pentru combinarea componentelor intr-un unic obiect, este folosit un

functor. Acesta va fi radacina arborelui intr-o reprezentare arborescenta.

Page 14: Limbaj Prolog

Limbaj Prolog – Prelegerea 3 Pastramă Emil 1

Operatori

Operatori aritmetici:

- sunt o rescriere infixata a unor structuri si de aceea valoarea

expresiei definite cu ei nu este calculata;

- evaluarea expresiei se face la cerere in cazul in care se foloseste

operatorul predefinit infixat is, ca in exemplul: X is 1+2 (in acest

caz se instantiaza variabila X la valoarea 3).

Operatori relationali:

- sunt predicate predefinite infixate;

- cel mai important este operatorul de egalitate, care functioneaza ca

si cand ar fi definit prin urmatorul fapt: X = X (VEZI

satisfacerea unui scop de tipul X = Y, prin incercarea de a unifica

X cu Y).

Un exemplu:

?- X = 1+2. ?- X is 1+2.

Prolog raspunde Prolog raspunde

X = 1+2 X = 3

deoarece, in primul caz, expresia 1+2 denota o structura (termen) Prolog, unde + este

functorul, iar 1 si 2 sunt argumentele sale. Nimic din acest scop nu declanseaza adunarea,

care este declansata de operatorul is.

Operatori relationali – continuare:

- Operatorul de inegalitate =\= se defineste ca un predicat opus celui de egalitate;

scopul X=\=Y reuseste daca scopul X=Y nu este satisfacut si esueaza daca X=Y

reuseste (semnificatie: valorile lui X si Y nu sunt egale).

- Predicatul == testeaza echivalenta a doua variabile; X==Y reuseste ori de cate

ori X=Y reuseste, dar reciproca este falsa. Este vorba de egalitatea literala a doi

termeni.

Page 15: Limbaj Prolog

Limbaj Prolog – Prelegerea 3 Pastramă Emil 2

- X==Y este adevarat daca termenii X si Y sunt identici, adica au exact aceeasi

structura si toate componentele corespunzatoare coincid. In particular, numele de

variabile trebuie sa fie aceleasi.

- Relatia complementara (de non-identitate) este \==

Un exemplu:

?- f(a, X) == f(a, Y).

no

- Operatorul =:= face numai evaluare aritmetica si nici o instantiere; semnificatia

lui X =:= Y este: valorile expresiilor aritmetice X si Y sunt egale.

Diferenta dintre operatorii = si =:=

?- 1+2 =:= 2+1.

yes

?- 1+2 = 2+1.

no

- Inegalitatea a doua expresii aritmetice se stabileste cu operatorul =\= (vezi folia

anterioara).

Valorile expresiilor aritmetice pot fi comparate prin intermediul operatorilor care

urmeaza. Acesti operatori forteaza evaluarea argumentelor lor.

X > Y (X este mai mare ca Y)

X < Y (X este mai mic ca Y)

X >= Y (X mai mare sau egal decat Y)

X <= Y (X mai mic sau egal cu Y)

X =:= Y (valorile lui X si Y sunt egale)

X =\= Y (valorile lui X si Y nu sunt egale)

Operatii aritmetice

- Exista proceduri incorporate care pot fi utilizate pentru efectuarea operatiilor

aritmetice.

- Efectuarea operatiilor aritmetice trebuie sa fie ceruta in mod explicit de catre

procedura incorporata is.

Page 16: Limbaj Prolog

Limbaj Prolog – Prelegerea 3 Pastramă Emil 3

- Exista proceduri incorporate asociate operatorilor predefiniti +, -, *, /, div si mod.

- In momentul in care se efectueaza evaluarea, toate argumentele trebuie sa fie deja

instantiate la anumite numere.

- Valorile expresiilor aritmetice pot fi comparate prin intermediul unor operatori

cum ar fi <, =< etc. (vezi folia anterioara). Acesti operatori forteaza evaluarea

argumentelor lor.

Operatorul infixat mod da restul unei impartiri intregi.

Operatorul infixat div da catul unei impartiri intregi.

Operatorul / poate sa desemneze impartire intreaga sau reala, in functie de

implementare. (De obicei se refera la impartirea reala, iar div la cea intreaga).

Comentariile in Prolog sunt precedate de caracterul %

Operatori definiti de utilizator

- Definirea de noi operatori de catre programator se face prin introducerea

in program a unor clauze de forma speciala, numite directive.

- Definirea de noi operatori se face cu ajutorul directivei

op(precedenta_operator, tip_operator, nume_operator).

precedata de simbolul :-

Exemplu:

:- op (600, xfx, are).

caz in care este legala expresia

coco are pene

Operatori definiti de utilizator – continuare

- Directivele actioneaza ca o definire de noi operatori ai limbajului, in care se

specifica numele, precedenta si tipul (infixat, prefixat sau postfixat) operatorului.

- Nu se asociaza nici o operatie operatorilor definiti de programator.

- Operatorii noi astfel definiti sunt utilizati ca functori numai pentru a combina

obiecte in structuri si nu pentru a executa actiuni asupra datelor.

- Exemplu: In loc de a utiliza structura

are (coco, pene)

Page 17: Limbaj Prolog

Limbaj Prolog – Prelegerea 3 Pastramă Emil 4

se poate defini un nou operator are

:- op (600, xfx, are).

caz in care este legala expresia

coco are pene

- Operatorii sunt atomi, iar precedenta lor trebuie sa fie o valoare intreaga intr-un

anumit interval si corelata cu precedenta operatorilor predefiniti in limbaj.

- Tipul operatorilor fixeaza caracterul infixat, prefixat sau postfixat al operatorului

si precedenta operanzilor sai. Tipul operatorului se defineste utilizand una din

urmatoarele forme standard:

(1) operatori infixati: xfx xfy yfx

(2) operatori prefixati: fx fy

(3) operatori postfixati: xf yf

unde f reprezinta operatorul, iar x si y operanzii sai.

- Utilizarea simbolului x sau a simbolului y depinde de precedenta operandului fata

de operator. Precedenta operanzilor se defineste astfel:

un argument intre paranteze sau un argument nestructurat are precedenta

0;

un argument de tip structura are precedenta egala cu cea a functorului

operator.

- Semnificatiile lui x si y in stabilirea tipului operatorului sunt urmatoarele:

x reprezinta un argument (operand) cu precedenta strict mai mica decat

cea a functorului (operatorului) f:

precedenta (x) < precedenta (f)

y reprezinta un argument (operand) cu precedenta mai mica sau egala cu

cea a functorului (operatorului) f:

precedenta (y) <= precedenta (f)

- Numele operatorului poate fi orice atom Prolog care nu este deja definit in Prolog.

Se poate folosi si o lista de atomi, daca se definesc mai multi operatori cu aceeasi

precedenta si acelasi tip.

Page 18: Limbaj Prolog

Limbaj Prolog – Prelegerea 3 Pastramă Emil 5

Exemplu :- op (100, xfx, [este, are]).

:- op (100, xf, zboara).

coco are pene.

coco zboara.

coco este papagal.

bozo este pinguin.

?- Cine are pene.

Cine = coco

?- Cine zboara.

Cine = coco

?- Cine este Ce.

Cine = coco, Ce = papagal;

Cine = bozo, Ce = pinguin;

no

In conditiile in care se adauga la baza de cunostinte anterioara si definitia

operatorilor daca, atunci si si

:- op (870, fx, daca).

:- op (880, xfx, atunci).

:- op (880, xfy, si).

urmatoarea structura este valida in Prolog:

daca Animalul are pene

si Animalul zboara

atunci Animalul este pasare.

Page 19: Limbaj Prolog

Limbaj Prolog – Prelegerea 3 Pastramă Emil 6

Controlul procesului de Backtracking: cut si fail

- Predicatul cut, notat cu atomul special ! este un predicat standard, fara argumente,

care se indeplineste (este adevarat) intotdeauna si nu poate fi resatisfacut.

- Comportarea predicatului cut este urmatoarea:

(C1) H :- D1, D2, … , Dm, ! , Dm+1, … , Dn.

(C2) H :- A1, … , Ap.

(C3) H.

Daca D1, D2, … , Dm sunt satisfacute, ele nu mai pot fi resatisfacute datorita lui

cut (se inhiba backtracking-ul).

Daca D1, D2, … , Dm sunt satisfacute, C2 si C3 nu vor mai fi utilizate pentru

resatisfacerea lui H. Resatisfacerea lui H se poate face numai prin resatisfacerea

unuia din scopurile Dm+1, … , Dn, daca acestea au mai multe solutii.

Observatie: Exista doua contexte diferite in care se poate utiliza predicatul cut, si

anume: intr-un context predicatul cut se introduce numai pentru cresterea eficientei

programului, caz in care el se numeste cut verde; in celalalt context utilizarea lui cut

modifica semnificatia procedurala a programului, caz in care el se numeste cut rosu. (La

cut-ul verde semnificatia procedurala a programului este aceeasi, adica nu conteaza

ordinea in care se scriu clauzele. La un cut rosu efectul programului este total diferit daca

se schimba ordinea clauzelor).

Cut rosu

Introducerea unui cut rosu modifica corespondenta dintre semnificatia declarativa

si semnificatia procedurala a programelor Prolog. El permite exprimarea in Prolog a unor

structuri de control de tipul

Daca conditie atunci actiune1

altfel actiune2

astfel:

Page 20: Limbaj Prolog

Limbaj Prolog – Prelegerea 3 Pastramă Emil 7

daca_atunci_altfel (Cond, Act1, Act2) :- Cond, !, Act1.

daca_atunci_altfel (Cond, Act1, Act2) :- Act2.

Obs.: Utilizarea predicatului cut in definirea predicatului asociat structurii de

control daca_atunci_altfel introduce un cut rosu deoarece efectul programului este total

diferit daca se schimba ordinea clauzelor.

Exemplu

Definirea predicatului de aflare a minimului dintre doua numere, in doua variante:

min1(X, Y, X) :- X=<Y,!. % cut verde

min1(X, Y, Y) :- X>Y.

min2(X, Y, X) :- X=<Y,!. % cut rosu

min2(X, Y, Y).

Ordinea clauzelor de definire a lui min1 poate fi schimbata fara nici un efect

asupra rezultatului programului. In cazul predicatului min2 se utilizeaza un cut rosu,

asemanator structurii

daca_atunci_altfel

Daca se schimba ordinea clauzelor de definire a predicatului min2:

min2(X,Y,Y).

min2(X, Y, X) :- X=<Y, !.

rezultatul programului va fi incorect pentru valori X < Y.

Page 21: Limbaj Prolog

Limbaj Prolog – Prelegerea 4 Pastramă Emil 1

Predicatul fail

Prolog permite exprimarea directa a esecului unui scop cu ajutorul predicatului

fail – un predicat:

standard,

fara argumente,

care esueaza intotdeauna.

Dupa fail nu se mai poate satisface nici un scop.

Introducerea unui predicat fail intr-o conjunctie de scopuri, de obicei la sfarsit

(caci dupa fail nu se mai poate satisface nici un scop), determina intrarea in

procesul de backtracking.

Daca fail se intalneste dupa predicatul cut, nu se mai face backtracking.

Exemplul 1 (folosirea predicatului fail pentru a determina esecul):

Enuntul “Un individ este rau daca nu este bun” se poate exprima astfel:

rau (X) :- bun (X),!,fail.

rau (X).

Exemplu de program – folosirea lui fail pentru a determina esecul:

bun (gelu).

bun (vlad).

bun (mihai).

rau (X) :- bun (X),!,fail. (*)

rau (X). (**)

Exemplu de executie a programului:

?- rau (gelu).

no

?- rau (mihai).

no

rau (petru).

yes

Page 22: Limbaj Prolog

Limbaj Prolog – Prelegerea 4 Pastramă Emil 2

Comentariu:

- la prima interogare: din clauza (*) avem rau (gelu) daca bun (gelu), care este

adevarat din primul fapt al bazei de cunostinte; apoi ! este intotdeauna adevarat si

urmeaza fail care genereaza esec; datorita existentei lui cut, clauza (**) nu va mai

fi utilizata pentru resatisfacerea scopului; deci raspunsul ramane no, ca si in al

doilea caz;

- la a treia interogare: pentru clauza (*) ar trebui sa am bun (petru), dar acest fapt

nu exista in baza de cunostinte; deoarece bun(petru) nu a fost satisfacut, am voie

sa utilizez clauza (**); clauza (**) furnizeaza rau (petru), deci satisface scopul

curent; atunci raspunsul este “yes”.

Observatie: Atunci cand este folosit pentru a determina esecul, fail este de obicei

precedat de cut, deoarece procesul de backtracking pe scopurile care il preced este inutil,

scopul esuand oricum, datorita lui fail.

Exemplul 2 – introducerea predicatului fail pentru a genera procesul de

backtracking pe scopurile care il preced:

rosu (mar).

rosu (cub).

rosu (soare).

afisare (X) :- rosu (X), write (X), fail.

afisare (_). (*)

Comentariu: Intrucat, pentru fiecare obiect considerat, scopul afisare (X) esueaza

datorita lui fail, se trece la clauza (*), care afiseaza obiectul respectiv, adica raspunde yes.

Trecerea la clauza (*) este posibila deoarece prima clauza nu contine cut inainte de fail.

In acest fel, vor fi afisate toate obiectele rosii cunoscute de programul Prolog, datorita

procesului de backtracking generat de fail; in acest fel se realizeaza, prin fail, o iteratie

peste faptele rosu ( ). Clauza afisare (_) este adaugata pentru ca raspunsul final la

satisfacerea scopului sa fie afirmativ. (Aceasta clauza raspunde yes la orice).

Page 23: Limbaj Prolog

Limbaj Prolog – Prelegerea 4 Pastramă Emil 3

Cum lucreaza programul anterior cu si fara cut inaintea lui fail:

1. Cazul cand NU avem cut inaintea lui fail: programul raspunde YES la orice

(datorita clauzei a doua); afiseaza (datorita lui write (X)) numai obiectele rosii

cunoscute de program (pentru aceste obiecte se scrie denumirea lor si apoi yes).

2. Cazul cand inaintea lui fail exista cut:

Pentru un obiect rosu cunoscut de program este scris numele obiectului si se

raspunde NO (pentru ca, datorita lui cut, nu se mai ajunge la clauza a doua).

Pentru un obiect necunoscut de program nu se mai afiseaza nimic si se

raspunde YES. (Aceasta deoarece, nefiind satisfacute clauzele dinaintea lui

cut, se ajunge la clauza a doua, care genereaza raspunsul YES).

Observatie: Combinatia !,fail poate fi utilizata cu rol de negatie.

Exemplu: “Mihai iubeste toate sporturile cu exceptia boxului.”

Pseudocod:

daca X este sport si X este box

atunci Mihai iubeste X este fals

altfel daca X este sport

atunci Mihai iubeste X este adevarat

PROLOG

Baza de cunostinte:

box(box).

sport(tenis).

sport(polo).

sport(innot).

sport(box).

Varianta 1 (cut rosu):

iubeste (mihai, X) :- sport (X), box (X), !, fail.

iubeste (mihai, X) :- sport (X).

Comentariu: Predicatul cut utilizat aici este un cut rosu.

Page 24: Limbaj Prolog

Limbaj Prolog – Prelegerea 4 Pastramă Emil 4

Comentariu: Predicatul cut utilizat aici este un cut rosu. Combinatia !,fail este

utilizata cu rol de negatie (pentru ca fail raspunde no, iar cut ma impiedica sa folosesc

clauza urmatoare). Se mai spune ca limbajul Prolog modeleaza negatia ca esec al

satisfacerii unui scop (negatia ca insucces), aceasta fiind, de fapt, o particularizare a

ipotezei lumii inchise. Combinatia !,fail este echivalenta cu un predicat standard existent

in Prolog, si anume predicatul not.

Predicatul not admite ca argument un predicat Prolog si reuseste daca predicatul

argument esueaza.

In Sicstus Prolog sintaxa pentru predicatul not este \+

Varianta 2 (cu predicatul not):

iubeste (mihai, X) :- sport (X), not (box(X)).

iubeste (mihai, X) :- sport (X).

Varianta 1 – program:

box(box).

sport(tenis).

sport(polo).

sport(innot).

sport(box).

iubeste(mihai,X):-sport(X),box(X),!,fail.

iubeste(mihai,X):-sport(X).

Exemple de interogari:

?- sport(X).

X=tenis ?;

X=polo ?;

X=innot ?;

X=box ?;

no

Page 25: Limbaj Prolog

Limbaj Prolog – Prelegerea 4 Pastramă Emil 5

?-sport(tenis).

yes

?- iubeste(mihai,tenis).

yes

?- iubeste(mihai,box).

no

Varianta 2 – program:

box(box).

sport(tenis).

sport(polo).

sport(innot).

sport(box).

iubeste(mihai,X) :- sport(X),\+(box(X)).

iubeste(mihai,X) :- sport(X).

Exemple de interogari:

- La primele trei interogari

?- sport(X).

?- sport(tenis).

?-iubeste(mihai,tenis).

rezultatul este identic cu cel de la programul anterior.

- La ultima interogare rezultatul difera:

?- iubeste(mihai,box).

yes

Aici raspunsul este YES deoarece, dupa ce esueaza prima clauza, se trece la

urmatoarea, care este satisfacuta. (Intrucat nu exista predicatul cut, se poate trece la

clauza urmatoare).

Page 26: Limbaj Prolog

Limbaj Prolog – Prelegerea 4 Pastramă Emil 6

Observatie: Chiar daca prima clauza este satisfacuta, se trece oricum la clauza

urmatoare (a doua) pentru ca este posibil ca ea sa furnizeze o noua solutie.

Predicatul call

- call este un alt predicat standard. El admite ca argument un predicat Prolog si are

ca efect incercarea de satisfacere a predicatului argument.

- call reuseste daca predicatul argument reuseste si esueaza in caz contrar.

- Utilizand acest predicat, se poate explicita efectul general al predicatului standard

not astfel:

not(P) :- call(P),!,fail.

not(P).

Observatie: Atat predicatul not, cat si predicatul call sunt predicate de ordinul II in

Prolog, deoarece admit ca argumente alte predicate.

Alte predicate incorporate

Predicatul =..

- Se scrie ca un operator infixat.

- Scopul

Term =.. L

este satisfacut daca L este o lista ce contine principalul functor al lui Term, urmat de

argumentele sale.

Exemplu:

?- f(a,b) =.. L.

L = [f,a,b]

?- T =.. [dreptunghi, 3, 5].

T = dreptunghi(3,5)

?- Z =.. [p,X,f(X,Y)].

Z = p(X,f(X,Y))

Observatie: Acest predicat descompune un termen in componentele sale – adica

functorul sau si argumentele acestuia.

Page 27: Limbaj Prolog

Limbaj Prolog – Prelegerea 4 Pastramă Emil 7

Predicatul bagof

Scopul

bagof(X,P,L)

va produce lista L a tuturor obiectelor X astfel incat sa fie satisfacut un scop P.

Observatie: Aceasta are sens numai daca X si P au unele variabile comune.

Exemplu: Presupunem ca programul contine urmatoarele fapte

varsta (petru,7).

varsta(ana,5).

varsta(patricia,8).

varsta(tom,5).

Atunci putem obtine lista tuturor copiilor care au 5 ani prin urmatoarea interogare:

?-bagof(Copil,varsta(Copil,5),Lista).

Lista = [ana, tom]

Predicatul findall

findall(X,P,L)

produce, de asemenea, o lista de obiecte care satisfac P. Diferenta fata de bagof este

aceea ca sunt colectate toate obiectele X, indiferent de solutii posibil diferite pentru

variabile din P care nu sunt partajate cu X.

Daca nu exista nici un obiect X care sa satisfaca P, atunci findall va avea succes

cu L = [ ].

Predicate standard de intrare / iesire (intotdeauna adevarate)

Predicatul write

- are forma write(E1, E2, … , Ek)

unde E1, E2, … , Ek sunt variabile sau obiecte elementare. Orice variabila trebuie sa fie

legata in momentul scrierii!

Page 28: Limbaj Prolog

Limbaj Prolog – Prelegerea 4 Pastramă Emil 8

- nl face trecerea pe linia urmatoare

Predicatul readln

Permite citirea unui string sau simbol. Valoarea obtinuta in urma citirii este legata

la X din

readln(X) LISTE

O lista este de forma [Cap|Coada].

Operatii cu liste:

1. Apartenenta la o lista

- se foloseste predicatul membru(X,L), unde X este un obiect si L este o lista. X este

membru al lui L daca

(1) X este capul lui L

sau

(2) X este membru al cozii lui L

ADICA

membru(X, [X|Coada]).

membru(X, [Cap|Coada]):-membru(X, Coada).

2. Concatenarea

- se foloseste relatia conc(L1, L2, L3)

- definitia predicatului conc este:

conc([ ], L, L).

conc([X|L1], L2, [X|L3]) :- conc(L1, L2, L3).

3. Adaugarea unui element

- elementul adaugat devine noul cap:

add(X, L, [X|L]).

Page 29: Limbaj Prolog

Limbaj Prolog – Prelegerea 4 Pastramă Emil 9

4. Stergerea unui element

- se foloseste relatia del(X, L, L1)

- definitia predicatului del este:

del(X, [X|Coada], Coada).

del(X, [Y|Coada], [Y|Coada1]) :- del(X,Coada, Coada1).

Observatie: Inserarea unui element intr-o lista poate fi definita folosind relatia del, astfel:

insert(X, Lista, ListaMaiMare):-

del (X, ListaMaiMare, Lista).

Subliste

relatia sublista([c,d,e], [a,b,c,d,e,f]) este adevarata, dar sublista([c,e], [a,b,c,d,e,f]) nu este

adevarata.

Definitie:

S este o sublista a lui L daca

(1) L poate fi descompusa in doua liste, L1 si L2

si

(2) L2 poate fi descompusa in doua liste, S si o alta lista L3

adica

sublista(S,L) :- conc(L1,L2,L), conc(S,L3,L2).