Funkcionální programování

NAIL097, Petr Pudlák, KTIML. Vyučováno v zimním semestru Zk 2/0. Kontakt na mě: kontaktní formulář

Zimní semestr 2012: Umluveno na pondělí 15:40 S10.

Varování: Funkcionální programování je vysoce návykové! Postižení programátoři odmítají programovat v jiných než funkcionálních jazycích. Nutí je svým týmovým kolegům a procedurální jazyky jim způsobují abstinenční příznaky.

Praktických návodů a úvodů do funkcionálního programování je mnoho. Ale po určité době každý funkcionální programátor zjišťuje, že pro hlubší pochopení této oblasti se bez znalosti teorie se neobejde. Cílem této přednášky je proto seznámit posluchače s teorií, která stojí za funkcionálním programováním. Nebudeme se naopak na přednášce příliš zabývat konkrétní syntaxí konkrétních funkcionálních jazyků (i když příklady budou uváděny především v Haskellu). Předpokládáme, že posluchač již má alespoň malé praktické zkušenosti s funkcionálními jazyky, a nebo si je v průběhu přednášky doplní samostudiem či v rámci některého jiného předmětu.

Po absolvování přednášky by měl mít posluchač (mimo jiné) takové znalosti, které by mu umožnily napsat jednoduchý překladač/interpret funkcionálního jazyka, obsahující například: rekurzi, líné vyhodnocování, silný typový systém (typový polymorfismus, odvozování typů), (rekurzivní) datové typy. V tomto duchu i budou zadávány úlohy v průběhu semestru. (Další info viz. slidy z přednášky z roku 2010.)

V případě dotazů k přednášce neváhejte využít kontaktního formuláře.

A language that doesn't affect the way you think about programming, is not worth knowing. (Epigrams in Programming)

Programátory přitahují funkcionální jazyky především pro eleganci, s jakou se v nich lze vyjadřovat a formulovat programy. Nejen že elegantní vyjádření myšlenky přináší intelektuální uspokojení. Elegantní kód snižuje složitost a komplexnost programu. Je čitelný. Obsahuje méně chyb. Je kratší. Snadno se udržuje. Snáze mu rozumí a používají jej ostatní.
Fools ignore complexity. Pragmatists suffer it. Some can avoid it. Geniuses remove it. (Epigrams in Programming)

Jeden z cílů funkcionální programování je umožnit co nejvíce specifikovat vlastnosti dané části kódu. Základní vlastností, ke které směřují funkcionální jazyky, je referenční transparentnost: výsledek funkce závisí pouze na jejích argumentech. Referenčně transparentní funkce mají velmi blízko k matematickému pojetí funkcí a umožňují velmi přesně analyzovat jejich vlastnosti. V imperativních jazycích se obvykle o této vlastnosti nehovoří, protože funkce běžně zasahují do prostředí programu nebo naopak z něho získávají informace, a tedy nelze jejich chování popsat jen pomocí jejich argumentů.

Snaha o referenční transparentnost vede nevyhnutelně k eliminaci změn stavů. Umožníme-li změny struktur, s kterými program pracuje, bude výsledek funkce pracující s nějakou strukturou záviset na čase, kdy bude zavolána. Nebude referenčně transparentní. Proto jsou obvykle všechny vytvořené struktury (až na výjimky)¹⁾ neměnné. Možná překvapivě to není velký problém, existuje mnoho (často velmi zajímavých) datových struktur, které jsou optimalizovány na neměnnost. (Doporučuji knihu Chris Okasaki: Purely Functional Data Structures - viz. Literatura.)

Eliminace změn stavů následně umožňuje líné vyhodnocování, tedy vyhodnocování výrazů až tehdy, pokud je jejich výsledek potřeba. To je mocná, i když někdy dvojsečná zbraň. Umožňuje například konstruovat nekonečné datové struktury (kupříkladu. seznam všech prvočísel). Nebo například pokud setřídíme merge sort algoritmem seznam, a vyžádáme si pouze první prvek výsledného seznamu, bude složitost tohoto programu pouze n, nikoliv n log n.

Proč se funkcionálním jazykům říká funkcionální? Protože v nich jsou funkce objekty první třídy. Mohou být předávány jako parametry jiným funkcím (tzv. funkcím vyšších řádů) nebo naopak vraceny jinými funkcemi jako výsledky. Vychází z lambda kalkulu, kde jsou všechny konstrukce funkcemi.

Důležitým prvkem funkcionálních jazyků jsou silné typové systémy. Čím silnější typový systém, tím více vlastností programů jím lze popsat a ověřit při překladu. Zároveň takové typové systémy umožňují vysokou míru abstrakce, zvlášť ve spojení s funkcemi vyšších řádů. Pro programátora to znamená kratší a elegantnější kód a velké možnosti abstrakce často se opakujících vzorů.

Funkcionální programování zasahuje do různých oblastí informatiky i matematiky. Zejména má blízko k intuicionistické logice a k teorii kategorií. Obojího se na přednášce dotkneme.

Stručně výhody funkcionálních programů:

• Funkcionální jazyky umožňují vyšší míru abstrakce než imperativní jazyky, a snazší 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).

a také nevýhody:

• Počítače jsou navrženy a optimalizovány na imperativní programy.
• Některé algoritmy (není jich moc) jsou z principu imperativní a těžko se implementují ve funkcionálních jazycích. Např. hašovací tabulka.
• Neměnnost datových struktur, či spíše jejich častější konstrukce, klade vyšší nároky a zátěž na garbage collector.
• 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í.

• Informace pro přednášku v roce 2010/11.
• Slidy a literatura k přednášce.
• Zajímavé odkazy.