e5x4xy
Limbajul Prolog
Inceputul programarii logice poate fi atribuit lui R. Kowalski si A. Colmerauer si se situeaza la inceputul anilor '70. Kowalski a plecat de la o formula logica de tipul:
S1 ? S2 ? ... Sn ? S care are, in logica cu predicate de ordinul intai semnificatia declarativa conform careia S1 ? S2 ? ... Sn implica S, adica daca S1 si S2 ... si Sn sunt fiecare adevarate atunci si S este adevarat, si a propus o interpretare procedurala asociata. Conform acestei interpretari, formula de mai sus poate fi scrisa sub forma:
S daca S1 si S2 ... si Sn si poate fi executata ca o procedura a unui limbaj de programare recursiv, unde S este antetul procedurii si S1, S2, ... Sn corpul acesteia. Deci, pe langa interpretarea declarativa, logica, a unei astfel de formule, formula poate fi interpretata procedural astfel: pentru a executa S se executa S1 si S2 ... si Sn.
In aceeasi perioada, A. Colmerauer si colectivul lui de cercetare de la Universitatea din Marsilia au dezvoltat un limbaj de implementare a acestei abordari, pe care l au denumit Prolog, abreviere de la "Programmation et Logique". De atunci si pina in prezent, limbajul Prolog s a impus ca cel mai important limbaj de programare logica si s au dezvoltat numeroase implementari, atat ale unor interpretoare cat si ale unor compilatoare ale limbajului.
Limbajul Prolog este un limbaj declarativ sustinut de o componenta procedurala. Spre deosebire de limbajele procedurale, cum ar fi C sau Pascal, in care rezolvarea problemei este specificata printr-o serie de pasi de executie sau actiuni, intr-un limbaj declarativ problema este specificata prin descrierea universului problemei si a relatiilor sau functiilor existente intre obiecte din acest univers. Exemple de astfel de limbaje sunt cele functionale, de exemplu Lisp, Scheme, ML, si cele logice, de exemplu Prolog.
Desi initial a fost gandit pentru un set restrans de probleme, Prolog a devenit cu timpul un limbaj de uz general, fiind o unealta importanta in aplicatiile de inteligenta artificiala aCM84, Bra88, SS86i. Pentru multe probleme, un program Prolog are cam de 10 ori mai putine linii decat echivalentul lui in Pascal.
In 1983, cercetatorii din Japonia au publicat un plan ambitios de creare a unor calculatoare de generatia a 5 a pentru care Prolog era limbajul de asamblare. Planul nu a reusit, dar acest proiect a marcat o dezvoltare deosebita a interpretoarelor si compilatoarelor de Prolog, precum si o crestere mare a numarului de programatori in acest limbaj.
Multe clase de probleme poate fi rezolvate in Prolog, existand anumite categorii care sunt rezolvabile mult mai usor in Prolog decat in orice alt limbaj procedural. Astfel de probleme sunt in principal cele dedicate prelucrarii simbolice sau care necesita un proces de cautare a solutiei intr-un spatiu posibil de transformari ale problemei.
Prezentarea limbajului Prolog ce urmeaza este in principal orientata pe descrierea limbajului Prolog standard. Exemplele de programe din aceasta parte cat si din partea a doua sunt rulate utilizand interpretorul ARITY Prolog pe microcalculatoare de tip IBM/PC, mediul de programare ARITY Prolog si particularitatile lui sintactice fiind prezentate in partea a doua.
1 Entitatile limbajului Prolog
Limbajul Prolog este un limbaj logic, descriptiv, care permite specificarea problemei de rezolvat in termenii unor fapte cunoscute despre obiectele universului problemei si a relatiilor existente intre aceste obiecte. Executia unui program Prolog consta in deducerea implicatiilor acestor fapte si relatii, programul definind astfel o multime de consecinte ce reprezinta intelesul sau semnificatia declarativa a programului.
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.
1.1 Fapte
Faptele sunt predicate de ordinul intai de aritate n considerate adevarate. Ele stabilesc relatii intre obiectele universului problemei. Numarul de argumente ale faptelor este dat de aritatea (numarul de argumente) corespunzatoare a predicatelor.
Exemple:
Fapt: Aritate: papagal(coco). 1 iubeste(mihai, maria). 2 iubeste(mihai, ana). 2 frumoasa(ana). 1 bun(gelu). 1 deplaseaza(cub, camera1, camera2). 3
Interpretarea particulara a predicatului si a argumentelor acestuia depinde de programator. Ordinea argumentelor, odata fixata, este importanta si trebuie pastrata la orice alta utilizare a faptului, cu aceeasi semnificatie. Multimea faptelor unui program Prolog formeaza baza de cunostinte Prolog. Se va vedea mai tarziu ca in baza de cunostinte a unui program Prolog sunt incluse si regulile Prolog.
1.2 Scopuri
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 Prolog. Scopurile sunt predicate pentru care se doreste aflarea valorii de adevar in contextul faptelor existente in baza de cunostinte. Cum scopurile pot fi vazute ca intrebari, rezultatul unui program Prolog este raspunsul la o intrebare (sau la o conjunctie de intrebari). Acest raspuns poate fi afirmativ, yes, sau negativ, no. Se va vedea mai tarziu ca programul Prolog, in cazul unui raspuns afirmativ la o intrebare, poate furniza si alte informatii din baza de cunostinte.
Exemplu
Considerand baza de cunostinte specificata anterior, se pot pune diverse intrebari, cum ar fi:
?- iubeste(mihai, maria). yes deoarece acest fapt exista in baza de cunostinte
?- papagal(coco). yes
?- papagal(mihai). no deoarece acest fapt nu exista in baza de cunostinte
?- inalt(gelu). no
1.3 Variabile
In exemplele prezentate pana acum, argumentele faptelor si intrebarilor au fost obiecte particulare, numite si constante sau atomi simbolici. Predicatele Prolog, ca orice predicate in logica cu predicate de ordinul I, admit ca argumente si obiecte generice numite variabile. In Prolog, prin conventie, numele argumentelor variabile incepe cu litera iar numele constantelor simbolice incepe cu litera mica. O variabila poate fi instantiata (legata) daca exista un obiect asociat acestei variabile, sau neinstantiata (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. Daca se intalneste un fapt cu un simbol predicativ identic cu cel al scopului, variabilele din scop se instantiaza conform algoritmului de unificare si valorile variabilelor astfel obtinute sunt afisate ca raspuns la satisfacerea acestui scop.
Exemple:
?- papagal(CineEste).
CineEste = coco
?- deplaseaza(Ce, DeUnde, Unde).
Ce = cub, DeUnde = camera1, Unde = camera2
?- deplaseaza(Ce, Aici, Aici). no
Cum se comporta sistemul Prolog in cazul in care exista mai multe fapte in baza de cunostinte care unifica cu intrebarea pusa? In acest caz exista mai multe raspunsuri la intrebare, corespunzand mai multor solutii ale scopului fixat. Prima solutie este data de prima unificare si exista atatea solutii cate unificari diferite exista. La realizarea primei unificari se marcheaza faptul care a unificat si care reprezinta prima solutie. La obtinerea urmatoarei solutii, cautarea este reluata de la marcaj in jos in baza de cunostinte. Obtinerea primei solutii este de obicei numita satisfacerea scopului iar obtinerea altor solutii, resatisfacerea scopului. La satisfacera 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.
Sistemul Prolog, fiind un sistem interactiv, permite utilizatorului obtinerea fie a primului raspuns, fie a tuturor raspunsurilor. In cazul in care, dupa afisarea tuturor raspunsurilor, un scop nu mai poate fi resatisfacut, sistemul raspunde no.
Exemple:
?- iubeste(mihai, X).
X = maria; tastand caracterul “;” si Enter, cerem o noua solutie
X = ana; no
?- iubeste(Cine, PeCine).
Cine = mihai, PeCine = maria;
Cine = mihai, PeCine = ana; no
Exista deci doua solutii pentru scopul iubeste(mihai, X) si tot doua solutii pentru scopul iubeste(Cine, PeCine), considerand tot baza de cunostinte prezentata in sectiunea 1.1.
1.4 Reguli
O regula Prolog exprima un fapt care depinde de alte fapte si este de forma:
S :- S1, S2, …Sn. cu semnificatia prezentata la inceputul acestui capitol. Fiecare Si, i = 1,n si S au forma faptelor Prolog, deci sunt predicate, cu argumente constante, variabile sau structuri. Faptul S care defineste regula, se numeste antet de regula, iar S1, S2, …Sn formeaza corpul regulii si reprezinta conjunctia de scopuri care trebuie satisfacute pentru ca antetul regulii sa fie satisfacut.
Fie urmatoarea baza de cunostinte Prolog: frumoasa(ana). % 1 bun(vlad). % 2 cunoaste(vlad, maria). % 3 cunoaste(vlad, ana). % 4 iubeste(mihai, maria). % 5 iubeste(X, Y) :- % 6 bun(X), cunoaste(X, Y), frumoasa(Y).
Se observa ca enuntul (6) defineste o regula Prolog; relatia iubeste(Cine, PeCine), fiind definita atat printr-un fapt (5) cat si printr o regula (6).
In conditiile existentei regulilor in baza de cunostinte Prolog, satisfacerea unui scop se face printr un procedeu similar cu cel prezentat in Sectiunea 1.2, dar 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, 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.
Pentru baza de cunostinte descrisa mai sus, satisfacerea scopului
?- iubeste(vlad, ana). se va face in urmatorul mod. Scopul unifica cu antetul regulii (6) si duce la instantierea variabilelor din regula (6): X = vlad si Y = ana. Pentru ca acest scop sa fie indeplinit, trebuie indeplinita regula, deci fiecare subscop din corpul acesteia. Aceasta revine la indeplinirea scopurilor bun(vlad), care reuseste prin unificare cu faptul (2), cunoaste(vlad, ana), care reuseste prin unificare cu faptul (4), si a scopului frumoasa(ana), care reuseste prin unificare cu faptul (1). In consecinta, regula a fost indeplinita, deci si intrebarea initiala este adevarata, iar sistemul raspunde yes.
Ce se intimpla daca se pune intrebarea:
?- iubeste(X, Y).
Prima solutie a acestui scop este data de unificarea cu faptul (5), iar raspunsul este:
X = mihai, Y = maria
Sistemul Prolog va pune un marcaj in dreptul faptului (5) care a satisfacut scopul. Urmatoarea solutie a scopului iubeste(X, Y) se obtine incepand cautarea de la acest marcaj in continuare in baza de cunostinte. Scopul unifica cu antetul regulii (6) si se vor fixa trei noi subscopuri de indeplinit, bun(X), cunoaste(X, Y) si frumoasa(Y). Scopul bun(X) este satisfacut de faptul (2) si variabila X este instantiata cu valoarea vlad, . Se incearca acum satisfacerea scopului cunoaste(vlad, Y), care este satisfacut de faptul (3) si determina instantierea Y = maria. Se introduce in baza de cunostinte un marcaj asociat scopului cunoaste(vlad, Y), care a fost satisfacut de faptul (3). Se incearca apoi satisfacerea scopului frumoasa(maria). Acesta esueaza. In acest moment sistemul intra intr un proces de backtracking in care se incearca resatisfacerea scopului anterior satisfacut, cunoaste(vlad, Y), in speranta ca o noua solutie a acestui scop va putea satisface si scopul curent care a esuat, frumoasa(Y). Resatisfacerea scopului cunoaste(vlad, Y) se face pornind cautarea de la marcajul asociat scopului in jos, deci de la faptul (3) in jos. O noua solutie (resatisfacere) a scopului cunoaste(vlad, Y) este data de faptul (4) care determina instantierea Y = ana. In acest moment se incearca satisfacerea scopului frumoasa(ana). Cum este vorba de un nou scop, cautarea se face de la inceputul bazei de cunostinte si scopul frumoasa(ana) este satisfacut de faptul (1). In consecinta a doua solutie a scopului iubeste(X, Y) este obtinuta si sistemul raspunde:
X = vlad, Y = ana urmand un mecanism de backtracking, descris intuitiv in figura 1 prin prezentarea arborilor de deductie construiti de sistemul Prolog.

Figura 1. Mecanismul de satisfacere a scopurilor in Prolog
La incercarea de resatisfacere a scopului iubeste(X, Y), printr un mecanism similar, se observa ca nu mai exista alte solutii. In concluzie, fiind data baza de fapte si reguli Prolog anterioara, comportarea sistemului Prolog este:
?- iubeste(X, Y).
X = mihai, Y = maria;
X = vlad, Y = ana; no
Observatii:
• La satisfacerea unei conjunctii de scopuri in Prolog, se incearca satisfacerea fiecarui scop pe rand, de la stanga la dreapta. Prima satisfacere a unui scop determina plasarea unui marcaj in baza de cunostinte in dreptul faptului sau regulii care a determinat satisfacerea scopului.
• Daca un scop nu poate fi satisfacut (esueaza), sistemul Prolog se intoarce si incearca resatisfacerea scopului din stanga, pornind cautarea in baza de cunostinte de la marcaj in jos. Inainte de resatisfacerea unui scop se elimina toate instantierile de variabile determinate de ultima satisfacere a acestuia. Daca cel mai din stanga scop din conjunctia de scopuri nu poate fi satisfacut, intreaga conjunctie de scopuri esueaza.
• Aceasta comportare a sistemului Prolog in care se incearca in mod repetat satisfacerea si resatisfacerea scopurilor din conjunctiile de scopuri se numeste backtracking.
• In Sectiunea 4 se va discuta pe larg structura de control a sistemului Prolog, mecanismul fundamental de backtracking si modurile in care se poate modifica partial acest mecanism.
1.5 Un program Prolog simplu
Simplitatea si expresivitatea limbajului Prolog poate fi pusa in evidenta de urmatorul exemplu de descriere a unui circuit logic "poarta SI". Se considera poarta SI ca fiind construita prin conectarea unei "porti SI NU" cu un inversor. Intregul circuit este definit de relatia: poarta_si(Intrare1, Intrare2, Iesire) pe baza relatiilor poarta_si_nu(Intrare1, Intrare2, Iesire) inversor(Intrare, Iesire).
In figura 2 este prezentata schema portii SI in care se observa ca inversorul este construit dintr un tranzistor cu sursa conectata la masa si un rezistor cu un capat conectat la alimentare. Poarta tranzistorului este intrarea inversorului, in timp ce celalalt capat al rezistorului trebuie conectat la colectorul tranzistorului care formeaza iesirea inversorului.

Figura 2. Un circuit logic poarta SI
Variabilele comune intre predicate sunt utilizate pentru a specifica legaturile comune. rezistor(alimentare, n1). rezistor(alimentare, n2). tranzistor(n2, masa, n1). tranzistor(n2, masa, n1). tranzistor(n3, n4, n2). tranzistor(n5, masa, n4). inversor(Intrare, Iesire) : tranzistor(Intrare, masa, Iesire), rezistor(alimentare, Iesire). poarta_si_nu(Intrare1, Intrare2, Iesire) : tranzistor(Intrare1, X, Iesire), tranzistor(Intrare2, masa, X), rezistor(alimentare, Iesire). poarta_si(Intrare1, Intrare2, Iesire) : poarta_si_nu(Intrare1, Intrare2, X), inversor(X, Iesire).
Pentru intrebarea
?- poarta_si(In1, In2, Iesire).
In1 = n3, In2= n5, Iesire = n1 raspunsul sistemului Prolog confirma faptul ca circuitul descris este o poarta SI, identificand intrarile si iesirile corespunzatoare.
2 Sintaxa limbajului Prolog
Asa cum s a aratat in sectiunea anterioara, un program Prolog este format din fapte, reguli si intrebari, acestea fiind construite pe baza predicatelor definite de utilizator sau predefinite. In orice sistem Prolog exista o multime de predicate predefinite, unele dintre acestea fiind predicate standard, iar altele depinzand de implementare. Argumentele predicatelor Prolog, prin analogie cu logica predicatelor de ordinul I, se numesc termeni, si pot fi constante, variabile sau structuri.
2.1 Constante
Constantele definesc obiecte specifice, particulare, sau relatii particulare. Exista doua tipuri de constante: atomi si numere. Atomii sunt constante simbolice care incep, de obicei, cu o litera si pot contine litere, cifre si caracterul “_”. Exista si alte caractere ce pot forma atomi speciali, care au o semnificatie aparte in limbaj. Atomii pot desemna:
• obiecte constante care sunt argumentele predicatelor, de exemplu atomii mihai si maria in faptul iubeste(mihai, maria);
• predicate Prolog, fie cele definite de utilizator, fie cele predefinite in sistem; de exemplu atomul iubeste in faptul iubeste(mihai, maria);
• atomi speciali, de exemplu atomii “:-” si “?”- ;
• diverse alte reguli de constructie sintactica a atomilor depind de implementare.
Numerele pot fi intregi sau reale; sintaxa particulara acceptata cat si domeniile de definitie depinzand de implementare. Detalii despre formatul numerelor si a altor tipuri de constante din mediul ARITY Prolog sunt descrise in partea a doua.
2.2 Variabile
Variabilele sunt, din punct de vedere sintactic, tot atomi, dar ele au o semnificatie speciala, asa cum s a aratat in Sectiunea 1.3. Spre deosebire de regulile generale admise pentru constructia atomilor, numele unei variabile 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.
De exemplu, interogarea ?- iubeste( _, maria). semnifica faptul ca se intreaba daca exista cineva care o iubeste pe Maria, dar nu intereseaza cine anume. Limbajul Prolog face distinctia intre litere mari si litere mici (este case sensitive). Se reaminteste ca, din punctul de vedere al conventiei Prolog, numele oricarei variabile trebuie sa inceapa fie cu litera mare, fie cu “_”.
2.3 Structuri
O structura Prolog este un obiect ce desemneaza o colectie de obiecte corelate logic, care formeaza componentele structurii. Un exemplu este structura asociata obiectului carte, care este formata din componentele: titlu carte, autor, si an aparitie. Un fapt ce refera relatia de posedare a unei carti de Prolog de catre Mihai poate fi exprimat astfel: poseda(mihai, carte(prolog, clocksin, 1981)). unde carte(prolog, clocksin, 1981) este o structura cu numele carte si cu trei componente: prolog, clocksin si 1981. Se admit si structuri imbricate, de exemplu: poseda(mihai, carte(prolog, autori(clocksin, mellish), 1981)). unde predicatul poseda are doua argumente: primul argument este constanta mihai, iar cel de al doilea este structura carte(prolog ....), cu doua componente, a doua componenta fiind structura autori(clocksin, mellish).
In Prolog, o structura se defineste prin specificarea:
(1) numelui structurii ( functorul structurii);
(2) elementelor structurii (componentele structurii).
Structurile Prolog pot fi utilizate pentru reprezentarea structurilor de date, de exemplu liste sau arbori. In Sectiunea 2.6 se vor prezenta structuri Prolog predefinite care permit lucrul cu liste. Un arbore binar poate fi reprezentat in Prolog tot printr o structura, de exemplu: arb(barbu, arb(ada, vid, vid), vid). reprezinta un arbore binar cu cheia din radacina barbu, cu subarborele drept vid si cu subarborele stang format dintr un singur nod cu cheia ada.
Observatii:
• Sintaxa structurilor este aceeasi cu cea a faptelor Prolog. Un predicat Prolog poate fi vazut ca o structura a carui functor este numele predicatului, iar argumentele acestuia reprezinta componentele structurii.
• Considerarea predicatelor Prolog ca structuri prezinta un interes deosebit; atat datele cat si programele in Prolog au aceeasi forma, ceea ce faciliteaza tratarea uniforma si sinteza dinamica de programe. In Sectiunea 4.3 se vor prezenta predicate predefinite in Prolog care permit sinteza si executia dinamica a programelor Prolog.
2.4 Operatori
Uneori este convenabil sa se scrie anumiti functori (nume de structuri sau predicate) in forma infixata. Aceasta este o forma sintactica ce mareste claritatea programului, cum ar fi cazul operatorilor aritmetici sau al operatorilor relationali.
Limbajul Prolog ofera o multime de operatori, unii care se regasesc in aproape orice implementare, iar altii care sunt specifici unei versiuni particulare de implementare a limbajului. In continuare se vor prezenta o parte dintre operatorii din prima categorie.
(1) Operatori aritmetici
Operatorii aritmetici binari, cum ar fi +, -, *, /, pot fi scrisi in Prolog in notatie infixata; de exemplu:
1 + 2*(X * Y) / Z
Aceasta sintaxa este de fapt o rescriere infixata a formei prefixate a structurilor echivalente:
+(1, 2) / (*(X, Y), Z)
Este important de retinut ca operatorii aritmetici sunt o rescriere infixata a unor structuri deoarce valoarea expresiei astfel definita nu este calculata. Evaluarea expresiei se face la cerere in cazul in care se foloseste operatorul predefinit infixat is, de exemplu:
X is 1 + 2. va avea ca efect instantierea variabilei X la valoarea 3.
(2) Operatori relationali
Operatorii relationali sunt predicate predefinite infixate. Un astfel de operator este operatorul de egalitate =. Predicatul (operatorul) de egalitate functioneaza ca si cum ar fi definit prin urmatorul fapt:
X = X. iar incercarea de a satisface un 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 urmatoarele:
• 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. De exemplu:
?- carte(barbu, poezii) = X. este un scop care reuseste si X se instantiaza la carte(barbu, poezii).
• Daca atat X cat si Y sunt variabile neinstantiate, scopul X = Y reuseste, variabila X este legata la Y si reciproc. Aceasta inseamna ca ori de cate ori una dintre cele doua variabile se instantiaza la o anumita valoare, cealalta variabila se va instantia la aceeasi valoare.
• Atomii si numerele sunt intotdeauna egali cu ei insisi. De exemplu, urmatoarele scopuri au rezultatul marcat drept comentariu: mihai = mihai % este satisfacut mare = mic % esueaza
102 = 102 % reuseste
1010 = 1011 % esueaza
• Doua structuri sunt egale daca au acelasi functor, acelasi numar de componente si fiecare componenta dintr o structura este egala cu componenta corespunzatoare din cealalta structura. De exemplu, scopul: autor(barbilian, ciclu(uvedenrode, poezie(riga_crypto))) = autor(X, ciclu(uvedenrode, poezie(Y))) este satisfacut, iar ca efect lateral se fac instantierile:
X = barbilian si Y = riga_crypto.
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. In plus, exista predicatele relationale de inegalitate definite prin operatorii infixati >, <, =<, >=, cu semnificatii evidente.
Un operator interesant este =:=. El face numai evaluare aritmetica si nici o instantiere. Exemplu:
?- 1 + 2 =:= 2 + 1. yes
?- 1 + 2 = 2 + 1. no
Predicatul = = testeaza echivalenta a doua variabile. El considera cele doua variabile egale doar daca ele sunt deja partajate. X = = Y reuseste ori de cate ori X = Y reuseste, dar reciproca este falsa:
?- X = = X.
X=_23 %variabila neinstantiata
?- X= =Y. no
?- X=Y, X= =Y.
X=_23, Y=_23 % X si Z variabile neinstantiate partajate
In cele mai multe implementari Prolog exista predefinit operatorul de obtinere a modulului unui numar, mod; scopul
X is 5 mod 3. reuseste si X este instantiat la 2.
Comentariile dintr un program Prolog sunt precedate de caracterul “%”.
Exemple:
1. Presupunand ca nu exista operatorul predefinit mod, se poate scrie un predicat Prolog cu efect similar. O definitie posibila a predicatului modulo(X, Y, Z), cu semnificatia argumentelor , presupunand X, Y > 0, este:
% modulo(X, Y, Z) modulo(X, Y, X) :- X < Y. modulo(X, Y, Z) :- X >= Y, X1 is X - Y, modulo(X1, Y, Z).
2. Plecand de la predicatul modulo definit anterior, se poate defini predicatul de calcul al celui mai mare divizor comun al doua numere, conform algoritmului lui Euclid, presupunand , , astfel:
% cmmdc(X, Y, C) cmmdc(X, 0, X). cmmdc(X, Y, C) :- modulo(X, Y, Z), cmmdc(Y, Z, C).
La intrebarea
?- cmmdc(15, 25, C).
C=5 raspunsul sistemului este corect. In cazul in care se incearca obtinerea unor noi solutii (pentru semnificatia cmmdc acest lucru este irelevant, dar intereseaza din punctul de vedere al functionarii sistemului Prolog) se observa ca sistemul intra intr o bucla infinita datorita imposibilitatii resatisfacerii scopului modulo(X, Y, Z) pentru . Daca la definitia predicatului modulo se adauga faptul: modulo(X, 0, X). atunci predicatul modulo(X, Y, Z) va genera la fiecare resatisfacere aceeasi solutie, respectiv solutia corecta, la infinit. Cititorul este sfatuit sa traseze executia predicatului cmmdc in ambele variante de implementare a predicatului modulo.
3. Calculul ridicarii unui numar natural la o putere naturala se poate face definind urmatorul predicat:
% expo(N, X, XlaN) expo( _ , 0, 0). expo(0, _ , 1). expo(N, X, Exp) :- N > 0, N1 is N - 1, expo(N1, X, Z), Exp is Z * X.
2.5 Operatori definiti de utilizator
Limbajul Prolog permite definirea de noi operatori de catre programator prin introducerea in program a unor clauze de forma speciala, numite directive. Directivele actioneaza ca o definire de noi operatori ai limbajului in care se specifica numele, precedenta si tipul (infixat, prefixat sau postfixat) operatorului. Se reaminteste faptul ca orice operator Prolog este de fapt o structura care are ca functor numele operatorului si ca argumente argumentele operatorului, dar este scris intr o sintaxa convenabila. La definirea de noi operatori in Prolog, se creeaza de fapt noi structuri carora le este permisa o sintaxa speciala, conform definitiei corespunzatoare a operatorului. Din acest motiv, nu se asociaza nici o operatie operatorilor definiti de programator. Operatorii noi definiti sunt utilizati ca functori numai pentru a combina obiecte in structuri si nu pentru a executa actiuni asupra datelor, desi denumirea de operator ar putea sugera o astfel de actiune.
De exemplu, in loc de a utiliza structura: are(coco, pene) se poate defini un nou operator are
:- op(600, xfx, are). caz in care este legala expresia coco are pene.
Definirea de noi operatori se face cu ajutorul directivei:
:- op(precedenta-operator, tip-operator, nume-operator).
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.
Observatie: In ARITY Prolog, cu cat valoare precedenta-operator este mai mare, cu atat operatorul are o precedenta mai mica si invers.
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 (operandului) f precedenta( y ) ? precedenta( f )
Aceste reguli ajuta la eliminarea ambiguitatii operatorilor multipli cu aceeasi precedenta. De exemplu, operatorul predefinit in Prolog - (minus) este definit din punct de vedere al tipului ca yfx, ceea ce inseamna ca structura este interpretata ca si nu ca . Daca acest operator ar fi fost definit ca xfy, atunci interpretarea structurii ar fi fost .
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.
Exemple:
:- op(100, xfx, aeste, arei).
:- 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.
2.6 Liste
O lista este o structura de date ce reprezinta o secventa ordonata de zero sau mai multe elemente. O lista poate fi definita recursiv astfel:
(1) lista vida (lista cu 0 elemente) este o lista
(2) o lista este o structura cu doua componente: primul element din lista (capul listei) si restul listei (lista formata din urmatoarele elemente din lista).
Sfarsitul unei liste este de obicei reprezentat ca lista vida.
In Prolog structura de lista este reprezentata printr o structura standard, predefinita, al carei functor este caracterul “.” si are doua componente: primul element al listei si restul listei. Lista vida este reprezentata prin atomul special a i. De exemplu, o lista cu un singur element a se reprezinta in Prolog, prin notatie prefixata astfel:
.(a, a i) avand sintaxa in ARITY Prolog '.'(a, a i) iar o lista cu trei elemene, a, b, c, se reprezinta ca:
.(a, . (b, . (c, a i))) cu sintaxa in ARITY Prolog '.'(a, '. '(b, '. '(c, a i))).
Deoarece structura de lista este foarte des utilizata in Prolog, limbajul ofera o sintaxa alternativa pentru descrierea listelor, formata din elementele listei separate de virgula si incadrate de paranteze drepte. De exemplu, cele doua liste anterioare pot fi exprimate astfel:
aai
aa, b, ci
Aceasta sintaxa a listelor este generala si valabila in orice implementare Prolog. O operatie frecventa asupra listelor este obtinerea primului element dintr o lista si a restului listei, deci a celor doua componente ale structurii de lista. Aceasta operatie este realizata in Prolog de operatorul de scindare a listelor “|” scris sub urmatoarea forma:
aPrim | Resti
Variabila Prim sta pe postul primului element din lista, iar variabila Rest pe postul listei care contine toate elementele din lista cu exceptia primului. Acest operator poate fi aplicat pe orice lista care contine cel putin un element. Daca lista contine exact un element, Rest va reprezenta lista vida. Incercarea de identificare a structurii aPrim | Resti cu o lista vida duce la esec. Mergand mai departe, se pot obtine chiar primele elemente ale listei si restul listei. Iata cateva echivalente:
aa, b, ci = aa | ab, ci i = aa, b | aci i = aa, b, c | a i i = aa | ab | aci i i = aa | ab | ac | a i i i i.
In Prolog elementele unei liste pot fi atomi, numere, liste si in general orice structuri. In consecinta se pot construi liste de liste.
Exemple:
1. Se poate defini urmatoarea structura de lista:
acarte(barbu, poezii), carte(clocksin, prolog)i
2. Considerand urmatoarele fapte existente in baza de cunostinte Prolog pred(a1, 2, 3, 4i). pred(acoco, sta, pe, amasa, albaii). se pot pune urmatoarele intrebari obtinand raspunsurile specificate:
?- pred(aPrim | Resti).
Prim = 1, Rest = a2, 3, 4i;
Prim = coco, Rest = asta, pe, amasa, albaii; no
?- pred(a _, _ , _ , a _ | Restii)
Rest = aalbai
3. Un predicat util in multe aplicatii este cel care testeaza apartenenta unui element la o lista si care se defineste astfel:
% membru(Element, Lista) membru(Element, aElement | _ i). membru(Element, a _ | RestulListeii) :- membru(Element, RestListei).
Functionarea acestui scurt program Prolog poate fi urmarita cerand raspunsul sistemului la urmatoarele scopuri:
?- membru(b, aa, b, ci). %1 yes
?- membru(X, aa, b, ci). %2
X = a;
X = b;
X = c; no
?- membru(b, aa, X, bi). %3
X = b;
X = _0038; no
Deci pentru cazul in care primul argument este o variabila (%2) exista trei solutii posibile ale scopului membru(Element, Lista). Daca lista contine o variabila (%3) exista doua solutii pentru forma listei (aa, b, bi sau aa, _ , bi).
4. Un alt predicat util este cel de concatenare a doua liste L1 si L2, rezultatul concatenarii obtinandu se in lista L3, initial neinstantiata.
% conc(L1, L2, L3) conc(ai, L2, L2). % lista vida concatenata cu L2 este L2. conc(aPrim1|Rest1i, Lista2, aPrim1|Rest3i) :- conc(Rest1, Lista2, Rest3). % lista rezultata este primul element
% al sublistei curente din L1 concatenat
% cu lista intoarsa de apelul recursiv. ?- conc(aa, bi, ac, d, ei, L3).
L3 = aa, b, c, d, ei; no
?- conc(aa, bi, ac, d, ei, L3).
L3 = aa, b, c, d, ei. % “.” si Enter cand nu cautam alte solutii yes
?- conc(L1, ac, d, ei, aa, b, c, d, ei).
L1 = aa, bi; no
?- conc(aa, bi, L2, aa, b, c, d, ei).
L2 = ac, d, ei; no
?- conc(L1, L2, aa, bi).
L1 = a i, L2 = aa, bi;
L1 = aai, L2 = abi;
L1 = aa, bi, L2 = a i; no
Se observa ca pentru cazul in care predicatul de concatenare are un singur argument neinstantiat exista o singura solutie, iar pentru cazul in care primele doua argumente sunt neinstantiate (variabile) se obtin mai multe solutii, corespunzatoare tuturor variantelor de liste care prin concatenare genereaza cea de a treia lista.
5. Urmatorul exemplu defineste predicatul de testare a existentei unei sortari in ordine crescatoare a elementelor unei liste de intregi. Predicatul reuseste daca elementele listei sunt sortate crescator si esueaza in caz contrar.
% sortcresc(Lista) sortcresc(a i). % lista vida se considera sortata sortcresc(a _ i). % lista cu un singur element este sortata sortcresc(aX, Y | Resti) :- X = < Y, sortcresc(aY | Resti).
?- sortcresc(a1, 2, 3, 4i). yes
?- sortcresc(a1, 3, 5, 4i). no
?- sortcresc(a i). yes
Daca se considera ca lista vida nu este o lista sortata crescator atunci se poate elimina faptul: sortcresc(a i). din definitia predicatului sortcresc, comportarea lui pentru liste diferite de lista vida ramanand aceeasi.
Observatii:
• Exemplul 3 pune in evidenta o facilitate deosebit de interesanta a limbajului Prolog, respectiv puterea generativa a limbajului. Predicatul membru poate fi utilizat atat pentru testarea apartenentei unui element la o lista, cat si pentru generarea, pe rand, a elementelor unei liste prin resatisfacere succesiva. In anumite contexte de utilizare aceasta facilitate poate fi folositoare, iar in altele ea poate genera efecte nedorite atunci cand predicatul membru este utilizat in definirea altor predicate, asa cum se va arata in partea a doua a lucrarii.
• Aceeasi capacitate generativa a limbajului Prolog poate fi observata si in Exemplul 4 unde in functie de combinatiile de argumente instantiate si neinstantiate, predicatul conc poate produce rezultate relativ diferite.
• La definirea unui predicat p care va fi utilizat in definirea altor predicate trebuie intotdeauna sa se analizeze numarul de solutii si solutiile posibile ale predicatului p. Acest lucru este necesar deoarece daca p apare intr o conjunctie de scopuri p1,…, pi 1, p ,pi+1,…, pn si unul dintre scopurile pi+1,…, pn esueaza, mecanismul de backtracking din Prolog va incerca resatisfacerea scopului p. Numarul de solutii si solutiile scopului p influenteaza astfel, in mod evident, numarul de solutii si solutiile conjunctiei de scopuri p1,…, pi 1, p ,pi+1,…, pn. Exemple in acest sens si modalitati de reducere a numarului total de solutii ale unui corp vor fi prezentate in Sectiunea 4.2.
3 Limbajul Prolog si logica cu predicate de ordinul I
Limbajul Prolog este un limbaj de programare logica. Desi conceput initial pentru dezvoltarea unui interpretor de limbaj natural, limbajul s-a impus ca o solutie practica de construire a unui demonstrator automat de teoreme folosind rezolutia. Demonstrarea teoremelor prin metoda rezolutiei necesita ca axiomele si teorema sa fie exprimate in forma clauzala, adica o disjunctie de literali, unde un literal este un predicat sau un predicat negat. Pentru detalii despre notiunea de clauza si modul de transformare a unei formule din logica cu predicate de ordinul I in forma clauzala se poate consulta aFlo93i. Sintaxa si semantica limbajului Prolog permit utilizarea numai a unei anumite forme clauzale a formulelor bine formate: clauze Horn distincte.
Deoarece faptele si regulile Prolog sunt in forma clauzala, forma particulara a clauzelor fiind clauze Horn distincte, ele se mai numesc si clauze Prolog.
Definitie. Se numeste clauza Horn o clauza care contine cel mult un literal pozitiv. O clauza Horn poate avea una din urmatoarele patru forme:
(1) o clauza unitara pozitiva formata dintr un singur literal pozitiv (literal nenegat);
(2) o clauza negativa formata numai din literali negati;
(3) o clauza formata dintr un literal pozitiv si cel putin un literal negativ, numita si clauza Horn mixta;
(4) clauza vida ( ? ).
Definitie. Se numeste clauza Horn distincta o clauza care are exact un literal pozitiv, ea fiind fie o clauza unitara pozitiva, fie o clauza Horn mixta.
Clauzele Horn unitare pozitive se reprezinta in Prolog prin fapte, iar clauzele Horn mixte prin reguli. O clauza Horn mixta de forma:
?S1 ? ?S2 ?…? ?Sn ? S se exprima in Prolog prin regula:
S :- S1, S2, …Sn.
Semnificatia intuitiva a unei reguli Prolog are un corespondent clar in logica cu predicate de ordinul I daca se tine cont de faptul ca o clauza Horn mixta poate proveni din urmatoarea formula bine formata:
S1 ? S2 ?…? Sn ? S
Variabilele din clauzele distincte se transforma in variabile Prolog, constantele din aceste formule in constante Prolog, iar functiile pot fi asimilate cu structuri Prolog. Deci argumentele unui predicat Prolog au forma termenilor din calculul cu predicate de ordinul I.
Exemple:
1. Fie urmatoarele enunturi: Orice sportiv este puternic. Oricine este inteligent si puternic va reusi in viata. Oricine este puternic va reusi in viata sau va ajunge bataus. Exista un sportiv inteligent. Gelu este sportiv. Exprimand enunturile in logica cu predicate de ordinul I se obtin urmatoarele formule bine formate:
A1. (?x) (sportiv(x) ? puternic(x))
A2. (?x) (inteligent(x) ? puternic(x) ? reuseste(x))
A3. (?x) (puternic(x) ? (reuseste(x) ? bataus(x)))
A4. (?x) (sportiv(x) ? inteligent(x))
A5. Sportiv(gelu)
Axiomele se transforma in forma clauzala si se obtin urmatoarele clauze:
C1. ? sportiv(x) ? puternic(x)
C2. ? inteligent(x) ? I puternic(x) ? reuseste(x)
C3. I puternic(x) ? reuseste(x) ? bataus(x)
C4. sportiv(a)
C4'. inteligent(a)
C5. sportiv(gelu)
Clauzele C1, C2, C4, C4' si C5 pot fi transformate in Prolog deoarece sunt clauze Horn distincte, dar clauza C3 nu poate fi transformata in Prolog. Programul Prolog care se obtine prin transformarea acestor clauze este urmatorul: puternic(X) :- sportiv(X). reuseste(X) :- inteligent(X), puternic(X). sportiv(a). inteligent(a). sportiv(gelu).
2. Fie urmatoarele enunturi:
(a) Orice numar rational este un numar real.
(b) Exista un numar prim.
(c) Pentru fiecare numar x exista un numar y astfel incat .
Daca se noteaza cu prim(x) “x este numar prim”, cu rational(x) ”x este numar rational”, cu real(x) “x este numar real” si cu mai_mic(x, y) “x este mai mic decat y“, reprezentarea sub forma de formule bine formate in calculul cu predicate de ordinul I este urmatoarea:
A1. (?x) (rational(x) ? real(x))
A2. (?x) prim(x)
A3. (?x) (?y) mai_mic(x, y)
Reprezentarea in forma clauzala este:
C1. I rational(x) ? real(x)
C2. prim(a)
C3. mai_mic(x, mai_mare(x)) unde mai_mare(x) este functia Skolem care inlocuieste variabila y cuantificata existential. Forma Prolog echivalenta a acestor clauze este: real(X) :- rational(X). prim(a). mai_mic(X, mai_mare(X)). unde mai_mare(x) este o structura Prolog.
Este evident ca nu orice axioma poate fi transformata in Prolog si ca, dintr un anumit punct de vedere, puterea expresiva a limbajului este inferioara celei a logicii cu predicate de ordinul I. Pe de alta parte, limbajul Prolog ofera o multime de predicate de ordinul II, adica predicate care accepta ca argumente alte predicate Prolog, care nu sunt permise in logica cu predicate de ordinul I. Acest lucru ofera limbajului Prolog o putere de calcul superioara celei din logica clasica. Uneori, aceste predicate de ordinul II existente in Prolog pot fi folosite pentru a modela versiuni de programe Prolog echivalente cu o multime de axiome care nu au o reprezentare in clauze Horn distincte.
Se propune cititorului, dupa parcurgerea sectiunii urmatoare, sa revina la Exemplul 1 si sa incerce gasirea unei forme Prolog relativ echivalente (cu un efect similar) cu clauza C3.
Limbajul Prolog demonstreaza scopuri (teoreme) prin metoda respingerii rezolutive aFlo93i. Strategia rezolutiva utilizata este strategia de intrare liniara, strategie care nu este in general completa dar este completa pentru clauze Horn. Aceasta strategie este deosebit de eficienta din punct de vedere al implementarii si jutifica astfel forma restrictionata a clauzelor Prolog.
4 Structura de control a limbajului Prolog
In aceasta sectiune se prezinta in detaliu structura de control specifica sistemului Prolog. Spre deosebire de limbajele de programare clasice, in care programul defineste integral structura de control si fluxul de prelucrari de date, in Prolog exista un mecanism de control predefinit.
4.1 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. Se reaminteste ca o instanta a unei clauze este clauza de baza (clauza fara variabile) obtinuta prin instantierea variabilelor din clauza initiala. In aceste conditii semnificatia declarativa a unui program Prolog se poate defini precum urmeaza:
Definitie. Un scop S este adevarat intr un program Prolog, adica poate fi satisfacut sau deriva logic din program, daca si numai daca:
1. exista o clauza C a programului;
2. exista o instanta I a clauzei C astfel incat:
2.1. antetul lui I sa fie identic cu cel al lui S;
2.2. toate scopurile din corpul lui I sunt adevarate, deci pot fi satisfacute.
Observatii:
• In definitia de mai sus clauzele refera atat fapte cat si reguli Prolog. Antetul unei clauze este antetul regulii daca clauza este o regula Prolog (clauza Horn mixta) si este chiar faptul daca clauza este un fapt Prolog (clauza unitara pozitiva). Corpul unui fapt este considerat vid si un fapt este un scop care se indeplineste intotdeauna.
• In cazul in care intrebarea pusa sistemului Prolog este o conjunctie de scopuri, definitia anterioara se aplica fiecarui scop din conjunctie.
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 semnificatia procedurala este aceea ca cea de a doua defineste, pe langa relatiile logice specificate de program, si ordinea de satisfacere a scopurilor si subscopurilor. In prima sectiune a acestui capitol s a facut o prezentare informala a modalitatii procedurale de satisfacere a scopurilor in Prolog. In continuare se rafineaza aceasta comportare. Din punct de vedere procedural, un program Prolog poate fi descris de schema bloc prezentata in figura 3.

Figura 3. Comportarea procedurala a sistemului Prolog
Semnificatia procedurala a unui program Prolog poate fi descrisa de urmatorul algoritm in care L = AS1, S2, …, SnS este lista de scopuri de satisfacut, iar B este lista de instantieri (unificari) ale variabilelor din scopuri, initial vida. Aceasta lista se va actualiza la fiecare apel.
Algoritm. Strategia de control Prolog
SATISFACE(L,B)
1. daca L = AS % lista vida atunci afiseaza B si intoarce SUCCES.
2. Fie S1 ? primul scop din L si p predicatul referit de S1. Parcurge clauzele programului, de la prima clauza sau de la ultimul marcaj fixat, asociat lui p, pana ce se gaseste o clauza C al carei antet unifica cu S1.
3. daca nu exista o astfel de clauza atunci intoarce INSUCCES.
4. Fie C de forma H :- D1,…,Dm, m?0. Plaseaza un marcaj in dreptul clauzei C, asociat lui p. (H contine predicatul p).
5. Redenumeste variabilele din C si obtine C' astfel incat sa nu existe nici o variabila comuna intre C' si L; C' este de tot forma H :- D1,…,Dm. cu redenumirile facute.
6. L’ ? A D1,…,Dm, S2,…,Sn S % daca C este fapt, atunci L se va reduce
7. Fie B1 instantierea variabilelor care rezulta din unificarea lui S1 cu H.
8. Substituie variabilele din L’ cu valorile date de B1 si obtine:
L” ? A D1’,…,Dm’, S2’,…,Sn’ S.
9. B ? B ? B1.
10. daca SATISFACE(L”, B)=SUCCES atunci afiseaza B si intoarce SUCCES.
11. repeta de la 1. sfarsit
Observatii:
• Algoritmul de mai sus reprezinta de fapt implementarea strategiei rezolutive de intrare liniara utilizata de limbajul Prolog, pentru care se impune o ordine prestabilita de considerare a clauzelor.
• Algoritmul arata functionarea sistemului pentru gasirea primei solutii.
• Indicatorul SUCCES/INSUCCES corespunde raspunsurilor de yes, respectiv no, date de sistemul Prolog la incercarea de satisfacere a unei liste de scopuri.
Urmatoarele doua exemple pun in evidenta diferenta dintre semnificatia declarativa si semnificatia procedurala a programelor Prolog. Primul exemplu este un scurt program care defineste relatiile de parinte si stramos existente intre membrii unei familii. Se dau patru definitii posibile ale relatiei de stramos, str1, str2, str3 si str4, toate fiind perfect corecte din punct de vedere logic, deci din punct de vedere a semnificatiei declarative a limbajului.
% parinte(IndividX, IndividY)
% stramos(IndividX, IndividZ) parinte(vali, gelu). parinte(ada, gelu). parinte(ada, mia). parinte(gelu, lina). parinte(gelu, misu). parinte(misu, roco). str1(X, Z) :- parinte(X, Z). str1(X, Z) :- parinte(X, Y), str1(Y, Z).

% Se schimba ordinea regulilor: str2(X, Z) :- parinte(X, Y), str2(Y, Z). str2(X, Z) :- parinte(X, Z).

% Se schimba ordinea scopurilor in prima varianta: str3(X, Z) :- parinte(X, Z). str3(X, Z) :- str3(X, Y), parinte(Y, Z).

% Se schimba atat ordinea regulilor, cat si ordinea scopurilor: str4(X, Z) :- str4(X, Y), parinte(Y, Z). str4(X, Z) :- parinte(X,Z).

Figura 4. Arborele genealogic definit de programul Prolog
Figura 4 prezinta arborele genealogic definit de faptele Prolog anterioare. In raport cu semantica declarativa a limbajului se pot schimba, fara a modifica intelesul logic, atat ordinea clauzelor care definesc relatia de stramos, cat si ordinea scopurilor in corpul regulii de aflare a stramosilor. Schimband ordinea clauzelor se obtine din predicatul str1 definitia alternativa a relatiei de stramos str2; schimband ordinea scopurilor din corpul regulii in varianta initiala se obtine definitia predicatului str3; si, schimband atat ordinea clauzelor, cat si ordinea scopurilor in regula, se obtine predicatul str4.
Comportarea programului folosind cele patru definitii alternative, daca se doreste aflarea adevarului relatiei de stramos pentru perechile (ada, misu) si (mia, roco), este cea prezentata in continuare.
?- str1(ada, misu). yes
Pentru acest scop, arborele de deductie este prezentat in figura 5.

Figura 5. Arborele de deductie a scopului str1(ada, misu)
?- str2(ada, misu). yes
?- str3(ada, misu). yes
Pentru scopul str3(ada, misu), arborele de deductie este cel prezentat in figura 6.

Figura 6. Arborele de deductie a scopului str3(ada, misu)
?- str4(ada, misu).
% bucla infinita; eventual mesaj de depasire a stivei
Pentru acest scop, arborele de deductie este cel prezentat in figura 7.

Figura 7. Arborele de deductie (infinit) a scopului str4(ada, misu)
Din punctul de vedere al semnificatiei procedurale, cele patru definitii nu sunt echivalente. Primele doua, str1 si str2, pot da raspuns pozitiv sau negativ la orice intrebare, dar str2 este mai ineficienta decat str1. Cititorul poate incerca trasarea arborelui de deductie al satisfacerii scopului str2(ada, misu) si compararea acestuia cu cel corespunzator satisfacerii scopului str1(ada, misu). Definitia str4 produce o bucla infinita datorita intrarii infinite in recursivitate. Este evident o definitie gresita din punct de vedere procedural. Definitia relatiei de stramos str3 este o definitie "capcana". Dupa cum se poate observa din arborele de deductie prezentat, raspunsul sistemului este afirmativ in cazul in care exista o relatie de stramos intre cele doua persoane argumente ale predicatului. In cazul in care o astfel de relatie nu exista, sistemul intra intr-o bucla infinita, cum ar fi, de exemplu, pentru persoanele mia si roco.
?- str1(mia, roco). no
?- str2(mia, roco). no
?- str3(mia, roco).
% bucla infinita; eventual mesaj de depasire a stivei
In acest caz, arborele de deductie al scopului str3(mia, roco) este prezentat in figura 8. 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.

Figura 8. Arbore de deductie infinit pentru un scop fals
Al doilea exemplu se refera la rezolvarea in Prolog a urmatoarei probleme. O maimuta se gaseste la usa unei camere si o banana se afla agatata de plafon in centrul camerei. Langa fereastra camerei se afla o cutie pe care maimuta o poate folosi pentru a se urca pe ea si a ajunge la banana. Maimuta stie sa faca urmatoarele miscari: sa mearga pe sol, sa se urce pe cutie, sa deplaseze cutia daca este langa cutie, sa apuce banana daca este pe cutie si cutia este in centrul camerei. Se cere sa se scrie un program Prolog care sa descrie aceasta problema si care sa poata raspunde daca, dintr o configuratie initiala specificata prin pozitia maimutei si a cubului, maimuta poate apuca banana dupa executia unei secvente de miscari.
Reprezentarea universului problemei in Prolog este specificata dupa cum urmeaza. Starea initiala este:
(1) Maimuta este la usa.
(2) Maimuta este pe sol.
(3) Cutia este la fereastra.
(4) Maimuta nu are banana. si poate fi descrisa prin structura Prolog: stare(la_usa, pe_sol, la_fereastra, nu_are_banana)
Starea finala este aceea in care maimuta are banana stare( _ , _ , _ , are_banana)
Miscarile cunoscute de maimuta, deci operatorii de tranzitie dintr o stare in alta, sunt:
(m1) Apuca banana. apuca
(m2) Urca pe cutie. urca
(m3) Muta cutia. muta(Pozitia1, Pozitia2)
(m4) Merge (maimuta se deplaseaza pe sol). merge(Pozitia1, Pozitia2) si sunt reprezentate prin structurile Prolog indicate la dreapta miscarilor.
Dintr o anumita stare numai anumite miscari sunt permise. De exemplu, maimuta nu poate apuca banana decat daca este urcata pe cutie si cutia este in centrul camerei, adica sub banana. Miscarile permise pot fi reprezentate in Prolog prin predicatul de deplasare depl cu trei argumente: depl(Stare1, Miscare, Stare2) care transforma problema din starea Stare1 in starea Stare2 prin efectuarea miscarii legale Miscare in starea Stare1. Se observa ca reprezentarea aleasa este o reprezentare a problemei folosind spatiul starilor aFlo93i.
Solutia problemei este completata prin adaugarea predicatului poatelua(Stare) care va reusi daca maimuta poate ajunge din starea initiala Stare intr o stare finala in care poate lua banana, stare finala descrisa de: poate_lua(stare( _ , _ , _ , are_banana)).
Programul Prolog complet este prezentat in continuare.
% Structura stare:
% stare(poz_o_maimuta, poz_v_maimuta, poz_cub, are_nu_are_banana)
% Miscari admise: apuca, urca, muta(Pozitia1, Pozitia2), merge(Pozitia1, Pozitia2),
% reprezentate tot prin structuri.
% Predicate:
% depl(Stare1, Miscare, Stare2)
% poate_lua(Stare) depl(stare(la_centru, pe_cutie, la_centru, nu_are_banana), apuca, stare(la_centru, pe_cutie, la_centru, are_banana)). depl(stare(P, pe_sol, P, H), urca, stare(P, pe_cutie, P, H)). depl(stare(P1, pe_sol, P1, H), muta(P1, P2), stare(P2, pe_sol, P2, H)). depl(stare(P1, pe_sol, B, H), merge(P1, P2), stare(P2, pe_sol, B, H)). poate_lua(stare( _ , _ , _ , are_banana)). poate_lua(Stare1) :- depl(Stare1, Miscare, Stare2), poate_lua(Stare2).

La intrebarea
?- poate_lua(stare(la_usa, pe_sol, la_fereastra, nu_are_banana)). yes sistemul raspunde afirmativ: maimuta este fericita si mananca banana.
O analiza atenta a programului conduce la concluzia ca programul da solutii numai pentru anumite situatii. In primul rand, strategia de control a miscarilor maimutei este impusa de ordinea clauzelor care definesc predicatul depl. Astfel, maimuta prefera intai sa apuce, apoi sa urce, apoi sa mute cubul si numai la urma sa mearga prin camera. Daca clauza corespunzatoare miscarii merge(Pozitia1, Pozitia2) ar fi fost pusa ca prima clauza in definitia predicatului de deplasare, maimuta ar fi mers la infinit prin camera fara sa mai ajunga sa mute cubul sau sa apuce banana. Chiar pentru ordinea data a clauzelor, daca se pune intrebarea
?- poate_lua(stare(X, pe_sol, la_fereastra, nu_are_banana)). deci daca intereseaza din ce pozitii maimuta poate lua banana, rezolvarea data nu este total satisfacatoare deoarece programul are o infinitate de solutii. La cererea repetata a unei solutii, se va afisa intotdeauna valoarea:
X = la_fereastra
Considerand din nou modelul spatiului starilor, se observa ca in acest caz este vorba de un spatiu de cautare de tip graf in care o aceeasi stare poate fi descoperita si redescoperita la infinit prin parcurgerea unui ciclu de tranzitii de stari in acest graf. Asa cum este aratat in aFlo93i, astfel de cazuri trebuie tratate prin introducerea unor liste de stari parcurse (listele FRONTIERA si TERITORIU) care sa impiedice parcurgerea repetata a unor stari deja parcurse.
Pericolul de aparitie a unor cicluri infinite datorita parcurgerii unui spatiu de cautare graf nu este specific limbajului Prolog si poate sa apara in orice implementare, in aceste cazuri. Ceea ce este neobisnuit in raport cu alte limbaje 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. Rezolvarea problemei ar mai trebui completata cu afisarea starilor si a miscarilor executate de maimuta pentru a ajunge in starea finala in care ea poate apuca banana. Modalitati de eliminare a ciclurilor infinite de tipul celor ce apar in aceasta problema vor fi discutate in partea a doua a lucrarii.
4.2 Controlul procesului de backtracking: cut si fail
Sistemul Prolog intra automat intr un proces de backtraking daca acest lucru este necesar pentru satisfacerea unui scop. Acest comportament poate fi in unele situatii deosebit de util, dar poate deveni foarte ineficient in alte situatii. Se considera urmatorul exemplu de program in care se definesc valorile unei functii: f(X, 0) :- X < 3. % 1 f(X, 2) :- 3 =< X, X < 6. % 2 f(X, 4) :- 6 =< X. % 3
La intrebarea:
?- f(1, Y).
Y = 0 sistemul raspunde indicand ca valoarea functiei pentru X=1 este Y=0. Daca se pune intrebarea formata din conjunctia de scopuri:
?- f(1, Y), 2 < Y. no sistemul semnaleaza esec. Arborii de deductie corespunzatori acestor raspunsuri sunt prezentati in figura 9.

Figura 9. Arborii de deductie a scopurilor f(1,Y) si f(1,Y),2 < Y
Se observa ca se incearca resatisfacerea primului scop cu regulile 2 si 3, desi acest lucru este evident inutil datorita semanticii acestor reguli. Cel care a scris aceste reguli poate cu usurinta constata ca, daca o valoare mai mica decat 3 pentru X duce la esecul scopului S din conjunctia de scopuri f(X, Y), S, este inutil sa se incerce resatisfacerea scopului f, deoarece aceasta nu este posibila aBra88i. Se poate impiedica incercarea de resatisfacere a scopului f(X, Y) prin introducerea predicatului cut.
Predicatul cut, notat cu atomul special !, este un predicat standard, fara argumente, care se indeplineste (este adevarat) intotdeauna si nu poate fi resatisfacut.
Predicatul cut are urmatoarele efecte laterale:
• La intalnirea predicatului cut toate selectiile facute intre scopul antet de regula si cut sunt "inghetate", deci marcajele de satisfacere a scopurilor sunt eliminate, ceea ce duce la eliminarea oricaror altor solutii alternative pe aceasta portiune. O incercare de resatisfacere a unui scop intre scopul antet de regula si scopul curent va esua.
• Daca clauza in care s a introdus predicatul cut reuseste, toate clauzele cu acelasi antet cu aceasta, care urmeaza clauzei in care a aparut cut vor fi ignorate. Ele nu se mai folosesc in incercarea de resatisfacere a scopului din antetul clauzei care contine cut.
• Pe scurt, 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. Daca D1, …, 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.
Utilizand predicatul cut, definitia functiei f(X, Y) poate fi rescrisa mult mai eficient astfel: f(X, 0) :- X < 3, !. f(X, 2) :- 3 =< X, X < 6, !. f(X, 4) :- 6 =< X.
Predicatul cut poate fi util in cazul in care se doreste eliminarea unor pasi din deductie care nu contin solutii sau eliminarea unor cai de cautare care nu contin solutii. El permite exprimarea in Prolog a unor structuri de control de tipul: daca conditie atunci actiune1 altfel actiune2 astfel: daca_atunci_altfel(Cond, Act1, Act2) :- Cond, !, Act1. daca_atunci_altfel(Cond, Act1, Act2) :- Act2.
Se observa insa ca exista doua contexte diferite in care se poate utiliza predicatul cut: intr un context predicatul cut se introduce numai pentru cresterea eficientei programului, caz in care el se numeste cut verde; in alt context utilizarea lui cut modifica semnificatia procedurala a programului, caz in care el se numeste cut rosu.
Exemplul de definire a functiei f(X, Y) cu ajutorul lui cut este un exemplu de cut verde. Adaugarea lui cut nu face decat sa creasca eficienta programului, dar semnificatia procedurala este aceeasi, indiferent de ordinea in care se scriu cele trei clauze.
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. Introducerea unui cut rosu modifica corespondenta dintre semnificatia declarativa si semnificatia procedurala a programelor Prolog.
Se considera exemplul de definire a predicatului de aflare a minimului dintre doua numere, in urmatoarele 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).
In definitia predicatului min1 se utilizeaza un cut verde; el este pus pentru cresterea eficientei programului, dar 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 evident incorect pentru valori X < Y.
In anumite cazuri efectul introducerii predicatului cut poate fi mai subtil. Se considera din nou definitia predicatului membru: membru(X, aX | _i). membru(X, a _ |Yi) :- membru(X, Y). si o definitie alternativa membru1(X, aX| _i) :- !. membru1(X, a _ |Yi) :- membru1(X, Y).
Introducerea predicatului cut in definitia primei clauze a predicatului membru1 este justificata datorita cresterii eficientei programului. Odata ce s a descoperit ca un element este membru al unei liste, este inutila incercarea de resatisfacere a scopului. Cu toate acestea predicatul cut de mai sus nu este un cut verde, deoarece el schimba comportarea programului in cazul in care se pun intrebari in care X este variabila neinstantiata in predicatele membru si membru1.
?- membru(X, aa, b, ci).
X = a;
X = b;
X = c; no trei solutii pentru membru
?- membru1(X, aa, b, ci).
X = a; no o solutie pentru membru1.
Efectul introducerii predicatului cut asupra semnificatiei declarative a programelor Prolog poate fi rezumat astfel: p :- a, b. % Semnificatia declarativa este: p :- c. % (a ? b) ? c
% indiferent de ordinea