Capitolul 2

Recursivitate n Prolog Multe definiii de concepte sunt definiii recursive, aa cum este de exemplu definiia recursiv a noiunii de list, arbore sau cum a fost definiia recursiv a predicatului strmo, prezentat n capitolul 1. De asemenea, o serie de noiuni matematice, cum ar fi factorialul unui numr sau numerele lui Fibonacci au o definiie recursiv.

2.1 Relaii recursive Limbajul Prolog permite exprimarea definiiilor recursive prin definirea recursiv a predicatelor. Trebuie ntotdeauna s se defineasc un fapt sau o regul care marcheaz punctul de oprire din recursivitate, deci cazul particular al definiiei recursive.

Ex1. S se scrie un program care calculeaz 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: N > 0, N1 is N - 1, %calculam (N - 1) pentru a-l 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. S se scrie un program care calculeaz X la puterea N, unde X i N sunt numere naturale.

% expo(+N, +X, -XlaN) expo( _ , 0, 0). expo(0, X , 1):- X > 0. expo(N, X, Exp) :- X > 0, N > 0, N1 is N - 1, expo(N1, X, Z), Exp is Z * X. Ex3. S se scrie un program care calculeaz termenul n din irul lui Fibonacci: 1, 1, 2, 3, 5, 8, 13, 21, ..., n care f(n) = f(n - 1) + f(n - 2), pentru n > 2.

38 CAPITOLUL 2

% fibo(+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. Aceast implementare este ineficient, deoarece n calculul lui fibo(N, _ ), predicatul fibo(N-k, _ ) este apelat de k ori. Implementarea urmtoare elimin aceast deficien, deoarece predicatul fib, care calculeaz F = f(M), este apelat cu ultimii doi termeni F1 = f(M-2) i F2 = f(M-1), pentru M = 2N: fibo1(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). Ex4. S se scrie un predicat care calculeaz cel mai mare divizor comun pentru dou numere. Se folosete definiia recursiv a lui Euclid:

Fie a i b dou numere naturale. dac b = 0 atunci cmmdc(a, b) = a;

altfel cmmdc(a, b) = cmmdc(b, r), cu r restul mpririi lui a la b.

Implementarea n 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). Ex5. S scriem predicatul divizor care testeaz dac un numr A divide un numr B. Pe baza acestui predicat s se scrie predicatul prim care verific dac un numr este prim.

% divizor(+A,+B) % prim(+N) divizor(A, B) :- 0 is B mod A. prim(N):- N > 1, Div is N - 1, nu_are_div(N, Div). nu_are_div(_, 1). nu_are_div(N, Divizor) :- not(divizor(Divizor, N)), DivNou is Divizor - 1, nu_are_div(N, DivNou).

RECURSIVITATE N PROLOG 39

Ex6. Predicatul rezolv(N) rezolv problema turnurilor din Hanoi cu N discuri.

% rezolva(+N) rezolva(N) :- hanoi(N, stnga, 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).

2.2 Direcia de construire a soluiilor Majoritatea programelor Prolog se bazeaz pe recursivitate. Ca n orice limbaj de programare recursiv, parametrii de ieire ai subprogramelor, deci argumentele sintetizate ale predicatelor n cazul limbajului Prolog, pot fi calculate fie pe ramura de avans n recursivitate, fie pe ramura de revenire din recursivitate. Se consider dou variante de definire a predicatului de numrare a elementelor dintr-o list. Prima variant, nr_elem(Lista, NrElem), construiete soluia (calculeaz numrul de elemente din list) pe ramura de revenire din recursivitate. % nr_elem(Lista, NrElem) nr_elem([], 0). nr_elem([ _ | Rest], N) :- nr_elem(Rest, N1), N is N1 + 1.

A doua variant, nr_elem2(Lista, NrElem) calculeaz numrul de elemente din list pe ramura de avans n recursivitate. Pentru a realiza acest lucru, se folosete un predicat ajuttor nr_elem1(Lista, NrAcumulat, NrElem), care are un argument suplimentar fa de predicatul nr_elem2. Acest argument, NrAcumulat, are rolul de variabil de acumulare a numrului de elemente din list, pe msura avansului n recursivitate i este instaniat la primul apel la valoarea 0. n momentul atingerii punctului de oprire din recursivitate, deci n cazul n care lista ajunge vid, valoarea acumulat n argumentul NrAcumulat este copiat n cel de-al treilea parametru al predicatului nr_elem1. Se face apoi revenirea din apelurile recursive succesive, fr a efectua nici o alt prelucrare, predicatul nr_elem1 reuete i trimite valoarea calculat n NrElem predicatului iniial nr_elem2.

% nr_elem2(Lista, NrElem) % nr_elem1(Lista, NrAcumulat, NrElem) nr_elem2(Lista, N) :- nr_elem1(Lista, 0, N). nr_elem1([], N, N).

40 CAPITOLUL 2

nr_elem1([ _ | Rest], N1, N2) :- N is N1 + 1, nr_elem1(Rest, N, N2). O abordare similar se poate vedea n cazul celor dou variante de definire a

predicatului de intersecie a dou liste (determinarea elementelor comune celor dou liste). Prima variant, inter(Lista1, Lista2, ListaRez), calculeaz soluia (lista intersecie) pe ramura de revenire din recursivitate.

Cea de a doua variant, int(Lista1, Lista2, ListaRez), calculeaz soluia pe ramura de avans n recursivitate, utiliznd int1(Lista1, Lista2, ListaAcumulare, ListaRez) ca predicat ajuttor cu parametrul suplimentar ListaAcumulare, instaniat la primul apel la lista vid.

% inter(Lista1, Lista2, ListaRez) membru(Elem, [Elem|_]). membru(Elem, [_|Rest]) :- membru(Elem, Rest). inter([], _, []). inter([Prim|Rest], Lista2, [Prim|LRez]) :- membru(Prim, Lista2), !, inter(Rest, Lista2, LRez). inter([ _ | Rest], Lista2, LRez) :- inter(Rest, Lista2, LRez).

% int(Lista1, Lista2, ListaRez) % int1(Lista1, Lista2, ListaAcumulare, ListaRez) int(L1, L2, LRez) :- int1(L1, L2, [], LRez). int1([], _, L, L). int1([Prim|Rest], L, L1, L2) :- membru(Prim,L), !, int1(Rest, L, [Prim | L1], L2). int1([ _ | Rest], L, L1, L2) :- int1(Rest, L, L1, L2).

Aceast tehnic de programare, des ntlnit n programele Prolog, are o serie de avantaje, printre care o claritate crescut i, n principal, utilizarea definiiilor de predicate recursive la urm. Un predicat recursiv la urm este un predicat n care apelul recursiv al acestuia este ultimul scop din conjuncia de scopuri care l definete i pentru care nu mai exist nici o regul posibil de aplicat dup apelul recursiv. Un astfel de predicat are avantajul c poate fi apelat recursiv de oricte ori, fr a genera o depire a stivei. n plus, execuia unui astfel de predicat este mai eficient.

Pentru a pune n eviden aceast comportare se definesc patru variante ale unui predicat care afieaz (numr) valori ntregi succesive la infinit, ncepnd de la o valoare fixat N.

RECURSIVITATE N PROLOG 41

% Predicatele numara(N), numara1(N), rau_numara(N) si % rau_numara1(N) afiseaza intregi succesivi pornind de la valoarea N. numara(N) :- write(N), nl, N1 is N + 1, numara(N1).

numara1(N) :- N >= 0, !, write(N), nl, N1 is N + 1, numara1(N1). numara1( _ ) :- write('Valoare negativa.').

rau_numara(N) :- write(N), nl, N1 is N + 1, rau_numara(N1), nl. rau_numara1(N) :- N >= 0, write(N), nl, N1 is N + 1, rau_numara1(N1). rau_numara1(N) :- N < 0, write('Valoare negativa.').

Primele dou variante ale acestui predicat, numara(N) i numara1(N), sunt predicate recursive la urm. Predicatul numara(N) este definit printr-o singur regul i apelul recursiv este ultimul scop al definiiei. Predicatul numara1(N) este definit prin dou reguli, dar, datorit predicatului cut din prima regul, dac N 0 nu mai exist nici o alt regul posibil de aplicat n momentul apelului recursiv. Ambele variante vor numra la infinit, ncepnd de la N i afind valori succesive. Urmtoarele dou variante, rau_numara(N) i rau_numara1(N), nu sunt predicate recursive la urm. Predicatul rau_numara(N) nu are apelul recursiv ca ultim scop n definiie, iar rau_numara1(N) are o variant (regula) nencercat n momentul apelului recursiv. Execuia ambelor predicate se va opri dup un anumit numr de valori, cu afiarea unui mesaj de eroare cauzat de depirea stivei.

2.3 Satisfacerea restriciilor prin recursivitate In aceast seciune se vor prezenta rezolvrile n Prolog pentru cteva probleme clasice ce implic recursivitate. Fiecare problem este prezentat sub urmtoarea form:

1) Enunul problemei (ipoteze i concluzie); 2) Rescrierea enunului sub form de clauze Prolog; 3) Demonstraia concluziei prin formularea unei interogri corecte n

Prolog.

2.3.1 Problema trezorierului Ipoteze:

1) Nici un membru al clubului nu are datorii la trezorierul clubului. 2) Dac un membru al clubului nu a pltit taxa, atunci el are datorii la

trezorierul clubului.

42 CAPITOLUL 2

3) Trezorierul clubului este un membru al clubului. Concluzie:

Trezorierul clubului a pltit taxa.

% Ipoteza 1 fara_datorii(X) :- membru(X). % Ipoteza 2 platit_taxa(X) :- fara_datorii(X). % Ipoteza 3 membru(trezorier). % Concluzia % ?- platit_taxa(trezorier).

2.3.2 Problema parteneriatului Ipoteze:

1) Tom este corect. 2) Bill nu este partener cu Tom. 3) Dac dou persoane X i Y sunt corecte, atunci X este partener cu Y. 4) Dac Bill nu este corect, atunci John este corect. 5) Dac o persoan X este partener cu Y, atunci i 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).

RECURSIVITATE N PROLOG 43

2.3.3 Problema vecinilor Ipoteze:

1) tefan este vecin cu Petre. 2) tefan este cstorit cu o doctori care lucreaz la Spitalul de

Urgen. 3) Petre este cstorit cu o actri care lucreaza la Teatrul Naional. 4) tefan este meloman i Petre este vntor. 5) Toi melomanii sunt sentimentali. 6) Toi vntorii sunt mincinoi. 7) Actriele iubesc brbaii sentimentali. 8) Soii au aceiai vecini. 9) Cstoria i vecintatea sunt relaii simetrice.

Concluzie: Soia lui Petre l iubete pe tefan.

% 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).

44 CAPITOLUL 2

casatorit(X, Y) :- casatorit1(Y, X). % Concluzia concluzie :- casatorit(petre, Sotie), iubeste(Sotie, stefan). % ?- concluzie.

2.3.4 Problema unicornului Problema unicornului este o problem celebr formulat de Lewis Carroll n cartea sa "Alice n ara minunilor". Ipoteze:

1) Leul minte luni, mari i miercuri i spune adevrul n toate celelalte zile.

2) Unicornul minte joi, vineri i smbt i spune adevrul n toate celelalte zile.

3) Astzi Leul spune: "Ieri a fost una din zilele n care eu mint." 4) Tot astzi Unicornul spune: "Ieri a fost una din zilele n care eu

mint." Concluzie:

Ce zi este astzi? (Rspuns: joi).

Prima variant:

% 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).

RECURSIVITATE N PROLOG 45

A doua variant:

% 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).

2.4 Exerciii propuse S se rescrie enunurile urmtoarelor probleme sub form de clauze Prolog i s se demonstreze concluziile prin formularea unor interogri corecte n Prolog.

EP1. Ipoteze 1. Oricine poate citi este literat. 2. Delfinii nu sunt literai. 3. Anumii delfini sunt inteligeni.

46 CAPITOLUL 2

Concluzie Exist fiine inteligente care nu pot citi.

EP2. Ipoteze 1. Dac oraul X este legat de oraul Y prin drumul D i pot circula

biciclete pe drumul D, atunci se poate merge de la X la Y. 2. Dac oraul X este legat de oraul Y prin drumul D, atunci i oraul

Y este legat de oraul X prin drumul D. 3. Dac se poate merge de la X la Y i de la Y la Z, atunci se poate

merge de la X la Z. 4. Oraul a este legat de oraul b prin drumul d1. 5. Oraul b este legat de oraul c prin drumul d2. 6. Oraul a este legat de oraul c prin drumul d3. 7. Pe drumul d1 pot circula biciclete. 8. Pe drumul d2 pot circula biciclete. Concluzie Se poate merge de la oraul a la oraul c.

EP3. Se nlocuiete ipoteza 8 de la EP2 cu Pot circula biciclete fie pe drumul d1, fie pe drumul d3, dar nu pe ambele n acelai timp. S se demonstreze aceeai concluzie.

EP4. Ipoteze 1. Marcus era om. 2. Marcus era pompeian. 3. Toi pompeienii erau romani. 4. Cezar era dictator. 5. Fiecare roman i era devotat lui Cezar sau l ura. 6. Fiecare om i este devotat cuiva. 7. Oamenii ncearc s i asasineze pe dictatorii fa de care nu sunt

devotai. 8. Marcus a ncercat s l asasineze pe Cezar. Concluzii 1. Marcus nu i era devotat lui Cezar. 2. Marcus l ura pe Cezar.