Patru ipostaze al recursivitatii in contextul prelucrarii secventiale a listelor in Prolog
<![CDATA[
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Patru ipostaze al recursivitatii in contextul prelucrarii secventiale a listelor in Prolog
% Nicolaie Popescu-Bodorin, 2009
% http://fmi.spiruharet.ro/bodorin/
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Ca exemplu vom considera urmatoarea prelucrare: pentru o lista data, toate elementele egale cu un numar dat N
% se substituie cu 2N.
DOMAINS
r=real
lr=r*
PREDICATES
cm1(r,lr,lr)
cm1(r,lr,lr,lr)
cm2(r,lr,lr)
cm3(r,lr,lr)
cm4(r,lr,lr)
CLAUSES
% 1. Forward tail-recursion with accumulator(s):
% Una din posibilitatile de a efectua o prelucrare secventiala a unei liste in Prolog este folosirea unei variabile
% acumulator:
cm1(X,L,R):-cm(X,L,[],R). % Instructiunea de schimbare de aritate introduce variabila acumulator
% pe pozitia a treia in lista parametrilor de apel.
cm1(_,[],Ri,Ri). % Fapt de oprire (cel mai interior aoutoapel): daca lista s-a epuizat,
% rezultatul intermediac acumulat pana in cel mai interior autoapel este
% (unificat) chiar (cu) rezultatul final.
cm1(X,[H|T],Ri,R):-
X=H,Y=2*X, Ria=[Y|Ri],cm1(X,T,Ria,R);
X<>H, Ria=[H|Ri],cm1(X,T,Ria,R). % Clauza de propagare a autoapelului specifica modul in care variabila
% acumulator colecteaza date odata cu parcurgerea listei, in functie de
% aparitia numarului cautat sau a unui numar diferit.
% 2. Backward regular recursion:
cm2(_,[],[]). % Fapt de oprire.
cm2(X,[H|T],R):- % Abordarea recursiva "inapoi" consta in descrierea legaturii care exista
% intre rezultatul calculului pe lista data si rezultatul calculului pe sublista
% obtinuta prin eliminarea capului listei date.
X=H,Y=2*X, cm2(X,T,Ri),R=[Y|Ri]; % Si aici, clauza de propagare a autoapelului specifica modul in care
% variabila acumulator colecteaza date odata cu parcurgerea listei, in
% functie de aparitia numarului cautat sau a unui numar diferit.
X<>H, cm2(X,T,Ri), R=[H|Ri]. % O abordare de acest tip este usor de recunoscut datorita prezentei
% dupa autoapeluri a relatiei de legatura dintre rezultate (aici R si Ri).
% 3. Trecerea de la "backward regular recursion" la "backward tail recursion" in cazul listelor prelucrate secventia:
cm3(_,[],[]). % Fapt de oprire.
cm3(X,[H|T],[Y|Rt]) :- % Se remarca faptul ca, in aceasta clauza de propagare, ultima instructiune
% este, pe toate alternativele, autoapelul. Predicatul astfel definit este
% deci recursiv la urma (tail recursive).
X=H,Y=2*X, cm3(X,T,Rt); % Si aici, clauza de propagare a autoapelului specifica modul in care
% variabila acumulator colecteaza date odata cu parcurgerea listei,
% in functie de aparitia numarului cautat sau a unui numar diferit.
X<>H,Y=H, cm3(X,T,Rt). % In cazul particular al prelucrarilor secventiale, relatia de legatura dintre
% rezultate "migreaza" in lista de apel a predicatului (aici sub forma [Y|Rt]).
% Este deci de retinunt ca, in cazul prelucrarilor secventiale pe liste, trecerea de la "backward regular recursion" la
% "backward tail recursion" este, de regula, posibila fara schimbarea aritatii predicatului.
% 4. A patra varianta de calcul a aceluiasi predicat este tot una de tip "backward tail recursion" care, in plus,
% minimizeaza numarul de operatii necesare:
cm4(_,[],[]).
cm4(X,[X|T],[H|Rt]) :- H=2*X, cm4(X,T,Rt),!.
cm4(X,[H|T],[H|Rt]):-cm4(X,T,Rt).
]]>