Úvod do funkcionálního programování

(Podle slidů minulé přednášky.)

• Imperativní programování je založeno na příkazech, které mění stav.
• Funkcionální programování
  • spadá do deklarativního programování,
  • je založeno na vyhodnocování výrazů,
  • obvykle se vyhýbá změnám stavů a proměnlivým datům.

• Funkcionální jazyky umožňují vyšší míru abstrakce než imperativní jazyky, a snažší rozdělení do komponent. Například, opakující se postup lze často abstrahovat pomocí funkcí vyšších řádů, a tím vzniká srozumitelnější a deklarativnější kód.
• Často jsou funkcionální programy kratší srozumitelnější, než odpovídající imperativní programy. (Někde se uvádí 2x až 10x.)¹⁾
• Silné typové systémy umožňují větší kontrolu kódu při překladu.²⁾
• Neměnitelná data umožňují překladači účinněji optimalizovat (nebo dokonce paralelizovat) výsledný kód.
• Líné vyhodnocování často výrazně urychlí některé algoritmy (příklad).

• Počítače jsou navrženy a optimalizovány na imperativní programy.
• Některé algoritmy jsou z principu imperativní a těžko se implementují ve funkcionálních jazycích. Např. hašovací tabulka.
• Výsledný kód je často méně efektivní (konstantním faktorem), zvlášť u jazyků s líným vyhodnocováním.
• … a s tím souvisí složitější překlad a nutnost specializovaných optimalizací.
• U jazyků s líným vyhodnocováním je často problém odhadovat a optimalizovat paměťovou náročnost algoritmu.

Funkce jsou objekty první třídy³⁾.

• Hodnoty jsou funkce s 0 argumenty.
• Funkce tedy mohou být použity jako parametry do jiných funkcí (kterým se někdy říká funkce vyššího řádu), nebo jako výsledky výpočtů.
• Lze tak snadno abstrahovat opakující se postupy. Například, naprostou většina operací na seznamech lze provést pomocí foldr.

• Funkce mohou být vnořené.
• Vnořené funkce se mohou odkazovat na proměnné nadřazených funkcí.

subtractNFromList :: Num alpha => alpha -> [alpha] -> [alpha]
subtractNFromList v xs = map (\x -> x - v) xs

• Funkce \x → x - v se odkazuje na v.
• Takové vnořené funkce mohou „unikat“ z kontextu.
• Na výraz subtractNFromList 3 se lze také dívat jako na funkci vyššího řádu, která z čísla vytváří funkci.

• Rekurze je základní prvek funkcionálních jazyků umožňující iterovat výpočty. Klasické cykly nejsou, jelikož se vyhýbáme změnám stavů.
• Rekurzi lze nahradit specializovaným kombinátorem. (To se hodí spíše pro teoretické aspekty, prakticky je efektivnější a čitelnější klasický rekurzivní zápis.)
• Cykly jsou vyjádřeny pomocí tail rekurze.

• Výrazům jazyka jsou staticky⁴⁾ přiřazovány typy, a to automaticky nebo programátorem.
• Výsledek výpočtu výrazu má stejný typ jako původní výraz.
• Typy zajišťují, že program nikdy nezhavaruje proto, že by přistupoval k datům nesprávným způsobem.
• Typické konstrukce typových systémů:
  • Typ pro funkce - funkce z typu a do typu b má typ a → b.
  • Typy pro uživatelské datové struktury.
  • Parametrizované polymorfní typy (např. funkce počítající délku seznamu).
  • Ad-hoc polymorfismus (např. rovnost definovaná různě na různých typech).

• Problém:
  • Slabé typové systémy přinášejí malý užitek.
  • Silné typové systémy neumožňují odvození typů, takže programátor musí explicitně uvádět typy výrazů.
• Kompromis – Hindley–Milnerův typový systém umožňuje jednoznačné odvození nejobecnějšího typu výrazu/funkce (princip podobný unifikaci), a přitom je dostatečně silný (polymorfismus).
• Od vzniku Hindley–Milnerova typového systému v 70-tých letech se začaly ve větší míře používat ve funkcionálních jazycích typové systémy odvozené z typovaných lambda kalkulů.
• Poznámka: Existují i systémy s tzv. závislými typy, které umožňují v typu postihnout jakýkoliv predikát.

• Z primitivních (a funkčních) typů konstruujeme nové typy pomocí (pojmenovaných) direktních součinů a součtů. (To vzdáleně odpovídá konstrukcím struct a union z C.)
• Typy mohou být rekurzivní.
• Hodnoty těchto typů pak můžeme rozpoznávat podle vzorů a zjišťovat tak hodnoty, z kterých byly zkonstruovány. U direktní součtů pak větvit výpočet.

Seznam je buďto prázdný, a nebo je to dvojice hodnota a zbytek seznamu. Matematicky: List a = μ t . 1 ⊕ (a ⊗ t) ⁵⁾ V Haskellu:

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

Součet čísel v seznamu můžeme zapsat:

sum :: List Int -> Int
sum Nil           = 0
sum (Cons x xs)   = x + sum xs

• Některé funkcionální jazyky umožňují funkcím, aby prováděly akce mimo výpočtu svého výsledku.
• Tyto akce se nazývají vedlejší efekty (side effects)⁶⁾.
• Jazyky, které neumožňují vedlejší efekty funkcí se nazývají čisté (pure).
• I v nečistých jazycích je vhodné psát kód tak, aby co největší část zůstala čistá – nečistý kód je obvykle náchylnější k chybám.

• Čisté jazyky neumožňují měnit data. (Změna dat by byla vedlejším efekt.)
• Místo změny datové struktury se vytvoří struktura nová, upravená o potřebné změny.
• Původní struktura zůstane zachována. Pokud není využita, tak její nadbytečné části jsou zlikvidovány GC.
• Optimální algoritmus zachová maximum původní struktury.
• Příklady:
  • U vyvážených binárních stromů při přidání prvku vznikne jen O(log n) nových uzlů.
  • Speciální datová struktura finger tree (shrnutí) pro reprezentaci konečných sekvencí má amortizovanou složitost⁷⁾ O(1) pro operace na koncích a O(log n) pro operace uvnitř.

• Referenční transparentnost: Výsledek čisté funkce závisí pouze na jejích argumentech.
• To umožňuje odvozovat a dokazovat vlastnosti programů vlastnosti.

• Programátor čas od času potřebuje i „nečisté“ prostředky, jako například:
  • Komunikace s uživatelem.
  • Zapisovat/číst do souborů.
  • Komunikovat po síti.
  • Používat a měnit velká pole.
• V praxi se používají tyto přístupy:
  1. Dovolí se vedlejší efekty funkcí (OCaml, F#). To vyžaduje větší disciplínu programátora. Nejde dohromady s líným vyhodnocováním.
  2. Unikátní typy, kde je překladačem ošetřeno, že se problematické hodnoty (např. file handle) mohou použít jen jednou.
  3. Vedlejší efekty se popíší pomocí monád (Haskell). Tento přístup zachovává čistotu a je konzistentní s líným vyhodnocováním. Zároveň lze z kódu jasně vyčíst, kde se provádějí jaké „nečisté“ akce.

• Líné vyhodnocování (Haskell):
  • Výraz se vyhodnocuje teprve tehdy, když je jeho hodnota potřeba.
  • Výraz se vyhodnocuje jen do té míry, kolik je v dané situaci nutné.
  • Místo hodnoty se funkcím v argumentu předává tzv. thunk⁸⁾, který říká, jak hodnotu spočítat.
  • Nejde dohromady s vedlejšími efekty – nevíme, kdy/zda se daná funkce vyhodnotí.
  • Například length [ 1, 2^1000, undefined ] bude vyhodnoceno na 3 v čase O(3).
  • Nevýhoda: Nevyhodnocený strom thunků může někdy nabývat nadměrných rozměrů – vzniká zcela zbytečná paměťová zátěž. Řešení: možnost přinutit překladač k striktnímu vyhodnocování, případně automatická detekce.
  • Striktní vyhodnocování (známé z imperativních jazyků) naopak nejprve vypočte hodnotu výrazu, než ji použije jako argument do funkce.