5 Mediul ARITY Prolog n4c4cl
In aceasta sectiune se prezinta comenzile de editare si depanare din mediul de programare ARITY Prolog si predicatele predefinite in aceasta versiune.
5.1 Generalitati
Pentru a putea lucra cu editorul din ARITY Prolog, trebuie inserata in fisierul config.sys linia de comanda DEVICE=C:DOS\ANSI.SYS /K, daca se utilizeaza MS DOS sau Windows 3.x, respectiv linia DEVICE=C:\95\COMMAND\ANSI.SYS /K, daca se utilizeaza Windows 95.
Unele din optiunile din meniurile ARITY Prolog sunt echivalente cu combinatii de taste. In aceste cazuri, ele vor fi specificate intre paranteze, alaturi de combinatiile echivalente. Pentru a selecta un meniu se tasteaza combinatia Alt + prima litera a numelui. Selectarea unei optiuni dintr un meniu se face tastand litera evidentiata din numele optiunii, sau folosind combinatia de taste asociata (daca exista). Atunci cand, intr un meniu, dupa numele unei optiuni urmeaza trei puncte, inseamna ca, eventual, utilizatorul mai are de completat o cutie de dialog. Se poate naviga cu Tab sau Shift + Tab intre campurile, butoanele si listele cutiei de dialog, iar in cadrul campurilor si listelor se poate naviga cu tastele cu sageti (?, ?, ? si ?). O optiune din meniu poate fi oricand parasita tastand Esc.
5.2 Comenzile editorului
Editorul are doua moduri de editare: inserare sau suprascriere de caractere. Trecerea de la un mod la altul se face cu tasta Ins. Deplasarea cursorului si pozitionarea pe ecran se pot face cu urmatoarele taste sau combinatii de taste:
Sageata la stanga ? Un caracter la stanga.
Sageata la dreapta ? Un caracter la dreapta.
Sageata in sus ? O linie in sus.
Sageata in jos ? O linie in jos.
Ctrl + ? Un cuvant la stanga.
Ctrl + ? Un cuvant la dreapta.
Home Inceputul liniei.
End Sfarsitul liniei.
PageUp O pagina in sus.
PageDown O pagina in jos.
Ctrl + Home Inceputul fisierului.
Ctrl + End Sfarsitul fisierului
Ctrl + g Deplasare la linia specificata.
Selectarea, copierea si cautarea in text se fac astfel:
Backspace (?) Sterge un caracter la stanga cursorului.
Del Sterge un caracter la dreapta cursorului.
Shift + ?, ?, ? sau ? Selecteaza o portiune de text, incepand de la pozitia curenta a cursorului.
Ctrl + r (Undo) Restaureaza o linie la starea in care era cand cursorul a fost mutat pe ea.
Shift + Del (Cut) Sterge textul selectat si il muta in clipboard.
F2 (Copy) copiaza in clipboard textul selectat.
Shift + Ins (Paste) Copiaza textul din clipboard.
Del (Clear) Sterge textul selectat, fara a l copia in clipboard.
F4 (Find) Cauta un sir in text.
Ctrl + \ (Find Selected) Cauta in text un sir selectat anterior.
F3 (Repeat Last Find) Repeta ultima cautare.
F5 (Change) Cauta un sir specificat si il inlocuieste cu alt sir specificat.
Mediul ARITY consta dintr o fereastra principala (main window) si zece fisiere tampon (buffers). Clipboard ul este buffer ul 0, in buffer ele de la 1 incolo fiind incarcate fisierele cu cod Prolog. Interpretarea de catre ARITY Prolog a continutului unui buffer se numeste consultare. Operatiile posibile cu aceste fisire (meniul Buffers) sunt:
F6 (Go to) Buffer ul activ (in care se face editarea curenta) devine cel selectat.
F7 (Go to Last) Bufer ul anterior selectat devine activ.
Erase Buffer Sterge continutul buffer ului curent.
Reconsult Buffer Reconsulta continutul buffer ului curent.
Save on Exit Continutul buffer ului curent este salvat pe discul local atunci cand buffer ul devine inactiv (buffer ul este inchis, sau nu mai e activ pentru ca s a trecut in alt buffer sau in fereastra principala).
Reconsult on Exit Continutul buffer ului curent este reconsultat cand buffer ul devine inactiv (buffer ul este inchis, sau nu mai e activ pentru ca s a trecut in alt buffer sau in fereastra principala).
Indent Indenteaza o linie noua la fel cu linia anterioara in buffer ul curent.
Read Only Marcheaza buffer ul curent ca putand fi doar citit; buffer ul nu mai poate fi modificat.
Tastele functionale F1 ? F8 au asociate urmatoarele actiuni:
F1 (Help) Deschide fisierul cu informatii despre predicatele ARITY predefinite.
F2 (Copy) Copiaza in clipboard textul selectat.
F3 (Repeat Last Find) Repeta ultima cautare.
F4 (Search) Cautarea unui sir in text.
F5 (Change) Cauta un sir specificat si il inlocuieste cu alt sir specificat.
F6 (Go to) Buffer ul activ (in care se face editarea curenta) devine cel selectat.
F7 (Go to Last) Bufer ul anterior selectat devine activ.
F8 (Switch) Comutare din buffer ul activ in fereastra principala (main window) sau invers.
Meniul File:
Operatiile posibile cu fisiere sunt urmatoarele:
New Deschide un fisier nou intr un buffer nou.
Open File Deschide un fisier deja creat intr un buffer nou.
Merge File Deschide un fisier si il adauga la sfarsitul buffer ului curent.
Save File Salveaza buffer ul curent intr un fisier.
Save File As Salveaza buffer ul curent intr un fisier cu un nume nou.
Consult File Consulta un fisier fara sa il incarce intr un buffer.
Operatiile posibile cu baza de cunostinte ARITY Prolog sunt urmatoarele:
Restore Db Inchide toate fisierele deschise si apoi, pe baza informatiilor din fisierul api.idb, restaureaza baza de date a interpretorului si deschide fisierele deschise la atunci cand s a facut salvarea respectiva.
Restore Db From Inchide toate fisierele deschise si apoi, pe baza informatiilor din fisierul indicat de utilizator, restaureaza baza de date a interpretorului si deschide fisierele deschise la atunci cand s a facut salvarea respectiva.
Save Db Salveaza baza de date a interpretorului si informatiile depre fisierele deschise in fisierul api.idb.
Save Db As Salveaza baza de date a interpretorului si informatiile depre fisierele deschise intr un fisier indicat de utilizator.
Dos Shell Lanseaza o sesiune MS DOS. Revenirea in mediul ARITY se face prin comanda exit.
Halt Parasire mediu de programare ARITY Prolog. Dintre fisierele deschise, modificate si nesalvate, utilizatorul este intrebat care trebuie salvate.

5.3 Informatiile de ajutor si depanare
Mediul ARITY Prolog are urmatoarele fisiere de ajutor (help files): arity.hlp (descrierea predicatelor predefinite), debug.hlp (descrierea comenzilor de depanare a programelor), editor.hlp (descrierea comenzilor mai importante ale editorului) si errors.hlp (descrierea mesajelor de eroare generate la consultarea unui buffer sau in executia unui predicat Prolog). Deoarece aceste fisiere sunt stocate in format ASCII, ele pot vizualizate atat din mediul ARITY Prolog, cat si cu un editor simplu de texte, putand fi listate la imprimanta. Din meniul Help se poate deschide fisierul arity.hlp, selectand optiunea Arity/Prolog, sau oricare din cele patru mentionate, cu optiunea Other Topics.
Notatia argumentelor din descrierea predicatelor predefinite (din help) denota semnificatia uzuala a acestora si este urmatoarea:
+ Argument Argumentul este, in mod normal, de intrare (trebuie specificat).
-Argument Argumentul este, in mod normal, de iesire (este calculat).
?Argument Argumentul poate fi de intrare sau de iesire.
S-a specificat “in mod normal”, deoarece, in unele cazuri, argumentele se pot folosi si altfel, folosind puterea generativa a limbajului Prolog. In exemplele descrise in sectiunile urmatoare se va folosi aceeasi conventie pentru indicarea argumentelor de intrare, iesire sau de ambele tipuri.
Meniul Info are doua optiuni Statistics si Modify Windows. Prima ofera informatii despre starea mediului de programare (stiva, cate operatii de garbage collection care au fost facute, memorie utilizata, etc.), iar a doua permite utilizatorului sa si creeze o interfata personalizata, stabilind proprietatile ferestrelor mediului de programare (culori, domensiuni, amplasare, titlu, etc.)
Meniul Debug are urmatoarele optiuni:
Spy Se specifica ce predicate trebuie urmarite la depanare
Trace On Activeaza depanatorul pentru trasarea predicatelor urmarite. Este echivalenta cu apelul predicatului trace.
Urmatoarele 4 optiuni specifica din ce punct al evolutiei predicatelor incep sa se afiseze informatii de trasare (care arata la ce structuri de date sunt legati parametrii acestora):
Call …de la inceputul satisfacerii predicatului.
Exit …de la terminarea satisfacerii predicatului.
Fail …de la esuarea satisfacerii predicatului.
Redo …de la inceputul resatisfacerii predicatului.
Trebuie mentionate doua lucruri: in ARITY Prolog, un predicat (scop) este vazut ca o cutie neagra (black box) cu patru porturi, doua de intrare: call, redo si doua de iesire exit, fail. Reconsultarea unui fisier in timpul depanarii unui predicat definit in acesta duce la rezultate imprevizibile, soldandu se de obicei cu blocarea definitiva a mediului de programare si chiar a calculatorului. De aceea, inainte de a reconsulta un fisier, este indicat sa se opreasca eventuala sesiune de depanare in curs de desfasurare.
In timpul depanarii apare o fereastra de depanare in care sunt afisate informatiile de trasare si in care pot fi introduse urmatoarele comenzi:
Space (toggle window) Comutare intre fereastra depanatorului si fereastra aplicatiei.
; (redo) Dupa un exit, pentru a forta resatisfacerea (redo) pentru scopul curent.
@ (accept goal) Permite apelul oricarui scop Prolog, cu reintoarcere imediata in depanator dupa terminarea scopului. a (abort) Terminare fortata a programului (abort) si reintoarcere la prompter ul interpretorului. Aceasta comanda este indicata in locul comenzii Ctrl + c. b (break) Se intra pe un nivel de break, adica se obtine un prompter de interpretor, fara a intrerupe programul depanat. Revenirea de pe nivelul de break si continuarea depanarii se fac cu Ctrl + z. Pentru fiecare nivel nou de break interpretorul adauga inca un semn de intrebare la prompter. De exemplu, pe nivelul al treilea, prompter ul este “????-“. c sau Enter (creep) Depanatorul trece la urmatorul port (punct de trasare). Daca portul este marcat ca urmarit in trasare, depanatorul se opreste si asteapta noi comenzi, altfel merge mai departe. d (display goal) Afiseaza scopul curent de satisfacut, folosind predicatul display. e (exit interpreter) Parasire interpretor si revenire la prompter ul DOS. f (fail goal) Forteaza esuarea scopului curent. Este folositor daca utilizatorul stie deja ca scopul curent va esua. h (help) Ofera informatii despre comenzile de depanare. l (leap) Depanatorul va sari la urmatorul punct de trasare. n (notrace) Dezactiveaza depanatorul. Aceasta comanda este echivalenta apelul predicatului notrace. q (quasi skip) Depanatorul sare la portul de exit sau fail al scopului curent. Daca insa exista un punct de trasare in scop, depanatorul se va opri la el. Acesta comanda se poate folosi numai dupa un call sau redo pentru un scop. (Vezi si comenzile s si z.) s sau Esc (skip) Sare la portul de exit sau fail, dupa cum exista sau nu puncte de trasare in cadrul scopului. Acesta comanda se poate folosi numai dupa un call sau redo pentru un scop. (Vezi si comenzile q si z.)
w (write goal) Scrie scopul curent, apeland predicatul write. x (bach to choice point) Aceasta comanda poate fi folosita la un port fail sau redo. Ea forteaza depanatorul sa continue esuarea pana cand este atins un port call sau exit. Desi in acest caz depanatorul nu se opreste sa accepte comenzi, depanatorul afiseaza cate un mesaj pentru fiecare port prin care trece. z (zip) Sare la portul de exit sau fail, dupa cum alte puncte de trasare sunt puse in scopul curent. Executia nu pastreaza informatie de depanare pentru punctele de backtracking din scop, fiind mai rapida si mai putin consumatoare de memorie. Acesta comanda se poate folosi numai dupa un call sau redo pentru un scop. (Vezi si comenzile q si s.)

5.4 Sintaxa ARITY Prolog
In aceasta sectiune se reiau elementele sintactice de baza din Prolog prezentate in prima sectiune, aratand particularitatile sintactice ale limbajului ARITY Prolog. Clasificarea obiectelor din ARITY Prolog este prezentata in figura 10.

Figura 10. Clasificarea obiectelor din ARITY Prolog
Un atom este un identificator care incepe cu litera mica si se continua cu orice insiruire de litere mici, litere mari, cifre sau underscore “_” . Daca se doreste ca atomul sa inceapa cu litera mare sau sa contina caractere speciale, atunci atomul se incadreaza intre caractere apostrof.
Exemple de atomi: dana nil x25 x_25 x_25AB x_ x__y domnul_popescu
'Ivan Bratko'
'<<------>>'
Reprezentarea sirurilor depinde de implementarea Prolog. In ARITY Prolog, interpretor care se aliniaza la standardul Edinbourg Prolog, sirurile se reprezinta intre caractere $.
Exemple de siruri de caractere:
$Constantin Noica$
$<<-------->>$
Diferenta dintre siruri si atomi este urmatoarea: sirurile au o reprezentare interna mai relaxata si nu pot fi folosite pe post de atomi, in timp ce atomii au de obicei reprezentari interne consumatoare de memorie in ideea ca ei trebuie regasiti rapid, cautarile Prolog facandu se in general dupa acesti atomi.
Un numar intreg este un sir de cifre zecimale, eventual precedate de un semn. Exemple de numere intregi: 1 +23 1515 0 -97. Numerele reale depind de implementarea de Prolog. In general ele sunt reprezentate intr o forma similara celor din limbaje gen Pascal, C, etc. Exemple de numere reale: 3.14 -0.0035 100.2 +12.02
La fel ca si in Prolog standard, o variabila este un sir de litere, cifre sau underscore ( _ ) care incepe cu litera mare sau underscore. Exemple de variabile:
X
Rezultat
Obiect1
Lista_de_nume
_x23
_23
In Prolog exista situatii in care o variabila apare o singura data intr o regula, caz in care nu avem nevoie de un nume pentru ea, deoarece nu este referita decat intr un singur loc. De exemplu, daca dorim sa scriem o regula care ne spune daca cineva este fiul cuiva, o solutie ar fi: este_fiu(X) :- parinte(Z, X).
Se observa ca s-a denumit cu Z un parinte anonim. In acest caz, nu intereseaza cine apare pe post de parinte. Pentru a nu incarca regulile cu nume inutile care pot distrage atentia si ingreuia citirea programelor, se pot considera astfel de variabile ca anonime, notate cu underscore “_”. Deci regula anterioara se poate rescrie astfel: este_fiu(X) :- parinte( _ , X).
Variabilele din Prolog nu sunt identice ca semnificatie cu variabilele Pascal sau C, fiind mai curand similare cu variabilele in sens matematic. O variabila, odata ce a primit o valoare, nu mai poate fi modificata. Acest lucru elimina efectele laterale care sunt permise in limbajele procedurale. O variabila Prolog neinstantiata semnifica ceva necunoscut. Pentru structurile de date care nu sunt variabile si care au nume, numele lor incepe cu minuscula, urmata de litere, cifre sau underscore.
Obiectele structurate, numite pe scurt structuri, sunt acele obiecte formate din mai multi constituenti sau componente. Componentele pot fi la randul lor structuri. Pentru a mixa constituentii intr un singur obiect avem nevoie de un functor. De exemplu, daca dorim reprezentarea unui obiect structurat data, el poate fi: data(24, august, 1997).
In acest caz, componentele sunt: 24, august si 1997, iar liantul este functorul data. Functorul poate fi orice atom. Constituentii pot fi orice obiect Prolog. Sa vedem un exemplu de obiect compus din alte obiecte compuse.
Fie tipul punct(X, Y). Atunci tipul segment poate fi reprezentat ca segment(P1, P2). De exemplu, un segment, avand capetele in punctele (1, 1) si (2, 3), poate fi reprezentat astfel: segment(punct(1, 1), punct(2, 3)).
Exista si cazuri in care un obiect poate avea constituenti compusi de adancime variabila. Astfel se ajunge la al doilea tip de recursivitate in Prolog, si anume, recursivitatea obiectelor. De exemplu, un arbore binar, cu chei numerice poate fi definit astfel:
1) Nodul vid este un arbore; putem nota acest nod vid prin constanta nil;
2) Un nod frunza este un arbore, de exemplu nod(15, nil, nil);
3) Un nod cu succesor stang si succesor drept este un arbore, de exemplu nod(20, ArbStang, ArbDrept).
De exemplu, reprezentarea in Prolog a arborelui

este nod(1, nod(2, nod(4, nil, nil), nod(5, nod(7, nil, nil), nil)), nod(3, nil, nod(6, nil, nil)))
Asa cum s-a aratat in prima parte, un program Prolog este o insiruire de fapte (facts) si reguli (rules) care poarta denumirea de clauze (clauses). Faptele si regulile au o structura comuna ceea ce permite sinteza dinamica de cod care este adaugat in baza de cunostinte. Un fapt poate fi privit ca o regula care are ca premisa (ipoteza) scopul true, care este adevarat intotdeauna. Astfel: fapt. este echivalent cu fapt :- true.
O regula fara antet, deci de forma:
:- scop. determina executia automata a scopului scop la reconsultarea bufer ului in care apare. Efectul este similar cu cel obtinut la introducerea in Main Window a intrebarii:
?- scop.
Exemple de intrebari: place(ellen, tennis). % lui ellen ii place tenisul place(john, fotbal). % lui john ii place fotbalul place(tom, baseball). % lui tom ii place baseball ul place(eric, inot). % lui eric ii place inotul place(mark, tenis). % lui mark ii place tenisul place(bill, X) :- place(tom, X). % lui bill ii place ce ii place lui tom

% Ce sporturi ii plac lui john?
?- place(john, X).
X = fotbal

% Cui ii place tenisul?
?- place(Y, tenis).
Y = ellen;
Y = mark

% Putem pune si intrebari particulare:
?- place(ellen, tenis). yes
?- place(ellen, fotbal). no
?- place(bill, baseball). yes

Urmeaza acum o serie de exemple necomentate pe care cititorul este indemnat sa le urmareasca si sa le inteleaga.
Ex1. Exprimati in Prolog urmatoarele fapte:
1) susan are un cal;
2) rex mananca carne;
3) aurul este pretios;
4) masina este un mercedes albastru cu capacitatea de cinci calatori.
Raspunsuri:
1) are(susan, cal).
2) mananca(rex, carne).
3) pretios (aur).
4) masina(mercedes, albastru, 5).
Ex2. Fie faptele: masina(mercedes, albastru, 5). masina(chrysler, rosu, 4). masina(ford, gri, 8). masina(datsun, rosu, 5).
Intrebarile:
1) Ce tipuri de masini au cinci locuri pentru calatori?
2) Ce masini sunt rosii? se scriu:
?- masina(Tip, _ , 5).
?- masina(Tip, rosu, _ ). iar regula:
X este o masina mare daca poate transporta cel putin 5 calatori. se scrie: masina_mare(X) :- masina(X, _ , Nr_calatori), Nr_calatori >= 5.
Ex3. Doi copii pot juca un meci intr un turneu de tenis daca au aceeasi varsta. Fie urmatorii copii si varstele lor: copil(peter, 9). copil(paul, 10). copil(chris, 9). copil(susan, 9).
Toate perechile de copii care pot juca un meci intr un turneu de tenis sunt calculate de predicatul: pot_juca(Pers1, Pers2) :- copil(Pers1, Varsta), copil(Pers2, Varsta), Pers1 \= Pers2.
Ex4. Sa scriem un program care sa ii gaseasca Anei un partener la bal. Ea doreste sa mearga cu un barbat care este nefumator sau vegetarian. Pentru aceasta dispunem de o baza de date cu informatii despre cativa barbatii: barbat(gelu). barbat(bogdan). barbat(toma). fumator(toma). fumator(dan). vegetarian(gelu).
Pentru a exprima doleantele Anei, vom scrie doua reguli:
1) Ana se intalneste cu X daca X este barbat si nu este fumator.
2) Ana se intalneste cu X daca X este barbat si este vegetarian.
Adica: ana_se_intalneste_cu(X) :- barbat(X), not(fumator(X)). ana_se_intalneste_cu(X) :- barbat(X), vegetarian(X).
5.5 Exercitii propuse
EP1. Se da o baza de fapte de forma: parinte(Parinte, Copil). barbat(Persoana). femeie(Persoana).
Se cere:
1) Sa se introduca cateva fapte de aceasta forma.
2) Sa se scrie regulile care definesc urmatoarele relatii de rudenie: tata(Tata, Copil). mama(Mama, Copil). fiu(Parinte, Copil). fiica(Parinte, Copil). bunic(Bunic, Copil). bunica(Bunica, Copil). nepot(Bunic, Copil). nepoata(Bunic, Copil).
3) Sa se puna urmatoarele intrebari:
Cine este parintele lui dan?
Cine este fiu?
Cine este bunic?
Cine este fiu si tata?

EP2. Sa se descrie principalele operatii logice in Prolog: not, or, and, xor, nor, nand. Pentru aceasta se considera faptele op_not(Variabila, Rezultat) si op_or(Variabila1,Variabila2, Rezultat).
Sa se scrie:
1) faptele necesare descrierii lui op_not si op_or;
2) regulile necesare constructiei celorlalti operatori pe baza lui op_not si op_or. Se cer reguli pentru: op_and(Var1, Var2, Rezultat). op_xor(Var1, Var2, Rezultat). op_nor(Var1, Var2, Rezultat). op_nand(Var1, Var2, Rezultat).
EP3. Se dau urmatoarele enunturi:
1) Oricine poate citi este literat.
2) Delfinii nu sunt literati.
3) Anumiti delfini sunt inteligenti.
Sa se demonstreze in Prolog ca: “Exista fiinte inteligente care nu pot citi”.
EP4. Se dau urmatoarele enunturi:
1) Fiecare om ii este devotat cuiva.
2) Oamenii incearca sa asasineze dictatorii fata de care nu sunt devotati.
3) Toti pompeienii erau romani.
4) Cezar era dictator.
5) Fiecare roman fie il ura pe Cezar, fie ii era devotat.
6) Marcus era pompeian.
7) Marcus era om.
8) Marcus a incercat sa il asasineze pe Cezar.
Sa se demonstreze in Prolog ca:
1) Marcus nu ii era devotat lui Cezar.
2) Marcus il ura pe Cezar.
6 Recursivitate in Prolog
Multe definitii de concepte sunt definitii recursive, asa cum este de exemplu definitia recursiva a notiunii de lista, arbore, sau cum a fost definitia recursiva a predicatului stramos prezentata in sectiunea 4.1. O serie de notiuni matematice, cum ar fi factorialul unui numar sau numerele lui Fibonacci au, de asemenea, o definitie recursiva.
6.1 Relatii recursive
Limbajul Prolog permite exprimarea definitiilor recursive prin definitia recursiva a predicatelor. Intr-o astfel de definitie trebuie intotdeauna sa se defineasca un fapt sau o regula care marcheaza punctul de oprire din recursivitate, deci cazul particular al definitiei recursive. Asa cum s-a aratat in sectiunea 4.4, trebuie analizate si aspecte privind directia de construire a solutiei.
Ex1. Sa se scrie un program care calculeaza n!, unde n! = 1 * 2 * 3 *...* n.
% fact(+N, - NFact) fact(0, 1). % Factorialul lui 0 este 1, punctul de oprire. fact(N,NFact) :- % Factorialul lui N este NFact daca:
N1 is N - 1, % calculam (N - 1) pentru al putea pasa ca argument fact(N1, Rezult), % fie Rezult factorial de (N - 1)
NFact is N * Rezult. % atunci NFact este N inmultit cu factorial de (N - 1)
Ex2. Sa se scrie un program care calculeaza termenul n din sirul lui Fibonacci: 1, 1, 2, 3, 5, 8, 13, 21, ..., in care f(n) = f(n - 1) + f(n - 2), pentru n ? 2.
% fib(+N, -F) fibo(1, 1). fibo(2, 1). fibo(N, F) :- N > 2, N1 is N - 1, N2 is N - 2, fibo(N1, F1), fibo(N2, F2), F is F1 + F2.
Aceasta implementare este ineficienta deoarece in calculul lui fibo(N, _ ), fibo(N-k, _ ) este apelat de k ori. Implementarea urmatoare elimina aceasta deficienta, deoarece predicatul fib, care calculeaza F = f(M), este apelat cu ultimii doi termeni F1 = f(M-2) si F2 = f(M-1), pentru M = 2?N: fibo(N, F) :- fib(2, N, 1, 1, F).
% predicat auxiliar fib(+M, +N, +F1, +F2, -F) fib(M, N, _ , F2, F2) :- M >= N. fib(M, N, F1, F2, F) : M < N, M1 is M + 1, F1plusF2 is F1 + F2, fib(M1, N, F2, F1plusF2, F).
Ex3. Sa se scrie un predicat care calculeaza cel mai mare divizor comun pentru doua numere. Se foloseste definitia recursiva a lui Euclid:
Fie a si b doua numere intregi pozitive. daca b = 0 atunci cmmdc(a, b) = a; altfel cmmdc(a, b) = cmmdc(b, r), unde r este restul impartirii lui a la b.
Implementarea in Prolog este:
% cmmdc(+A, +B, -Cmmdc) cmmdc(A, 0, A). cmmdc(A, B, Rez) :- B > 0, Rest is A mod B, cmmdc(B, Rest, Rez).
Ex4. Sa scriem predicatul divizor care testeaza daca un numar este divizibil cu altul. Pe baza acestui predicat sa se scrie predicatul prim care verifica daca un numar este prim.
% divizor(+A,+B)
% prin(+N) divizor(A, B) :- 0 is B mod A. prim(N):- Div is N - 1, nu_are_div(N, Div). nu_are_div(N, 1). nu_are_div(N, Divizor) :- not(divizor(Divizor, N)), DivNou is Divizor - 1, nu_are_div(N, DivNou).
Ex5. Predicatul rezolva(N) rezolva problema turnurilor din Hanoi cu N discuri.

% rezolva(+N) rezolva (N) :- hanoi(N, stanga, dreapta, mijloc). hanoi(0, _ , _ , _ ). hanoi(N, A, B, C) : N > 0, N1 is N - 1, hanoi(N1, A, C, B),
write($Din $), write(A), write($ pe $), write(B), nl, hanoi(N1, C, B, A).
6.2 Problema trezorierului
In aceasta sectiune si in sectiunile urmatoare ale capitolului se vor prezenta rezolvarile in Prolog ale cateva probleme clasice ce implica recursivitate. Fiecare problema este prezentata sub urmatoarea forma:
1) Enuntul problemei (ipoteze si concluzie);
2) Rescrierea enuntului sub forma de clauze Prolog;
3) Demonstratia concluziei prin formularea unei interogari corecte in Prolog.
Ipoteze:
1) Nici un membru al clubului nu are datorii la trezorierul clubului.
2) Daca un membru al clubului nu a platit taxa, atunci el are datorii la trezorierul clubului.
3) Trezorierul clubului este un membru al clubului.
Concluzie:
Trezorierul clubului a platit taxa.

% Ipoteza 1 fara_datorii(X) :- membru(X).
% Ipoteza 2 platit_taxa(X) :- fara_datorii(X).
% Ipoteza 3 membru(trezorier).
% Concluzia
% ?- platit_taxa(trezorier).
6.3 Problema parteneriatului
Ipoteze:
1) Tom este corect.
2) Bill nu este partener cu Tom.
3) Daca doua persoane X si Y sunt corecte, atunci X este partener cu Y.
4) Daca Bill nu este corect, atunci John este corect.
5) Daca o persoana X este partener cu Y, atunci si Y este partener cu X.
Concluzie:
John este partener cu Tom.

% Ipoteza 1 corect(tom).
% Ipoteza 2 not_partener(bill, tom).
% Ipoteza 3 partener(X, Y) :- corect(X), corect(Y), X \= Y.
% Ipoteza 4, se foloseste si ipoteza 3, inversata conform principiului reducerii
% la absurd: formula p ? q este echivalenta cu !q ? !p. corect(john) :- not_corect(bill). not_corect(X) :- not_ambii_corecti(X, Y), corect(Y). % din ipoteza 3 not_ambii_corecti(X, Y) :- not_partener(X, Y).
% Ipoteza 5
% Este reprezentata in definitia lui partener (ipoteza 3), care include simetria.
% Concluzia
% ?- partener(john, tom).
6.4 Problema vecinilor
Ipoteze:
1) Stefan este vecin cu Petre.
2) Stefan este casatorit cu o doctorita care lucreaza la Spitalul de Urgenta.
3) Petre este casatorit cu o actrita care lucreaza la Teatrul National.
4) Stefan este meloman si Petre este vanator.
5) Toti melomanii sunt sentimentali.
6) Toti vanatorii sunt mincinosi.
7) Actritele iubesc barbatii sentimentali.
8) Sotii au aceiasi vecini.
9) Casatoria si vecinatatea sunt relatii simetrice.
Concluzie:
Il iubeste sotia lui Petre pe Stefan?

% Ipoteza 1 vecin1(stefan, petre).
% Ipoteza 2 casatorit1(stefan, sotie_stefan). doctorita(sotie_stefan). lucreaza(sotie_stefan,urgenta).
% Ipoteza 3 casatorit1(petre, sotie_petre). actrita(sotie_petre). lucreaza(sotie_petre, national).
% Ipoteza 4 meloman(stefan). vanator(petre).
% Ipoteza 5 sentimental(X) :- meloman(X).
% Ipoteza 6 mincinos(X) :- vanator(X).
% Ipoteza 7 iubeste(X, Y) :- actrita(X), sentimental(Y).
% Ipoteza 8 vecin(X, Y) :- casatorit(X, Z), vecin(Z, Y).
% Ipoteza 9 vecin(X, Y) :- vecin1(X, Y). vecin(X, Y) :- vecin1(Y, X). casatorit(X, Y) :- casatorit1(X, Y). casatorit(X, Y) :- casatorit1(Y, X).
% Concluzia concluzie :- casatorit(petre, Sotie), iubeste(Sotie, stefan).
% ?- concluzie.
6.5 Problema unicornului
Problema unicornului este o problema celebra formulata de Lewis Carroll in cartea sa "Alice in tara minunilor".
Ipoteze:
1) Leul minte luni, marti si miercuri si spune adevarul in toate celelalte zile.
2) Unicornul minte joi, vineri si sambata si spune adevarul in toate celelalte zile.
3) Astazi Leul spune: "Ieri a fost una din zilele in care eu mint."
4) Tot astazi Unicornul spune: "Ieri a fost una din zilele in care eu mint."
Concluzie:
Ce zi este astazi? (Raspuns: joi).

Prima varianta:
% zilele saptamanii urmeaza(luni, marti). urmeaza(marti, miercuri). urmeaza(miercuri, joi). urmeaza(joi, vineri). urmeaza(vineri, sambata). urmeaza(sambata,duminica). urmeaza(duminica, luni).
% Ipoteza 1
% minte(Animal, Zi) - Animal minte in ziua Zi. minte(leu, luni). minte(leu, marti). minte(leu, miercuri).
% Ipoteza 2 minte(unicorn, joi). minte(unicorn, vineri). minte(unicorn, sambata).
% Ipotezele 3 si 4
% spune(Animal, Zi) - Animal spune adevarul in ziua Zi. spune(Animal, Azi) :- urmeaza(Ieri, Azi), minte(Animal, Ieri). posibil(Animal, Azi) :- spune(Animal, Azi), not(minte(Animal, Azi)). posibil(Animal, Azi) :- minte(Animal, Azi), not(spune(Animal, Azi)).
% Pregatire concluzie azi(Azi) :- posibil(leu, Azi), posibil(unicorn, Azi).
% Concluzia
% ?- azi(Azi).
A doua varianta:
% zilele saptamanii urmeaza(luni, marti). urmeaza(marti, miercuri). urmeaza(miercuri, joi). urmeaza(joi, vineri). urmeaza(vineri, sambata). urmeaza(sambata,duminica). urmeaza(duminica, luni).
% Ipoteza 1
% spune(Animal, Zi, Ce) - Ce spune Animal in fiecare Zi. spune(leu, luni, minciuna). spune(leu, marti, minciuna). spune(leu, miercuri, minciuna). spune(leu, joi, adevar). spune(leu,vineri, adevar). spune(leu, sambata, adevar). spune(leu, duminica, adevar).
% Ipoteza 2 spune(unicorn, luni, adevar). spune(unicorn, marti, adevar). spune(unicorn, miercuri, adevar). spune(unicorn, joi, minciuna). spune(unicorn, vineri, minciuna). spune(unicorn, sambata, minciuna). spune(unicorn, duminica, adevar).
% Ipotezele 3 si 4 enunt(Animal, Azi) :- urmeaza(Ieri, Azi), spune(Animal, Ieri, minciuna).
% adevarul - Ce inseamna ca minte, pentru Prolog; este un metapredicat. adevarul(Animal, Zi, Enunt, not(Enunt)) :- spune(Animal, Zi, minciuna). adevarul(Animal, Zi, Enunt, Enunt) :- spune(Animal, Zi, adevar).
% Pregatire concluzie azi(Azi) :- adevarul(leu, Azi, enunt(leu, Azi), Adevar1),
Adevar1, % sau call(Adevar1) adevarul(unicorn, Azi, enunt(unicorn, Azi), Adevar2),
Adevar2. % sau call(Adevar2)
% Concluzia
% ?- azi(Azi).
6.6 Exercitii propuse
Sa se rescriere enunturile urmatoarelor probleme sub forma de clauze Prolog si sa se demonstreze concluziile prin formularea unor interogari corecte in Prolog.
EP1. Ipoteze
1. Oricine poate citi este literat.
2. Delfinii nu sunt literati.
3. Anumiti delfini sunt inteligenti.
Concluzie
Exista fiinte inteligente care nu pot citi.

EP2. Ipoteze
1. Daca orasul X este legat de orasul Y prin drumul D si pot circula biciclete pe drumul D, atunci se poate merge de la X la Y.
2. Daca orasul X este legat de orasul Y prin drumul D, atunci si orasul Y este legat de orasul X prin drumul D.
3. Daca se poate merge de la X la Y si de la Y la Z, atunci se poate merge de la X la Z.
4. Orasul a este legat de orasul b prin drumul d1.
5. Orasul b este legat de orasul c prin drumul d2.
6. Orasul a este legat de orasul c prin drumul d3.
7. Pe drumul d1 pot circula biciclete.
8. Pe drumul d2 pot circula biciclete.
Concluzie
Se poate merge de la orasul a la orasul c.

EP3. Se inlocuieste ipoteza 8 de la EP2 cu “Pot circula biciclete fie pe drumul d1, fie pe drumul d3, dar nu pe ambele in acelasi timp.” Sa se demonstreze aceeasi concluzie.

EP4. Ipoteze
1. Marcus era om.
2. Marcus era pompeian.
3. Toti pompeienii erau romani.
4. Cezar era dictator.
5. Fiecare roman ii era devotat lui Cezar sau il ura.
6. Fiecare om ii este devotat cuiva.
7. Oamenii incearca sa ii asasineze pe dictatorii fata de care nu sunt devotati.
8. Marcus a incercat sa il asasineze pe Cezar.
Concluzii
1. Marcus nu ii era devotat lui Cezar.
2. Marcus il ura pe Cezar.
7 Prelucrarea listelor in Prolog
Structura de date lista este cea mai frecvent utilizata structura de date in programele Prolog. Acest capitol prezinta in detaliu lucrul cu liste in Prolog.
7.1 Predicate de prelucrare a listelor
Cele mai frecvente predicate utilizate in prelucrarea listelor sunt cel de apartenenta a unui element la o lista si concatenarea a doua liste, care au fost prezentate in prima parte a lucrarii. Reamintim aceste definitii: member(Elem, aElem|_i) :- !. member(Elem, a_|Resti) :- member(Elem, Rest). append(ai, L2, L2). append(aPrim1|Rest1i, Lista2, aPrim1|Rest3i) :- append(Rest1, Lista2, Rest3).
In continuare se prezinta o serie de alte predicate utile in prelucrarea listelor.
Eliminarea unui obiect dintr o lista. Sa scriem un predicat care elimina un obiect dintr o lista. Astfel, elim(a, aa, b, ci, L) va returna in L lista ab, ci. Implementarea in Prolog este:
% elim(+El,+Lista,-ListaRez) elim(X, aX | Resti, Rest). elim(X, aY | Resti, aY | Rest1i) :- elim(X, Rest, Rest1).
Conform acestei implementari, elim nu va elimina decat o aparitie a elementului cautat. Astfel, eliminarea lui a din lista aa,b,a,ci va genera doua solutii posibile:
?- elim(a, aa, b, a, ci, L).
L = ab, a, ci;
L = aa, b, ci; no
Dar este posibila si intrebarea “Ce liste din care se elimina a dau ca rezultat lista ab, ci?”:
?- elim(a, L, ab, ci).
L = aa, b, ci;
L = ab, a, ci;
L = ab, c, ai; no
Incluziunea listelor. Fie un predicat care este adevarat daca o lista este sublista alteia. De exemplu, sublist(ac, d, ei, aa, b, c, d, e, fi) este adevarat, iar sublist(ab, c, ei, aa, b, c, d, e, fi) este fals. Ne putem folosi de predicatul deja scris append. O lista S este sublista a listei L daca:
1) Exista o descompunere a lui L in L1 si L2 si
2) Exista o descompunere a lui L2 in S si L3.
Implementare:
% sublist(+SubLista,+Lista) sublist(S, L) :- append(L1, L2, L), append(S L3, L2).
Aceasta implementare are un mic defect: afiseaza lista vida de mai multe ori. Incercati sa aflati de ce. O varianta care elimina acest defect este subset: subset(ai, L). subset(aX | Resti, L) :- member(X, L), subset(Rest, L).
Liniarizarea listelor. Vom scrie predicatul liniar(ListaListe, Lista), unde ListaListe este o lista de elemente care pot fi randul lor liste, iar in Lista se construieste liniarizarea listei ListaListe:
% liniar(+Lista,ListaLiniarizata) liniar(ai , ai). liniar(aa i | Resti, Rez) :- liniar(Rest, Rez). liniar(aX | Resti, aX | Rezi) :- X \= ai, X \= a _ | _ i, liniar(Rest, Rez). liniar(aaX | Resti | RestListi, Rez) :- liniar(aX, Rest | RestListi, Rez).
Un exemplu de executie este:
?- liniar(a1, 2, a3, 4i, a5, a6, 7i, aa8i, 9iii, L).
L = a1, 2, 3, 4, 5, 6, 7, 8, 9i. yes
Predicatul descomp(N, Lista) primeste un numar intreg N si intoarce o lista factorilor primi ai numarului N; de exemplu: descomp(12, a2, 2, 3i) este adevarat.
% descomp(+N,?L) descomp(N, L) :- factp(N, L, 2). factp(1, a i, _ ). factp(N, aDivizor | Listai, Divizor) : N > 1, 0 is N mod Divizor, N1 is N // Divizor, factp(N1, Lista, Divizor). factp(N,Lista,Divizor) : N > 1, not(0 is N mod Divizor), D1 is Divizor + 1, factp(N, Lista, D1).
Predicatul palindrom(Lista) verifica daca o lista este palindrom. Un palindrom este o secventa care, daca este parcursa de la stanga la dreapta sau de la dreapta la stanga, este identica; de exemplu: aa, b, c, b, ai sau aa, b, c, c, b, ai.
% Idee: o lista este palindrom daca este egala cu inversa ei. palindrom(L) :- reverse(L, ai, L). reverse(ai, Acc, Acc). reverse(aX | Resti, Acc, L) :- reverse(Rest, aX | Acci, L).
7.2 Multimi
Multimile pot fi reprezentate in Prolog ca liste. Predicatul multime(L, M) transforma lista L in multimea M. multime(ai, ai). multime(aX | Resti, Rez) :- member(X, Rest), multime(Rest, Rez). multime(aX | Resti, aX | Rezi) :- not(member(X, Rest)), multime(Rest, Rez).
Predicatul de definire a intersectiei a doua liste prezentat in sectiunea 4.4 se poate aplica si pentru obtinerea intersectiei a doua multimi. Prezentam in continuare predicatul de determinare a reuniunii a doua multimi.
% reun(+L1,+L2,-L) reun(ai,L,L). reun(aX | Resti, L, Rez) :-member(X,L), reun(Rest,L,Rez). reun(aX | Resti, L, aX | Rezi) :-not member(X,L), reun(Rest,L,Rez).
7.3 Problema drumurilor
Fie o baza de date cu drumuri intre orase, de forma drum(oras1, oras2): drum(bucuresti, ploiesti). drum(bucuresti, cheia). drum(cheia, brasov). drum(brasov, bucuresti). drum(cheia, sinaia). drum(ploiesti, sinaia). drum(ploiesti, brasov).
Predicatul traseu(X, Y, T) este adevarat daca se poate ajunge de la orasul X la orasul Y, calculand si traseul T intre cele doua orase. Drumurile sunt bidirectional (daca exista un drum de la X la Y, atunci exista implicit un drum de la Y la X). member(X, aY | Ti) :- X == Y, ! ; member(X, T). traseu(Y, X) :- traseu(X, Y, aXi). traseu(Y, Y, Traseu) :- write(Traseu), nl. traseu(X, Y, Traseu) :-

(drum(X, Z) ; drum(Z, X)), not member(Z, Traseu), traseu(Z, Y, aZ | Traseui). traseu( _ , _ , _ ) :- write($Nu exista traseu.$), nl.

% cateva teste test : traseu(bucuresti, sinaia), traseu(sinaia, bucuresti), traseu(bucuresti, ploiesti), traseu(ploiesti, bucuresti), traseu(cheia, craiova).
Daca apelam predicatul test sistemul va raspunde:
?- test.
abucuresti, brasov, cheia, sinaiai
asinaia, ploiesti, bucurestii
abucuresti, brasov, cheia, sinaia, ploiestii
aploiesti, bucurestii
Nu exista traseu. yes
7.4 Exercitii propuse
EP1. Aflati care este defectul predicatului sublist.
EP2. Folosind predicatul elim, puneti intrebarea: “Ce elemente se pot elimina din aa, b, a, ci si ce lista rezulta in cazul fiecarei eliminari?”
EP3. Sa se defineasca si sa se exemplifice cu cate doua exemple in Prolog urmatoarele predicate de prelucrare a listelor:
1) invers(Lista, ListaInversata) - inverseaza elementele unei liste; sa se scrie doua variante ale predicatului de inversare a unei liste: o varianta in care lista inversata este calculata pe ramura de revenire din recursivitate si o varianta in care lista inversata este calculata pe ramura de avans in recursivitate.
2) reun(Lista1, Lista2, ListaRez) - produce ListaRez care contine reuniunea elementelor din Lista1 si din Lista2; se va da o implementere alternativa pe baza predicatului multime din sectiunea 7.2.
3) rotire(Lista, Directie, Nr, ListaRez) - roteste Lista cu un numar de Nr elemente la stanga (daca Directie = stg) sau la dreapta (daca Directie = dr), depunand rezultatul in ListaRez;
EP4. Sa se scrie predicatul Prolog substitutie(X, Y, L1, L2), unde L2 este rezultatul substituirii tuturor aparitiilor lui X din lista L1 cu Y, producand lista L2.
Ex: substi¬tutie(a, x, aa, ab,a,i ci, L2) va produce: L2 = ax, ab, xi, ci.
EP5. Sa se scrie predicatul imparte(L, L1, L2) care imparte lista L in doua subliste L1 si L2, care au un numar de elemente aproximativ egal, fara a calcula lungimea listei L.
Ex: imparte(aa, b, c, d, ei, L1, L2) va produce: L2 = aa, b, ci si L3 = ad, ei.
8 Mecanisme specifice Prolog
8.1 Exemple de utilizare a mecanismului cut
Reamintim functionarea mecanismului cut: sa denumim scop parinte scopul care identifica cu antetul clauzei ce contine cut. Cand cut este intalnit ca scop, el reuseste imediat, dar obliga sistemul sa ramana la toate optiunile facute intre momentul apelului scopului parinte si momentul intalnirii cut lui. Toate alternativele care raman intre scopului parinte si cut sunt ignorate. Sa investigam aceasta functionare pentru urmatorul exemplu:
C :- P, Q, R, !, S, T, U.
C :- V.
A :- B, C, D.
?- A.
Executia scopului C va fi afectata de cut astfel: procesul de backtracking va fi posibil pe lista de scopuri P, Q, R; totusi, indata ce cut ul este atins, toate solutiile alternative ale listei de scopuri P, Q, R sunt eliminate. Clauza alternativa despre C:
C :- V. va fi si ea ignorata. Procesul de acktracking va fi totusi inca posibil pe lista de scopuri S, T, U. Scopul parinte al clauzei care contine cut ul este scopul C din clauza:
A :- B, C, D.
Prin urmare cut ul va afecta doar executia scopului C. Pe de alta parte, el nu va fi vizibil in scopul A. Astfel, procesul de backtracking in cadrul listei de scopuri B, C, D va ramane activ indiferent de cut ul din clauza folosita pentru a satisface C.
Am definit predicatul care calculeaza maximul dintre doua numere (in prima parte) astfel:
% max(+X, +Y, -Max). max(X, Y, X) :- X >= Y. max(X, Y, Y) :- X < Y.
Cele doua reguli sunt mutual exclusive. Daca prima reuseste atunci a doua va esua. Daca prima esueaza, atunci a doua trebuie sa reuseasca. Prin urmare, o reformulare mai eficienta este posibila: daca X ? Y atunci Max = X altfel Max = Y.
Aceasta se scrie in Prolog utilizand cut astfel: max(X, Y, X) :- X >= Y, !. max( _ , Y, Y).
Sa vedem ce se intampla insa atunci cand dorim sa folosind puterea generativa a limbajului Prolog:
% max(?X, ?Y, ?Max) max(X, Y, X) :- X >= Y. max(X, Y, Y) :- X < Y. % max(?X, ?Y, ?Max) max(X, Y, X) :- X >= Y, !. max( _ , Y, Y).
?- max(X, 3, 4). X = 4 X = 4
?- max(X, 3, 3). X = 3 X = 3
?- max(3, X, 4). X = 4 X = 4
?- max(X, X, 3). X = 3 X = 3
Cazuri in care predicatul max trebuie sa esueze:
?- max(X, 3, 2). No no
?- max(3, X, 3). No X = 3
?- max(3, X, 2). No X = 2
?- max(X, Y, 3). No X = _0038 Y = 3
?- max(X, 3, X). no X = 3
?- max(3, X, Y). no X = _0038 Y = _0038
?- max(X, 3, Y). no X = _0038 Y = 3
Din exemplele prezentate se observa ca varianta mai “explicita” se comporta corect in toate cazurile, in timp ce varianta “eficienta” genereaza rezultate eronate. De aceea, inainte de a utiliza cut trebuie sa ne gandim in ce context si cum vor fi apelate predicatele in care el apare, deoarece adesea folosirea lui cut creste posibilitatea aparitiei erorilor de programare.
8.2 Negatia ca insucces
Faptul ca ceva nu este adevarat in Prolog poate fi exprimat explicit in Prolog utilizand predicatul special fail, care esueaza intotdeauna, fortand scopul parinte sa esueze. Enuntul “Maria iubeste toate animalele cu exceptia serpilor” se exprima in Prolog astfel: iubeste(maria, X) :- sarpe(X), !, fail. iubeste(maria, X) :- animal(X).
Prima regula va avea grija de serpi: daca X este sarpe atunci cut ul va impiedica backtracking ul (excluzand astfel a doua regula) si predicatul fail va cauza esuarea. Cele doua clauze pot fi compactate intr una singura astfel: iubeste(maria, X) :- sarpe(X), !, fail ; animal(X).
La fel se poate scrie un predicat care testeaza daca doua numere sunt diferite: diferite(X, X) :- !, fail. diferite( _ , _ ). sau: diferite(X, Y) :- X = Y, !, fail ; true.
Predicatul not este predefinit in ARITY Prolog ca un operator prefixat, astfel incat not(sarpe(X)) se poate scrie ca not sarpe(X). Exemplele anterioare se pot rescrie cu not astfel: iubeste(maria, X) :- animal(X), not(sarpe(X)). diferite(X, Y) :- not ( X = Y ).
Predicatul not functioneaza deoarece rationamentul Prolog se bazeaza pe ipoteza lumii inchise. Not ul definit prin esuare nu corespunde exact cu negatia din logica matematica. De aceea folosirea lui not trebuie facuta cu atentie.
In ARITY Prolog, mai exista un cut partial, numit snip “a! !i”, care specifica o lista de scopuri care sunt ignorate in backtracking. Fie scopul p definit prin regulile: p :- a, b, a! c, d, e !i, f, g. p :- t, u, v.
Daca scopurile a, b, c, d si e reusesc scopul parinte al lui p ramane fixat pe prima regula a lui p si prin backtracking se pot resatisface scopurile a, b, f si g. De asemenea, atat timp cat nu s au satisfacut toate scopurile din cadrul snip ului, pana la satisfacerea scopului e se pot resatisface prin backtracking scopurile a, b, c si d. Daca nu se poate satisface deloc f, dupa executia tuturor satisfacerilor scopurilor a, b, c si d, se trece la regula a doua a predicatului p.
Ca o aplicatie la cele discutate pana acum, iata trei exemple:
Ex1: Plasarea a opt regine pe o tabla de sah astfel incat ele sa nu se atace intre ele:
% solutie(?Solutie) solutie(ai). solutie(aX/Y | CelelalteReginei) : solutie(CelelalteRegine), member(Y, a1, 2, 3, 4, 5, 6, 7, 8i), not ataca(X/Y, CelelalteRegine).

% ataca(+Regina, +CelelalteRegine) - verifica daca Regina ataca CelelalteRegine ataca(X/Y, CelelalteRegine) : member(X1/Y1, CelelalteRegine),
(Y1 = Y; Y1 is Y + X1 - X; Y1 is Y - X1 + X).

% member(?X, ?Lista) - member generativ member(X, aX| _ i). member(X, a _ |Li) :- member(X, L).

% model de solutie model(a1/Y1, 2/Y2, 3/Y3, 4/Y4, 5/Y5, 6/Y6, 7/Y7, 8/Y8i).

% toate solutiile toate :- model(L), assert(count(1)), !,
( solutie(L), retract(count(N)), N1 is N + 1, assert(count(N1)),
write(N), write($.$), a! N < 10, tab(3) ; tab(2) !i, write(L), nl, fail
; retract(count( _ )), true).
Cut ul a fost introdus doar pentru eficienta (cut verde), iar parantezele care inchid disjunctia de conjunctii de scopuri au fost puse din cauza lui. Clauzele count(NumarSolutie) au fost folosite pentru numerotarea solutiilor, iar snip ul pentru indentarea lor. Predicatul predefinit tab(N) afiseaza N blank uri.
Ex2: Fie urmatoarele predicate: a(X) :- (X is 1; X is 2), tab(1), write(a(X)). b(X) :- X = 1, write($ !b$), !, fail ; write($ b$). c(X) :- X > 1, write($ !c$), !, fail ; write($ c$).

p :- nl, write(ap1i), a(X), a! b(X), fail !i, c(X). p :- nl, write(ap2i), a(X), a! b(X) !i, c(X). p :- nl, write(ap3i), a(X), a! b(X) !i, not c(X). p :- nl, write(ap4i).
La interogarea:
?- p. sistemul va raspunde:
ap1i a(1) !b a(2) b
ap2i a(1) !b a(2) b !c
ap3i a(1) !b a(2) b !c yes
Ex3. Sa scriem predicatul unifica(X, Y) care reuseste daca X si Y unifica, fara insa a modifica pe X sau pe Y. Folosind predicatul not, putem scrie: unifica(X, Y) :- not not (X = Y).
Daca X si Y unifica, adica X = Y reuseste, atunci not (X = Y) esueaza, unificarea fiind desfacuta, si not not (X = Y) reuseste (deci unifica(X, Y) reuseste), X si Y ramanand neunificate.
8.3 Utilizarea operatorilor
Notatia cu operatori permite programatorului sa ajusteze sintaxa programelor conform propriilor dorinte. Intelegerea programelor este mult imbunatatita atunci cand se folosesc operatori.
Exemplu: Daca definim operatorii joaca si si:
:- op(300,xfx, joaca).
:- op(200, xfy, si). atunci urmatorii termeni sunt obiecte legale din punct de veder sintactic:
Termen1 = tom joaca fotbal si tenis.
Termen2 = susan joaca tenis si volei si ping pong.
Calculele aritmetice sunt facute prin proceduri predefinite. Evaluarea unei expresii aritmetice este fortata de procedura is si de predicatele de comparatie <, =<, etc. De exemplu:
?- X = 3 / 2
X = 3 / 2
?- X is 3 / 2
X = 1.5
In continuare este prezentat ca exemplu un mini sistem de reguli de productie:
% operatorii fundamentali
:- op(100, yfx, si).
:- op(110, yfx, sau).
:- op(120, fx, daca).
:- op(130, xfy, atunci).

% intreb(+Fapt) - deduce valoare de adevar unui fapt
X si Y :- intreb(X), intreb(Y).
X sau Y :- intreb(X) ; intreb(Y). intreb(X) :- cunosc(X). intreb(X) :- call(X). intreb(X) :- daca Y atunci X, a! intreb(Y) !i, adaug(X). intreb(X) :- intreb_utiliz(X).

% adaug(+Fapt) - adauga un fapt cunoscut ca fiind adevarat in memoria
% sistemului sub forma cunosc(Fapt). adaug(X) :- not var(X), (cunosc(X) ; asserta(cunosc(X))), !.

% intreb_utiliz(F) - intreaba utilizatorul despre valoarea de adevar a unui fapt
% despre care nu se poate deduce nimic intreb_utiliz(X) :- X =.. aOp, Yi, var(Y), !, fail. intreb_utiliz(X) :- X =.. aOp, Y, Zi, (var(Y) ; var(Z)), !, fail. intreb_utiliz(X) :- X =.. aOp, _ , _ , _ | _ i, !, fail. intreb_utiliz(X) :- not(var(X)), write(X), write('? ay/_ i '), (read(y), adaug(X) ; fail ), !.

% ret - elimina toate faptele din memoria sistemului ret(X) :- retract(cunosc(X)), fail ; true. ret :- nl, write('fapte retractate:'), nl, retract(cunosc(X)), tab(2), write(cunosc(X)), nl, fail
; true.

% operatorii utilizatorului
:- op(10, xf, zboara).
:- op(20, xfx, are).
:- op(20, xfx, este).

% faptele cunoscute de utilizator (fapte Prolog). coco are cioc. % echivalent cu: are(coco, cioc) coco are pene. coco are picioare.

% regulile utilizatorului pentru generarea de noi fapte
% (aceste reguli sunt tot fapte Prolog) daca X are picioare atunci X este fiinta.
% echivalenta cu: atunci(daca(are(X, picioare)), este(X, fiinta)). daca X este fiinta si X are pene atunci X zboara. daca X este fiinta si X are pene atunci X are cioc. daca X zboara si X are cioc atunci X este pasare. daca X este pasare si X este fiinta atunci X este frumos. daca X este frumos sau X este peste atunci X este vanat. daca X are solzi atunci X este peste. daca X este vanat atunci X este nefericit.

% posibile intrebari ale utilizatorului a :- intreb(coco este peste), ret. b :- intreb(coco este X), write(coco este X), nl, fail ; ret. c :- intreb(coco are X), write(coco are X), nl, fail ; ret. d :- intreb(Z), write(Z), nl, fail ; ret. e :- intreb(X este Y), write(X este Y), nl, fail ; ret.
Predicatul ret a fost apelat doar pentru a porni de fiecare data cu memoria vida. Altfel, pe masura ce raspunde intrebarilor utilizatorul, memoria sistemului creste (sistemul “invata”).

8.4 Fisiere
Incarcarea programelor in sistem se poate face prin doua predicate predefinite, consult(Fisier) si reconsult(Fisier). Efectul lui consult este acela ca toate clauzele din Fisier sunt citite si vor fi folosite de Prolog atunci cand va raspunde intrebarilor puse de utilizator. Daca mai este consultat si alt fisier, clauzele din acesta vor fi adaugate la sfarsitul setului de clauze in baza de cunostinte Prolog.
Prolog poate accepta si comenzi direct de la terminal, care corespunde pseudo fisierului user. Dupa evaluarea scopului:
?- consult(user)
Prolog asteapta introducerea clauzelor de la terminal.
Exista o prescurtare a comenzii de consultare a fisierelor. Fisierele sunt consultate daca numele lor sunt puse intr o lista scrisa ca scop. De exemplu:
?- afisier1, fisier2, fisier3i este echivalenta cu:
?- consult(fisier1), consult(fisier2), consult(fisier3).
Predicatul reconsult(Fisier) are acelasi efect ca si consult(Fisier), cu o singura exceptie. Daca exista clauze in Fisier despre o relatie care a fost definita anterior, vechea definitie va fi suprascrisa de noile clauze despre relatie din Fisier. Diferenta dintre consult si reconsult este aceea ca predicatul consult adauga intotdeauna noi clauze, in timp ce reconsult redefineste relatii definite anterior. Reconsultarea cu reconsult nu va afecta insa relatiile despre care nu exista nici o clauza in Fisier. Detaliile despre (re)consultare depind de implementarea de Prolog.
In ARITY Prolog, la reconsultare, redefinirea unor relatii poate fi partiala. ARITY Prolog are si alte predicate predefinite pentru manipularea fisierelor si bazei de cunostinte Prolog (ele sunt descrise in fisierul arity.hlp). De exemplu, predicatul listing(…) listeaza clauzele din baza de date.
Intrarea si iesirea pentru date (altele decat cele asociate interogarii programului) sunt facute prin proceduri predefinite. Fisierele sunt accesate secvential. Exista un flux curent de date de intrare si un flux curent de date de iesire. Terminalul utilizatorului este tratat ca un fisier, fiind denumit user.
Comutarea intre fluxuri de date se poate face cu:
• see(Fisier) - fisierul Fisier devine fluxul curent de intrare
• tell(Fisier) - fisierul Fisier devine fluxul curent de iesire
• seen - inchide fluxul curent de intrare
• told - inchide fluxul curent de iesire
Fisierele pot fi citite si scrise in doua moduri: ca secvente de caractere si ca secvente de termeni; in al doilea caz termenii sunt urmati de punct si despartiti de cel putin un blank sau un caracter sfarsit de linie (CR). Procedurile predefinite pentru citirea si scrierea caracterelor si termenilor sunt:
• read(Termen) - citeste in Termen urmatorul termen din fluxul curent de intrare
• write(Termen) - scrie termenul Termen in fluxul curent de iesire
• put(CodCaracter) - scrie caracterul care are codul ASCII CodCaracter
• get0(CodCaracter) - citeste urmatorul caracter si intoarce codul lui ASCII
• get(CodCaracter) - citeste urmatorul caracter tiparibil si intoarce codul lui ASCII
Pentru formatarea iesirii exista doua proceduri:
• nl - scrie un caracter sfarsit de linie
• tab(N) - scrie N caractere blank
Procedura name(Atom, ListaCoduri) descompune si construieste atomi. ListaCoduri este lista codurilor ASCII ale caracterelor din Atom. Exemple: name( ana, a97, 110, 97i ). name( 'Ana', a65, 110, 97i ). name( 'Ana vine.', a65, 110, 97, 32, 118, 105, 110, 101, 46i ).
8.5 Exercitii propuse
EP1. Fie urmatorul program Prolog: este(a). este(b). este(c). exista(X) :- este(X) ; true.
Cate solutii are fiecare din urmatoarele scopuri:
?- exista(A), exista(B), exista(C), A \= a, B \= b, C \= c.
?- exista(A), exista(B), exista(C), !, A \= a, B \= b, C \= c.
?- exista(A), !, exista(B), exista(C).
EP2. Sa se scrie doua variante ale predicatului de calcul al sumei unei liste de intregi: o varianta in care calculul se face pe ramura de avans in recursivitate si o a doua varianta in care calculul sumei se face pe ramura de revenire din recursivitate, afisand lista partiala la fiecare apel recursiv.
EP3. Sa se scrie un predicat care verifica daca un numar intreg pozitiv poate fi exprimat ca suma a doua patrate perfecte. (Ex: 65 = 16 + 49 = 4 2 + 7 2 ).
EP4. Sa se scrie un predicatul care citeste in bucla numere si raspunde daca sunt prime sau nu, pana la intalnirea unui numar negativ, folosind predicatul predefinit repeat.
EP5. Sa se scrie un program care calculeaza numarul de zile dintre doua date exprimate sub forma Zi-Luna, presupunand ca datele se refera la acelasi an. Caracterul “-” se va defini ca un operator infixat.
Ex: interval(3-martie, 7-aprilie, I) produce I = 35.
EP6. Sa se scrie un predicat care implementeaza operatia de diferenta intre doua multimi. Multimile sunt reprezentate prin liste.
Ex: diferenta(a1, 2, a, bi, ab, 3, 2, di, D) produce D = a1, ai.
EP7. Sa se scrie un program care citeste propozitii simple (afirmatii si intrebari, pe care le adauga in baza de cunostinte Prolog), avand una din formele:
_ este un _.
_ este o _.
Un _ este un/o _.
O _ este un/o _.
Este _ un/o _ ? si raspunde adecvat (da, nu sau necunoscut) la intrebari pe baza afirmatiilor introduse. Exemplu: Radu este un student. Un om este o fiinta. Radu este un om. Este Maria o persoana?
EP8. Sa se defineasca operatorii Prolog este, are, un etc. astfel incat sa poata fi introduse clauze de forma: diana este secretara lui toma. maria are un pian. si sistemul sa poata raspunde la intrebari de tipul:
?-Cine este secretara lui toma.
Cine=Diana
?-diana este Ce.
Ce=secretara lui toma
?-maria are un Ce.
Ce=pian
EP9. Sa se scrie un program Prolog de evaluare a unei expresii aritmetice care contine variabile, constante intregi, paranteze si operatorii: +, -, *, /. Valorile variabilelor sunt date sub forma de fapte Prolog prin predicatul valoare(Variabila, Valoare); de exemplu valoare(x, 100) sau valoare(y, -50).
EP10. Sa se scrie un program care determina negarea unei formule in logica cu propozitii. Conectorii logici considerati sunt: not, and, or si implies. Sa se dea definitii adecvate pentru acesti operatori.
Ex: neaga(p implies (q and not r),E) va produce E = p and (not q or r)
EP11. Sa se scrie predicatul cauta(Cuvant, F) care cauta cuvantul Cuvant in fisierul text F.
EP12. Sa se scrie predicatul cuburi(F1, F2), care citeste numere intregi din fisierul text F1 si scrie cuburile lor in fisierul text F2.
EP13. Utilizand predicatul bagof, scrieti predicatul parti_mult(Mult, Submult) care calculeaza in Submult multimea partilor multimii Mult. Reprezentati multimile sub forma de liste.
Exemplu: parti_mult( a1, 2, 3i, a a i, a1i, a2i, a3i, a1, 2i, a1, 3i, a2, 3i i ).
9 Sortare si cautare
9.1 Metoda de sortare prin generare si testare
Utilizand structura de control a limbajului Prolog, se poate realiza foarte simplu sortarea unei secvente de elemente utilizand metoda generare si testare. Aceasta metoda de rezolvare a problemelor, utilizata in inteligenta artificiala dar putin potrivita pentru o sortare, are la baza urmatoarea idee: o componenta generatoare construieste solutii candidate si o a doua componenta, componenta de testare, verifica fiecare solutie candidata pentru a vedea daca este sau nu o solutie a problemei. In acest fel se pot obtine fie toate solutiile problemei, fie una singura. Aceasta metoda poate fi exprimata succint in Prolog astfel: gaseste(Solutie) :- genereaza(Solutie), testeaza(Solutie).
Metoda este in general ineficienta chiar in cazul problemelor tipice de inteligenta artificiala care necesita un proces de cautare a solutiei. Metoda este extrem de ineficienta in cazul rezolvarii problemelor de sortare, pentru care exista algoritmi eficienti de rezolvare. Cu toate acestea, se prezinta in continuare solutia de sortare in ordine crescatoare a unei liste de intregi prin metoda generare si testare ca exercitiu Prolog.
% sortare(+Lista, -ListaSortata) - sortare prin metoda generare si testare sortare(Lista, ListaSortata) :- permut(Lista, ListaSortata), ordonata(ListaSortata).

% permut(+Lista, -PermutareLista) permut(ai, ai). permut(Lista, aPrim | Resti) :- elim(Prim, Lista, L), permut(L, Rest).

% elim(+Element, +Lista, -ListaMinusElement) elim(Elem, aElem | Resti, Rest). elim(Elem, aPrim | Resti, aPrim | Li) :- elim(Elem, Rest, L).

% rel(+X, +Y) - verifica daca X si Y respecta relatia de ordine rel rel(X, Y) :- X =< Y.

% ordonata(+Lista) - verifica daca Lista este sortata dupa relatia rel(X, Y) ordonata(a _ i). ordonata(aPrim, Secund | Resti) :- rel(Prim, Secund), ordonata(aSecund | Resti).
Se observa ca sortarea se face prin generarea permutarilor elementelor din lista si verificarea daca o permutare generata este o secventa sortata. Componenta generatoare este predicatul permut(Lista, ListaSortata) si componenta de testare este predicatul ordonata(Lista). Desi implementarea este simpla, exploatand facilitatile nedeterministe ale limbajului Prolog, ea este foarte ineficienta.
9.2 Metoda de sortare prin insertie
Sortarea prin insertie a unei liste de elemente L = aH | Ti se poate exprima recursiv astfel: se sorteaza mai intai lista T in TS si apoi se insereaza elementul H in lista TS acolo unde ii este locul conform relatiei de ordine rel(X, Y).
% isort1(+Lista, -ListaSortata) - sortare prin insertie, varianta 1 isort1(ai, ai) :- !. isort1(aH | Ti, LS) :- isort1(T, TS), insereaza(H, TS, LS).

% rel(+X, +Y) - verifica daca X si Y respecta relatia de ordine rel(X, Y) :- X =< Y.

% insereaza(+Element, +Lista, -ListaPlusElement) % insereaza Element in Lista sortata astfel incat ListaPlusElement sa ramana sortata insereaza(Elem, ai, aElemi). insereaza(Elem, aPrim | Resti, aElem, Prim | Resti) :- rel(Elem, Prim), !. insereaza(Elem, aPrim | Resti, aPrim | Li) :- not rel(Elem, Prim), insereaza(Elem, Rest, L).
Predicatul cut folosit in definirea predicatului insereaza este un cut verde. Se poate rescrie predicatul insereaza folosind un cut rosu astfel: insereaza(Elem, ai, aElemi). insereaza(Elem, aPrim | Resti, aElem, Prim | Resti) :- rel(Elem, Prim), !. insereaza(Elem, aPrim | Resti, aPrim | Li) :- insereaza(Elem, Rest, L).
A doua varianta de sortare prin insertie este urmatoarea: Lista poate fi privita la un moment dat ca L' = PS::PN, unde PS este partea sortata si PN = aX | Ti este partea nesortata. Se ia primul element X din PN si se insereaza in PS. Algoritmul porneste cu PS = ai si PN = L, si se opreste cand PN = ai, in acel moment PS fiind chiar lista sortata. Se observa ca PS are rol de acumulator, rezultatul final fiind intors in al treilea parametru (constructia rezultatului se face pe apelul recursiv).
% isort2(+Lista, -ListaSortata) - sortare prin insertie, varianta 2 isort2(L, LS) :- isort2( ai, L, LS). isort2(PS, ai, PS). isort2(PS, aX | Ti, LS) :- insereaza(X, PS, PS1), isort2(PS1, T, LS).
9.3 Metoda de sortare rapida
Sortarea rapida (quicksort) a unei liste de elemente L se defineste recursiv astfel:
1. Elimina un element Pivot din lista L si obtine Rest = L - Pivot.
2. Imparte lista Rest in doua liste: ListaInf, cu toate elementele din Rest inferioare elementului Pivot si ListaSup cu toate lementele din Rest superioare elementului Pivot.
3. Sorteaza ListaInf si obtine ListaInfSort.
4. Sorteaza ListaSup si obtine ListaSupSort.
5. Concateneaza listele ListaInfSort, lista formata din Pivot, ListaSupSort si obtine ListaSortata.
Predicatul quicksort(Lista, ListaSortata), definit mai jos, implementeaza acest algoritm. Elementul Pivot este considerat, in implementare urmatoare, primul element al listei Lista, iar impartirea listei in ListaInf si ListaSup in functie de elementul pivot se face cu ajutorul predicatului scindeaza(Element, Lista, ListaInf, ListaSup).
% quicksort(+Lista, -ListaSortata) - sortare prin metoda sortarii rapide quicksort(ai, ai). quicksort(aPivot | Resti, ListaSortata) : scindeaza(Pivot, Rest, L1, L2), quicksort(L1, L1Sortata), quicksort(L2, L2Sortata),

% conc(+L1, +L2, -L) - concateneaza listele L1 si L2 in lista L conc(L1Sortata, aPivot | L2Sortatai, Li