Co je to funkcionální programování
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

Co je to funkcionální programováníCo je to funkcionální programování

 

Co je to funkcionální programování

Google       Google       12. 4. 2006       24 730×

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.

Reklama
Reklama

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}; aiaj

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 * 7

Tento 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 )
jsou tyto podvýrazy:


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 23

anebo takto (infixově):

19 + 23

Nutnou 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.

×Odeslání článku na tvůj Kindle

Zadej svůj Kindle e-mail a my ti pošleme článek na tvůj Kindle.
Musíš mít povolený příjem obsahu do svého Kindle z naší e-mailové adresy kindle@programujte.com.

E-mailová adresa (např. novak@kindle.com):

TIP: Pokud chceš dostávat naše články každé ráno do svého Kindle, koukni do sekce Články do Kindle.

Hlasování bylo ukončeno    
0 hlasů
Google
Autor je profesorem na Fakultě informatiky Masarykovy univerzity v Brně.

Nové články

Obrázek ke článku Delphi 10.1.2 (Berlin Update 2) – na co se můžeme těšit

Delphi 10.1.2 (Berlin Update 2) – na co se můžeme těšit

Touto roční dobou, kdy je zem pokrytá barevným listím a prsty křehnou v mrazivých ránech, se obvykle těšíme na zbrusu novou verzi RAD Studia. Letos si však ale budeme muset počkat na Godzillu a Linux až do jara. Vezměme tedy za vděk alespoň updatem 2 a jelikož dle vyjádření pánů z Embarcadero se budou nové věci objevovat průběžně, pojďme se na to tedy podívat.

Reklama
Reklama
Obrázek ke článku Konference: Moderní datová centra pro byznys dneška se koná už 24. 11.

Konference: Moderní datová centra pro byznys dneška se koná už 24. 11.

Stále rostoucí zájem o cloudové služby i maximální důraz na pružnost, spolehlivost a bezpečnost IT vedou k výrazným inovacím v datových centrech. V infrastruktuře datových center hraje stále významnější roli software a stále častěji se lze setkat s hybridními přístupy k jejich budování i provozu.

Obrázek ke článku Konference: Mobilní technologie mají velký potenciál pro byznys

Konference: Mobilní technologie mají velký potenciál pro byznys

Firmy by se podle analytiků společnosti Gartner měly  rychle přizpůsobit skutečnosti, že mobilní technologie už zdaleka nejsou horkou novinkou, ale standardní součástí byznysu. I přesto - nebo možná právě proto - tu nabízejí velký potenciál. Kde tedy jsou ty největší příležitosti? I tomu se bude věnovat již čtvrtý ročník úspěšné konference Mobilní řešení pro business.

Obrázek ke článku Hackerský kongres přiveze v září do Prahy špičky světové kryptoanarchie

Hackerský kongres přiveze v září do Prahy špičky světové kryptoanarchie

Hackerský kongres HCPP16 pořádá od 30. září do 2. října nezisková organizace Paralelní Polis již potřetí, a to ve stejnojmenném bitcoinovém prostoru v pražských Holešovicích. Letos přiveze na třídenní konferenci přes 40 většinou zahraničních speakerů – lídrů z oblastí technologií, decentralizované ekonomiky, politických umění a aktivismu. Náměty jejich přednášek budou také hacking, kryptoměny, věda, svoboda nebo kryptoanarchie.

loadingtransparent (function() { var po = document.createElement('script'); po.type = 'text/javascript'; po.async = true; po.src = 'https://apis.google.com/js/plusone.js'; var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(po, s); })();
Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý