ZuriHac: ćwiczenie programowania funkcjonalnego

W czerwcu tego roku w małym szwajcarskim miasteczku Rapperswil odbyło się wydarzenie pod nazwą ZuriHac. Tym razem zgromadziło ponad pięciuset miłośników Haskella, od początkujących po ojców założycieli języka. Choć organizatorzy nazywają to wydarzenie hackatonem, nie jest to konferencja ani hackaton w klasycznym tego słowa znaczeniu. Jego format różni się od tradycyjnych programistów. O ZuriHacu dowiedzieliśmy się przez przypadek, wzięliśmy w nim udział i teraz uważamy za swój obowiązek opowiedzieć o niezwykłym znalezisku!

O nas

Artykuł został przygotowany przez dwóch studentów III roku programu „Matematyka stosowana i informatyka” w Wyższej Szkole Ekonomicznej Państwowego Uniwersytetu Badawczego w St. Petersburgu: Wasilija Alferowa i Elizawetę Wasilenko. Nasza pasja do programowania funkcjonalnego zaczęła się od serii wykładów D. N. Moskvina na drugim roku studiów. Wasilij uczestniczy obecnie w programie Google Summer of Code, w ramach którego pod okiem zespołu projektowego wdraża grafy algebraiczne w Haskell Alga. Elizaveta wykorzystała nabyte umiejętności programowania funkcjonalnego w pracy szkoleniowej poświęconej implementacji algorytmu antyunifikacyjnego z późniejszym zastosowaniem w teorii typów.

Forma wydarzenia

Docelową grupą odbiorców są właściciele projektów open source, programiści chcący uczestniczyć w ich rozwoju, badacze programowania funkcjonalnego oraz ludzie, którzy po prostu pasjonują się Haskellem. W tym roku programiści z ponad pięćdziesięciu projektów Haskell typu open source z całego świata zebrali się w miejscu – HSR Hochschule für Technik Rapperswil – aby porozmawiać o swoich produktach i zainteresować nowych ludzi ich rozwojem.

Zdjęcie z Twittera ZuriHac

Schemat jest bardzo prosty: musisz wcześniej napisać kilka propozycji dotyczących swojego projektu i przesłać je organizatorom, którzy zamieścią informację o Twoim projekcie na stronie wydarzenia. Dodatkowo pierwszego dnia autorzy projektów mają trzydzieści sekund, aby w bardzo krótkim czasie opowiedzieć ze sceny, co robią i co jest do zrobienia. Następnie zainteresowani wyszukują autorów i szczegółowo pytają o zadania.

Nie mamy jeszcze własnych otwartych projektów, ale bardzo chcemy wnieść swój wkład w już istniejące, dlatego zarejestrowaliśmy się jako stali uczestnicy. W ciągu trzech dni pracowaliśmy z dwiema grupami programistów. Okazuje się, że wspólne studiowanie kodu i komunikacja na żywo sprawia, że ​​interakcja pomiędzy autorami projektów a współautorami jest bardzo produktywna - w ZuriHac udało nam się zrozumieć obszary, które były dla nas nowe i mogliśmy pomóc dwóm zupełnie różnym zespołom, wykonując po jednym zadaniu w każdym projektów.

Oprócz cennych praktyk, w ZuriHac odbyło się także kilka wykładów i kursów mistrzowskich. Szczególnie zapadły nam w pamięć dwa wykłady. W pierwszym z nich Andrey Mokhov z University of Newcastle mówił o selektywnych funktorach aplikacyjnych – klasie typów, które powinny stać się pośrednimi pomiędzy funktorami aplikacyjnymi a monadami. W innym wykładzie jeden z założycieli Haskella, Simon Peyton Jones, mówił o tym, jak działa wnioskowanie o typie w kompilatorze GHC.

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

Zajęcia mistrzowskie prowadzone podczas hackatonu zostały podzielone na trzy kategorie w zależności od poziomu wyszkolenia uczestników. Zadania oferowane uczestnikom, którzy włączyli się w realizację projektów, również zostały oznaczone stopniem trudności. Mała, ale przyjazna społeczność programistów funkcjonalnych chętnie wita nowicjuszy w swoich szeregach. Jednak do zrozumienia wykładów Andrieja Mochowa i Simona Peytona Jonesa bardzo przydał się kurs programowania funkcjonalnego, który odbyliśmy na uniwersytecie.

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

A teraz porozmawiamy o projektach, w rozwoju których braliśmy udział.

Pandoc

Pandoc to uniwersalny konwerter dokumentów tekstowych, właściwie z dowolnego formatu na dowolny. Na przykład z docx do pdf lub z Markdown do MediaWiki. Jej autor, John MacFarlane, jest profesorem filozofii na Uniwersytecie Kalifornijskim w Berkeley. Ogólnie Pandoc jest dość sławny i niektórzy z naszych znajomych byli zaskoczeni, gdy dowiedzieli się, że Pandoc został napisany w Haskell.

Lista formatów dokumentów obsługiwanych przez Pandoc. Na stronie jest też cały wykres, ale to zdjęcie nie pasuje do artykułu.

Oczywiście Pandoc nie zapewnia bezpośredniej konwersji dla każdej pary formatów. Aby obsłużyć tak szeroką gamę przekształceń, stosuje się standardowe rozwiązanie architektoniczne: najpierw cały dokument jest tłumaczony na specjalną wewnętrzną reprezentację pośrednią, a następnie z tej wewnętrznej reprezentacji generowany jest dokument w innym formacie. Twórcy nazywają wewnętrzną reprezentację „AST”, co oznacza abstrakcyjne drzewo składniowe lub abstrakcyjne drzewo składni. Możesz spojrzeć na reprezentację pośrednią w bardzo prosty sposób: wystarczy, że ustawisz format wyjściowy na „natywny”

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

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

Czytelnicy, którzy przynajmniej trochę pracowali z Haskellem, mogą już założyć na podstawie tego małego przykładu, że Pandoc jest napisany w Haskell: wyjściem tego polecenia jest ciąg znaków reprezentujący wewnętrzne struktury Pandoc, utworzone na podobieństwo tego, jak to się zwykle robi w Haskell, na przykład w bibliotece standardowej.

Zatem tutaj widać, że reprezentacja wewnętrzna jest strukturą rekurencyjną, w każdym wewnętrznym węźle znajduje się lista. Przykładowo na najwyższym poziomie znajduje się lista jednego elementu - nagłówek pierwszego poziomu z atrybutami „hello-world”,[],[]. Wewnątrz tego nagłówka ukryta jest lista ciągu „Hello”, po którym następuje spacja i ciąg „World!”.

Jak widać, reprezentacja wewnętrzna nie różni się zbytnio od HTML. Jest to drzewo, w którym każdy węzeł wewnętrzny dostarcza informacji o formatowaniu swoich potomków, a liście zawierają rzeczywistą zawartość dokumentu.

Jeśli zejdziemy na poziom implementacji, typ danych dla całego dokumentu definiuje się następująco:

data Pandoc = Pandoc Meta [Block]

Tutaj Block to dokładnie wspomniane wyżej wewnętrzne wierzchołki, a Meta to metainformacja o dokumencie, taka jak tytuł, data utworzenia, autorzy - jest to różne dla różnych formatów, a Pandoc stara się, jeśli to możliwe, zachować takie informacje podczas tłumaczenia z formatu na format.

Prawie wszystkie konstruktory typu Block - na przykład Header lub Para (akapit) - przyjmują jako argumenty atrybuty i listę wierzchołków niższego poziomu - z reguły Inline. Na przykład Space lub Str są konstruktorami typu Inline, a znacznik HTML również zamienia się w swój własny, specjalny Inline. Nie widzimy sensu podawania pełnej definicji tych typów, ale pamiętajmy, że można ją znaleźć tutaj tutaj.

Co ciekawe, typ Pandoc jest monoidem. Oznacza to, że istnieje jakiś pusty dokument i że dokumenty można układać w stosy. Jest to wygodne w użyciu podczas pisania Czytników - możesz podzielić dokument na części, stosując dowolną logikę, przeanalizować każdą z nich osobno, a następnie złożyć wszystko w jeden dokument. W takim przypadku metainformacje zostaną pobrane ze wszystkich części dokumentu jednocześnie.

Podczas konwersji, powiedzmy, z LaTeX-a na HTML, najpierw specjalny moduł o nazwie LaTeXReader konwertuje dokument wejściowy na AST, a następnie inny moduł o nazwie HTMLWriter konwertuje AST na HTML. Dzięki tej architekturze nie ma potrzeby zapisywania kwadratowej liczby konwersji - wystarczy napisać Reader i Writer dla każdego nowego formatu, a wszystkie możliwe pary konwersji będą automatycznie obsługiwane.

Oczywiste jest, że taka architektura ma również swoje wady, od dawna przewidywane przez ekspertów w dziedzinie architektury oprogramowania. Najbardziej znaczący jest koszt wprowadzenia zmian w drzewie składni. Jeśli zmiana jest wystarczająco poważna, konieczna będzie zmiana kodu we wszystkich czytnikach i zapisach. Na przykład jednym z wyzwań stojących przed programistami Pandoc jest obsługa złożonych formatów tabel. Teraz Pandoc może tworzyć tylko bardzo proste tabele z nagłówkiem, kolumnami i wartością w każdej komórce. Na przykład atrybut colspan w HTML zostanie po prostu zignorowany. Jedną z przyczyn takiego zachowania jest brak jednolitego schematu reprezentacji tabel we wszystkich lub przynajmniej w wielu formatach - w związku z tym nie jest jasne, w jakiej formie tabele powinny być przechowywane w reprezentacji wewnętrznej. Ale nawet po wybraniu konkretnego widoku będziesz musiał zmienić absolutnie wszystkich czytelników i pisarzy, którzy obsługują pracę z tabelami.

Język Haskell został wybrany nie tylko ze względu na wielką miłość autorów do programowania funkcjonalnego. Haskell jest znany ze swoich szerokich możliwości przetwarzania tekstu. Jednym z przykładów jest biblioteka parsek to biblioteka, która aktywnie wykorzystuje koncepcje programowania funkcjonalnego - monoidy, monady, funktory aplikacyjne i alternatywne - do pisania dowolnych parserów. Pełną moc Parseka można zobaczyć w przykład z HaskellWiki, gdzie analizowany jest kompletny parser prostego imperatywnego języka programowania. Oczywiście Parsec jest również aktywnie wykorzystywany w Pandoc.

Krótko mówiąc, monady są używane do sekwencyjnego analizowania, kiedy najpierw pojawia się jedna rzecz, a potem inna. Na przykład w tym przykładzie:

whileParser :: Parser Stmt
whileParser = whiteSpace >> statement

Najpierw musisz policzyć spację, a następnie instrukcję - która również ma typ Parser Stmt.

Funktory alternatywne służą do wycofywania zmian w przypadku niepowodzenia analizy. Na przykład,

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

Oznacza, że ​​musisz albo spróbować przeczytać stwierdzenie w nawiasach, albo spróbować przeczytać kilka stwierdzeń po kolei.

Funktory aplikacyjne są używane głównie jako skróty dla monad. Na przykład niech funkcja tok odczyta jakiś token (jest to prawdziwa funkcja z LaTeXReadera). Spójrzmy na tę kombinację

const <$> tok <*> tok

Odczyta dwa tokeny z rzędu i zwróci pierwszy.

Dla wszystkich tych klas Haskell ma piękne operatory symboliczne, dzięki czemu programowanie w programie Reader wygląda jak grafika ASCII. Po prostu podziwiaj ten wspaniały kod.

Nasze zadania dotyczyły LaTeXReadera. Zadaniem Wasilija była obsługa poleceń mbox i hbox, przydatnych przy pisaniu pakietów w LaTeX-ie. Elizabeth odpowiadała za obsługę polecenia epigraph, które pozwala na tworzenie epigrafów w dokumentach LaTeX-owych.

Nienawiść

Systemy operacyjne typu UNIX często implementują wywołanie systemowe ptrace. Jest przydatny w debugowaniu i symulowaniu środowisk programu, umożliwiając śledzenie wywołań systemowych wykonywanych przez program. Na przykład bardzo przydatne narzędzie strace używa wewnętrznie ptrace.

Hatrace to biblioteka zapewniająca interfejs do ptrace w Haskell. Faktem jest, że sam ptrace jest bardzo wyrafinowany i dość trudno go bezpośrednio używać, zwłaszcza z języków funkcjonalnych.

Hatrace przy uruchomieniu działa jak strace i akceptuje podobne argumenty. Różni się od strace tym, że jest także biblioteką zapewniającą prostszy interfejs niż tylko ptrace.

Przy pomocy hatrace złapaliśmy już jeden nieprzyjemny błąd w kompilatorze GHC Haskell - zabity w niewłaściwym momencie generuje nieprawidłowe pliki obiektowe i nie rekompiluje ich po ponownym uruchomieniu. Skrypty za pomocą wywołań systemowych umożliwiły niezawodne odtworzenie błędu w jednym uruchomieniu, podczas gdy losowe zabójstwa odtwarzały błąd w ciągu około dwóch godzin.

Dodaliśmy do biblioteki interfejsy wywołań systemowych - Elizaveta dodała brk, a Wasilij dodał mmap. Na podstawie wyników naszej pracy możliwe jest prostsze i dokładniejsze wykorzystanie argumentów tych wywołań systemowych podczas korzystania z biblioteki.

Źródło: www.habr.com