neděle 6. října 2013

Jak je to s volbou menšího zla? Proč se nebát volit malou stranu?

Blíží se další volby a k volbám obvykle patří debata o menším zlu. Myslím si ale, že zde dochází k určitým zjednodušením, která někdy dokáží – byť neúmyslně – přinést zmatek. Musíme totiž rozlišit, jaké jsou možnosti, a jaký je volební systém.

Poměrný systém

Pokud bychom měli dokonalý poměrný systém, pak by volba menšího zla evidentně neměla smysl. Mohu volit, koho/co chci, a v každém případě mám šanci na ovlivnění výsledku stejnou.

V praxi ovšem dokonale poměrný systém asi nenajdeme. Tím, že je počet volených zástupců mnohem menší než počet voličů, a tím, že každý zástupce má stejně silný hlas (není ovlivněn např. počtem voličů), bude vždy docházet k menším či větším zaokrouhlováním. To ale většinou není velký problém.

Jenže ani takto jednoduché to obvykle není. To by pro získání mandátu v Poslanecké sněmovně muselo stačit získat 0,5 % hlasů. To nestačí, protože tu jsou další deformace, jako třeba známý 5% práh. A tady začínají obvykle vznikat úvahy o volbě menšího zla. „Podpořil bych radši tuto malou stranu, ale ta se zcela určitě nedostane přes potřebných 5 %.“ To je do jisté míry sebenaplňující předpověď, která může dlouhodobě ovlivnit výsledek voleb dost výrazně. Je tu ale několik možných důvodů, proč i přesto může stát volba malé strany za to:

  1. I pokud strana nezíská 5 % v těchto volbách, má její výsledek vliv na příští volby. Pokud strana získá např. jen 3 %, bude u příštích voleb brána nerozhodnutými voliči asi vážněji, než kdyby získala pouze 0,5 %.
  2. Spekulace na těsné překročení 5% hranice. Případná ztráta nízká, případný výnos vysoký.
    Pokud strana získá pravděpodobně kolem 5 % hlasů, pak jeden hlas má mnohem větší šanci udělat významnější posun v celkovém výsledku voleb. Zvlášť pokud by mohla být potřebná pro vznik koalice.
    Toto jsem mimochodem reálně zvažoval u voleb v roce 2010.
  3. Nechcete se nechat dovést k sebenaplňující předpovědi. Když přesvědčíte více lidí, aby se nenechali ovlivnit průzkumy, možná se budeme výsledkům voleb divit.

K čemu vede myšlenka „ztraceného hlasu“?

Upřímně by mě celkem zajímalo, co by se stalo, kdyby byla 5% hranice zrušena. Přirozená hranice u voleb do Poslanecké sněmovny by tak byla zhruba 0,5 %. Bez výrazné kampaně tuto hranici byli ve stávajícím systému například Svobodní v roce 2010 přesáhnout. Tehdy to byla nová strana, vznikli v roce 2009. Zajímalo by mě, kolik by taková strana mohla tehdy dostat, kdyby nebylo 5% hranice nebo kdyby ji voliči ignorovali. Možná i přes 5 %.

Dlouhodobě navíc může tento přístup vést k tomu, že bude mít hlavní slovo několik stran, které málokdo chce. Protože se skoro všichni budou bát volit nové strany. Staré strany pak budou mít možnost dělat si celkem co chtějí. Třeba slíbit, že daně zvyšovat nebudou, a po volbách je zvýšit.

Většinový dvoukolový systém

První kolo

První kolo je celkem nezajímavé. I když zde může být k volbě „menšího zla“ větší motivace, argumenty a protiargumenty jsou v zásadě velmi podobné.

Vlastně nějaká výjimka by se našla. V prvním kole je úplně jedno, kdo je první, a kdo druhý. Ti dva se utkají až ve druhém kole. Aspoň pokud ten první nezíská v prvním kole přes 50 %, což obvykle nezíská.

Druhé kolo

Ve druhém kole je to ale jiné. Pokud jeden z kandidátů je přijatelný a druhý ne, je volba jasná. Pokud je ale jeden špatný a druhý ještě horší, máme se také vyhnout volbě menšího zla, když je ta volba menšího zla tak špatná?

Ptám se, co tím člověk získá. Jediná možnost, jak se vyhnout volbě menšího zla, je nevolit. To v dnešních systémech neznamená, že chcete, aby místo zůstalo neobsazeno, tím pouze necháte volbu na ostatních. Kteří možná vyberou menší zlo a možná vyberou větší zlo. V čem si zde člověk pomůže oproti volbě menšího zla? V tomto případě v ničem. Nevolit tak má význam jen ve speciálních případech, například když z těch dvou variant neumíte vybrat menší zlo.

Proto si taky myslím, že je konzistentní na jedné straně kritizovat volbu menšího zla ve volbách do Poslanecké sněmovny, ale na druhé straně volit menší zlo ve druhém kole voleb do Senátu nebo ve druhém kole voleb prezidenta.

sobota 16. února 2013

[AKTUALIZOVÁNO] Co bude znamenat přechod Opery na WebKit pro Operu Mini?

Asi jste zaznamenali, že Opera opouští vlastní vykreslovací jádro Presto a přechází na WebKit. Nevím, co bude s funkcí Opera Turbo, ale nejspíš by mohla v nějaké (byť technicky možná odlišné) podobě přežít. Co ale Opera Mini? Opera Software slíbila, že ji zachová. Což možná nebude tak jednoduché...

Jak funguje Opera Mini?

To, co si člověk stáhne do mobilu (klientská část Opery Mini), neumí ani HTML a CSS. To umí formát OBMP, který dostane ze serverů Opery. Nejde jen o nějakou obyčejnou kompresi typu GZIP. Server Opery patrně téměř kompletně vykreslí stránku a pošle ji v úsporném formátu klientovi. Ukázat si to můžeme malými experimenty:

  • Zkuste otočit displej. Text se nijak nepřeskládá, vše zůstane tak, jak je. Text se přeskládá jen po reloadu stránky. Starší verze Opery Mini (zřejmě 4.*) se v tomto případě dokonce ptala, jestli uživatel chce stránku znovu načíst.
  • Zkuste zkopírovat nějaký text na stránce. Zkopíruje se i s novými řádky a případnými přidanými mezerami. To jen podporuje variantu, kdy i lámání textu probíhá na serveru.
  • Zkuste na nějaké stránce kliknout nějaké tlačítko, které provede nějakou akci offline. Například může jít o rozbalení/sbalení textu. (Dřív to šlo vidět dobře například na mobilní Wikipedii, dnes už ne.) Opera Mini to neprovede offline. Musí se zeptat serveru, co s tím. Javascriptová validace formulářů tak může docela obtěžovat.

Jistě by se našlo mnoho dalších příkladů. Formát OBML se nejspíš v jistém smysllu podobá PDF. Je to připraveno pro přesně dané rozměry stránky a nejde nějak snadno provést například text reflow. (Ano, u PDF to jde, ale je to spíš hack a jsou s tím spojeny jisté problémy, pokud se například používá dělení slov.)

A kde je problém?

Zkusme navrhnout, jak to implementovat. Mějme nějaké obecné jádro prohlížeče a implementujme nad ním prohlížeč podobný Opeře Mini. Co budeme potřebovat? Základ je jasný, klient pošle, řekněme, URL, rozlišení obrazovky a DPI, server to vykreslí a pošle zpět. Pro začátek třeba použijeme PNG, nebudeme řešit výběr textu, hledání, zoom ani datovou náročnost. Budeme asi muset sázet text do sloupců širokých nejvýše stejně jako obrazovka. To v případě WebKitu, který se používá v mnohých jiných mobilních prohlížečích, problém nebude. Budeme muset nějak udělat funkční formuláře, což vyřešíme posíláním pozic a identifikátorů jednotlivých elementů formuláře. Nejzajímavější ale může být implementace Javascriptu. Budeme muset vyřešit, která část stránky reaguje na kliknutí, udělat z ní odkaz, který se nějak speciálně zpracuje na serveru. Zároveň ale budeme chtít, aby se při kliknutí mimo klikatelné oblasti nemuselo nic vyměňovat se serverem. Toto už bude chtít celkem těsnou spolupráci s enginem.

Pokud se do toho Opera pustí touto cestou, nabízejí se navíc některé otázky. Udělá nějaký patch pro jednodušší integraci, který pošle vývojářům WebKitu? Kdo se o tyto patche bude starat? Bude se chtít vývojářům WebKitu?

Co s tím Opera udělá?

Je tu několik možností, jak se s tím Opera může vyrovnat.

Použít Presto pro Operu Mini?

Problém je v tom, že by museli Presto vyvíjet a záplatovat. Je otázka, jestli se to vyplatí. Nejspíš by to znamenalo jen vývoj v rozsahu oprav. Prvně jsem byl skeptický, ale postupně si kladu otázku, jestli by to nebylo u tohoto prohlížeče good enough.

Opustit stávající model renderování na serveru?

Pak by ale nejspíš nebyl rozdíl mezi Operou Mini a Operou Mobile (popř. Operou Ice). Pokud slibovali Operu Mini zachovat, pak asi nepůjdou touto cestou. To je dobrá zpráva pro uživatele J2ME verze, protože portovat WebKit pro J2ME by asi nikdo nechtěl. Když ne z jiných důvodů, tak kvůli nemožnosti spouštět přímo nativní kód. Kód v C++ by se špatně portoval.

Rozdělit WebKit na server a klienta?

Jak jsem psal, je to sice jedna z možností, ale jsou s tím spojeny různé výše uvedené komplikace. Možná by se změnil (zvětšil?) objem přenesených dat. Od verze 5 zřejmě v Opeře Mini funguje u interaktivních stránek někdy rozdílový update. (To je můj odhad podle měření objemu přenesených dat.) To by se mohlo změnit a třeba v první verzi by to nemuselo tak fungovat.

Co rozhodne

Vidím tu dvě reálné možnosti – adaptace WebKitu a udržování jádra Presto. Záleží na tom, jestli má jít o urdžení prohlížeče zhruba ve stávajícím stavu, nebo jestli Opera předpokládá další vývoj. Pokud předpokládá další vývoj, WebKit je asi jasná volba. Pokud ne, udržování jádra Presto (zejména opravy chyb) se může ukázat jako výhodnější varianta.

AKTUALIZOVÁNO: Opera kupuje Skyfire

Přidala se nová zpráva, kterou jsem si bohužel přečetl až po publikaci tohoto blogpostu. Totiž že Opera kupuje Skyfire. Trošku jsem zavzpomínal a pohledal a přinejmenším se dost nabízí, že Skyfire bude dost souviset s budoucí podobou Opery Mini. Dám sem citaci z článku z Wikipedie, které mluví za vše: In Skyfire's first generation (1.x) browser, a web page is fully rendered by a server separate from the mobile device, similar to the operation of a thin client.[3] This approach is also used by Opera Mini. Skyfire's second generation (2.x) browser employs a hybrid approach, using a conventional rendering of Web pages on the handheld device, but streaming video from Skyfire's servers.[4]

Je to otázka. Starší verze byla založena na jádru Gecko (stejně jako Firefox) a šlo o tenkého klienta stejně jako Opera Mini. Dnes staví na WebKitu, ale je mnohem blíže klasickým prohlížečům, protože na svém serveru zpracovává jen videa a podobný obsah. Může jít jen o komponentu do Opery Ice. Nebo se pro Operu Mini použije upravený kód ze Skyfire 1 a pro Operu Ice videa z novějších verzí Skyfire? Nevím, budoucnost je po tomto kroku ještě možná o něco nejasnější.

neděle 20. ledna 2013

Zeman vs. Schwarzenberg: žádná sláva

Tak se nám blíží druhé kolo prezidentské volby. Zbyli nám jen dva kandidáti. Navzdory tomu, jak se prezentují, mezi nimi nevidím příliš rozdílů. Ani jednoho na hradě nechci. Ale přece jen vybírám, jeden z nich tam, bohužel, bude.

Kauzy

Zeman je spojen s mnoha kauzami. O tom se mluví tak, že je zde snad ani nemusím zmiňovat. Mnohem méně se mluví o tom, že čistý není ani Schwarzenberg. Ten například hlasoval pro podporu fotovoltaiky. (Omlouvám se za Google cache, na senat.cz to dnes nefunguje.) Údajně hlasoval pro povinná biopaliva. (Nedaří se mi dohledat.) Doporučil schválit ACTA. A hlasoval pro ESM. Přesto má podle mnohých pověst čestného politika.

Čistě nevypadá ani jeden. I tak se je můžeme pokusit srovnat:

  • Ke Schwarzenbergovi najdeme asi méně kauz.
  • Není ale až tak důležitý počet, ale závažnost. V souvislosti se Zemanem jsem slyšel především o kauzách, kde se ztratil jednorázově nějaký milión, desítka milionů, možná miliarda. Máte-li jiné informace, uvítám. Zvlášť protože sám nejsem úplně rozhodnut, koho volit.
  • Naproti tomu Schwarzenberg hlasoval pro smlouvu ESM a doporučil schválit smlouvu ACTA. Tuším, že tyto smlouvy by mohly (ACTA mohla, ESM může) páchat škodu řadu let po schválení.
  • Od Zemana vyčnívá kauza Slonková. Ale nevím, jestli s tím měl Zeman něco přímo společného.

Dohled médií

Jak jsem psal, média jsou zajímavá věc. Zemanovy kauzy (aniž bych chtěl tím zmenšovat jejich význam) jsou propírány, zatímco podle dojmu z médií by Schwarzenberg měl být snad co nejdříve svatořečen. Nevím, čím to je, ale dobrý dojem z toho nemám.

Bankovní rada ČNB

Prezident jmenuje bankovní radu České národní banky. Stávajícím členům funkce mají končit v letech 2014, 2016, 2017 a 2018 (opravil jsem to podle ProInvestory.cz). Tady by se kandidáti lišili:

  • Zeman by zvažoval mj. Švejnara.
  • U Schwarzenberga jsem nic konkrétnějšího nenašel. V roce 2016 ale bude dost možná TOP09 mimo vládu a Kalousek by mohl mít zájem. Je to ale jen spekulace.

Ani z jednoho nejsem nadšený.

Zdroj: debata na iHned.

Euro

Oba by chtěli euro nejdříve v roce 2017, pokud se nepletu. Ani jeden mě tím nenadchnul, rozdíly zde moc nejsou. Zeman má u mě menší mínus za mlžení okolo Sorose. Ve skutečnosti by podobná situace mohla nastat i mezi dolarem a eurem, nezávisle na „velikosti“ měny.

Levice vs. pravice?

Zeman se otevřeně hlásí k levici, která se nebojí vyšších daní ani regulací. Karel Schwarzenberg se hlásí k pravici. Takže snižuje daně a dereguluje? Hmm, asi ne.

Tady taky není moc rozdílů. Nejde o souboj pravice vs. levice. A i kdyby byl, není to podle mého názoru u prezidenta až tak podstatné.

ESM

Už jsem o tom psal, zmiňuji to znovu, protože to zde má i další význam. Evropský stabilizační mechanismus by pro Českou republiku mohl znamenat povinnost platit dluhy („půjčovat“) za státy, které se příliš zadlužily. Až po vstupu do eurozóny, ke kterému jsme ale zavázáni (nemáme na rozdíl od Velké Británie a Švédska výjimku, takže si o tom nemůžeme rozhodnout sami). Vstup do eurozóny podporují oba kandidáti a u mnohých států (hmm, Řecko) ani nevadilo nesplnění příslušných kritérií. Je to tedy sice závazek do budoucna, ale ČR zřejmě nemá v případě jeho přijetí možnost se mu vyhnout. Šlo by to leda vystoupením z EU, které by mohlo trvat podle Lisabonské smlouvy až dva roky, ale na to bych se nespoléhal.

ESM schválila Poslanecká sněmovna i Senát. Prezident Václav Klaus odmítl tuto smlouvu podepsat. Je tedy otázka, jak se k tomu postaví příští prezident.

Tady se postoje kandidátů liší. Karel Schwarzenberg hlasoval pro ESM. V Prezidentském duelu 2013 na ČT uvedl, že by si smlouvu důkladně přečetl a pak by nejspíš podepsal. Jeden ústavní právník by ho od toho neodradil. Kdyby byli proti všichni ústavní právníci, pak by se podle svých slov ještě jednou zamyslel.

Naproti tomu Zeman jasně uvedl své výhrady proti ESM. Sice neslíbil, že nepodepíše, ale byl zde mnohem přesvědčivější než Schwarzenberg.

Dopady na další volby

Schwarzenberg je předseda strany TOP09. Přestože se mnozí voliči za volbu této strany omlouvali, Schwarzenberg je stále populární. Je otázka, co by se stalo, kdyby se stal prezidentem a nekandidoval ve volbách do Poslanecké sněmovny. Mohl by nastat propad TOP09. Je otázka, k čemu by to vedlo – jestli k větší popularitě ČSSD (vlastně žádná velká změna), nebo k větší popularitě skutečně pravicových stran.

U Zemana nedokážu odhadnout. Pokud by se stal prezidentem, byl by více na očích a více na očích by mohla být jeho strana. Ale na druhou stranu, pokud by do Poslanecké sněmovny nekandidoval Zeman, výrazná ikona této strany, jakou šanci by měla SPOZ.

Slovník prezidenta

Zemanovi je vyčítán jeho slovník. Zajímavé je, že se prakticky vůbec nemluví o tom, že ani Schwarzenberg nemá problém někoho označit např. za magora. Nevím proč.

Na druhou stranu, je asi podstatné hlavně to, co prezident reálně udělá, než co (a jakými vyjadřovacími prostředky) říká.

Koho tedy volit?

Sám nevím. Zvažuji Zemana, ale ve hře jsou všechny tři možnosti. Snížit zisk TOP09 ve volbách do PS 2014 ale může být též zajímavé. Jisté je jen to, že k volbám půjdu. Není jisté, jestli k nim půjdu střízlivý. (Za střízliva se chci rozhodnout, ale ne vhazovat obálku s jedním z těchto dvou kandidátů.) Možná podpořím někoho třetího (via Dominik Stroukal), nevím.

čtvrtek 10. ledna 2013

Grahamův problém v Javě je ukecaný. A vadí to?

Grahamův problém má ukázat, jak je nějaký jazyk expresivní. V některých jazycích stačí dva nebo tři řádky, v Javě jsem napočítal aspoň devět řádků. Vadí to?

V Javě vypadá řešení zhruba takto, když chceme být struční:

public class Accumulator {
 private int value;
 public Accumulator(int value) {
  this.value = value;
 }
 public int add(int i) {
  return value += i;
 }
}

Prakticky totéž ve Scale by bylo stručnější:

class MutableAccumulator(private var value: Int){
 def apply(i: Int) = {
  value += i
  value
 }
}

Ačkoli dám přednost Scale, musím uznat, že i Javové řešení je dobře čitelné. A jak je to s psaním? Sice nešetřím každý úder do klávesnice, ale nemám rád, když s sebou psaní kódu nese zbytečně velkou režii, která odvádí pozornost. Není to trochu problém?

Síla Javy je ale jinde. K Javě existují dobrá IDE. Napsal jsem v principu jen něco přes dva řádky, abytek řešilo celkem intuitivní cestou IDE. V mém případě IntelliJ IDEA, ale podobnou službu udělá i Eclipse nebo NetBeans. Tady je video (bez zvuku):


Pokud je to špatně vidět, doporučuji přepnout na vyšší kvalitu videa.
Nejde-li video přehrát, je ke stažení jako OGV.

Schválně jsem nastavil malé rozměry okna. Dá se na to koukat i z 3" mobilu. Až na rozměry okna ale je to pro mě normální nastavení. Nic navíc tam nezaclání, většina okna slouží k psaní kódu.

Jak vidíte na videu:

  • Mám kód, který používá neexistující (neimplementovanou) třídu a neexistující metody. IDE mě na toto upozorní.
  • Nechám tu zatím neexistující třídu vytvořit. (Alt+Enter)
  • Přidám ručně private int n;
  • Nakouknu se do mainu a vidím, že nesedí konstruktor. Nechám si tedy vygenerovat konstruktor z fieldů třídy. (Shift+Insert)
  • Nakouknu se do mainu a vidím, že ještě chybí add. Nechám si tedy vytvořit metodu add (Alt+Enter), určím návratový typ a napíšu return n += i. Ostatní jen schválím
  • V mainu teď nic není červené. Můžu spustit.
  • Ještě jako bonus přidám getter a setter. (Možná se do akumulátoru nehodí, ale pro ukázku IDE...)
  • Hmm, pojmenovat ten field n nebylo moudré. Nevadí, můžu jej přejmenovat (Shift+F6). Přejmenují se i metody getN a setN na getValue a setValue. Může se přejmenovat i parametr konstruktoru. Tady jsem to zamítl.
  • Přidám i výpis hodnoty acc.getValue(). Napsal jsem ale jen acc.gV a IDE zbytek doplnilo.

Nabízí se tu otázky. Mohou kvality IDE nahradit všechny kvality jazyka? Nebo je to naopak a dobré IDE je tu jen od toho, aby pomohlo programátorovi strpět špatný jazyk?

Pravda tu bude asi někde uprostřed. Dobré IDE těžko vyřeší šílené konstrukce nějakého jazyka. Na druhou stranu, IDE se hodí i u příjemnějších jazyků. Typickým příkladem je přejmenování nějaké metody, které je potřeba řešit i všude, kde se ta metoda používá. IDE tuto změnu udělá napříč celým projektem.

Úplně ideální kombinaci jazyka a IDE jsem nenašel. Takovou podporu IDE, jakou má Java (toto video je jen stručný nástřel), jsem u jiného jazyka neviděl. Pokud si ale můžu vybírat jazyk, dám většinou přednost Scale. Podpora IDE se sice s Javou srovnávat nemůže, ale celkem to stačí. I díky tomu, že jde o příjemnější jazyk.

pátek 4. ledna 2013

Jaké je vlastně funkcionální programování? (debata k ĚĽŠČŘ)

Jiří Knesl napsal plugin ĚĽŠČŘ, Jakub Vrána mu jej zkritizoval a Jiří Knesl zareagoval na Jakubovu kritiku tím, že mu šlo hlavně o vyzkoušení funkcionálního programování. Jakub Vrána se ale podivuje, co je na tom tak elegantního. I já se tedy do diskuze zapojím, byť se zpožděním. Napřed ale trošku odbočím.

Způsoby vyhodnocování

Nechci tu mít moc teorie, tak jen ve stručnosti:

Striktní vyhodnocování

Toto určitě všichni znáte, protože to využívají snad všechny mainstreamové jazyky. Vyhodnotí se prostě vše (nepočítáme-li optimalizace jako &&), i pokud to nebude nikdy potřeba. To je právě důvod, proč v Javascriptu výraz [3, decodeURIComponent("aa=%gg"), 8, 9][3] nevrátí hodnotu 9, ale skončí výjimkou.

Vyhodnocování on-demand

Druhá možnost je provést vyhodnocování teprve ve chvíli, kdy je to potřeba. Sem patřì normální a líné vyhodnocování, rozdíly mezi nimi teď nejsou podstatné. Pokud se v Haskellu pokusíme vyhodnotit [3, 1 `div` 0, 8, 9] !! 3, dostaneme 9, ačkoli celočíselné dělení nulou končí v Haskellu výjimkou. Funguje to díky tomu, že výraz 1 `div` 0 není potřeba vyhodnocovat. Pokud by se vyhodnocoval, vznikla by v Haskellu výjimka kvůli dělení nulou.

Asi je zřejmé, proč v mainstreamových (aspoň trošku imperativních) jazycích na toto nenarazíte: jakmile byste začali ve výrazech používat side effects, nastala by pravá magie. Těžko by se ovlivňovalo pořadí vyhodnocování (nebo to, zda by se něco vůbec vyhodnotilo) a chování programu by se začalo nepředvídatelně měnit.

Funkcionální klasika: linked list

Ve funkcionálním programování je spojový seznam velmi oblíbený. Ne, že by nešlo používat např. klasické pole, ale klasický funkcionální spojový seznam je dobré znát. Seznam je buď prázdný (v Haskellu []), nebo se skládá z jednoho prvku a reference na zbytek seznamu (v Haskellu head:tail). Tak je seznam definován rekurzivně a lze některé suffixy seznamu použí ve více různých seznamech. Například budeme mít dva seznamy o sto prvcích, ale budou se lišit vždy jen v prvním prvku, takže do paměti uložíme jen 101 prvků. Na funkčnost to nebude mí vliv, protože tyto seznamy jsou immutable. U vyhodnocování on-demand je navíc možné mít nekonečné seznamy. Součet nekonečné řady tak sice nespočítáte (aspoň ne přesně, sum (takeWhile (<epsilon) someList), tedy součet členů menších než epsilon u klesající řady, fungovat bude), ale třeba seznam všech prvočísel, ze kterého se na konec ve skutečnosti vyhodnotí jen prvních n z nich, není problém.

Jak je to s funkcemi map a filter

A už se dostávám ke článku, na který jsem reagoval. Funkce map a filter (popř. další, jako třeba reduceLeft, reduceRight, take, drop, takeWhile, dropWhile...) skutečně nejsou vše, o čem je funkcionální programování. Programovat bez nich skutečně lze. Ale není to ono. Až tak se nedivím, že se Jakub Vrána pod článkem podivil, kde je ta elegance.

Jak jsou tyto funkce (map, reduce, ...) ve skutečnosti implementovány?

Teď budu trošku kritizovat. A to článek nejen Jiřího Knesla, ale i samotné funkcionální programování. Jde mi o to, že funkce typické pro funkcionální programování není až tak snadné napsat správně. Ukážeme si to na funkci map. Nejdřív si odbydeme vyhodnocování on-demand (které zkritizuju za chvilku). Tam není nutné řešit tail call optimization, protože díky způsobu vyhodnocování nenastane rekurze v té podobě, v jaké ji známe ze striktního vyhodnocování. Můžeme tedy namapovat první prvek a rekurzivně namapovat zbytek:

map f (x:xs) = (f x) : (map f xs)

Funkce tedy vezme funkci f a seznam (x:xs). Zápis (x:xs) ve skutečnosti znamená, že parametr je neprázdný seznam a ten je rozdělen na první prvek (x) a zbytek (xs). Zbývá dořešit prázdný seznam, ten se namapuje na prázdný seznam:

map f [] = []

Jenže takto to funguje dobře jen u vyhodnocování on-demand. U striktního vyhodnocování získáme s dlouhými seznamy mnoho rekurzí a potřebujeme velký stack. Nepomůže ani tail call optimization, protože poslední operace není rekurze, ale vytvoření seznamu (:). Takto tedy ne.

Pak se nám nabízí použít akumulátor, což přesně udělal Jiří Knesl. Určitou nevýhodou je, že seznam procházíme od začátku, ale přidáváme též na začátek. Výsledný seznam tedy dostaneme v opačném pořadí:

map f list = map0 f list []
map0 f [] acc = acc
map0 f (x:xs) acc = map0 f xs ((f x):acc) -- chyba, obracíme pořadí.

Můžeme na to zavolat i funkci reverse (tu jde naštěstí napsat snadno) a dostaneme dokonce i dobrou asymptotickou složitost (konstantní na stack, lineární na heap a na čas), ale je to velmi neelegantní. O paměťové lokalitě nemluvě.

Trošku po svém si s tím poradila Scala (funkcionální jazyk se striktním vyhodnocováním). Funkce map je u třídy List efektivní, elegantní, čitelná (byť se znalostí pokročilejších konstrukcí), ale bohužel ne funkcionální. Autoři byli pragmatici, ne fanatici.

Původně jsem sem chtěl zkopírovat i implementaci pro důkaz, že to je fakt imperativně. Třída List ale nechává implementaci metody map na traitu TraversableLike, který to implementuje obecněji. Vysvětlovat tu implementaci lidem, kteří jazyk Scala nepotkali, by ale bylo nad rámec tohoto článku.

Snadný paralelismus?

Funkcionální programování k paralelismu přímo vybízí. Například ve Scale stačí do funkcionálního kódu přidat na pár míst par a hned je paralelní. (No dobře, má to svá úskalí, ale o tom třeba jindy.) U striktního vyhodnocování to funguje celkem dobře, pokud se u funkcí jako je map vzdáme části elegance. Menší problém je formát seznamu, spojový seznam není příliš vhodný u mnoha krátkých výpočtů.

Horší situace je u vyhodnocování on-demand. Co všechno má být vyhodnoceno paralelně? Pokud se výpočet něčeho odloží na později, nemusí se to vykonávat paralelně. Pokud se má vyhodnotit vše, bude se to vyhodnocovat striktně. Mimochodem, na tento problém jsem narazil ve Scale u funkce mapValues, která se kupodivu nechovala striktně. Místo toho, aby výpočet proběhl celý paralelně, se podstatná část odložila na později a spočítala se až při výpisu. Samozřejmě sériově.

Tail call optimization

A ještě jedna věc, která se sice netýká výhradně funkcionálního programování, ale – protože se tam rekurze prostě používá často – stojí za zmínku. Navíc chci v tomto reagovat i na Jiřího Knesla. Myšlenka je, že pokud je nějaké volání funkce posledním příkazem, lze uvolnit místo na stacku již při volání. Typicky se toho využívá při rekurzi. Z koncové rekurze kompilátor může udělat (mírně zjednodušeno) skok na začátek funkce. Program s rekurzí se tak může přeložit úplně stejně, jako kdyby měl cyklus. Teorie je to pěkná, Jiří Knesl se na to i odvolává při obhajobě svého skriptu. Jak je to ale doopravdy?

Hledal jsem Tail call optimization v Javascriptových enginech (na kterých bdou záviset i optimalizace Livescriptu), ale moc jsem o tom nenašel, nejvýše plány. Možná jsem jen špatně hledal, ale spíš bych se na to nespoléhal.

Ona to vlastně ani není ekvivalentní úprava. Pokud čteme stack trace (např. z výjimky), dostáváme po optimalizaci jiné údaje. To nemusí vadit, pokud o tom víme. U Javy je ale snaha zpětným nekompatibilitám (třeba i teoretickým) bránit, takže se tato optimalizace sice zvažuje, ale volání metody musí být (podle jednoho návrhu) uvozeno speciální instrukcí. Nevím o tom, že by dnes něco takového bylo v nějaké production-ready JVM podporováno. Podporovat to může kompilátor (a kompilátor pro Scalu to skutečně podporuje), ale možnosti jsou omezené. Optimalizovat takto rekurzi známou v době překladu lze relativně snadno (stačí do parametrů přiřadit nové hodnoty a goto 0, jen je potřeba řešit, aby korektně fungovalo např. i prohození parametrů), ale jiné tail calls moc dobře nejdou, protože JVM nemá instrukce pro takto low-level práci se zásobníkem. A v případě Scaly doporučuji @tailrec, aby kompilátor nezradil. U Livescriptu by teoreticky mohlo být něco podobného, překladač má asi podobné možnosti.

Závěr

Ano, funkcionální programování nabízí řadu výhod – eleganci, použitelné vyhodnocování on-demand, snadný paralelismus a další. Nemůžte ale od toho chtít všechno současně. Mám sice rád líný čistě funkcionální Haskell, ale v praxi píšu spíš v ne úplně čistě funkcionální Scale.

Pure functional programming is like anarchism: everything is stateless. Although I believe that reducing the state is often useful, I am not sure if total elimination of state is a good idea.