ZuriHac: упражняваме функционално програмиране

През юни тази година в малкия швейцарски град Рапперсвиле вече за десети път се проведе събитие, наречено ZuriHac. Този път се събраха над петстотин любители на Хаскел, от начинаещи до основателите на езика. Въпреки че организаторите наричат това събитие хакатон, то не е конференция или хакатон в класическия смисъл. Форматът му се различава от традиционното програмистко събитие. Разбрахме за ZuriHac по щастлива случайност, участвахме в него и сега смятаме за свой дълг да разкажем за необичайната находка!

За нас

Тази статия е написана от двама студенти от трети курс на програмата „Приложна математика и информатика“ на НИУ ВШЭ — Санкт-Петербург: Василий Алферов и Елизавета Василенко. Увлечението ни към функционалното програмиране започна с цикъл от лекции на Д. Н. Москвин през втори курс на университета. В момента Василий участва в програмата Google Summer of Code, в рамките на която работи по реализиране на алгебрични графи на езика Хаскел под ръководството на екипа на проекта Alga. Елизавета приложи придобитите умения по функционално програмиране в курсовата работа, посветена на реализирането на алгоритъм за анти-унификация с последващо приложение в теорията на типовете.

Формат на събитието

Целевата аудитория включва собственици на проекти с отворен код, програмисти, желаещи да участват в тяхното развитие, изследователи на функционалното програмиране и просто ентусиасти на Хаскел. Тази година на мястото на провеждане – университета HSR Hochschule für Technik Rapperswil – се събраха разработчици от над петдесет открити проекта на езика Haskell от цял свят, за да разкажат за продуктите си и да привлекат нови хора за тяхното развитие.

Снимки от Twitter ZuriHac

Схемата е много проста: нужно е предварително да напишете няколко изречения за проекта си и да ги изпратите на организаторите, които ще публикуват информацията за проекта ви на страницата на събитието. Освен това, в първия ден авторите на проектите имат по тридесет секунди, за да разкажат много накратко от сцената за това, с което се занимават и какво трябва да се направи. След това заинтересованите хора търсят авторите и подробно разпитват за задачите.

В момента нямаме собствени отворени проекти, но много искаме да допринесем за вече съществуващите, затова се регистрирахме като обикновени участници. През последните три дни работихме с две групи разработчици. Оказа се, че съвместното изучаване на кода и живата комуникация прави взаимодействието между авторите на проекта и контрибуторите изключително продуктивно – на ZuriHac успяхме да се ориентираме в нови за нас области и да помогнем на два напълно различни екипа, затваряйки по една задача във всеки от проектите.

Освен ценен опит, на ZuriHac бяха изнесени и няколко лекции и майсторски класове. Особено помним две лекции. На първата от тях Андрей Мохов от университета в Нюкасъл разказа за селективните аппликативни функтори — клас типове, който трябва да бъде междинен между аппликативни функтори и монади. На другата лекция един от основателите на Хаскел, Саймън Пейтон Джоунс, говори за начина, по който е организирано извеждането на типове в компилатора GHC.

Лекция на Саймън Пейтон Джоунс. Снимка от Twitter ZuriHac

Майсторските класове, провеждани по време на хакатона, бяха разделени на три категории в зависимост от нивото на подготовка на участниците. Задачите, предлагани на участниците, присъединили се към разработката на проекти, също имаха бележки за ниво на трудност. Небройно, но сплотено общество на функционални програмисти с радост приема новаците в редиците си. За да разберем лекциите на Андрей Мохов и Саймън Пейтон Джоунс, обаче, ни помогна преминалият в университета курс по функционално програмиране.

Регистрацията за мероприятието е безплатна както за обикновените участници, така и за авторите на проектите. Подадохме заявления за участие в началото на юни, след което доста бързо бяхме прехвърлени от списъка на чакащите в списъка на потвърдените участници.

Сега ще разкажем за проектите, в разработката на които участвахме.

Pandoc

Pandoc е универсален преобразувател на текстови документи, всъщност — от всеки формат в всеки. Например, от docx в pdf или от Markdown в MediaWiki. Неговият автор Джон Макфарлейн е професор по философия в Калифорнийския университет в Бъркли. Всъщност, Pandoc е доста известен, и някои от нашите познати бяха изненадани, когато научиха, че Pandoc е написан на Хаскел.

Списък с формати на документи, поддържани от Pandoc. В сайта има и цяла графика, но тази картинка не може да се побере в статията.

Разбира се, в Pandoc не е реализирана директна конверсия за всяка двойка формати. За да се поддържа толкова обширно множество преобразувания, се използва стандартно архитектурно решение: първо целият документ се превежда в специално вътрешно междинно представяне, а след това по това междупредставяне се генерира документ в друг формат. Вътрешното представяне разработчиците наричат „AST“, което се разшифрова като Abstract Syntax Tree, или абстрактно синтаксическо дърво. Можете много лесно да видите междинното представяне: за целта просто трябва да зададете изходния формат като „native“

$ cat example.html
<h1>Здравей, свят!</h1>

$ pandoc -f html -t native example.html
[Header 1 ("hello-world",[],[]) [Str "Здравей,",Space,Str "свят!"]]

Читатели, които са работили поне малко с Haskell, вече могат от този малък пример да предположат, че Pandoc е написан именно на Haskell: изходът от тази команда е представление на вътрешните структури на Pandoc под формата на низ, създадено по подобие на начина, по който обикновено се прави в Haskell, например в стандартната библиотека.

Така че, тук можете да видите, че вътрешното представяне е рекурсивна структура, в която всеки вътрешен възел съдържа списък. Например, на най-високото ниво има списък от един елемент — заглавие на първо ниво с атрибутите „hello-world“,[],[]. Вътре в това заглавие е скрит списък от низ „Hello,“ , пробел и низ „World!“.

Както можем да видим, вътрешното представяне не се различава много от HTML. То представлява дърво, в което всеки вътрешен възел съобщава определена информация за форматирането на своите потомци, а в листата се намира съдържанието на документа.

Ако слезем на нивото на конкретната реализация, типът данни за целия документ е определен по следния начин:

data Pandoc = Pandoc Meta [Block]

Тук Block — това са именно вътрешните върхове, за които става дума по-горе, а Meta — това е метаинформация за документа, като заглавие, дата на създаване, автори — за различни формати това е различно и Pandoc се стреми да запази тази информация при превод от формат в формат.

Почти всички конструктори тип Block — например, Header или Para (параграф) — приемат като аргументи атрибути и списък от по-ниски нива — обикновено Inline. Например, Space или Str — това са конструктори тип Inline, а HTML-тегът
също става специален Inline. Не виждаме смисъл да даваме пълно определение на тези типове, но отбелязваме, че можете да видите такова тук. тук.

Интересно е, че типът Pandoc е моноид. Това означава, че има някакъв празен документ и че документите могат да се събират помежду си. Това е удобно за използване при написването на Reader’и — можете да разделите документа на части с произволна логика, да парсите всяка отделно, а след това да съберете всичко заедно в един документ. При това метаинформацията ще се събере от всички части на документа наведнъж.

При конвертиране, да кажем, от LaTeX в HTML, първо специален модул, наречен LaTeXReader, преобразува входния документ в AST, след което друг модул, наречен HTMLWriter, преобразува AST в HTML. Благодарение на такава архитектура не е нужно да пишете квадратно число конвертации — достатъчно е за всеки нов формат да напишете Reader и Writer, и всички възможни двойки конвертации ще се поддържат автоматично.

Ясно е, че такава архитектура има и своите недостатъци, които отдавна са предсказани от специалистите в областта на архитектурата на софтуер. Най-същественото е цената на внесените промени в синтактичното дърво. Ако промяната е достатъчно сериозна, ще трябва да промените кода във всички Reader’и и Writer’и. Например, една от задачите пред разработчиците на Pandoc е поддръжката на сложни формати на таблици. В момента Pandoc умее само да работи с най-простите таблици, с заглавие, колони и стойност в всяка клетка. Например, атрибутът colspan в HTML просто ще бъде игнориран. Една от причините за такова поведение е отсъствието на единна схема за представяне на таблиците във всички или поне много формати — следователно, не е ясно в какъв вид трябва да се съхраняват таблиците в вътрешното представяне. Но дори след избора на конкретно представяне, ще трябва да промените абсолютно всички Reader’и и Writer’и, които поддържат работа с таблици.

Езикът Haskell не беше избран само заради голямата любов на авторите към функционалното програмиране. Haskell е известен с широките си възможности за обработка на текстове. Един от примерите е библиотеката parsec — библиотека, която активно използва концепции от функционалното програмиране — моноиди, монади, аппликативни и алтернативни функтори — за написване на произволни парсери. Цялата мощ на Parsec може да се види в примера от HaskellWiki, където се разглежда пълния парсер на прост императивен език за програмиране. Разбира се, Parsec активно се използва и в Pandoc.

Ако накратко опишем, монадите се използват за последователно парсване, когато първо идва едно, а след това друго. Например, в такъв пример:

whileParser :: Parser Stmt
whileParser = whiteSpace > > statement

Първо трябва да прочетем пустото място, а след това statement — който също има тип Parser Stmt.

Алтернативните функтори се използват за откат в случай, че парсирането не е успешно. Например,

statement :: Parser Stmt
statement = parens statement  sequenceOfStmt

Това означава, че трябва или да опитаме да прочетем statement в скоби, или последователно да опитаме да прочетем няколко statement’а.

Аппликативните функтори се използват основно като кратки пътища за монадите. Например, нека функцията tok прочита някакъв токен (това е реалната функция от LaTeXReader). Нека се запознаем с такава комбинация

const  tok  tok

Тя ще прочете два токена последователно и ще върне първия.

За всичките тези класове в Хаскел съществуват красиви символьни оператори, което прави програмирането на Reader-ите да изглежда като ASCII-арт. Само погледнете този великолепен код.

Нашите задачи бяха свързани с LaTeXReader. Задачата на Василий беше да поддържа командите mbox и hbox, полезни при написването на пакети в LaTeX. Отговорността на Елизабета беше поддръжката на командата epigraph, която позволява оформянето на епиграфи в LaTeX документи.

Hatrace

В UNIX-подобните операционни системи често е реализиран системен повик ptrace. Той е полезен при отстраняване на грешки и симулация на среди за програми, позволявайки проследяване на системните повиквания, които прави програмата. Например, много полезната утилита strace използва именно ptrace.

Hatrace — библиотека, която предоставя интерфейс за ptrace в Haskell. Факт е, че самият ptrace е много сложен и използването му директно е доста трудно, особено от функционални езици.

Hatrace при стартиране работи като strace и приема подобни аргументи. Разликата му от strace е, че той е и библиотека, предоставяща по-прост интерфейс от просто ptrace.

С помощта на hatrace вече бяха открити проблеми в компилатора на Haskell GHC — ако бъде убит в неподходящ момент, той генерира некоректни обектни файлове и не ги прекомпилира при повторно стартиране. Скриптоването на системни повиквания позволи надеждно възпроизвеждане на грешката с едно стартиране, когато произволните убивания я произвеждаха приблизително за два часа.

Добавихме интерфейси на системни повиквания в библиотеката — Елизавета добави brk, а Василий добави mmap. Резултатите от нашата работа позволяват по-просто и точно използване на аргументите на тези системни повиквания при работа с библиотеката.

Източник: habr.com