Vlákno názorů k článku Clojure aneb jazyk umožňující tvorbu bezpečných vícevláknových aplikací pro JVM (3.část - funkcionální programování) od M. Prýmek - Znovu díky, Pavle. Myslím, že se vloudila drobná chybička...
-
Znovu díky, Pavle.
Myslím, že se vloudila drobná chybička do příkladu: fact(0) -> 0 Mělo by být 1.
Jak je to vlastně s tou tail rekurzí? Zkoušel jsem ten příklad s faktoriálem na Erlangu a nemá s tím problém ani v té verzi s koncovým násobenám, ani žádný "pokud máte dostatek trpělivosti" se nekoná - je to slušně rychlý (jak rychle to počítá v Closure?). Má Erlang rekurzi nějak líp ošéfovanou? (nikdy jsem neměl potřebu to zkoumat...)
# cat fac.escript
#!/usr/bin/env escriptfac(N) when N=<1 -> 1;
fac(N) -> N*fac(N-1).main([NStr]) ->
{N,_} = string:to_integer(NStr),
io:format("~p! = ~p~n",[N,fac(N)]).# time ./fac.escript 1000 >/dev/null
0.168u 0.029s 0:00.21 85.7% 0+0k 0+14io 0pf+0w
# time ./fac.escript 10000 > /dev/null
0.534u 0.039s 0:00.57 98.2% 0+0k 0+0io 0pf+0w
# time ./fac.escript 100000 > /dev/null
43.360u 0.729s 0:45.19 97.5% 0+0k 0+0io 0pf+0w
(spuštěno na Core 2 Duo 2.6GHz, 2GB RAM) -
Kratsi funkce i automaticky prevadi na inline - http://www.erlang.org/doc/man/compile.html sekce Inlining, ale to asi nebude tenhle pripad.
Co se tyce toho tail callu me zajima, jestli ho umi poznat i v pripade, ze tam je to zaverecne nasobeni (tzn. nemusi se tam delat ty cachry, co jsou popsane v clanku), nebo neumi.
-
Ledaze by to umel chytre prevest na smycku s akumulatorem. Ale to by asi chtelo az moc inteligence.
Nicmene teda to urcite neumi - viz http://www.erlang.org/doc/reference_manual/functions.html - sekce Tail recursion, posledni veta.
Skoda :)
-
Radek Miček (neregistrovaný)
Složitější výpočty lze přepsat na tail rekurzivní pomocí kontinuací. Například v F# lze použít příslušné workflow a je to téměř bezpracné - viz http://lorgonblog.wordpress.com/2008/06/07/catamorphisms-part-seven/ .
-
Radek Miček (neregistrovaný)
Přepisem pomocí kontinuací myslím to, že každá funkce dostane navíc jeden parametr, a to funkci k, která určuje, co dělat dál. Místo toho, aby funkce vrátila výsledek zavolá k s výsledkem. Faktoriál lze přepsat takto:
def factorial(n, k): if n <= 0: return k(1) else: # Spočtená hodnota (n-1)! se předá lambda funkci, # jenž spočte n! a následně zavolá k(n!) return factorial(n-1, lambda x : k(x * n))Aby tohle fungovalo, musí kompilátor umět provést tail call optimization, jinak se zásobník rychle zaplní, protože všechny funkce vrací až na konci výpočtu.
Výhoda je, že transformace je mechanická a lze transformovat i složitější funkce jako třeba vyhodnocování výrazu (tj. n-árního stromu).
Ten odkazovaný článek jen ukazuje, že v F# může podobný přepis udělat kompilátor skoro automaticky. Takto může v F# vypadat výpočet faktoriálu, který není tail rekurzivní:
let rec factorial n = if n <= 0 then 1 else let fact = factorial (n-1) n * factNyní kompilátoru vysvětlíme, jak má provádět přepis (kód z toho článku):
type ContinuationBuilder() = member this.Return(x) = (fun k -> k x) member this.ReturnFrom(x) = x member this.Bind(m,f) = (fun k -> m (fun a -> f a k)) let K = ContinuationBuilder()A zde je tail rekurzivní kód:
let rec factorial2 n = K { if n <= 0 then return 1 else let! fact = factorial2 (n-1) return n * fact } -
Ivan (neregistrovaný)
Neni to cele dane omezenim JVM?
Jestli to dobre chapu, tak JVM ma v defaultu pro zasobnik pouze 32MB. Pro imperativni jazyk to staci, protoze jsou stejne vsechny promenne na heapu. U jazyku jde se vyuziva rekurze to ale muze byt problem. Pamatuju si, ze jsem kdysi mel problemy s velikosti zasobniku JVM, kdyz jsem "kompiloval" gramatiu pomoci ANTLR.
-
Pavel TišnovskýZlatý podporovatelZasobnik pro JRE se da jednoduse zvysit, ale to problem nevyresi, jen ho odsune tak, aby se projevil az v ostrem nasazeni :-)
Zalezi na programu, i pri zpracovani nejakych silenych XML v Jave jsme museli zvetsovat veliksot zasobniku, protoze se XML samozrejme zpracovalo rekurzivne. ANTLR na tom asi bude podobne, i kdyz se priznam, ze nevim, jestli dela rekurzivni sestup nebo jake gramatiky vlastne dokaze prijimat (podle nazvu ma asi LL i LR parsery ne?)
-
Pavel TišnovskýZlatý podporovatel
Aha diky za info, ted se divam, ze to LR z nazvu Ant_LR_ je odvozeno z Language Recognition a ne z typu parseru, docela vtipne :-/
-
Dan Škarda (neregistrovaný)
Tail rekurze obecně znamená, že pokud funkce Z volá X a funkce X volá funkci Y jako poslední svou akci, tak mohu mít na zásobníku místo Z X Y rovnou Z Y, tj jako poslední akci ve funkci X "zahodit" část zásobníku a přepsat ho voláním Y.
Tail rekurze je tradiční součástí funkcionálních jazyků (například ve Scheme a dalších). To, že Clojure implementuje tail rekurzi speciálním způsobem, není způsobeno libovůlí autorů. Rich Hickey promýšlí věci velmi pečlivě, doporučuji jeho přednášku o Datomicu, knihovně reducers nebo i Hammock driven development.
Zvláštnost implementace tail recurse v Clojure je způsobena tím, že vlastnosti JVM neumožňují práci se zásobníkem, jak jsem ji popsal na začátku.
Tj je lepší, pokud se tail rekurze vyjádří explicitně v případě X volá X (a v tom okamžiku programátor ví, že píše tail rekurzi a chce ji optimalizovat jako smyčku).
Pro případy Z volá X volá Y je nutné použít funkci trampoline.
-
Pavel TišnovskýZlatý podporovatel
Ja jsem myslel, ze predrecnik ma na mysli predevsim to, ze u rekurzivniho vypoctu dojde k vycerpani zasobniku tak brzo a ze je to kvuli (defaultni) male velikosti zasobniku.
Co pisete vy, je samozrejme dalsi problem a to dokonce o dost vaznejsi, alespon ve chvili, kdy Clojure preklada kazdou funkci jako Javovskou metodu (nekdy dokonce jako tridu), protoze bajtkod skutecne neumoznuje provest jump kamkoli v kodu - vzdy pouze v ramci jedne metody.
ČLÁNKY DO MAILU