Jiří Knesl napsal plugin ĚĽŠČŘ, Jakub Vrána mu jej zkritizoval a Jiří Knesl zareagoval na Jakubovu kritiku tím, že mu šlo hlavně o vyzkoušení funkcionálního programování. Jakub Vrána se ale podivuje, co je na tom tak elegantního. I já se tedy do diskuze zapojím, byť se zpožděním. Napřed ale trošku odbočím.
Způsoby vyhodnocování
Nechci tu mít moc teorie, tak jen ve stručnosti:
Striktní vyhodnocování
Toto určitě všichni znáte, protože to využívají snad všechny mainstreamové jazyky. Vyhodnotí se prostě vše (nepočítáme-li optimalizace jako &&), i pokud to nebude nikdy potřeba. To je právě důvod, proč v Javascriptu výraz [3, decodeURIComponent("aa=%gg"), 8, 9][3] nevrátí hodnotu 9, ale skončí výjimkou.
Vyhodnocování on-demand
Druhá možnost je provést vyhodnocování teprve ve chvíli, kdy je to potřeba. Sem patřì normální a líné vyhodnocování, rozdíly mezi nimi teď nejsou podstatné. Pokud se v Haskellu pokusíme vyhodnotit [3, 1 `div` 0, 8, 9] !! 3, dostaneme 9, ačkoli celočíselné dělení nulou končí v Haskellu výjimkou. Funguje to díky tomu, že výraz 1 `div` 0 není potřeba vyhodnocovat. Pokud by se vyhodnocoval, vznikla by v Haskellu výjimka kvůli dělení nulou.
Asi je zřejmé, proč v mainstreamových (aspoň trošku imperativních) jazycích na toto nenarazíte: jakmile byste začali ve výrazech používat side effects, nastala by pravá magie. Těžko by se ovlivňovalo pořadí vyhodnocování (nebo to, zda by se něco vůbec vyhodnotilo) a chování programu by se začalo nepředvídatelně měnit.
Funkcionální klasika: linked list
Ve funkcionálním programování je spojový seznam velmi oblíbený. Ne, že by nešlo používat např. klasické pole, ale klasický funkcionální spojový seznam je dobré znát. Seznam je buď prázdný (v Haskellu []), nebo se skládá z jednoho prvku a reference na zbytek seznamu (v Haskellu head:tail). Tak je seznam definován rekurzivně a lze některé suffixy seznamu použí ve více různých seznamech. Například budeme mít dva seznamy o sto prvcích, ale budou se lišit vždy jen v prvním prvku, takže do paměti uložíme jen 101 prvků. Na funkčnost to nebude mí vliv, protože tyto seznamy jsou immutable. U vyhodnocování on-demand je navíc možné mít nekonečné seznamy. Součet nekonečné řady tak sice nespočítáte (aspoň ne přesně, sum (takeWhile (<epsilon) someList), tedy součet členů menších než epsilon u klesající řady, fungovat bude), ale třeba seznam všech prvočísel, ze kterého se na konec ve skutečnosti vyhodnotí jen prvních n z nich, není problém.
Jak je to s funkcemi map a filter
A už se dostávám ke článku, na který jsem reagoval. Funkce map a filter (popř. další, jako třeba reduceLeft, reduceRight, take, drop, takeWhile, dropWhile...) skutečně nejsou vše, o čem je funkcionální programování. Programovat bez nich skutečně lze. Ale není to ono. Až tak se nedivím, že se Jakub Vrána pod článkem podivil, kde je ta elegance.
Jak jsou tyto funkce (map, reduce, ...) ve skutečnosti implementovány?
Teď budu trošku kritizovat. A to článek nejen Jiřího Knesla, ale i samotné funkcionální programování. Jde mi o to, že funkce typické pro funkcionální programování není až tak snadné napsat správně. Ukážeme si to na funkci map. Nejdřív si odbydeme vyhodnocování on-demand (které zkritizuju za chvilku). Tam není nutné řešit tail call optimization, protože díky způsobu vyhodnocování nenastane rekurze v té podobě, v jaké ji známe ze striktního vyhodnocování. Můžeme tedy namapovat první prvek a rekurzivně namapovat zbytek:
map f (x:xs) = (f x) : (map f xs)
Funkce tedy vezme funkci f a seznam (x:xs). Zápis (x:xs) ve skutečnosti znamená, že parametr je neprázdný seznam a ten je rozdělen na první prvek (x) a zbytek (xs). Zbývá dořešit prázdný seznam, ten se namapuje na prázdný seznam:
map f [] = []
Jenže takto to funguje dobře jen u vyhodnocování on-demand. U striktního vyhodnocování získáme s dlouhými seznamy mnoho rekurzí a potřebujeme velký stack. Nepomůže ani tail call optimization, protože poslední operace není rekurze, ale vytvoření seznamu (:). Takto tedy ne.
Pak se nám nabízí použít akumulátor, což přesně udělal Jiří Knesl. Určitou nevýhodou je, že seznam procházíme od začátku, ale přidáváme též na začátek. Výsledný seznam tedy dostaneme v opačném pořadí:
map f list = map0 f list []
map0 f [] acc = acc
map0 f (x:xs) acc = map0 f xs ((f x):acc) -- chyba, obracíme pořadí.
Můžeme na to zavolat i funkci reverse (tu jde naštěstí napsat snadno) a dostaneme dokonce i dobrou asymptotickou složitost (konstantní na stack, lineární na heap a na čas), ale je to velmi neelegantní. O paměťové lokalitě nemluvě.
Trošku po svém si s tím poradila Scala (funkcionální jazyk se striktním vyhodnocováním). Funkce map je u třídy List efektivní, elegantní, čitelná (byť se znalostí pokročilejších konstrukcí), ale bohužel ne funkcionální. Autoři byli pragmatici, ne fanatici.
Původně jsem sem chtěl zkopírovat i implementaci pro důkaz, že to je fakt imperativně. Třída List ale nechává implementaci metody map na traitu TraversableLike, který to implementuje obecněji. Vysvětlovat tu implementaci lidem, kteří jazyk Scala nepotkali, by ale bylo nad rámec tohoto článku.
Snadný paralelismus?
Funkcionální programování k paralelismu přímo vybízí. Například ve Scale stačí do funkcionálního kódu přidat na pár míst par a hned je paralelní. (No dobře, má to svá úskalí, ale o tom třeba jindy.) U striktního vyhodnocování to funguje celkem dobře, pokud se u funkcí jako je map vzdáme části elegance. Menší problém je formát seznamu, spojový seznam není příliš vhodný u mnoha krátkých výpočtů.
Horší situace je u vyhodnocování on-demand. Co všechno má být vyhodnoceno paralelně? Pokud se výpočet něčeho odloží na později, nemusí se to vykonávat paralelně. Pokud se má vyhodnotit vše, bude se to vyhodnocovat striktně. Mimochodem, na tento problém jsem narazil ve Scale u funkce mapValues, která se kupodivu nechovala striktně. Místo toho, aby výpočet proběhl celý paralelně, se podstatná část odložila na později a spočítala se až při výpisu. Samozřejmě sériově.
Tail call optimization
A ještě jedna věc, která se sice netýká výhradně funkcionálního programování, ale – protože se tam rekurze prostě používá často – stojí za zmínku. Navíc chci v tomto reagovat i na Jiřího Knesla. Myšlenka je, že pokud je nějaké volání funkce posledním příkazem, lze uvolnit místo na stacku již při volání. Typicky se toho využívá při rekurzi. Z koncové rekurze kompilátor může udělat (mírně zjednodušeno) skok na začátek funkce. Program s rekurzí se tak může přeložit úplně stejně, jako kdyby měl cyklus. Teorie je to pěkná, Jiří Knesl se na to i odvolává při obhajobě svého skriptu. Jak je to ale doopravdy?
Hledal jsem Tail call optimization v Javascriptových enginech (na kterých bdou záviset i optimalizace Livescriptu), ale moc jsem o tom nenašel, nejvýše plány. Možná jsem jen špatně hledal, ale spíš bych se na to nespoléhal.
Ona to vlastně ani není ekvivalentní úprava. Pokud čteme stack trace (např. z výjimky), dostáváme po optimalizaci jiné údaje. To nemusí vadit, pokud o tom víme. U Javy je ale snaha zpětným nekompatibilitám (třeba i teoretickým) bránit, takže se tato optimalizace sice zvažuje, ale volání metody musí být (podle jednoho návrhu) uvozeno speciální instrukcí. Nevím o tom, že by dnes něco takového bylo v nějaké production-ready JVM podporováno. Podporovat to může kompilátor (a kompilátor pro Scalu to skutečně podporuje), ale možnosti jsou omezené. Optimalizovat takto rekurzi známou v době překladu lze relativně snadno (stačí do parametrů přiřadit nové hodnoty a goto 0, jen je potřeba řešit, aby korektně fungovalo např. i prohození parametrů), ale jiné tail calls moc dobře nejdou, protože JVM nemá instrukce pro takto low-level práci se zásobníkem. A v případě Scaly doporučuji @tailrec, aby kompilátor nezradil. U Livescriptu by teoreticky mohlo být něco podobného, překladač má asi podobné možnosti.
Závěr
Ano, funkcionální programování nabízí řadu výhod – eleganci, použitelné vyhodnocování on-demand, snadný paralelismus a další. Nemůžte ale od toho chtít všechno současně. Mám sice rád líný čistě funkcionální Haskell, ale v praxi píšu spíš v ne úplně čistě funkcionální Scale.
Pure functional programming is like anarchism: everything is stateless. Although I believe that reducing the state is often useful, I am not sure if total elimination of state is a good idea.
