Ú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í 2 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. 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.