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>Hello, World!</h1>

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

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

Така че, тук може да се види, че вътрешното представяне е рекурсивна структура, в която всяки вътрешен възел съдържа списък. Например, на най-горното ниво има списък с един елемент — заглавие на първо ниво с атрибути "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

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

За всички тези класове в Haskell съществуват красиви символни оператори, което прави програмирането на 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