ZuriHac: ćwiczymy programowanie funkcyjne

W czerwcu tego roku w małym szwajcarskim miasteczku Rapperswil już po raz dziesiąty odbyła się impreza pod nazwą ZuriHac. Tym razem zgromadziła ponad pięciuset entuzjastów Haskella, od nowicjuszy po założycieli języka. Choć organizatorzy nazywają to wydarzenie hackathonem, to jednak nie jest to konferencja ani hackathon w klasycznym sensie. Jego format różni się od tradycyjnych wydarzeń programistycznych. O ZuriHac przypadkowo usłyszeliśmy i postanowiliśmy wziąć w nim udział, a teraz czujemy się zobowiązani, aby opowiedzieć o tej niezwykłej odkryciu!

O nas

Artykuł ten przygotowali dwaj studenci trzeciego roku programu "Matematyka stosowana i informatyka" w HSE w Petersburgu: Wasilij Alfiorow i Elizawieta Wasilenko. Nasza przygoda z programowaniem funkcyjnym zaczęła się od cyklu wykładów D. N. Moskwiń na drugim roku studiów. W tej chwili Wasilij bierze udział w programie Google Summer of Code, w ramach którego pracuje nad implementacją algebrycznych grafów w języku Haskell pod kierunkiem zespołu projektu Alga. Elizawieta wykorzystała nabyte umiejętności programowania funkcyjnego w pracy dyplomowej dotyczącej realizacji algorytmu anty-unifikacji z późniejszym zastosowaniem w teorii typów.

Format wydarzenia

Docelową grupą odbiorców są właściciele projektów open source, programiści chcący włączyć się w ich rozwój, badacze programowania funkcyjnego oraz po prostu zapaleni entuzjaści Haskella. W tym roku w miejscu wydarzenia – uniwersytecie HSR Hochschule für Technik Rapperswil – zgromadzili się deweloperzy z ponad pięćdziesięciu otwartych projektów w języku Haskell z całego świata, aby przedstawić swoje produkty i zainteresować nimi nowych ludzi.

Zdjęcie z Twittera ZuriHac

Zasada jest bardzo prosta: należy wcześniej napisać kilka zdań o swoim projekcie i wysłać je do organizatorów, którzy umieszczą informacje o Twoim projekcie na stronie wydarzenia. Ponadto, w pierwszy dzień autorzy projektów mają po trzydzieści sekund, aby bardzo krótko opowiedzieć z sceny, czym się zajmują i co trzeba zrobić. Następnie zainteresowane osoby poszukują autorów i szczegółowo pytają o zadania.

Na razie nie mamy własnych otwartych projektów, ale bardzo chcemy wnieść swój wkład w już istniejące, więc zarejestrowaliśmy się jako zwykli uczestnicy. Przez trzy dni pracowaliśmy z dwiema grupami programistów. Okazuje się, że wspólne studiowanie kodu i bezpośrednia komunikacja sprawiają, że współpraca autorów projektów i kontrybutorów jest bardzo produktywna – na ZuriHac udało nam się zgłębić nowe dla nas obszary i pomóc dwóm zupełnie różnym zespołom, zamykając po zadaniu w każdym z projektów.

Oprócz cennej praktyki, podczas ZuriHac wygłoszono także kilka wykładów i warsztatów. Szczególnie zapadły nam w pamięć dwa wykłady. Na pierwszym z nich Andriej Mocho z Uniwersytetu w Newcastle opowiedział o selektywnych aplikacyjnych funktorach — klasie typów, która ma stanowić pośredni etap między aplikacyjnymi funktorami a monadami. Na drugim wykładzie jeden z założycieli Haskella, Simon Peyton Jones, mówił o tym, jak działa wnioskowanie typów w kompilatorze GHC.

Wykład Simona Peytona Jonesa. Zdjęcie z Twittera ZuriHac

Warsztaty, które odbywały się w czasie hackathonu, podzielono na trzy kategorie w zależności od poziomu doświadczenia uczestników. Zadania, które proponowano uczestnikom do przystąpienia do projekcji, miały także oznaczenia poziomu trudności. Nieliczne, ale zgrane środowisko programistów funkcyjnych chętnie przyjmuje nowicjuszy. Do zrozumienia wykładów Andrieja Mocho i Simona Peytona Jonesa bardzo przydał się jednak odbyty na uniwersytecie kurs programowania funkcyjnego.

Rejestracja na wydarzenie jest darmowa zarówno dla zwykłych uczestników, jak i dla autorów projektów. Zgłoszenia złożyliśmy na początku czerwca, po czym dość szybko zostaliśmy przeniesieni z listy oczekujących na listę potwierdzonych uczestników.

A teraz opowiemy o projektach, w których rozwój braliśmy udział.

Pandoc

Pandoc — to uniwersalny konwerter dokumentów tekstowych, praktycznie — z dowolnego formatu na dowolny. Na przykład, z docx na pdf, lub z Markdown na MediaWiki. Jego autorem jest John McFarlane — profesor filozofii na Uniwersytecie Kalifornijskim w Berkeley. W ogóle, Pandoc jest dość znany, a niektórzy z naszych znajomych byli zdumieni, gdy dowiedzieli się, że Pandoc jest napisany w Haskellu.

Lista formatów dokumentów wspieranych przez Pandoc. Na stronie dostępna jest również cała grafika, ale ten obrazek nie mieści się w artykule.

Oczywiście, w Pandoc nie zrealizowano bezpośredniej konwersji dla każdej pary formatów. Aby wspierać tak szeroki wachlarz transformacji, stosuje się standardowe rozwiązanie architektoniczne: najpierw cały dokument jest tłumaczony na specjalne wewnętrzne reprezentacje pośrednie, a następnie na podstawie tej wewnętrznej reprezentacji generowany jest dokument w innym formacie. Wewnętrzną reprezentację deweloperzy nazywają „AST”, co jest skrótem od Abstrakcyjnego Drzewa Składniowego, czyli abstrakcyjne drzewo składniowe. Na przedstawienie wewnętrznej reprezentacji można spojrzeć bardzo łatwo: wystarczy ustawić jako format wyjściowy „native”

$ cat example.html
<h1>Witaj, świecie!</h1>

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

Czytelnicy, którzy przynajmniej trochę pracowali z Haskellem, mogą z tego małego przykładu przypuszczać, że Pandoc jest napisany właśnie w Haskellu: wynik tej komendy to reprezentacja wewnętrznych struktur Pandoc w postaci ciągu, stworzona na wzór sposobu, w jaki zwykle to się robi w Haskellu, na przykład w bibliotece standardowej.

Tak więc, można tutaj zobaczyć, że wewnętrzna reprezentacja jest recursive structure, w każdym wewnętrznym węźle znajduje się lista. Na przykład, na najwyższym poziomie znajduje się lista zawierająca jeden element — nagłówek pierwszego poziomu z atrybutami "hello-world",[],[]. Wewnątrz tego nagłówka ukryta jest lista z ciągiem "Hello," oraz ciągiem "World!".

Jak widać, wewnętrzna reprezentacja niewiele różni się od HTML. Jest to drzewo, w którym każdy wewnętrzny węzeł przekazuje jakąś informację o formatowaniu swoich potomków, a w liściach znajduje się właściwa treść dokumentu.

Jeśli zejdziemy na poziom konkretnej realizacji, typ danych dla całego dokumentu jest określony w ten sposób:

data Pandoc = Pandoc Meta [Block]

Tutaj Block to dokładnie wewnętrzne wierzchołki, o których mowa powyżej, a Meta to metainformacje o dokumencie, takie jak tytuł, data utworzenia, autorzy — dla różnych formatów jest to różne, a Pandoc stara się w miarę możliwości zachować takie informacje podczas konwersji z formatu na format.

Prawie wszystkie konstruktory typu Block — na przykład Header lub Para (akapit) — przyjmują jako argumenty atrybuty i listę niższych węzłów — zazwyczaj Inline. Na przykład, Space lub Str to konstruktory typu Inline, a HTML-tag również przekształca się w swój specjalny typ Inline. Nie widzimy sensu, aby podawać pełną definicję tych typów, jednak zauważamy, że można ją zobaczyć tutaj tutaj.

Interesujące jest to, że typ Pandoc jest monoidem. Oznacza to, że istnieje jakiś pusty dokument, i że dokumenty można łączyć ze sobą. Jest to wygodne podczas pisania Reader’ów — można dzielić dokument na części według dowolnej logiki, analizować każdą z osobna, a następnie połączyć wszystko w jeden dokument. W międzyczasie metainformacje zbiorą się ze wszystkich części dokumentu jednocześnie.

Podczas konwersji, powiedzmy, z LaTeX-a do HTML, najpierw specjalny moduł noszący nazwę LaTeXReader przekształca wejściowy dokument do AST, a następnie inny moduł, nazywający się HTMLWriter, przekształca AST do HTML. Dzięki takiej architekturze nie trzeba pisać kwadratowej liczby konwersji — wystarczy napisać Reader i Writer dla każdego nowego formatu, a wszystkie możliwe pary konwersji będą automatycznie wspierane.

Oczywiście taka architektura ma również swoje wady, od dawna przewidywane przez specjalistów w dziedzinie architektury oprogramowania. Najważniejszą z nich jest koszt wprowadzania zmian w drzewie składniowym. Jeśli zmiana jest wystarczająco poważna, trzeba będzie zmienić kod we wszystkich Reader’ach i Writer’ach. Na przykład, jedno z wyzwań stojących przed twórcami Pandoc to wsparcie złożonych formatów tabel. Obecnie Pandoc obsługuje tylko najprostsze tabele, z nagłówkiem, kolumnami i wartością w każdej komórce. Na przykład, atrybut colspan w HTML będzie po prostu ignorowany. Jedną z przyczyn takiego zachowania jest brak jednolitego schematu reprezentacji tabel we wszystkich lub przynajmniej wielu formatach — w związku z tym nie jest jasne, w jakiej formie należy przechowywać tabele w wewnętrznej reprezentacji. Ale nawet po wyborze konkretnej reprezentacji, trzeba będzie zmienić absolutnie wszystkie Reader’y i Writer’y, które wspierają pracę z tabelami.

Język Haskell został wybrany nie tylko z powodu wielkiej miłości autorów do programowania funkcyjnego. Haskell jest znany z szerokich możliwości przetwarzania tekstów. Przykładem jest biblioteka parsec — biblioteka, która aktywnie wykorzystuje koncepcje programowania funkcyjnego — monoidy, monady, aplikatywne i alternatywne funktory — do pisania dowolnych parserów. Całą moc Parsec można zobaczyć w przykładzie HaskellWiki, gdzie omawiany jest pełny parser prostego języka programowania imperatywnego. Oczywiście Parsec jest również szeroko stosowany w Pandoc.

Krótko mówiąc, monady są wykorzystywane do sekwencyjnego parsowania, kiedy najpierw następuje jedno, a potem drugie. Na przykład w takim przykładzie:

whileParser :: Parser Stmt
whileParser = whiteSpace >> statement

Najpierw trzeba przeczytać białą przestrzeń, a potem statement — który również ma typ Parser Stmt.

Alternatywne funktory są używane do wycofywania się w przypadku, gdy parsowanie się nie uda. Na przykład,

statement :: Parser Stmt
statement = parens statement  sequenceOfStmt

Oznacza to, że można albo spróbować przeczytać statement w nawiasach, albo próbować kolejno przeczytać kilka statementów.

Aplikatywne funktory są głównie używane jako skróty dla monad. Na przykład, niech funkcja tok odczytuje jakiś token (to jest rzeczywista funkcja z LaTeXReader). Przyjrzyjmy się takiej kombinacji

const  tok  tok

Odczyta dwa tokeny pod rząd i zwróci pierwszy z nich.

Dla wszystkich tych klas w Haskellu istnieją piękne symboliczne operatory, co sprawia, że programowanie Readerów przypomina ASCII-art. Tylko spójrzcie na ten wspaniały kod.

Nasze zadania były związane z LaTeXReaderem. Zadanie Wasilija dotyczyło wsparcia dla poleceń mbox i hbox, przydatnych przy pisaniu pakietów w LaTeX. Odpowiedzialność Elżbiety obejmowała wsparcie dla polecenia epigraph, pozwalającego na formatowanie epigrafów w dokumentach LaTeX.

Hatrace

W systemach operacyjnych podobnych do UNIX często realizowany jest wywołanie systemowe ptrace. Jest przydatne w debugowaniu i symulacji środowisk programów, pozwalając na monitorowanie wywołań systemowych, które wykonuje program. Na przykład bardzo przydatne narzędzie strace wykorzystuje wewnętrznie właśnie ptrace.

Hatrace to biblioteka, która udostępnia interfejs dla ptrace w Haskellu. Problem polega na tym, że sam ptrace jest bardzo skomplikowany, a jego bezpośrednie użycie jest dość trudne, szczególnie dla języków funkcyjnych.

Hatrace działa jak strace i akceptuje podobne argumenty. Jego różnica w stosunku do strace polega na tym, że jest również biblioteką, która oferuje prostszy interfejs niż sam ptrace.

Dzięki hatrace zidentyfikowaliśmy jeden nieprzyjemny błąd w kompilatorze Haskella GHC – gdy jest zabijany w niewłaściwym momencie, generuje niepoprawne pliki obiektowe i nie rekompiluje ich przy ponownym uruchomieniu. Skryptowanie na poziomie wywołań systemowych pozwoliło na pewne odtworzenie błędu w jednym uruchomieniu, podczas gdy przypadkowe zabicia powodowały błąd mniej więcej co dwie godziny.

Dodaliśmy do biblioteki interfejsy wywołań systemowych – Elżbieta dodała brk, a Wasilij mmap. Dzięki naszej pracy można teraz łatwiej i dokładniej używać argumentów tych wywołań systemowych w korzystaniu z biblioteki.

Źródło: habr.com