Uvod u funkcionalno programiranje (3. deo)

Autor: Stefan Nožinić

U prethodnom delu smo uveli notaciju tipova, a u ovom ćemo se detaljnije baviti sistemima tipova. Tip je zapravo unija tagovanih proizvoda nekih drugih tipova, na primer:

data Nat = 0 | 1 | 2 | ...

Dakle ovde imamo uniju tagova 0, 1, …. ali skup prirodnih brojeva možemo definisati i ovako:

data Nat = 0 | Succ Nat

Dakle prirodni broj može biti ili nula ili naredni element od nekog prirodnog broja. Na primer:

1 = Succ 0 2 = Succ 1 = Succ (Succ 0) ...

Skup celih brojeva onda možemo definisati kao:

data Int = 0 | Succ Int | Pred Int

pa je onda:

1 = Succ 0 -1 = Pred 0 ...

Motivacija za uvođenje tipova se javlja na sledećem primeru. Uvodimo let … in … izraz na sledeći način:

let x = E1 in E2 <=> (λx. E2) E1

Dakle svako pojavljivanje x u izrazu E2 zamenjujemo sa E1.

Uzmimo sada sledeći primer:

let f = λx. if x then 5 else 2 in f 5

Ovde imamo situaciju da se broj 5 koristi za Bool odnosno proverava se da li je 5 tačno i ako jeste onda celokupan izraz ima vrednost 5, a ako nije onda celokupan izraz ima vrednost 2. Ovde nailazimo na problem što ne možemo da tvrdimo da li je 5 ekvivalent TRUE ili FALSE. Na primer, u programskom jeziku C je svaki broj osim 0 ekvivalent TRUE a 0 je ekvivalent FALSE. U drugim jezicima ovo pak ne mora da važi i dolazi do nekonzistentnosti tipova. Zbog ovoga uvodimo sistem tipova i kažemo da x mora biti tipa Bool odnosno da mora imati ili vrednost TRUE ili FALSE:

data Bool = True | False let f :: Bool -> Int f = λx. if x then 5 else 2 in f True

Ovo možemo napisati i bez lambda izraza kako bismo lakše razumeli notaciju:

let f :: Bool -> Int f x = if x then 5 else 2 in f True

Ovde smo definisali funkciju f koja preslikava Bool u Int, ovo znači da je izraz “f x” validan ako je x tipa Bool i da je tip ovog izraza Int.

Drugi primer gde su tipovi ključni jeste sledeći: da li sledeći izraz može da se izračuna?

(λx. x x) (λx. x x)

Da li bismo, na bilo koji način mogli da odredimo tip ovog izraza?

Za jezik kažemo da je statički tipovan ako je određivanje tipova izvršeno tokom prevođenja. Ovo ne znači nužno da u kodu moramo navoditi tip objekta!

Polimorfizam je svojstvo sistema tipova da se data operacija može generalizovati na više različitih tipova bez potrebe da se data operacija implementira za svaki tip zasebno.

Za ilustraciju ovog svojstva uzećemo listu. Lista može biti lista brojeva, ali isto tako može biti lista slova. Ovo znači da tip lista ima dodatni parametar koji određuje tip koji sadrži lista. Mnogi jezici, na ovaj ili onaj način, ovo podržavaju. Na primer C++ ima svoj templejting sistem, a Java ima generičke klase. Za svrhu ovog članka, i kasnije za svrhu rada u Haskelu, mi ćemo reći da lista prima parametar koji određuje tip objekta koji lista sadrži:

data List a = Empty | Cons a (List a)

Ovde smo definisali listu kao tip koji prima parametar, a koji određuje tip objekta koji lista sadrži. Lista je unija dva moguća skupa podataka: prazna lista (Empty) ili uređenog para objekta tipa a (glava liste) i liste objekata tipa a (telo liste, ostatak liste).

Za lakše objašnjavanje tipova uzmimo sledeći primer:

twice f x = f (f x)

Sada postavimo uslove:

x :: t0 f :: t1 f x :: t2 f (f x) :: t3

Sada donosimo zaključke:

twice :: t1 -> t0 -> t3 t1 = t0 -> t2 (zato što f x je tipa t2) t1 = t2 -> t3 (zbog f (f x)) t0 -> t2 = t2 -> t3 t0 = t2 = t3 t1 = t0 -> t0

Odavde sledi da je tip funkcije twice: (t0 → t0) → t0 → t0

Drugi primer je sledeći:

conditionalSum cond x y = if cond then x+y else 0

Prvo postavimo sistem:

0 :: Int cond :: t0 x :: t1 y :: t2 + :: Int -> Int -> Int x+y :: t3 if ... then ... else ... :: Bool -> t5 -> t5 -> t5 if cond then x+y else 0 :: t4

Sada zapisujemo zaključke:

conditionalSum :: t0 -> t1 -> t2 -> t4 t1 = t2 = t3 = Int (zbog +) t5 = Int (zbog else 0) t5 = t3 (zbog x+y) t0 = Bool t4 = t5 conditionalSum :: Bool -> Int -> Int -> Int

Hajde sada da odredimo tip sledeće funkcije i vidimo kako se na isti način može doći do kontradikcije:

f x = x + "pera" x :: t0 "pera" :: String + :: Int -> Int -> Int x + "pera" :: t1 f :: t0 -> t1

t1 = Int t0 = Int String = Int <- kontradikcija!

Međutim, ovo se može popraviti ako se operator + definiše kao:

+ :: t2 -> t2 -> t2

Onda se dobija:

t0 = String = t1 = t2 f :: String -> String

Kasnije tokom ovog serijala ćemo direktno implementirati sistem tipova u Haskelu, a u narednom delu ćemo uvesti Haskel kao jezik i objasniti njegovu sintaksu.

Prethodni deo