ZuriHac: procvičování funkcionálního programování

V červnu letošního roku se v malém švýcarském městečku Rapperswil uskutečnila akce tzv ZuriHac. Tentokrát se na něm sešlo více než pět set milovníků haskellu, od začátečníků až po otce zakladatele tohoto jazyka. Přestože pořadatelé tuto akci nazývají hackathon, nejedná se o konferenci ani hackathon v klasickém slova smyslu. Jeho formát je odlišný od tradičních programátorů. O ZuriHac jsme se dozvěděli náhodou, zúčastnili jsme se toho a nyní považujeme za svou povinnost o neobvyklém nálezu vyprávět!

O nás

Tento článek připravili dva studenti 3. ročníku programu „Aplikovaná matematika a informatika“ na Vysoké ekonomické škole National Research University – Petrohrad: Vasilij Alferov a Elizaveta Vasilenko. Vášeň pro funkcionální programování pro nás oba začala sérií přednášek D. N. Moskvina ve 2. ročníku VŠ. Vasily se v současné době účastní programu Google Summer of Code, v rámci kterého pod vedením projektového týmu implementuje algebraické grafy v Haskellu Řasa. Elizaveta uplatnila získané dovednosti funkcionálního programování v kurzech věnovaných implementaci anti-unification algoritmu s následnou aplikací v teorii typů.

Formát události

Cílovou skupinou jsou majitelé projektů s otevřeným zdrojovým kódem, programátoři, kteří se chtějí podílet na jejich vývoji, výzkumníci funkčního programování a lidé prostě nadšení pro Haskell. Letos se vývojáři z více než padesáti open source projektů Haskell z celého světa sešli na místě konání - HSR Hochschule für Technik Rapperswil -, aby pohovořili o svých produktech a získali nové zájemce o jejich vývoj.

Foto z Twitteru ZuriHac

Schéma je velmi jednoduché: musíte předem napsat několik návrhů o vašem projektu a poslat je organizátorům, kteří informace o vašem projektu zveřejní na stránce události. Navíc první den mají autoři projektů třicet vteřin na to, aby z pódia velmi stručně řekli, co dělají a co je potřeba udělat. Poté zájemci hledají autory a podrobně se ptají na úkoly.

Zatím nemáme vlastní otevřené projekty, ale opravdu chceme přispět k těm stávajícím, proto jsme se zaregistrovali jako pravidelní účastníci. Během tří dnů jsme spolupracovali se dvěma skupinami vývojářů. Ukazuje se, že díky společnému studiu kódu a živé komunikace je interakce mezi autory projektu a přispěvateli velmi produktivní – ve společnosti ZuriHac jsme byli schopni porozumět oblastem, které pro nás byly nové, a byli jsme schopni pomoci dvěma zcela odlišným týmům, přičemž v každém jsme dokončili jeden úkol. projektů.

Kromě cenné praxe se na ZuriHac uskutečnilo také několik přednášek a mistrovských kurzů. Zvláště vzpomínáme na dvě přednášky. Na prvním z nich Andrey Mokhov z University of Newcastle hovořil o selektivních aplikačních funktorech - třídě typů, které by se měly stát prostředníkem mezi aplikačními funktory a monádami. V další přednášce jeden ze zakladatelů Haskellu, Simon Peyton Jones, hovořil o tom, jak funguje odvození typu v kompilátoru GHC.

Přednáška Simona Peytona Jonese. Foto z Twitteru ZuriHac

Mistrovské kurzy pořádané během hackathonu byly rozděleny do tří kategorií podle úrovně trénovanosti účastníků. Úkoly nabízené účastníkům, kteří se zapojili do vývoje projektů, byly rovněž označeny mírou obtížnosti. Malá, ale přátelská komunita funkčních programátorů s radostí vítá nováčky ve svých řadách. Pro pochopení přednášek Andreje Mokhova a Simona Peytona Jonese byl ale velmi užitečný kurz funkcionálního programování, který jsme absolvovali na univerzitě.

Registrace na akci je pro běžné účastníky i autory projektů zdarma. Přihlášky k účasti jsme podali začátkem června, poté jsme byli rychle převedeni z pořadníku na seznam potvrzených účastníků.

A nyní si povíme o projektech, na jejichž vývoji jsme se podíleli.

Pandoc

Pandoc je univerzální převodník textových dokumentů, ve skutečnosti z jakéhokoli formátu do libovolného. Například z docx do pdf nebo z Markdown do MediaWiki. Její autor John MacFarlane je profesorem filozofie na Kalifornské univerzitě v Berkeley. Obecně je Pandoc docela slavný a někteří naši přátelé byli překvapeni, když se dozvěděli, že Pandoc byl napsán v Haskell.

Seznam formátů dokumentů podporovaných Pandocem. Na stránkách je také celý graf, ale tento obrázek se do článku nevejde.

Pandoc samozřejmě neposkytuje přímou konverzi pro každou dvojici formátů. Pro podporu tak široké škály transformací se používá standardní architektonické řešení: nejprve je celý dokument přeložen do speciální vnitřní mezilehlé reprezentace a poté je z této interní reprezentace vygenerován dokument v jiném formátu. Vývojáři nazývají interní reprezentaci „AST“, což je zkratka pro Abstract Syntax Tree, popř abstraktní strom syntaxe. Na přechodnou reprezentaci se můžete podívat velmi jednoduše: vše, co musíte udělat, je nastavit výstupní formát na „nativní“

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

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

Čtenáři, kteří s Haskellem alespoň trochu pracovali, již z tohoto malého příkladu mohou předpokládat, že Pandoc je napsán v Haskellu: výstupem tohoto příkazu je řetězcová reprezentace vnitřních struktur Pandocu, vytvořená podobně, jak se to obvykle dělá. v Haskellu, například ve standardní knihovně.

Zde tedy vidíte, že vnitřní reprezentace je rekurzivní struktura, jejíž seznam je v každém vnitřním uzlu. Například na nejvyšší úrovni je seznam jednoho prvku - záhlaví první úrovně s atributy „hello-world“,[],[]. V této hlavičce je skrytý seznam řetězce „Ahoj“ následovaný mezerou a řetězcem „World!“.

Jak vidíte, interní reprezentace se příliš neliší od HTML. Je to strom, kde každý vnitřní uzel poskytuje nějaké informace o formátování svých potomků a listy obsahují skutečný obsah dokumentu.

Pokud půjdeme dolů na úroveň implementace, datový typ pro celý dokument je definován takto:

data Pandoc = Pandoc Meta [Block]

Zde Block jsou právě výše zmíněné vnitřní vrcholy a Meta je metainformace o dokumentu, jako je název, datum vytvoření, autoři - to se liší pro různé formáty a Pandoc se snaží, pokud je to možné, takové informace zachovat při překladu z formátu do formát.

Téměř všechny konstruktory typu Block - například Header nebo Para (odstavec) - berou jako argumenty atributy a seznam vrcholů nižší úrovně - zpravidla Inline. Například Space nebo Str jsou konstruktory typu Inline a HTML tag se také promění ve svůj speciální Inline. Nevidíme žádný smysl poskytovat úplnou definici těchto typů, ale všimněte si, že ji lze nalézt zde zde.

Zajímavé je, že typ Pandoc je monoidní. To znamená, že existuje nějaký druh prázdného dokumentu a že dokumenty lze skládat dohromady. To je vhodné použít při psaní Readers – dokument můžete rozdělit na části pomocí libovolné logiky, analyzovat každou zvlášť a pak vše dát dohromady do jednoho dokumentu. V tomto případě budou metainformace shromážděny ze všech částí dokumentu najednou.

Při převodu, řekněme, z LaTeXu do HTML, nejprve speciální modul nazvaný LaTeXReader převede vstupní dokument na AST, poté další modul nazvaný HTMLWriter převede AST na HTML. Díky této architektuře není potřeba zapisovat kvadratický počet převodů – pro každý nový formát stačí napsat Reader a Writer a budou automaticky podporovány všechny možné dvojice převodů.

Je jasné, že taková architektura má i své úskalí, dlouho předvídané odborníky v oblasti softwarové architektury. Nejvýznamnější jsou náklady na provedení změn ve stromu syntaxe. Pokud je změna dostatečně závažná, budete muset změnit kód ve všech čtečkách a zapisovatelích. Jednou z výzev, kterým čelí vývojáři Pandoc, je například podpora složitých formátů tabulek. Nyní může Pandoc vytvářet pouze velmi jednoduché tabulky se záhlavím, sloupci a hodnotou v každé buňce. Například atribut colspan v HTML bude jednoduše ignorován. Jedním z důvodů tohoto chování je chybějící jednotné schéma pro reprezentaci tabulek ve všech nebo alespoň mnoha formátech - není tedy jasné, v jaké podobě by měly být tabulky v interní reprezentaci uloženy. Ale i po výběru konkrétního pohledu budete muset změnit absolutně všechny čtečky a zapisovače, které podporují práci s tabulkami.

Jazyk Haskell byl zvolen nejen kvůli velké lásce autorů k funkcionálnímu programování. Haskell je známý svými rozsáhlými možnostmi zpracování textu. Jedním z příkladů je knihovna parsek je knihovna, která aktivně využívá koncepty funkcionálního programování - monoidy, monády, aplikační a alternativní funktory - k psaní libovolných parserů. Plná síla Parsecu je vidět v příklad z HaskellWiki, kde je analyzován kompletní parser jednoduchého imperativního programovacího jazyka. Parsec je samozřejmě aktivně využíván i v Pandocu.

Stručně popsáno, monády se používají pro sekvenční analýzu, kdy je první věc a pak druhá. Například v tomto příkladu:

whileParser :: Parser Stmt
whileParser = whiteSpace >> statement

Nejprve je třeba spočítat mezeru a poté příkaz - který má také typ Parser Stmt.

Alternativní funktory se používají k vrácení zpět, pokud se analýza nezdaří. Například,

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

To znamená, že musíte buď zkusit přečíst příkaz v závorkách, nebo zkusit přečíst několik příkazů za sebou.

Aplikativní funktory se používají především jako zkratky pro monády. Nechte například funkci tok přečíst nějaký token (toto je skutečná funkce z LaTeXReaderu). Podívejme se na tuto kombinaci

const <$> tok <*> tok

Přečte dva tokeny za sebou a vrátí první.

Pro všechny tyto třídy má Haskell krásné symbolické operátory, díky nimž programování Readeru vypadá jako ASCII art. Jen obdivujte tento úžasný kód.

Naše úkoly se týkaly LaTeXReaderu. Vasilyho úkolem bylo podporovat příkazy mbox a hbox, užitečné pro psaní balíčků v LaTeXu. Elizabeth byla zodpovědná za podporu příkazu epigraph, který umožňuje vytvářet epigrafy v dokumentech LaTeXu.

Hatrace

Operační systémy podobné UNIXu často implementují systémové volání ptrace. Je užitečný při ladění a simulaci programových prostředí a umožňuje vám sledovat systémová volání, která program provádí. Například velmi užitečná utilita strace používá interně ptrace.

Hatrace je knihovna, která poskytuje rozhraní pro ptrace v Haskell. Faktem je, že ptrace je sám o sobě velmi sofistikovaný a je poměrně obtížné jej přímo používat, zejména z funkcionálních jazyků.

Hatrace běží jako strace při spuštění a přijímá podobné argumenty. Od strace se liší tím, že je to také knihovna, která poskytuje jednodušší rozhraní než jen ptrace.

S pomocí hatrace jsme již zachytili jednu nepříjemnou chybu v kompilátoru GHC Haskell – zabití ve špatnou chvíli generuje nesprávné objektové soubory a po restartu je nepřekompiluje. Skriptování pomocí systémových volání umožnilo spolehlivě reprodukovat chybu v jednom běhu, zatímco náhodné zabití reprodukovalo chybu asi za dvě hodiny.

Do knihovny jsme přidali rozhraní systémových volání – Elizaveta přidala brk a Vasily přidal mmap. Na základě výsledků naší práce je možné při používání knihovny jednodušeji a přesněji využít argumenty těchto systémových volání.

Zdroj: www.habr.com