Proč bychom se báli rekurze a Scaly

Jedním z témat probíraných v kurzu funkcionálního programování Functional Programming Principles in Scala bylo použití rekurze. V tomto článku se blíže podíváme na přirozený soulad rekurze s funkcionálním stylem programování a optimalizaci rekurze ve Scale.

Rekurze je mocným nástrojem pro řešení řady problémů. Může být aplikována, kdykoliv je možné problém rozložit na problémy menší velikosti stejného typu, když jsme schopni z výsledného řešení problému menší velikosti složit řešení problému větší velikosti a jsme si jisti, že problém triviální velikosti má jednoznačné řešení a rekurzivní volání skončí právě na vyhodnocování tohoto triviálního problému.

Funkcionální programování s oblibou využívá rekurzivního volání, které často vede k elegantně a jednoduše zapsaným algoritmům, které se díky rekurzi obejdou bez zbytečného cyklení, které je typické pro imperativní styl programování. Ve Scale samozřejmě je možné používat cykly, ale použití cyklu znamená použití nějaké řídící proměnné cyklu, jejíž stav se mění (např. inkrementuje), a zde už můžeme nadělat některé nepěkné chyby, obzvlášť pokud ve svém kódu cykly často opakujeme, aniž bychom danou logiku zapouzdřili do nějaké znovupoužitelné funkce.

Takovou chybou je typicky nesprávná inicializace nebo aktualizace řídící proměnné - např. vynechání některých průchodů, přetečení. Obzvláště při složitějších podmínkách pro ukončení cyklu nebo při aktualizaci řídící proměnné jen v určitých průchodech kódem může snadno dojít i k vytvoření nechtěného nekonečného cyklu.

Čistě funkcionální styl programování upřednostňuje řešení bez řídících proměnných cyklu, u kterých se mění stav - vystačí si čistě s voláním funkcí, které vrací výslednou hodnotu a nemají žádné vedlejší efekty. Zde může být nápomocné právě použití rekurze. Zapouzdření funkcionality do samostatné testovatelné, případně znovupoužitelné a rozšiřitelné funkce (funkcí) je hlavní výhodou oproti cyklům, ke které nás funkcionální styl programování přirozeně vede. Kód využívající kratší funkce se samovysvětlujícím názvem je rovněž čitelnější. I v případě rekurze si však musíme dát pozor na konečnost výsledného algoritmu.

Tail rekurze

Scala kompilátor umožňuje optimalizovat rekurzivní volání na cyklické volání kódu, musí se však jednat o tzv. tail rekurzi. Optimalizace rekurzivního volání nám zajistí, že algoritmus bude použitelný i na data velkého rozsahu, u kterých by jinak mohlo dojít k přetečení zásobníku (StackOverflowException za běhu programu).

Optimalizovaná rekurze využije pro všechna rekurzivní volání cyklické volání kódu a jen jeden rámec zásobníku, což se projeví např. i pouze jedním řádkem ve výpisu stacktrace při debugování takového kódu namísto více řádků pro jednotlivé rekurentně volané průchody. Tímto se nesmíme nechat zmást.

Jak poznáme tail rekurzi?

  • Rekurzivně volaná funkce/metoda musí být privátní, nesmí být přepsatelná v potomkovi,
  • rekurzivní volání se musí objevovat samostatně na konci větve/větví průchodu kódem, tj. nesmí být součástí nějaké jiné operace.

Zobecněním termínu "tail rekurze" je "tail volání", které zahrnuje i případy, kdy se jako poslední akce funkce volá jiná funkce (nemusí se tedy nutně jednat o volání té samé funkce). I tato tail volání lze teoreticky optimalizovat tak, že na ně může být použit jen jeden rámec zásobníku. JVM nepodporuje tzv. Tail Call Optimization (TCO) nativně, optimalizaci provádí Scala kompilátor. Kvůli omezením JVM se optimalizují jen rekurzivní volání stejné funkce, ve které se volání nachází, nikoliv nepřímá rekurzivní volání.

Například následující funkce pro výpočet faktoriálu není tail rekurzivní, protože rekurzivní volání není prováděné samostatně na konci funkce, ale je součástí operace násobení:

Před definicí metody (nebo funkce), u které si myslíme, že je tail rekurzivní, se doporučuje uvést anotaci @tailrec, která zajistí, že kompilátor prověří podmínky pro aplikovatelnost optimalizace, a pokud optimalizaci neprovede, je při kompilaci vyvolána chyba (could not optimize @tailrec annotated method factorial: it contains a recursive call not in tail position). Tímto si tedy potvrdíme očekávané provedení optimalizace rekurze.

Příklad tail rekurzivní funkce pro výpočet největšího společného dělitele:

Kdy použít tail rekurzi

Některé algoritmy jsou přirozeně tail rekurzivní, nekteré ne. Některé je možné upravit (kód přeuspořádat) tak, aby tail rekurzivní byly. Nemá smysl se o to ale snažit za každou cenu, je vhodné upřednostnit spíše čitelnost (optimalizace by nikdy neměla být prováděna předčasně). Pokud je převod na tail rekurzi obtížný, vždy lze rekurzi nahradit imperativním stylem programování s cykly, což se děje např. i v interní implementaci metod Scala kolekcí, aby byl algoritmus tzv. "production ready" a při použití na rozsáhlých kolekcích nedocházelo k přetečení zásobníku.

Převod na tail rekurzi

Na příkladu si předvedeme užitečný postup, které lze použít při převodu rekurze na tail rekurzi. Příklad vychází z on-line kurzu Functional Programming Principles in Scala.

Výpočet faktoriálu převedený na tail rekurzi:

Výpočet používá pomocnou vnořenou funkci accumFactors, která slouží k akumulování výsledku v proměnné accumulator - ten je hned vracen, pokud se jedná o triviální případ výpočtu, nebo použit jako vstup do dalšího rekurzivního volání, aniž by byla přímo měněna hodnota nějaké proměnné. Vnořená funkce accumFactors je tak "funkcionální" náhradou "imperativního" cyklu.

Použití takovýchto pomocných funkcí vede k poměrně bezpečnému, explicitnějšímu a znovupoužitelnějšímu způsobu řešení oproti použití cyklu se změnou stavu, který jako syntaktická konstrukce jazyka není nijak uživatelsky zapouzdřen a srozumitelně pojmenován. Díky obdobné akumulační funkci můžeme například nahradit sestavení mutable kolekce (např. vkládáním prvků na konec) čistě funkcionálním vytvořením immutable kolekce (akumulováním prvků).

Příklad metody, která kóduje jednotlivé znaky ze vstupního seznamu remainingText do bitů a ty akumuluje do výsledného seznamu accum, který je vrácen ve výsledku:

Zdroje

  1. Odersky, Martin, Lex Spoon, Bill Venners. Programming in Scala, Second Edition. Artima Press, 2010. Web: http://booksites.artima.com/programming_in_scala_2ed.
  2. Suereth, Joshua D. Scala in Depth. Manning Publications Co., 2012. Web: http://www.manning.com/suereth/.
  3. Odersky, Martin. Functional Programming Principles in Scala. 2012. Dostupné na webu: https://class.coursera.org/progfun-2012-001/class/index.

Článek obsahuje 0 komentářů