Увод у функционално програмирање (1. део)

Аутор: Стефан Ножинић

Током развоја рачунарства постојала су два смера куда су теоретичари желели да се рачунарство развија. Данас најраспрострањенији правац је задао Алан Тјуринг увођењем своје машине стања. Ова машина је базирана на следећој структури: имамо бесконачну траку (у пракси довољно велику) која нам служи као меморија, имамо главу која може да се креће по траци и имамо операције уписа и читања на/са траке на позицији где се налази глава. Данас је сваки рачунар заснован на овом принципу. Наши процесори заправо извршавају инструкције сталног читања и писања по меморији (траци). Тјурингова машина се, дакле, понаша на основу унапред задатог редоследа инструкција. У таквом процесу, Тјурингова машина стално мења своје стање. Из оваквог размишљања је настала и Фон Нојманова архитектура на којој је данас базиран скоро сваки рачунарски систем. Она налаже да имамо једну јединицу за рачунање и извршавање инструкција (процесор), да имамо меморију односно јединицу за складиштење података и њихово читање и да имамо улазно/излазне јединице које нам добављају информације и испоручују информације спољном свету (терминал, екран, тастатура, звучник, камера …). Наравно, сваки екстерни уређај (улазни, излазни или улазно-излазни) може бити изоловани рачунарски систем за себе базиран на истој архитектури. Поред Тјурингове машине, развијао се још један модел израчунавања: ламбда алгебра. Овај модел је базиран на томе да имамо универзалан језик за опис израчунавања који се састоји из неких правила. Иако овај модел није нашао примену у изради физичких рачунарских система, он данас наилази на огромну примену у развоју софтвера, а нарочито када је реч о обради великих података (енг. big data) jер је програме писане у оваквом моделу лако паралелизовати.

Ламбда алгебра је математички модел језика који се састоји из три правила:

1. Променљива – низ од једног или више карактера.

2. Апстракција – дефиниција функције која има једну улазну (увезану) променљиву и израз који је резултат рачунања те функције.

3. Апликација – примена, односно позив функције где јој се прилаже вредност коју има увезана променљива.

У наставку, због лакоће писања, променљиве ћемо обележавати са x,y,z… а ламбда функције односно апстракцију са

λx.M

где је M неки израз односно неки ламбда израз од горе наведених могућности. Апликацију ћемо обележавати са М X где је М ламбда-израз а X вредност коју примењујемо.

Исто тако, израз М[x] је израз који зависи само од променљиве x.

Сада ћемо увести још нека додатна правила како бисмо лакше разумели цео овај модел и како бисмо касније лакше разумели начин функционисања програмских језика (Хаскелл у овом серијалу).

1. Алфа-конверзија је правило које нам омогућава да увезаној променљивој функцији можемо променити назив, тачније ово правило налаже да је

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

2. Бета-редукција је правило да када позовемо одређену функцију са одређеним аргументом (апликација), да је то исто као да израз у тој функцији заменимо свуда где се помиње дата променљива са задатим аргументом, тј:

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

Ова теорема налаже да редослед примене бета-редукције није важан и да ће увек дати исти резултат. Узмимо за пример следећи израз:

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

Ако прво урадимо бета редукцију на десни израз добијамо нови израз

(λx.x+1) 3

што заправо даје 4. Са друге стране, ако урадимо бета-редукцију прво на левом изразу, добијамо

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

Функције више променљивих се лако могу дефинисати употребом ламбда функција унутар других ламбда функција. На пример, функција која узима два броја се може дефинисати као

λx.λy.x+y

Ово значи да је то функција која узима променљиву x и враћа функцију која узима променљиву y која враћа збир ове две променљиве. Овде кажемо да једна функција обухвата другу функцију и то ћемо краће писати као

λx y. M[x,y]

Овде се може приметити да смо увели и додатни знак “+” који не упада у наша три правила о ламбда изразу. Овај оператор је оператор сабирања и посматрамо га као дефинисану функцију која враћа збир два њена аргумента односно (+) X Y враћа збир бројева X и Y и то ћемо записивати као X+Y. Аналогно су дефинисани и множење, дељење, одузимање као и функција “if” која узима 3 израза где је први логички израз који ако је тачан функција враћа други задати израз, а у супротном враћа трећи. Даке if X М N ће бити М ако је X тачно односно N ако је X нетачно.

Сада можемо дефинисати и природне бројеве као:

0 = λf x. x

1 = λf x. (f) x

2 = λf x. f (f x)

итд…

Ово заправо значи да је

1 f x = f x

а да је

 2 f x = f (f x)

Дакле, природни бројеви нам омогућавају да радимо н-пута композицију функције са самом собом. По дефиницији је

 0 f x = x

Сада можемо дефинисати функцију NULA која враћа TRUE ако је x једнак нули:

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

Са овом функцијом је лако дефинисати оператор (==) који проверава да ли су његови операнди једнаки:

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

Као што видимо, функције у ламбда-алгебри немају име, односно не можемо се референцирати на функцију која још није дефинисана. Због овога рекурзију није могуће урадити на начин на који смо навикли у стандардном програмирању. Ипак, овако нешто се може урадити тако што се направи функција која прима функцију и параметре, а онда унутар ње позива ту функцију. Та се функција потом позове са првим параметром идентичне функције. Ово ћемо демонстрирати на примеру факторијела:

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

Ради лакшег записа, уводимо нову функцију РЕЦ која ће ово позивање урадити уместо нас, тачније:

REC = λf. f f

тако да факторијел функцију можемо дефинисати овако:

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

У наредним текстовима ћемо још детаљније описати ламбда алгебру и кренути да је примењујемо у пракси употребом програмског језика Хаскел.