ZuriHac: precvičovanie funkčného programovania

V júni tohto roku sa v malom švajčiarskom mestečku Rapperswil uskutočnilo podujatie tzv ZuriHac. Tentoraz sa na ňom zišlo viac ako päťsto milovníkov Haskellu, od začiatočníkov až po otcov zakladateľov tohto jazyka. Aj keď organizátori toto podujatie nazývajú hackathon, nejde o konferenciu ani hackathon v klasickom ponímaní. Jeho formát je odlišný od tradičných programátorov. O ZuriHac sme sa dozvedeli šťastím, zúčastnili sme sa ho a teraz považujeme za svoju povinnosť povedať o nezvyčajnom náleze!

o nás

Tento článok pripravili dvaja študenti 3. ročníka programu „Aplikovaná matematika a informatika“ na Vysokej škole ekonomickej Národnej výskumnej univerzity v Petrohrade: Vasilij Alferov a Elizaveta Vasilenko. Vášeň pre funkcionálne programovanie pre nás oboch začala sériou prednášok D. N. Moskvina v 2. ročníku vysokej školy. Vasilij sa momentálne zúčastňuje programu Google Summer of Code, v rámci ktorého pod vedením projektového tímu implementuje algebraické grafy v Haskell riasa. Elizaveta aplikovala získané zručnosti funkcionálneho programovania v kurze venovanom implementácii anti-unification algoritmu s následnou aplikáciou v teórii typov.

Formát udalosti

Cieľovou skupinou sú majitelia projektov s otvoreným zdrojovým kódom, programátori, ktorí sa chcú podieľať na ich vývoji, výskumníci funkčného programovania a ľudia jednoducho nadšení pre Haskell. Tento rok sa na mieste konania – HSR Hochschule für Technik Rapperswil – zišli vývojári z viac ako päťdesiatich open source projektov Haskell z celého sveta, aby porozprávali o svojich produktoch a získali nových záujemcov o ich vývoj.

Fotografia z Twitteru ZuriHac

Schéma je veľmi jednoduchá: musíte vopred napísať niekoľko návrhov o vašom projekte a poslať ich organizátorom, ktorí zverejnia informácie o vašom projekte na stránke podujatia. Navyše, v prvý deň majú autori projektov tridsať sekúnd na to, aby z javiska veľmi stručne povedali, čo robia a čo treba urobiť. Potom záujemcovia hľadajú autorov a podrobne sa pýtajú na úlohy.

Zatiaľ nemáme vlastné otvorené projekty, ale naozaj chceme prispieť k už existujúcim, preto sme sa zaregistrovali ako pravidelní účastníci. Počas troch dní sme spolupracovali s dvoma skupinami vývojárov. Ukazuje sa, že spoločné štúdium kódu a živej komunikácie robí interakciu medzi autormi projektu a prispievateľmi veľmi produktívnou – v ZuriHac sme dokázali porozumieť oblastiam, ktoré boli pre nás nové, a boli sme schopní pomôcť dvom úplne odlišným tímom, pričom v každom sme dokončili jednu úlohu. projektov.

Okrem hodnotnej praxe sa v ZuriHac uskutočnilo aj niekoľko prednášok a majstrovských kurzov. Pamätáme si najmä dve prednášky. Na prvom z nich Andrey Mokhov z University of Newcastle hovoril o selektívnych aplikačných funktoroch – triede typov, ktoré by sa mali stať medzistupňom medzi aplikačnými funktormi a monádami. V ďalšej prednáške jeden zo zakladateľov Haskellu, Simon Peyton Jones, hovoril o tom, ako funguje typová inferencia v kompilátore GHC.

Prednáška Simona Peytona Jonesa. Fotografia z Twitteru ZuriHac

Majstrovské kurzy, ktoré sa konali počas hackathonu, boli rozdelené do troch kategórií v závislosti od úrovne trénovanosti účastníkov. Úlohy ponúkané účastníkom, ktorí sa zapojili do vývoja projektov, boli tiež označené úrovňou náročnosti. Malá, ale priateľská komunita funkčných programátorov s radosťou víta nováčikov vo svojich radoch. Na pochopenie prednášok Andreja Mokhova a Simona Peytona Jonesa bol však kurz funkcionálneho programovania, ktorý sme absolvovali na univerzite, veľmi užitočný.

Registrácia na podujatie je pre pravidelných účastníkov aj autorov projektov bezplatná. Žiadosti o účasť sme podali začiatkom júna, po ktorých sme boli rýchlo preradení z čakacej listiny do zoznamu potvrdených účastníkov.

A teraz si povieme niečo o projektoch, na vývoji ktorých sme sa podieľali.

Pandoc

Pandoc je univerzálny konvertor textových dokumentov v skutočnosti z akéhokoľvek formátu do akéhokoľvek. Napríklad z docx do pdf alebo z Markdown do MediaWiki. Jej autor John MacFarlane je profesorom filozofie na Kalifornskej univerzite v Berkeley. Vo všeobecnosti je Pandoc dosť slávny a niektorí naši priatelia boli prekvapení, keď sa dozvedeli, že Pandoc je napísaný v Haskell.

Zoznam formátov dokumentov podporovaných Pandocom. Na stránke je aj celý graf, ale tento obrázok sa do článku nezmestí.

Samozrejme, Pandoc neposkytuje priamu konverziu pre každý pár formátov. Na podporu takejto širokej škály transformácií sa používa štandardné architektonické riešenie: najprv sa celý dokument preloží do špeciálnej internej medzireprezentácie a potom sa z tejto internej reprezentácie vygeneruje dokument v inom formáte. Vývojári nazývajú internú reprezentáciu “AST”, čo je skratka pre Abstract Syntax Tree, resp abstraktný strom syntaxe. Na prechodnú reprezentáciu sa môžete pozrieť veľmi jednoducho: všetko, čo musíte urobiť, je nastaviť výstupný formát na „native“

$ cat example.html
<h1>Hello, World!</h1>

$ pandoc -f html -t native example.html
[Header 1 ("hello-world",[],[]) [Str "Hello,",Space,Str "World!"]]

Čitatelia, ktorí s Haskellom aspoň trochu pracovali, už z tohto malého príkladu môžu predpokladať, že Pandoc je napísaný v Haskelli: výstupom tohto príkazu je reťazcová reprezentácia vnútorných štruktúr Pandocu, vytvorená podobne, ako sa to zvyčajne robí. v Haskell, napríklad v štandardnej knižnici.

Takže tu vidíte, že vnútorná reprezentácia je rekurzívna štruktúra, ktorej zoznam je v každom vnútornom uzle. Napríklad na najvyššej úrovni je zoznam jedného prvku - hlavička prvej úrovne s atribútmi „hello-world“,[],[]. V tejto hlavičke je skrytý zoznam reťazca „Ahoj“, za ktorým nasleduje medzera a reťazec „World!“.

Ako vidíte, interná reprezentácia sa príliš nelíši od HTML. Je to strom, v ktorom každý vnútorný uzol poskytuje nejaké informácie o formátovaní svojich potomkov a listy obsahujú skutočný obsah dokumentu.

Ak prejdeme na úroveň implementácie, typ údajov pre celý dokument je definovaný takto:

data Pandoc = Pandoc Meta [Block]

Tu Block sú práve vyššie spomínané interné vrcholy a Meta je metainformácia o dokumente, ako je názov, dátum vytvorenia, autori – to je pre rôzne formáty rôzne a Pandoc sa snaží, ak je to možné, takéto informácie zachovať pri preklade z formátu do formát.

Takmer všetky konštruktory typu Block - napríklad Header alebo Para (odsek) - berú atribúty a zoznam vrcholov nižšej úrovne ako argumenty - spravidla Inline. Napríklad Space alebo Str sú konštruktory typu Inline a HTML tag sa tiež zmení na vlastný špeciálny Inline. Nevidíme zmysel poskytovať úplnú definíciu týchto typov, ale všimnite si, že ju možno nájsť tu tu.

Je zaujímavé, že typ Pandoc je monoid. To znamená, že existuje nejaký druh prázdneho dokumentu a dokumenty je možné poskladať. Toto je vhodné použiť pri písaní čítačiek – dokument môžete rozdeliť na časti pomocou ľubovoľnej logiky, každú z nich analyzovať samostatne a potom všetko poskladať do jedného dokumentu. V tomto prípade budú metainformácie zhromaždené zo všetkých častí dokumentu naraz.

Pri konverzii, povedzme, z LaTeXu do HTML, najprv špeciálny modul s názvom LaTeXReader skonvertuje vstupný dokument na AST, potom ďalší modul s názvom HTMLWriter prevedie AST na HTML. Vďaka tejto architektúre nie je potrebné zapisovať kvadratický počet konverzií – pre každý nový formát stačí napísať Reader a Writer a automaticky budú podporované všetky možné dvojice konverzií.

Je jasné, že takáto architektúra má aj svoje úskalia, dlhodobo predpovedané odborníkmi v oblasti softvérovej architektúry. Najvýznamnejšie sú náklady na vykonanie zmien v strome syntaxe. Ak je zmena dostatočne závažná, budete musieť zmeniť kód vo všetkých čítačkách a zapisovateľoch. Napríklad jednou z výziev, ktorým čelia vývojári Pandoc, je podpora zložitých formátov tabuliek. Teraz môže Pandoc vytvárať iba veľmi jednoduché tabuľky s hlavičkou, stĺpcami a hodnotou v každej bunke. Napríklad atribút colspan v HTML bude jednoducho ignorovaný. Jedným z dôvodov tohto správania je chýbajúca jednotná schéma reprezentácie tabuliek vo všetkých alebo aspoň v mnohých formátoch – preto nie je jasné, v akej forme majú byť tabuľky uložené v internej reprezentácii. Ale aj po výbere konkrétneho zobrazenia budete musieť zmeniť absolútne všetky čítačky a zapisovače, ktoré podporujú prácu s tabuľkami.

Jazyk Haskell bol vybraný nielen kvôli veľkej láske autorov k funkcionálnemu programovaniu. Haskell je známy svojimi rozsiahlymi možnosťami spracovania textu. Jedným z príkladov je knižnica parsek je knižnica, ktorá aktívne využíva koncepty funkcionálneho programovania - monoidy, monády, aplikačné a alternatívne funktory - na písanie ľubovoľných syntaktických analyzátorov. Plnú silu Parsecu je možné vidieť v príklad z HaskellWiki, kde je analyzovaný kompletný analyzátor jednoduchého imperatívneho programovacieho jazyka. Parsec sa samozrejme aktívne používa aj v Pandoc.

Stručne opísané, monády sa používajú na sekvenčnú analýzu, keď je prvá vec a potom druhá. Napríklad v tomto príklade:

whileParser :: Parser Stmt
whileParser = whiteSpace >> statement

Najprv musíte spočítať medzeru a potom príkaz - ktorý má tiež typ Parser Stmt.

Alternatívne funktory sa používajú na vrátenie späť, ak analýza zlyhá. Napríklad,

statement :: Parser Stmt
statement = parens statement <|> sequenceOfStmt

To znamená, že musíte buď skúsiť prečítať vyhlásenie v zátvorkách, alebo sa pokúsiť prečítať niekoľko vyhlásení za sebou.

Aplikačné funktory sa používajú predovšetkým ako skratky pre monády. Napríklad, nechajte funkciu tok čítať nejaký token (toto je skutočná funkcia z LaTeXReadera). Pozrime sa na túto kombináciu

const <$> tok <*> tok

Prečíta dva žetóny za sebou a vráti prvý.

Pre všetky tieto triedy má Haskell krásne symbolické operátory, vďaka ktorým programovanie v aplikácii Reader vyzerá ako umenie ASCII. Len obdivujte tento úžasný kód.

Naše úlohy súviseli s LaTeXReaderom. Vasilyho úlohou bolo podporovať príkazy mbox a hbox, užitočné na písanie balíkov v LaTeXe. Elizabeth bola zodpovedná za podporu príkazu epigraph, ktorý vám umožňuje vytvárať epigrafy v dokumentoch LaTeXu.

Hatrace

Operačné systémy podobné UNIXu často implementujú systémové volanie ptrace. Je to užitočné pri ladení a simulácii programových prostredí, čo vám umožňuje sledovať systémové volania, ktoré program uskutočňuje. Napríklad veľmi užitočná utilita strace používa interne ptrace.

Hatrace je knižnica, ktorá poskytuje rozhranie pre ptrace v Haskell. Faktom je, že samotný ptrace je veľmi sofistikovaný a je pomerne ťažké ho priamo použiť, najmä z funkčných jazykov.

Hatrace beží ako strace pri spustení a prijíma podobné argumenty. Od strace sa líši tým, že je to tiež knižnica, ktorá poskytuje jednoduchšie rozhranie ako len ptrace.

Pomocou hatrace sme už zachytili jednu nepríjemnú chybu v kompilátore GHC Haskell – zabitie v nesprávnom momente generuje nesprávne objektové súbory a pri reštarte ich neprekompiluje. Skriptovanie pomocou systémových volaní umožnilo spoľahlivo reprodukovať chybu v jednom spustení, zatiaľ čo náhodné zabitia reprodukovali chybu približne za dve hodiny.

Do knižnice sme pridali rozhrania systémových volaní – Elizaveta pridala brk a Vasily pridal mmap. Na základe výsledkov našej práce je možné pri používaní knižnice jednoduchšie a presnejšie použiť argumenty týchto systémových volaní.

Zdroj: hab.com