Uvod u funkcionalno programiranje (1. deo)

Autor: Stefan Nožinić

Tokom razvoja računarstva postojala su dva smera kuda su teoretičari želeli da se računarstvo razvija. Danas najrasprostranjeniji pravac je zadao Alan Tjuring uvođenjem svoje mašine stanja. Ova mašina je bazirana na sledećoj strukturi: imamo beskonačnu traku (u praksi dovoljno veliku) koja nam služi kao memorija, imamo glavu koja može da se kreće po traci i imamo operacije upisa i čitanja na/sa trake na poziciji gde se nalazi glava. Danas je svaki računar zasnovan na ovom principu. Naši procesori zapravo izvršavaju instrukcije stalnog čitanja i pisanja po memoriji (traci). Tjuringova mašina se, dakle, ponaša na osnovu unapred zadatog redosleda instrukcija. U takvom procesu, Tjuringova mašina stalno menja svoje stanje. Iz ovakvog razmišljanja je nastala i Fon Nojmanova arhitektura na kojoj je danas baziran skoro svaki računarski sistem. Ona nalaže da imamo jednu jedinicu za računanje i izvršavanje instrukcija (procesor), da imamo memoriju odnosno jedinicu za skladištenje podataka i njihovo čitanje i da imamo ulazno/izlazne jedinice koje nam dobavljaju informacije i isporučuju informacije spoljnom svetu (terminal, ekran, tastatura, zvučnik, kamera …). Naravno, svaki eksterni uređaj (ulazni, izlazni ili ulazno-izlazni) može biti izolovani računarski sistem za sebe baziran na istoj arhitekturi. Pored Tjuringove mašine, razvijao se još jedan model izračunavanja: lambda algebra. Ovaj model je baziran na tome da imamo univerzalan jezik za opis izračunavanja koji se sastoji iz nekih pravila. Iako ovaj model nije našao primenu u izradi fizičkih računarskih sistema, on danas nailazi na ogromnu primenu u razvoju softvera, a naročito kada je reč o obradi velikih podataka (eng. big data) jer je programe pisane u ovakvom modelu lako paralelizovati.

Lambda algebra je matematički model jezika koji se sastoji iz tri pravila:

1. Promenljiva – niz od jednog ili više karaktera.

2. Apstrakcija – definicija funkcije koja ima jednu ulaznu (uvezanu) promenljivu i izraz koji je rezultat računanja te funkcije.

3. Aplikacija – primena, odnosno poziv funkcije gde joj se prilaže vrednost koju ima uvezana promenljiva.

U nastavku, zbog lakoće pisanja, promenljive ćemo obeležavati sa x,y,z… a lambda funkcije odnosno apstrakciju sa

λx.M

gde je M neki izraz odnosno neki lambda izraz od gore navedenih mogućnosti. Aplikaciju ćemo obeležavati sa M X gde je M lambda-izraz a X vrednost koju primenjujemo.

Isto tako, izraz M[x] je izraz koji zavisi samo od promenljive x.

Sada ćemo uvesti još neka dodatna pravila kako bismo lakše razumeli ceo ovaj model i kako bismo kasnije lakše razumeli način funkcionisanja programskih jezika (Haskell u ovom serijalu).

1. Alfa-konverzija je pravilo koje nam omogućava da uvezanoj promenljivoj funkciji možemo promeniti naziv, tačnije ovo pravilo nalaže da je

λx.M[x] = λy.M[y]

2. Beta-redukcija je pravilo da kada pozovemo određenu funkciju sa određenim argumentom (aplikacija), da je to isto kao da izraz u toj funkciji zamenimo svuda gde se pominje data promenljiva sa zadatim argumentom, tj:

(λx.M) X = M[x=X]

Ova teorema nalaže da redosled primene beta-redukcije nije važan i da će uvek dati isti rezultat. Uzmimo za primer sledeći izraz:

(λx.x+1) (λx. x+2) 1

Ako prvo uradimo beta redukciju na desni izraz dobijamo novi izraz

(λx.x+1) 3

što zapravo daje 4. Sa druge strane, ako uradimo beta-redukciju prvo na levom izrazu, dobijamo

((λx.x+2) 1) + 1 = 3+1 = 4

Funkcije više promenljivih se lako mogu definisati upotrebom lambda funkcija unutar drugih lambda funkcija. Na primer, funkcija koja uzima dva broja se može definisati kao

λx.λy.x+y

Ovo znači da je to funkcija koja uzima promenljivu x i vraća funkciju koja uzima promenljivu y koja vraća zbir ove dve promenljive. Ovde kažemo da jedna funkcija obuhvata drugu funkciju i to ćemo kraće pisati kao

λx y. M[x,y]

Ovde se može primetiti da smo uveli i dodatni znak “+” koji ne upada u naša tri pravila o lambda izrazu. Ovaj operator je operator sabiranja i posmatramo ga kao definisanu funkciju koja vraća zbir dva njena argumenta odnosno (+) X Y vraća zbir brojeva X i Y i to ćemo zapisivati kao X+Y. Analogno su definisani i množenje, deljenje, oduzimanje kao i funkcija “if” koja uzima 3 izraza gde je prvi logički izraz koji ako je tačan funkcija vraća drugi zadati izraz, a u suprotnom vraća treći. Dake if X M N će biti M ako je X tačno odnosno N ako je X netačno.

Sada možemo definisati i prirodne brojeve kao:

0 = λf x. x

1 = λf x. (f) x

2 = λf x. f (f x)

itd…

Ovo zapravo znači da je

1 f x = f x

a da je

 2 f x = f (f x)

Dakle, prirodni brojevi nam omogućavaju da radimo n-puta kompoziciju funkcije sa samom sobom. Po definiciji je

 0 f x = x

Sada možemo definisati funkciju NULA koja vraća TRUE ako je x jednak nuli:

NULA = λx. x (λy. FALSE) TRUE

Sa ovom funkcijom je lako definisati operator (==) koji proverava da li su njegovi operandi jednaki:

(==) = λx y. NULA (x-y)

Kao što vidimo, funkcije u lambda-algebri nemaju ime, odnosno ne možemo se referencirati na funkciju koja još nije definisana. Zbog ovoga rekurziju nije moguće uraditi na način na koji smo navikli u standardnom programiranju. Ipak, ovako nešto se može uraditi tako što se napravi funkcija koja prima funkciju i parametre, a onda unutar nje poziva tu funkciju. Ta se funkcija potom pozove sa prvim parametrom identične funkcije. Ovo ćemo demonstrirati na primeru faktorijela:

(λf n. if (n == 0) 1 (n * ((f) f n))) (λf n. if (n == 0) 1 (n * ((f) f n)))

Radi lakšeg zapisa, uvodimo novu funkciju REC koja će ovo pozivanje uraditi umesto nas, tačnije:

REC = λf. f f

tako da faktorijel funkciju možemo definisati ovako:

FAKTORIJEL = (!) = REC (λf x. if (NULA x) (1) (x * (REC f (x-1))))

U narednim tekstovima ćemo još detaljnije opisati lambda algebru i krenuti da je primenjujemo u praksi upotrebom programskog jezika Haskel.