CPS

CPS

Abreviere de la Continuation passing style, un stil de programare utilizabil in limbajele de programare functionale, si la nevoie chiatr si in C++. El se bazeaza pe posibilitatea de a stoca acele calcule care vor fi de facut in viitor, dar aflam de ele acum. Foloseste compunerea functiilor, operatorul ".".

De exemplue un proces format din calcule succesive este vazut ca:

- sirul calculelor initiale
- sirul functiilor cu care se compune rezultatul al pasii finali

si poate fi executat in acest fel din doua locuri, de la inceput si de la sfarsit. La inceput facem efectiv calculele iar pentru sfarsit compunem functiile care se vor aplica la sfarsit. Cand ajungem la mijloc aplicam pe rezultatul calculelor din prima parte functia care e rezultatul compunerilor din a doua parte (ea era un fel de acumulator al calculelor viitoare). Se poate asemana cu un fel de Acumulative programming la care calculele de facut in viitor se acumuleaza intr-un parametru functional, prin compunere.

De exemplu factorialul unui numar:

1*2*3* .... * (n-2) * (n-1) * (n)

Poate fi vazut in prima sa parte ca :

1*2* .. * i

si in acelasi timp, spre final, ca acumularea prin compunere a functiilor:

(*n) . (* (n-1)) . ..... .(* (n-i))

Aceasta e partea "continuation". Cand ambele parti sunt gata calculate aplicam functia "continuation" rezultatului primei parti.

Iata un exemplu ad hoc de functie factorial, scris intr-un stil apropiat si de CPS si de acumulative programming:

fact n=cps 1 (n+1) 1 id
	    where 
	       cps i n p f = if i < n-i 
			      then
				cps (i+1) n (p*i)  (f.(*(n-i)))
			      else  
			      if i == n - i 
				then f (p*i)
				else f p

Parametrii functiei cps sunt: - i indicele curent - n - valoarea maxima a indicelui (se poate renunta la ea) - p - produsul curent al elementelor de la inceputul sirurilor - f compunerea functiilor care continua calculul

Observati ca aceasta implementare de factorial face de doua ori mai putine apeluri recursive decat cea uzuala, deoarece merge simultan de la ambele capete ale listei de factori. Dezavantaj: Stocarea functiilor care se compun pe stiva cere si ea loc, si avem un parametru acumulativ in plus.

Exercitiu: Eliminati parametrul n care este inutil.

Nota: Nu stiu daca este cel mai reusit exemplu, acesta l-am scris ad hoc mai ales ca pe wiki nu e voie sa faci paste din alte surse, dar il cred suficient de bun ca sa va dea o idee ca se pot scrie si calcule din viitor, pe care le compunem ca produs de functii, iar la momentul potrivit, PAC (vorba lui Caragiale), plasam rezultatul din trecut functiei care va face calculele din viitor si gata. Obtinem rezultatul final.

Ideea este ca putem stoca, pastra compune si calcule din viitor despre care am aflat in prezent ca URMEAZA sa le facem. Ne ajuta la aceasta compunerea functiilor.

Vedeti si: pagina Evolution of a Haskell Programmer. O gasiti cu Google.

---

Pagina in lucru

---

Pagina indexata la indexul Categories:Ro

---

<= Inapoi la pagina principala Ro/Haskell.

<- Inapoi la inceputul paginii 'Intrebarile incepatorului Ro/Haskell'.

Linkuri reactualizate dupa mutrarea site-ului. OK