Názory 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í)
-
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.
-
Inkvizitor (neregistrovaný)
To mi připomíná moje první pokusy v Haskellu, když jsem chtěl všechno řešit rekurzí. Pak jsem s úlevou zjistil, že rekurze se v Haskellu používá spíš výjimečně. Chápu ale, že pro výuku je rekurze cenná.
Pro pobavení: http://www.willamette.edu/~fruehr/haskell/evolution.html
-
Adam (neregistrovaný)
Toto není pokus o flame, spíše snaha rozpoutat diskuzi.
S funkcionálním programováním a překladači mám celkem zkušenosti, ale nebyl jsem schopen se zbavit dojmu, že jde o write-only jazyky.
Naučit se to je rozhodně užitečné, človék pak řeší některé problémy i v imperativních jazycích mnohem elegantněji.
V reálných projektech je však dost nutné udržovat kód i několik let a imperativní jazyky mají tu výhodu, že jsou opravdu blízko tomu, jak většina lidí nad programováním přirozeně uvažuje. Prostě mám teď nějaký stav, pak udělám krok a stav se změní, nehledě na to, že se dobře ladí.
Co se týká paralelizace, tak je to samozřejmě tragédie a s funkcionálními jazyky má překladač nerovnatelně mnoho možností, co s kódem dělat, ale dle mého názoru to naráží na ten problém, že funkcionální jazyky nejsou pro člověka zdaleka tolik přirozené.
Co si o tom myslíte? -
Pavel TišnovskýZlatý podporovatel
Díky za příspěvek. Sám totiž mám alespoň částečně podobné pocity. Ovšem podle mě hodně záleží na tom, jak se člověk naučil programovat.
Například já jsem kdysi dávno začínal jako samouk v BASICu, takže jsem si v dalších letech musel projít mnohdy bolestivou cestou směrem k procedurálním strukturovaným jazykům (Pascal, C, PL/1, C--), OOP-like jazykům (C++, Java) a přes krátkou odbočku k Forthu i k jazykům funkcionálním (nepočítám assembler, ten stojí trošku stranou).
Každý z těch přechodů: špagetový kód -> strukturovaný kód -> OOP -> funkcionální paradigma byl dosti složitý, protože vůbec nejde o syntaxi (to je to nejmenší), ale o mnohdy zcela odlišný styl myšlení.
Teď si říkám, že je škoda, že jsem třeba nezačal s funkcionálním Logem, protože by byl mozek nastaven úplně jinak. Takže když shrnu svůj pohled - chtělo by to možná najít někoho, kdo už od začátku dělal ve funkcionálním jazyku (Logo, Scheme, Lisp, Cat), aby nám pověděl o svém pohledu na programování.
-
pozortucnak (neregistrovaný)
No si spíše myslím, že záleží na jazyku... třeba o Perlu se také říká že je write-only. Vemte si třeba takový Erlang, praxí ověřený jazyk, například s edoc... a celkově i svou jednoduchostí...
Oproti tomu lisp... nic proti, v porovnání se středníky u Javy je to v podstatě pouze uzávorkování výrazu, ale na můj vkus ten jazyk dává až příliš volnosti...
Co se týče funkcionálního myšlení... asi jde pouze o zvyk, nevím, zas tolik jsem toho neprogramoval...
Stejně já funkcionální jazyky z části beru jako nutnost, protože rychlost dnešních procesorů se nezvyšuje - zvyšuje se počet jader... a na to jazyky jako C++ zkrátka nebyly vymyšlené...
Docela by mě zajímalo, jak vícejádrové procesory využívá java... :-)
-
Pavel TišnovskýZlatý podporovatel
Ad Java: no samostna JVM se s nimi vyporada docela dobre, spousta veci je tam navrzena pro paralelni beh, i implementace nekterych GC a locky tam jsou samozrejme taky, ale jen tam, kde jsou skutecne zapotrebi.
Problem je s javovskymi aplikacemi, ktere to v naproste vetsine pripadu nedokazou vyuzit - nekdy se to trosku "skryje" tim, ze jde o webovskou aplikaci, ktera idealne dokaze zpracovat pozadavky nezavisle/paralelne - ale u GUI aplikaci je to spatenka ;-/ Ale neni se cemu divit, paralelnost zalozena na vlaknech s explicitni synchronizaci, to se tezko programuje neco slozitejsich nez nejaky skolni priklad paralelniho vypoctu :-)
-
> protože by byl mozek nastaven úplně jinak.
Napadlo mě něco podobnýho, když jsem v příspěvku výš četl to " jak většina lidí nad programováním přirozeně uvažuje" :)
Asi je pravda, že člověk přirozeně rozděluje úkol na nějaké postupné kroky (viz např. kuchařka), na tom něco bude. Proto třeba když chce člověk donutit takhle "po konkrétních krocích" postupovat jazyk, který je vymšlený jinak, je to docela porod a intelektuální cvičení. Asi nejvíc jsem to pocítil nad Prologem - pokud se ho člověk fakt dotazuje, je to pohoda, ale jakmile potřebuje něco "pseudo-imperativního", je to běs.
Ale třeba s Erlangem tenhle problém nemám, Erlang pořád postupuje "po krocích", akorát logika zápisu a uspořádání programu je trochu jiná.
Mně se třeba Erlang strašně moc zalíbil oproti OOP, protože tam není jedna nelogičnost, která mi u OOP vždycky vadila: objekty se vysvětlují jako "Objektu žárovka pošlu příkaz "rožnout" a on něco udělá". Ve skutečnosti ale objekt není ten, kdo něco dělá, tím je VLÁKNO, které do kódu objektu vstupuje. Proto objekt je pořád jenom "kuchařka" a "kuchařem" je pořád vlákno. Takže žádné "řeknu objektu", ale pořád "řeknu vláknu". U jedno- nebo málo-vláknových programů se rozdíl moc nepozná, ale u masivně paralelních už je to guláš.
Tohle zmatení Erlang elegantně odstraňuje - kuchařem je proces. Procesu posílám příkazy. Proces vykonává instrukce. Proto mi Erlang přijde (pozor náběh na flejm! :) jako vůbec nejobjektovější jazyk, který znám :)
-
Pavel TišnovskýZlatý podporovatel
Ano, je pravda, ze Erlang posunul chapani vlaken uplne nekam jinam, osobne si myslim, ze s postupem vyvoje HW se bude posunovat i obliba Erlangu, ale uvidime.
-
Bylo by to super, kdyby se obliba Erlangu zvyšovala, ale moc v tom optimista nejsem. Hlavní problém je, že oproti mainstreamovým jazykům jsou úplně jiné patterny a to je dost zásadní problém. Teoreticky by šlo řadové kodéry vyškolit poměrně rychle (jazyk je syntakticky jednoduchý a základní idiomy člověk pochopí docela rychle), ale potíž bude nedostatek zkušených analytiků.
-
Pavel TišnovskýZlatý podporovatel
Treba to nakonec pujde :-) Ono se v dobach masivniho nastupu klasickych OOP jazyku (resp. ne zcela klasickych kdyz klasikou je ST) do tohoto zpusobu programovani museli dostat i tehdejsi vyvojari, i kdyz pravda - nekterych se OOP dodnes moc nedotklo ;-)
OOP pristup umoznil zvladnout tvorbu rozsahlejsich aplikaci s GUI a milionem ruznych stavu, takze az bude opravdu zapotrebi paralelnost, tak Erlang nebo (jak doufam) i Clojure, popr. dalsi jazyky se prosadi.
-
Radek Miček (neregistrovaný)
Body 1, 2, 4 neplatí obecně pro OO jazyky. A u bodu 3 nechápu, co se myslí
In an OOPL I have to choose some base object in which I will define the ubiquitous data structure, all other objects that want to use this data structure must inherit this object. Suppose now I want to create some "time" object, where does this belong and in which object...
-
Pavel TišnovskýZlatý podporovatel
No ja mam pocit, ze je to psany hodne sarkasticky. Mozna se pletu, ale kdyz to ma topic "Test page" :)))
-
SB (neregistrovaný)
OOP nečlení úlohy na kroky, ale na podproblémy.
Dále mícháte do sebe 2 věci - deklarované chování (třeba objektu v OOP) a realizaci výpočtu (např. v Erlangu). Koexistence objektů je už ze své podstaty asynchronní (posílání zprávy je synchronní, ale o tom tu řeč není), komunikovat spolu můžou teoreticky NAJEDNOU různé páry. Abstrakce objektů NEZNÁ vlákna a nijak s nimi nesouvisí! Teprve realizace na nižší úrovni používá jedno nebo několik vláken, která chování objektů realizují, často sekvenčně, protože každý objekt by jinak musel mít své vlákno, které by čekalo na zprávu. Případná exkluzivita přístupu je věcí návrhu (vyplývá až z úlohy, ne z podstaty paradigmatu) a je zajištěna dalšími abstraktními mechanismy jako např. semafory ap. Dle vašeho popisu exkluzivitu zajišťuje Erlang (neznám ho) na nižší úrovni spouštěním sekvenčně závislých operací vždy v rámci vlákna. Neboli abstraktnější semafor nahrazuje systémovým prostředkem. Neříkám, že je to špatně, ale je to na jiné systémové úrovni, přičemž nelogičnost v asynchronnosti objektů žádnou nevidím, naopak se to podobá realitě, kterou často modeluje.
Objekt v žádném případě není kuchařkou (ve smyslu předpisu)! Objekt je samostatně existující a asynchronně pracující entitou. Jak může být Erlang „objektovější“, když právě to je principem objektového paradigmatu? -
Máš pravdu, smísil jsem "OOP" a "reálné OOP".
To je samozřejmě špatně, stejně jako bysme neměli zavrhovat socialismus kvůli tomu jak vypadá reálný socialismus :)))
>> Objekt v žádném případě není kuchařkou (ve smyslu předpisu)! Objekt je samostatně existující a asynchronně pracující entitou. Jak může být Erlang „objektovější“, když právě to je principem objektového paradigmatu?
Je docela obtížný vysvětlit, jak jsem to myslel. Zkusím to rádobylingvisticky: OOP tvrdí, že objekt je subjekt :) zatímco zpráva je objekt:
Kuchaři pošlu zprávu "uvař oběd". Kuchař oběd uvaří.
Ve skutečnosti ale žádný (mně známý) OOP jazyk takhle ve skutečnosti nefunguje. Ve skutečnosti je to jenom pořád zakuklené volání funkce v rámci téhož vlákna:
Chci uvařit oběd, tedy se stanu kuchařem, chvíli vařím podle jeho (tajné, "zapouzdřené") kuchařky a potom zase z této role vyskočím spolu s obědem zpátky.
V Erlangu to opravdu často funguje tak, jak si to neumíte představit: "protože každý objekt by jinak musel mít své vlákno, které by čekalo na zprávu". Přesně takhle, akorát místo (systémových) vláken se používají erlangovské "procesy", které jsou výrazně lehčí (viz http://goo.gl/TXE0b ).
Např. erlangovské bindingy wx jsou udělány tak, že každý widget má vlastní proces (tedy sám je kuchařem, který jenom dostává instrukce).
Abysme si rozuměli: nehodlám vás přesvědčovat, že Erlang je boží a nedostižitelný. Klidně si programujte v čem chcete a jak chcete, pouze jsem vyjádřil svůj názor, že "reálné OOP" ve skutečnosti jenom vytváří iluzi, že je tím, čím tvrdí být. Tento názor nikomu nevnucuju.
-
SB (neregistrovaný)
Jasně, že implementace (řešení) OOP vždy nějak vypadá, rozumně s několika vlákny, protože je asi zbytečné dělat každému objektu vlastní vlákno, protože pro abstrakci pseudoparalelizace dostačuje, ale nemůžu spoléhat na kauzalitu/exkluzivní přístup jen proto, že v realizaci pomocí např. jednoho vlákna to ono vlákno prostě musí udělat sekvenčně. Takže musím uvažovat abstraktně (to platí u OOM/OOP obecně) a synchronizaci garantovat jinak.
Na nízké úrovni je samozřejmě i OOP volání funkcí/spouštění strojového kódu, protože počítač to jinak neumí, neboli převod abstrakce na konkrétní řešení dané platformy, ale na vysoké úrovni je to skutečně zpráva, což je jakýsi dopis objektu, že má něco dělat, přičemž interpretaci celé zprávy řeší objekt. To je drtivý rozdíl oproti imperativnímu programování, kdo toto nepochopí, nikdy nepochopí OOP. Zpráva tedy je jakýsi objekt, ale ne ve smyslu OOP (odkazovatelný jako ostatní objekty).
Erlang neznám, ale z vašeho příkladu není jasné, jak moc abstraktní je samotný erlangový proces. Ale to nechám jiným, tomu fakt nerozumím. Z vašeho popisu je jasné, že Erlang využívá zcela jiný model výpočtu, kdy se určuje, co bude systémový(?) prostředek počítat, ne co je třeba spočítat (bez ohledu na systénové prostředky).
Vzhledem k tomu, že chci abstraktní OOP, ale k dispozici je počítač, který pracuje ÚPLNĚ jinak, je opravdu třeba tu iluzi naemulovat, to říkáte správně. Právě proto to taky něco (systémové zdroje) stojí. -
Dan Škarda (neregistrovaný)
Používáte Clojure pro své projekty?
Moje tříměsíční zkušenost s Clojure je vysloveně pozitivní. Původně jsem se docela obával persistentních datových struktur, ale pár blogů vysvětlujících interní implementaci PersistentArray a PersistantHashMap moje obavy rozptýlilo (naopak cítím velký respekt k autorům).
Clojure v kombinaci s ClojureScriptem (Clojure překládaná do JavaScriptu) a databází Datomic jsou hodně slibné řešení.
ČLÁNKY DO MAILU
