Recursivitate in Prolog

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 capitolul 1. De asemenea, o serie de notiuni matematice, cum ar fi factorialul unui numar sau numerele lui Fibonacci au o definitie recursiva.

Relatii recursive

Limbajul Prolog permite exprimarea definitiilor recursive prin definirea recursiva a predicatelor. Trebuie intotdeauna sa se defineasca un fapt sau o regula care marcheaza punctul de oprire din recursivitate, deci cazul particular al definitiei recursive.

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:

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)

Ex Sa se scrie un program care calculeaza X la puterea N, unde X si 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.  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 >

% 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 + F

Aceasta implementare este ineficienta, deoarece in calculul lui fibo(N, _ ), predicatul 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:

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.  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 naturale.

daca b

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

Ex5. Sa scriem predicatul divizor care testeaza daca un numar A divide un numar B. Pe baza acestui predicat sa se scrie predicatul prim care verifica daca un numar 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).

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

Directia de construire a solutiilor

Majoritatea programelor Prolog se bazeaza pe recursivitate. Ca in orice limbaj de programare recursiv, parametrii de iesire ai subprogramelor, deci argumentele sintetizate ale predicatelor in cazul limbajului Prolog, pot fi calculate fie pe ramura de avans in recursivitate, fie pe ramura de revenire din recursivitate. Se considera doua variante de definire a predicatului de numarare a elementelor dintr‑o lista Prima varianta, nr_elem(Lista, NrElem), construieste solutia (calculeaza numarul de elemente din lista) 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 varianta, nr_elem2(Lista, NrElem) calculeaza numarul de elemente din lista pe ramura de avans in recursivitate. Pentru a realiza acest lucru, se foloseste un predicat ajutator nr_elem1(Lista, NrAcumulat, NrElem), care are un argument suplimentar fata de predicatul nr_elem Acest argument, NrAcumulat, are rolul de variabila de acumulare a numarului de elemente din lista, pe masura avansului in recursivitate si este instantiat la primul apel la valoarea 0. In momentul atingerii punctului de oprire din recursivitate, deci in cazul in care lista ajunge vida, valoarea acumulata in argumentul NrAcumulat este copiata in cel de‑al treilea parametru al predicatului nr_elem1. Se face apoi revenirea din apelurile recursive succesive, fara a efectua nici o alta prelucrare, predicatul nr_elem1 reuseste si trimite valoarea calculata in NrElem predicatului initial nr_elem

% nr_elem2(Lista, NrElem)

% nr_elem1(Lista, NrAcumulat, NrElem)

nr_elem2(Lista, N) :- nr_elem1(Lista, 0, N).

nr_elem1([], N, N).

nr_elem1([ _ | Rest], N1, N2) :- N is N1 + 1, nr_elem1(Rest, N, N2).

O abordare similara se poate vedea in cazul celor doua variante de definire a predicatului de intersectie a doua liste (determinarea elementelor comune celor doua liste). Prima varianta, inter(Lista1, Lista2, ListaRez), calculeaza solutia (lista intersectie) pe ramura de revenire din recursivitate.

Cea de a doua varianta, int(Lista1, Lista2, ListaRez), calculeaza solutia pe ramura de avans in recursivitate, utilizand int1(Lista1, Lista2, ListaAcumulare, ListaRez) ca predicat ajutator cu parametrul suplimentar ListaAcumulare, instantiata la primul apel la lista vida

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

Aceasta tehnica de programare, des intilnita in programele Prolog, are o serie de avantaje, printre care o claritate crescuta si, in principal, utilizarea definitiilor de predicate recursive la urma. Un predicat recursiv la urma este un predicat in care apelul recursiv al acestuia este ultimul scop din conjunctia de scopuri care il defineste si pentru care nu mai exista nici o regula posibila de aplicat dupa apelul recursiv. Un astfel de predicat are avantajul ca poate fi apelat recursiv de oricate ori, fara a genera o depasire a stivei. In plus, executia unui astfel de predicat este mai eficienta

Pentru a pune in evidenta aceasta comportare se definesc patru variante ale unui predicat care afiseaza (numara) valori intregi succesive la infinit, incepand de la o valoare fixata N

% 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 doua variante ale acestui predicat, numara(N) si numara1(N), sunt predicate recursive la urma Predicatul numara(N) este definit printr‑o singura regula si apelul recursiv este ultimul scop al definitiei. Predicatul numara1(N) este definit prin doua reguli, dar, datorita predicatului cut din prima regula, daca N   0 nu mai exista nici o alta regula posibila de aplicat in momentul apelului recursiv. Ambele variante vor numara la infinit, incepand de la N si afisand valori succesive. Urmatoarele doua variante, rau_numara(N) si rau_numara1(N), nu sunt predicate recursive la urma. Predicatul rau_numara(N) nu are apelul recursiv ca ultim scop in definitie, iar rau_numara1(N) are o varianta (regula) neincercata in momentul apelului recursiv. Executia ambelor predicate se va opri dupa un anumit numar de valori, cu afisarea unui mesaj de eroare cauzat de depasirea stivei.

Satisfacerea restrictiilor prin recursivitate

In aceasta sectiune se vor prezenta rezolvarile in Prolog pentru cateva probleme clasice ce implica recursivitate. Fiecare problema este prezentata sub urmatoarea forma:

Enuntul problemei (ipoteze si concluzie);

Rescrierea enuntului sub forma de clauze Prolog;

Demonstratia concluziei prin formularea unei interogari corecte in Prolog.

Problema trezorierului

Ipoteze:

Nici un membru al clubului nu are datorii la trezorierul clubului.

Daca un membru al clubului nu a platit taxa, atunci el are datorii la trezorierul clubului.

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

Problema parteneriatului

Ipoteze:

Tom este corect.

Bill nu este partener cu Tom.

Daca doua persoane X si Y sunt corecte, atunci X este partener cu Y.

Daca Bill nu este corect, atunci John este corect.

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

Problema vecinilor

Ipoteze:

Stefan este vecin cu Petre.

Stefan este casatorit cu o doctorita care lucreaza la Spitalul de Urgenta.

Petre este casatorit cu o actrita care lucreaza la Teatrul National.

Stefan este meloman si Petre este vanator.

Toti melomanii sunt sentimentali.

Toti vanatorii sunt mincinosi.

Actritele iubesc barbatii sentimentali.

Sotii au aceiasi vecini.

Casatoria si vecinatatea sunt relatii simetrice.

Concluzie

Sotia lui Petre il iubeste 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.

Problema unicornului

Problema unicornului este o problema celebra formulata de Lewis Carroll in cartea sa 'Alice in tara minunilor'.

Ipoteze:

Leul minte luni, marti si miercuri si spune adevarul in toate celelalte zile.

Unicornul minte joi, vineri si sambata si spune adevarul in toate celelalte zile.

Astazi Leul spune: 'Ieri a fost una din zilele in care eu mint.'

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),

Adevar % sau call(Adevar2)

% Concluzia

% ?- azi(Azi).

Exercitii propuse

Sa se rescrie enunturile urmatoarelor probleme sub forma de clauze Prolog si sa se demonstreze concluziile prin formularea unor interogari corecte in Prolog.

EP1. Ipoteze

Oricine poate citi este literat.

Delfinii nu sunt literati.

Anumiti delfini sunt inteligenti.

Concluzie

Exista fiinte inteligente care nu pot citi.

EP Ipoteze

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.

Daca orasul X este legat de orasul Y prin drumul D, atunci si orasul Y este legat de orasul X prin drumul D.

Daca se poate merge de la X la Y si de la Y la Z, atunci se poate merge de la X la Z.

Orasul a este legat de orasul b prin drumul d1.

Orasul b este legat de orasul c prin drumul d

Orasul a este legat de orasul c prin drumul d3.

Pe drumul d1 pot circula biciclete.

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

Marcus era om.

Marcus era pompeian.

Toti pompeienii erau romani.

Cezar era dictator.

Fiecare roman ii era devotat lui Cezar sau il ura.

Fiecare om ii este devotat cuiva.

Oamenii incearca sa ii asasineze pe dictatorii fata de care nu sunt devotati.

Marcus a incercat sa il asasineze pe Cezar.

Concluzii

Marcus nu ii era devotat lui Cezar.

Marcus il ura pe Cezar.