Rychlost Haskell vs. C++

[andy]

Andy, seq v Haskellu je "magic": https://stackoverflow.com/questions/6442019/how-does-seq-force-functions

seq cannot be implemented in Haskell. Instead, it is a primitive "hook" into evaluation to weak-head normal form in whatever runtime your Haskell is running on. E.g. on GHC it is compiled to a case in GHC Core, which triggers evaluation to the outermost constructor.

Hele, nechceš se na to už vykašlat? Není lepší jít za holkama, dát si pivo, nebo si třeba jít zaběhat? Nejen computer science živ je člověk. Já s dovolením půjdu za těma holkama.

Ano, přesně. Seq není pure funkce, pokud je první parametr bottom. Souhlas? Pokud ne, proč?

[Reklama]

[andy]

Ad pure funkce: to není o tom jak je ta funkce implementovaná (FFI volání klidně můžou být z hlediska haskellu pure), ale že závisí výhradně na tom, jaké jim přijdou parametry. A funkce "seq" neví o prvním parametru vůbec nic, takže na něm nemůže záviset. Jenomže závisí. Přinejlepším by ta funkce musela schematicky vypadat takhle:

Kód: [Vybrat]

seq a b = if isBottom a then bottom else b
jenomže to nejde. Non-observable znamená, že žádná funkce isBottom neexistuje. Nejde na to udělat pattern match. A ta funkce výše NENÍ identická:

Kód: [Vybrat]

seq :: () -> b -> b
seq a b = case a of () -> b
Protože tady dělám pattern-match na (). A to observable je.

Jinak non-CS věnuju docela hodně času, akorát v jiné denní hodiny

[andy]

A tady je na to téma článeček od někoho, kdo tomu na rozdíl od mě rozumí http://www.janis-voigtlaender.eu/papers/TheImpactOfSeqOnFreeTheoremsBasedProgramTransformations.pdf

Since seq violates the parametricity property dictated by its type, other terms that are built using seq might do so as well.

Interpretoval bych to tak, že použití seq určitým způsobem může rozbít očekávání, která existují ohledně haskellého programu. Lepší typový systém by mohl být schopen omezit použití seq způsobem, kdy to tato očekávání nerozbije.

No a vzhledem k tomu, že ta výsledná pravidla při existenci seq a bottom jsou poněkud složitější, tak kdo v haskellu programuje, tak se používání "bottom" vyhýbá, protože v takovém modelu je všechno výrazně jednodušší a funguje jak má.

[lopata]

Ano, přesně. Seq není pure funkce, pokud je první parametr bottom. Souhlas? Pokud ne, proč?

Já ti řeknu proč. Zase se snažíš aplikovat teoretické poučky, které jsi slyšel ve škole, ale děláš to úplně blbě.

Tak zaprvé, seq v Haskellu implementovat nejde. Proto nemá smysl o seq uvažovat jako o Haskellovské funkci, ten tvůj formální popis je k ničemu. seq je nějaký "magic", který je zadrátovaný v překladačí, v podstatě je to implementation dependent, GHC to dělá nějak, jiný překladač to může dělat jinak. Použitím seq se dostáváš do vážných problémů: https://stackoverflow.com/questions/12687392/why-is-seq-bad

The seq function is not lambda definable (i.r., cannot be defined in the lambda-calculus), which means that that all the results from lambda calculus can no longer be trusted when we have seq.

Zadruhé, ty řešíš seq, ale to vůbec nemáš dělat, máš řešit bang patterns, protože -XStrict je implementované pomocí bang patterns. Ano, bang patterns můžou interně používat seq, ale to je implementační detail, klidně to může být udělané i úplně jinak. Kdyby sis přečetl specifikaci bang patterns, tak bys narazil na jednu důležitou větu, která rozbíjí všechny tvoje teorie, chování pro bottom je jasně definované: https://downloads.haskell.org/~ghc/7.8.4/docs/html/users_guide/bang-patterns.html

The key change is the addition of a new rule to the semantics of pattern matching in the Haskell 98 report. Add new bullet 10, saying: Matching the pattern !pat against a value v behaves as follows: if v is bottom, the match diverges otherwise, pat is matched against v.

Jak vidíš, strict vyhodnocení v Haskellu není pro normální lidi. Normální člověk nedokáže domyslet důsledky, nepodařilo se to ani tobě. V podstatě by na každé instalačce Haskellu mělo být varování:

"POZOR! NEBEZPEČNÉ! UCHOVÁVEJTE MIMO DOSAH BĚŽNÝCH PROGRAMÁTORŮ. NEPOUŽÍVEJTE STRIKTNĚ. NEOPATRNÉ POUŽITÍ MŮŽE PORUŠIT PRAVIDLA LAMBDA KALKULU. V PŘÍPADĚ POTÍŽÍ VYHLEDEJTE NEJBLIŽŠÍHO TEORETICKÉHO MATEMATIKA."

Tím by se myslím vyřešila spousta problémů.

[andy]

Zadruhé, ty řešíš seq, ale to vůbec nemáš dělat, máš řešit bang patterns, protože -XStrict je implementované pomocí bang patterns. Ano, bang patterns můžou interně používat seq, ale to je implementační detail, klidně to může být udělané i úplně jinak

Já bych si nesměle tipnul, že bang patterns a seq jsou isomorfní. Seq jde implementovat pomocí bang pattern, a bang pattern jde implementovat tak, že se předkaždé volání funkce vrazí seq s parametrama.... Takže řeším seq a je to přesně to, o čem je celou dobu řeč. To, jak je to implementované, je fakt implementační detail...

Jak vidíš, strict vyhodnocení v Haskellu není pro normální lidi. Normální člověk nedokáže domyslet důsledky, nepodařilo se to ani tobě. V podstatě by na každé instalačce Haskellu mělo být varování:

"POZOR! NEBEZPEČNÉ! UCHOVÁVEJTE MIMO DOSAH BĚŽNÝCH PROGRAMÁTORŮ. NEPOUŽÍVEJTE STRIKTNĚ. NEOPATRNÉ POUŽITÍ MŮŽE PORUŠIT PRAVIDLA LAMBDA KALKULU. V PŘÍPADĚ POTÍŽÍ VYHLEDEJTE NEJBLIŽŠÍHO TEORETICKÉHO MATEMATIKA."

Tím by se myslím vyřešila spousta problémů.

Ne, mělo by tam být varování:

Nevyhazujte výjimky v pure kódu (ať už jakýmkoliv způsobem), protože pravidla pro použití speciálně s použitím seq jsou dost složitá a může to porušit free theorems, na kterých je postavena spousta věcí mimo jiné v optimalizátoru a může to vést k nedefinovanému chování. V případě potřeby vyhledejte nejbližšího teoretického matematika.

Hmmm.... Možná bych mohl spočítat, kolikrát něco takového v tomhle threadu padlo... tak 10x? 20x? V tebou odkazovaných textech týkajících se vyhazování výjimek v pure kódu to bylo napsané. Narazil jsem na to v 15 let staré učebnici haskellu, předpokládám, že dneska to budou akcentovat ještě víc...

[Reklama]

[BoneFlute]

Nojo... víš, to je tak: pokud v tom programu provedeme výměnu IO za třeba "Either SomeException" obalené nějakým WriterT, kde si odchytíme ty putStrLn, a všechny ty funkce budou na stejné vstupy dávat stejné výstupy, pak by tvůj program měl ve výsledku udělat totéž. To je tak nějak základem pure programování. Takže pokud taková transformace není možná, pak je tvůj program nekorektní. A vzhledem k tomu, že ty tvrdíš, že je korektní, tak bych očekával, že mi ukážeš, jak se to krásně udělá.

Toto bych zdůraznil.