TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
První část je úvodní: vysvětlíme principy, na kterých je založeno funkcionální paradigma, a srovnáme funkcionální programování s imperativním.
V ukázkách budeme používat funkcionální jazyk
Haskell, jehož interpret
Hugs lze zdarma stáhnout a nainstalovat.
Funkcionální programovací paradigma patří mezi tzv. deklarativní paradigmata. Slovo paradigma (z řeckého παραδειγμα – vzor) značí myšlenkový vzor, metodu, přístup, model uvažování.
Klasický imperativní přístup se zaměřuje na to, jak problém řešit. Popis řešení je rozepsán do kroků probíhajících v čase.
Naproti tomu deklarativní přístup klade důraz na to, co je řešením daného problému. Deklarativní zápis programu představuje již samotné řešení problému zapsané v jistém tvaru. Výpočet podle tohoto programu je pak transformací takového popisu do tvaru jednoduššího, použitelnějšího.
Rozdíl mezi imperativním a funkcionálním přístupem k řešení problému lze ilustrovat třeba na úloze „Najít index největšího prvku v posloupnosti a1, a2, … an navzájem různých kladných celých čísel“. Imperativní program zavádí pomocné proměnné – paměťová místa i, j, max – a skládá se z kroků.
Polož max = 0.
Pro j od 1 do n opakuj: jestliže aj > max, pak polož i = j a max = aj.
Výsledkem je hodnota proměnné i.
Deklarativní popis řešení téže úlohy může vypadat takto:
Takové i z množiny {1, … n}, pro které platí: ∀ j z {1, … n}; ai≥aj
Funkcionální paradigma je založeno na zápisu programu ve tvaru výrazu. Nejdůležitějšími složkami těchto výrazů jsou funkce a jejich aplikace na argumenty. Výpočet funkcionálního programu spočívá ve zjednodušování výrazu až do doby, kdy výraz dále zjednodušit nelze. Tento dále nezjednodušitelný tvar je výsledkem výpočtu.
Například problém „Najít součin čísel 6 a 7“ je zapsán výrazem
6 * 7Tento výraz je aplikací funkce násobení (*) na argumenty 6 a 7. Výpočtem – zjednodušením výrazu – dostaneme hodnotu 42. Ta je dále nezjednodušitelná, tj. je odpovědí (řešením) problému.
Skutečnost, že výraz e se zjednoduší (redukuje) na hodnotu c, budeme značit e →* c, takže výše uvedenou redukci můžeme zapsat 6 * 7 →* 42.
Výrazy se skládají z jednodušších výrazů – podvýrazů. Podvýrazy výrazu M N jsou sám výraz M N, výraz M, výraz N a podvýrazy těchto podvýrazů. Například ve výrazu
sqrt ( sin x )
sqrt
sin
x
sin x
sqrt ( sin x )
Nejdůležitější způsob, jak ze dvou výrazů vytvořit výraz složitější, je aplikace funkce na argument. Aplikace funkce M na argument N je totéž, čemu se v imperativních jazycích říká „volání funkce M s argumentem N“. Aplikaci výrazu M na výraz N zapisujeme M N.
Například zapsáním výrazu pi za výraz sin dostáváme výraz
sin pi
jehož význam je aplikace funkce sinus na číslo π.
Některé funkce a operátory lze aplikovat na více než jeden argument. Například operaci sčítání (+) lze aplikovat na dvě čísla (sčítance). Takovým funkcím a operátorům, které lze aplikovat na dva argumenty, říkáme binární. Obecně může být arita funkce nebo operátoru libovolná – funkce může mít tolik argumentů, kolik jí v definici určíme. Později však uvidíme, že vždy lze vystačit jen s unárními funkcemi – binární a „více-ární“ funkce jsou jen speciálním případem unárních.
Aplikaci binárního operátoru na dva argumenty můžeme zapsat buď takto (prefixově):
(+) 19 23anebo takto (infixově):
19 + 23Nutnou podmínkou, aby mělo smysl aplikovat výraz M na výraz N, je, aby M byla funkce. Například má smysl psát
square 5
not False
neboť square je funkce z čísel do čísel a not je funkce z logických hodnot do logických hodnot, ale nemá smysl aplikace
5 square
True 8
Rovněž by nemělo smysl aplikovat funkci na libovolný argument – výrazy
toUpper False
not 7
sqrt '#'
nemají smysl (toUpper je funkce pro převod malého písmene na velké). V typovaných funkcionálních jazycích se problémů se
zacházením s takovými „nesmyslnými“ výrazy zbavíme prostě tím, že je za výrazy vůbec nepovažujeme: kompilátor typovaného jazyka výskyt
takového „výrazu“ v programu považuje za syntaktickou chybu. V netypovaných jazycích, kde se na synaktické úrovni nedají rozlišit výrazy smysluplné od nesmyslných, by však třeba
výraz not 7 byl legálním programem. Teprve jeho výpočet (tj. až v době běhu) by skončil chybovým hlášením.
Klasické imperativní jazyky zpravidla chápou funkce zcela odlišně od ostatních hodnot – většinou umožňují funkce definovat pouze jako konstanty bez možnosti předávat je jako parametry nebo vracet funkce jako výsledek aplikace jiných funkcí. V Pascalu například můžeme mít pole čísel, ale nemůžeme mít pole funkcí. V jazyku C bychom toto mohli simulovat pomocí ukazatelů, ale přímo samotné funkce do polí či proměnných ukládat nemůžeme. Funkcionální jazyky však pohlížejí na funkci stejně jako na každou jinou hodnotu. Zejména tedy může funkce být parametrem jiné funkce nebo může být funkce výsledkem výpočtu. Funkcím, jejichž argument může být zase funkce, říkáme funkce vyšších řádů. Je možno například definovat operátor (.) vyššího řádu.
( f . g ) x = f (g x)
Tento operátor realizuje skládání funkcí. Pak výraz sin . sqrt má hodnotu funkce počítající sinus druhé odmocniny svého argumentu, zatímco sqrt . sin je funkce počítající druhou odmocninu sinu svého argumentu.
Srovnání s imperativním programováním
Základní sémantickou jednotkou funkcionálního jazyka je výraz. Z jednodušších výrazů se podle syntaktických pravidel mohou skládat výrazy složitější. Sémantická vazba mezi podvýrazy ve výrazu je dána přirozeným pravidlem:
Ve výrazu F A je funkce, která se bude aplikovat na argument, dána hodnotou podvýrazu F; hodnota argumentu, na který se tato funkce bude aplikovat,
je dána hodnotou podvýrazu A.
Základní sémantickou jednotkou imperativního jazyka je příkaz. Na rozdíl od výrazů, příkazy obvykle nemají hodnotu. Proto musí existovat jiný prostředek pro „výměnu dat“ mezi příkazy. Tímto prostředkem je tzv. stav. Stavem se rozumí vektor hodnot programových proměnných v daném okamžiku výpočtu. Příkazy mohou stav měnit. Nejznámějším příkazem pro změnu stavu je přiřazovací příkaz.
Existence stavu má jeden závažný důsledek. Třeba máme funkci, která pro každé kladné celé číslo n spočítá součet druhých mocnin přirozených čísel od 1 do n, a zapíšeme ji v imperativním jazyce (C):
int sumsq (int n) {
int s, k;
s = 0;
for (k = 1; k<=n; k++)
s = s + k*k;
return s;
}
Při volání této funkce s argumentem n se výraz s+k*k vyhodnocuje nkrát, ale pokaždé má jinou hodnotu, zejména hodnoty proměnných s a k jsou v každém průchodu cyklu jiné.
To se ve funkcionálních jazycích stát nemůže (přesněji v čistě funkcionálních, které nekombinují více paradigmat). Čistě funkcionální jazyky mají totiž vlastnost, jíž říkáme referenční transparentnost:
Jestliže se ve stejném kontextu vyskytne tentýž podvýraz, pak jeho hodnota bude vždy stejná.
Například funkci sumsq z předchozího příkladu můžeme definovat takto:
sumsq n = if n==1 then 1 else n*n + sumsq (n-1)
Pak při každém zavolání této funkce bude například hodnota parametru n stejná na všech čtyřech místech výrazu na pravé straně definice funkce sumsq. Ostatně ani neexistuje způsob, jak bychom ji mohli změnit – ve funkcionálním programování nemáme přiřazovací příkaz ani jiné příkazy, které by měly vedlejší efekty, tj. které by měnily globální stav.
Nabízí se tu námitka, že funkce sumsq je referenčně transparentní jen do té doby, než dojde k jejímu opětnému vyvolání; pak se hodnota proměnné n změní – sníží se o jedničku. Ve skutečnosti však k porušení referenční transparentnosti nedochází – proměnná n má ve výrazu if n==1 then 1 else n*n + sumsq (n-1) pouze čtyři výskyty a mimo definici
funkce sumsq tato proměnná neexistuje. Při dalším zavolání funkce
sumsq jde o novou proměnnou, která má s původní společné jen jméno.
Funkcionální jazyky nemají pojem stavu ani přiřazení do proměnné. Proměnné mohou být vázány na hodnotu (formální parametr funkce na skutečný argument), ale tato hodnota nemůže být přepsána. Jediný způsob, jak svázat proměnnou s hodnotou, je při aplikaci funkce na argument – proměnná (formální parametr) se sváže s argumentem (skutečným parametrem). Máme-li například funkci square definovanou
square x = x * x
a aplikujeme-li ji na argument (6+7) ve výrazu
square (6+7)
pak se při výpočtu proměnná x sváže s výrazem (6+7), výraz square(6+7) se nahradí pravou stranou definice funkce square, tj. výrazem x * x.
V něm se však proměnná x nahradí výrazem, s nímž je svázána, takže na konci prvého kroku výpočtu bude mít celý výraz tento tvar:
(6+7) * (6+7)
Vazbě formálních parametrů funkcí na skutečné parametry se říká prostředí.
Funkcionálního přístupu lze k řešení nějakého problému s výhodou použít všude tam, kde řešení má mít tvar funkce – k danému (jednorázově zadanému) vstupu vydat (jeden) výstup. Například algoritmu, jehož parametrem je síť ulic a a dva body a výsledkem nejkratší cesta z jednoho bodu do druhého. Už méně se funkcionální přístup hodí k programování úloh, které vyžadují mnoho interakcí s uživatelem a okolím. I v takových úlohách se však obvykle vyskytují dílčí podúlohy formulované „funkcionálně“, takže v praxi se také používá kombinace funkcionálního a imperativního přístupu.
Skutečnost, že ve funkcionálních programech není pojem stavu, usnadňuje formální manipulace s programy, například formální dokazování jejich správnosti. Určité transformace funkcionálních programů se definují a provádějí mnohem jednodušeji než odpovídající transformace programů imperativních.
Funkcionální jazyky, překladače, interprety
Matematickým vzorem, z něhož vychází většina funkcionálních jazyků, je tzv. lambda kalkul, který vznikl už počátkem 30. let minulého století.
Prvním skutečným funkcionálním programovacím jazykem s implementovaným překladačem byl jazyk Lisp, který měl velmi jednoduchou syntaxi, nebyl typovaný a nebyl vlastně ani čistě funkcionální – měl i řadu imperativních rysů. Z Lispu se později vyvinul jeho dialekt Scheme.
Koncem 70. let vznikl v Edinburghu jazyk ML s velmi silnou typovou disciplínou. Na jeho principech bylo navrženo několik dalších jazyků (Hope, Clean, Miranda …).
V 90. letech vznikl jazyk Haskell, který používáme v našich ukázkách. Podrobný popis Haskellu najdete na jeho domovské stránce.
Kompilátorů Haskellu je několik. Za nejpropracovanější je považován Glasgow Haskell Compiler.
Pokud nebudeme v Haskellu vyvíjet velké programy, stačí na vyzkoušení interpret Hugs. Jeho instalace je rychlá a na zkoušení malých příkladů je pohotovější než neustálé překládání kompilátorem. Interpretace je samozřejmě mnohem pomalejší než výpočet přeloženého programu, ale to nám u malých příkladů obvykle nevadí.
Shrnutí
- Ve funkcionálním programování je následující pojetí programu a výpočtu:
program...........................výraz
výpočet............................úprava výrazu
výsledek...........................dále nezjednodušitelný tvar výrazu - Funkce jsou „občané první kategorie“ mající stejná „práva a povinnosti“ jako například konstanty.
- Funkcionální jazyky jsou referenčně transparentní, stejný výraz má ve stejném prostředí vždy stejnou hodnotu.
- V příkladech budeme používat jazyk Haskell. Příklady si můžete nechat zkoušet počítat pomocí programu Hugs – interpretu Haskellu.
