Fórum Root.cz
Hlavní témata => Vývoj => Téma založeno: dl 03. 05. 2014, 12:53:10
-
(...) In imperative languages, recursion always raises the specter of stack overflows (too many recursive calls) and performance issues (...)
Jaký je rozdíl mezi správně naprogramovanou rekurzivní funkcí (pokud neudělám nějakou nekonečnou smyčku) např. v C namísto nějakého funcionálního jazyka?
-
To jsou nehezka sluvka a veticky. Viz http://en.wikipedia.org/wiki/Tail_recursion
Tail calls are significant because they can be implemented without adding a new stack frame to the call stack.
Traditionally, tail call elimination is optional. However, in functional programming languages, tail call elimination is often guaranteed by the language standard, and this guarantee allows using recursion, in particular tail recursion, in place of loops
Vetsina dnesnich prekladacu imperativnich jazyku dela eliminaci tail-callu, ergo vyse zmineny citat neni pravdivy.
-
Sám jste si odpověděl, i když to nevíte :) Ve funkcionálních jazycích není problém mít nekonečnou rekurzi, oblíbená bývá funkce vracející celou Fibonacciho posloupnost, program používá lazy evaluation a výpočet provádí, až když je potřeba, a jen do potřebné hloubky. V imperativních jazycích to nepůjde (pokud si na to explicitně nenapíšete funktor), program by se tu posloupnost pokusil vypočítat rovnou.
-
napr. java [jazyk] tail-call-optimization nerobi, rovnako ani clojure, groovy 2.3+ umoznuje dodat anotaciu a pomoct kompilatoru
-
Clojure má konstrukci loop-recur (případně se používá trampoline) právě pro to, že JVM neumožňuje tail-call optimalizaci. Na druhou straunu překladač Scaly, která taky běží nad JVM, to "umí" - tím, že z toho udělá cyklus.
Jestli je to možné u C# 5, to se přiznám, že nevím - překladač verze 4 to neumí byť .Net to podporuje. C/C++ u novějších překladačů (jak Microsoft tak GCC) to umí a nedávno jsem to viděl i u free pascalu. Nicméně často se musí explicitně zapnout.
Každopádně i když rekurze je ve funkcionálních (a logických) jazycích celkem často k vidění, v imperativních jazycích není až tak potřeba - stejně je většinou pohodlnější tu danou věc zapsat cyklem než rekurzí.
-
@Sten
Děkuju, to mne vlastně ani nenapadlo. To je odpověď hodná lišky :D
@ded.kenedy
Díky za připomínku.
-
http://llvm.org/docs/Passes.html#tailcallelim-tail-call-elimination
-
Jestli je to možné u C# 5, to se přiznám, že nevím - překladač verze 4 to neumí byť .Net to podporuje.
v C# to nejde vnutit (jazyk to neumi) a ani si nemuzete byt uplne jisti, ze neco bude tail call. Ale jak pises, tak .NET to umi a JIT compiler pouziva tail call optimalizace. Takze rekurzivni funkce v release konfiguraci je dost casto tail call optimalizovana a stack neplni.
(Na coz jsem prisel kdyz se mi v release kofiguraci zacyklilo vlakno a v logach nic nebylo. Jenom v nekterejch vicemene nahodnejch situacich diky blbe napsany rekurzi pribyl 1 worker thread co nikdy nezkoncil a sezral 1 CPU. Prijit na to proc server zpomaluje a zpomaluje dalo diky absenci chyb celkem praci. Zase me to naucilo davat vsude timeouty :) )
-
Asi jsem už moc starý, ale za mých mladých let jsme si takový luxus jako je "tail recursion optimalization" nemohli užívat, takže jsme se museli naučit přemýšlet a rekurzi psát jen tam kde jsme si nemohli vystačit s jinými, efektivnějšími přístupy. Napsat počítání faktoriálu nebo Fibonacciho posloupnosti pomocí rekurze bylo považováno za hrubou chybu. Mimochodem, mám pocit že zrovna ta Fibonacciho posloupnost se automaticky optimalizovat nebude ani dnes - že by tedy nastal čas opět u programování přemýšlet? Ale abych odpověděl k původnímu tématu - imperativní jazyky obvykle nedělají optimalizaci v případě že rekurzivní volání je poslední v rekurzivně volané metodě, což modernější jazyky umějí optimalizovat - ale to ani zdaleka nepokrývá všechny druhy rekurze! A vězte že metoda se nemusí volat rekurzivně sama, může jít o více metod které se rekurzivně volají navzájem - a tam podle mě už nezbývá než doopravdy hodně dobře přemýšlet, zatím jsem neviděl jazyk který by toto dokázal optimalizovat...
-
takže jsme se museli naučit přemýšlet a rekurzi psát jen tam kde jsme si nemohli vystačit s jinými, efektivnějšími přístupy.
Rekurzia sa da vzdy prepisat inak, aj ked je na to niekedy treba premyslat.
Každopádně i když rekurze je ve funkcionálních (a logických) jazycích celkem často k vidění, v imperativních jazycích není až tak potřeba - stejně je většinou pohodlnější tu danou věc zapsat cyklem než rekurzí.
Naopak - pri netrivialnych problemoch byva pohodlnejsie "rozdel a panuj", co vedie priamociaro na rekurziu. Ta sa sice da prepisat na iterativny postup, ale to potom nebyva take prehladne.
Navrh pomocou rozdel a panuj ma pri aspon trochu rozumnom navrhu 1 velku vyhodu - chova sa to lepsie ku cache a teda to zvykne fungovat rychlejsie.
-
Mimochodem, mám pocit že zrovna ta Fibonacciho posloupnost se automaticky optimalizovat nebude ani dnes - že by tedy nastal čas opět u programování přemýšlet?
Ona ta tail optimalizace není zadarmo, daná metoda musí splňovat určité požadavky. Musí jít o lineární rekurzi tzn. že metoda sama sebe volá pouze jednou a toto volání musí být poslední výraz v ní. Triviální fibonacci nesplňuje ani jedno z toho, takže je třeba ho přepsat do podoby s akumulátorem, která už není tak elegantní.
-
že by tedy nastal čas opět u programování přemýšlet?
Pro úplnost bych doplnil, že cílem optimalizace tail recursion není a nikdy nebylo programování bez přemýšlení. Spíš naopak.
-
Ona ta tail optimalizace není zadarmo, daná metoda musí splňovat určité požadavky [...]
Což vyplývá z definice "tail call optimization" - optimalizuje se pouze poslední výraz.
Rekurze s akumulátorem je možná o trochu méně elegantní, ale zrovna v tomto případě stále lépe čitelná než imperativní přístup se změnou hodnot proměnných v cyklu.
-
Tady ještě jak to konkrétně vypadá ve Scale:
@tailrec
private def fibonacciTail(n: Int, acc: (BigInt, BigInt)): BigInt = {
val (x, y) = acc
if (n == 0 || n == 1) y
else fibonacciTail(n - 1, (y, x + y))
}
def fibonacci(n: Int) = fibonacciTail(n, (1, 1))
Kompilátor aplikuje tail call optimalizace automaticky, @tailrec anotace pouze zajistí kontrolu, že daná metoda opravdu tail rekurzivní je (jinak compile error).
-
Kompilátor aplikuje tail call optimalizace automaticky, @tailrec anotace pouze zajistí kontrolu, že daná metoda opravdu tail rekurzivní je (jinak compile error).
Bohužel tail call optimalizace se ve Scale u řady tail callů neaplikuje.
-
Rekurze, pokud nemá omezenou hloubku, skutečně dokáže přeplnit zásobník. V devadesátých letech to ale nebyl problém, protože programátoři věděli, kdy použít rekurzi a kdy iteraci. Jenže dnes se asi všechno řeší metodou hrubé síly a tak se spíše optimalizuje rekurze, než aby se použila iterace. Přitom před 20 lety se běžně učilo na úlohách typu "přepište následující část programu z rekurze na iteraci".
-
Rekurze, pokud nemá omezenou hloubku, skutečně dokáže přeplnit zásobník. V devadesátých letech to ale nebyl problém, protože programátoři věděli, kdy použít rekurzi a kdy iteraci. Jenže dnes se asi všechno řeší metodou hrubé síly a tak se spíše optimalizuje rekurze, než aby se použila iterace. Přitom před 20 lety se běžně učilo na úlohách typu "přepište následující část programu z rekurze na iteraci".
Ani iterace s neomezenou hloubkou nebude v imperativních jazycích to pravé ;)
-
Přitom před 20 lety se běžně učilo na úlohách typu "přepište následující část programu z rekurze na iteraci".
Scheme umí tail call optimalizaci už skoro 40 let.
-
Ani iterace s neomezenou hloubkou nebude v imperativních jazycích to pravé ;)
Co je hloubka u iterace? Můžu klidně iterovat přes „nekonečný“ vstup a třeba sčítat hodnoty nebo transformovat data a posílat je na výstup a nebude v tom problém.
-
Přitom před 20 lety se běžně učilo na úlohách typu "přepište následující část programu z rekurze na iteraci".
Scheme umí tail call optimalizaci už skoro 40 let.
To nepopírám. Já tvrdím, že před 20 lety to byl zajímavý bonus, zatímco dnes to díky stylu programování občas představuje životní nutnost. Ve chvíli, kdy pak z nějakého důvodu tail call neuspěje, jsou mladí chlapci často bezradní, protože díky všelijakým funkcionálním jazykům nezvládají klasické imperativní iterace.
-
Ani iterace s neomezenou hloubkou nebude v imperativních jazycích to pravé ;)
Neomezená hloubka nepředstavuje pro iterace žádný problém. Možná jste si to spletl s podobně vypadajícím výrazem "nekonečná". To ano, nekonečné iterace obvykle nekončí. Ale jakmile je hloubka konečná, tak to prostě jednou dopočítá. Lazy evaluation to v obecné rovině žádným způsobem nezlepší. Je to jen syntaktický cukr, který za vás opodmínkuje, zda se má výpočet vůbec provést nebo ne, případně omezí hloubku výpočtu. To můžete i v imperativních jazycích, jen se víc napíšete.
-
mě by taky zajímalo co je to ta "Neomezená hloubka iterace" a "nekonečná" a proč je to problém
-
mě by taky zajímalo co je to ta "Neomezená hloubka iterace" a "nekonečná" a proč je to problém
Rekurzivní volání vytváří záznamy na zásobníku. Kupříkladu VBA vám v závislosti na nastavení může omezit hloubu zásobníku na 100 volání. Pokud budete mít funkci, která vám rekurzivně počítá například nejmenšího společného dělitele, tak vám to NSD(2, 100) spočítá, protože se zanoří cca 50x. Jenže pokud zavoláte NSD(2,1000), tak už je to cca 500 volání a to je problém.
A teď k omezená / neomezená. Pokud já nějakým způsobem omezím množinu, nad kterou se funkce používá, tak také omezím počet rekurzivních volání. Tedy hloubku zanoření. Pokud funkce NSD bude jen pro čísla od 1 do 100, tak je to omezení dostatečně přísné na to, abych se nemusel zabývat limitem technologie. Pokud ale ten limit nebude, nebo bude mnohem vyšší, pak mohu na problémy technologie narazit. Mohu vyčerpat volnou paměť, narazit na nějaký limit stránkování atd.
Funkce s neomezenou hloubkou rekurze je tedy funkce, u které z povahy dat může být nutná hloubka jakákoliv. Ale je tam, někde se zastaví. Pokud budu počítat NSD(2,200000000), tak ta hloubka bude cca 100 milionů vnoření. To je na zásobník příliš mnoho, ale přesto je to číslo, u kterého se to zastaví.
No a nekonečná hloubka je taková, kdy se to prostě nezastaví. Na první pohled je zřejmé, že volání nekonečné funkce je problém. Jenže tomu tak být nemusí, protože díky lazy evaluation nakonec vůbec k volání funkce nemusí dojít a program doběhne přesto, že tam to volání zjevně napsané je.
Co tím autor myslel v případě iterací si nejsem jistý, ale přepokládal jsem, že to měla být analogie právě k hloubce rekurze. Zatímco vnořit se do funkce 100 milionkrát je pro zásobník problém, tak mít cyklus, který se 100 milionkrát zopakuje, to už problém není. U iterace tudíž existence limitu vstupních hodnot nemá vliv na to, zda to fungovat bude nebo ne. Má to vliv jen na to, zda to doběhne v rozumné době. U rekurze je neexistence limitu risk, protože program může spadnout.
Obecně se proto doporučuje odhadovat hloubku rekurze a buď do ní uměle limit přidat, nebo ji nahradit iterací. Výše zmíněné "tail call" je technika, kdy specifickým způsobem zapsané rekurzivní volání může překladač nebo interpretter převést na iteraci za vás. Skutečností je, že úprava rekurzivní funkce na tail call není snadnější, než její přepsání na iteraci. Kolikrát spíše naopak. Přiznávám, že tail call se trochu lépe čte.
-
děkuji za vyčerpávající odpověď na otázku, kterou jsem nepoložil
-
To nepopírám. Já tvrdím, že před 20 lety to byl zajímavý bonus, zatímco dnes to díky stylu programování občas představuje životní nutnost. Ve chvíli, kdy pak z nějakého důvodu tail call neuspěje, jsou mladí chlapci často bezradní, protože díky všelijakým funkcionálním jazykům nezvládají klasické imperativní iterace.
Zajímavé tvrzení. Jsou pro to nějaké (byť jen minimální) podklady?
Nebo jak říkají mladí chlapci: [Citation needed]
-
Mě se jeden ostřílený borec zeptal co je "unique_ptr" v C++ - po odpovědi "náhrada za auto_ptr" se zeptal "co je to auto_ptr". Místo, aby si všiml, že před 14 lety přibyla šablona auto_ptr do standardní knihovny jazyka, raději řešil memory leaky a bordel na haldě. Podobný dotaz položil k výrazu "builder pattern".
Mám to snad po vzoru Karla také tak debilně generalizovat na větu:
Já zas vidím spoustu ostřílených zkušených borců, co díky všemožným asemblerům, Cčkům, Pascalům a Fortranům nezvládají základní objektové návrhové vzory, C# po nich vypadá jako brainfuck (teda sorry, COBOL) a díky ignoraci nových věcí v základní knihovně jejich hlavního jazyka nezvládají základní práci s pamětí?
-
To nepopírám. Já tvrdím, že před 20 lety to byl zajímavý bonus, zatímco dnes to díky stylu programování občas představuje životní nutnost. Ve chvíli, kdy pak z nějakého důvodu tail call neuspěje, jsou mladí chlapci často bezradní, protože díky všelijakým funkcionálním jazykům nezvládají klasické imperativní iterace.
To je skutecne roztomiloucke tvrzeni. Ano, setkal jsem se s mladymi i starymi "chlapci", co byli bezradni, kdyz po nich nekdo chtel i velmi trivialni veci napsat funkcionalne. Fold pro ne byla cerna magie a veci jako "write-only" promenne brali jako satanovo prokleti. Ale s tim, ze by nejaky "chlapec" libovolneho veku, ovladajici nejaky funkcionalni jazyk, mel "problem s klasickou imperativni iteraci", tak to ne, s tim jsem se tedy opravdu nesetkal.
-
Mě se jeden ostřílený borec zeptal co je "unique_ptr" v C++ - po odpovědi "náhrada za auto_ptr" se zeptal "co je to auto_ptr". Místo, aby si všiml, že před 14 lety přibyla šablona auto_ptr do standardní knihovny jazyka, raději řešil memory leaky a bordel na haldě. Podobný dotaz položil k výrazu "builder pattern".
Nic proti nikomu, ale programoval ten borec v C++?
Znam par lidi, co dle jejich slov programuji v C++, ale pritom je to C se special structama se jmenem "class", co obsahuje funkce a dokonce jista navesti public a private, ktera maji specialni vyznam. A abych nezapomel, misto malloc a free se pouzivaji new a delete.
-
To je skutecne roztomiloucke tvrzeni. Ano, setkal jsem se s mladymi i starymi "chlapci", co byli bezradni, kdyz po nich nekdo chtel i velmi trivialni veci napsat funkcionalne. Fold pro ne byla cerna magie a veci jako "write-only" promenne brali jako satanovo prokleti. Ale s tim, ze by nejaky "chlapec" libovolneho veku, ovladajici nejaky funkcionalni jazyk, mel "problem s klasickou imperativni iteraci", tak to ne, s tim jsem se tedy opravdu nesetkal.
"write-only" promenne? K cemu je to dobry?
-
To je skutecne roztomiloucke tvrzeni. Ano, setkal jsem se s mladymi i starymi "chlapci", co byli bezradni, kdyz po nich nekdo chtel i velmi trivialni veci napsat funkcionalne. Fold pro ne byla cerna magie a veci jako "write-only" promenne brali jako satanovo prokleti. Ale s tim, ze by nejaky "chlapec" libovolneho veku, ovladajici nejaky funkcionalni jazyk, mel "problem s klasickou imperativni iteraci", tak to ne, s tim jsem se tedy opravdu nesetkal.
"write-only" promenne? K cemu je to dobry?
Taky mě to překvapilo, protože to je Satanovo prokletí :) Write-only proměnné jsou úplně k ničemu. Ale možná si to autor spletl s write-once proměnnými, ty jsou ve funkcionálních jazycích (a nejen tam) docela běžné.
-
Write only proměnná je například ToDo list. :)
-
Nic proti nikomu, ale programoval ten borec v C++?
Znam par lidi, co dle jejich slov programuji v C++, ale pritom je to C se special structama se jmenem "class", co obsahuje funkce a dokonce jista navesti public a private, ktera maji specialni vyznam. A abych nezapomel, misto malloc a free se pouzivaji new a delete.
Byl to přesně takový typ. C++ = C wrapped in classes.
-
Mě se jeden ostřílený borec zeptal co je "unique_ptr" v C++ - po odpovědi "náhrada za auto_ptr" se zeptal "co je to auto_ptr". Místo, aby si všiml, že před 14 lety přibyla šablona auto_ptr do standardní knihovny jazyka, raději řešil memory leaky a bordel na haldě. Podobný dotaz položil k výrazu "builder pattern".
Mám to snad po vzoru Karla také tak debilně generalizovat na větu:
Já zas vidím spoustu ostřílených zkušených borců, co díky všemožným asemblerům, Cčkům, Pascalům a Fortranům nezvládají základní objektové návrhové vzory, C# po nich vypadá jako brainfuck (teda sorry, COBOL) a díky ignoraci nových věcí v základní knihovně jejich hlavního jazyka nezvládají základní práci s pamětí?
No, jak by asi řekl pan Virius, který nás měl na C++ - "programátor, který neví, co je auto_ptr, je stále jen programátor, který neví, co je auto_ptr; ale programátor, který se nedovede správně popasovat s rekurzí, to není programátor."
-
Kazdej slusnej programator musi iteraci, rekurzi a pouziti funkci vyssich radu pro podobne ucely (map, collect...) zvladat levou zadni.
Nepamatuju se, ze bych potkal nekoho, kdo umi ty druhe dve veci a neumel by tu prvni.
-
Taky mě to překvapilo, protože to je Satanovo prokletí :) Write-only proměnné jsou úplně k ničemu. Ale možná si to autor spletl s write-once proměnnými, ty jsou ve funkcionálních jazycích (a nejen tam) docela běžné.
Ano, presne tak :)
-
No, jak by asi řekl pan Virius, který nás měl na C++ - "programátor, který neví, co je auto_ptr, je stále jen programátor, který neví, co je auto_ptr; ale programátor, který se nedovede správně popasovat s rekurzí, to není programátor."
+1