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

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

За нас

Тази статия е подготвена от двама студенти от 3-та година на специалност „Приложна математика и информатика” в Националния изследователски университет „Висше училище по икономика” – Санкт Петербург: Василий Алферов и Елизавета Василенко. Страстта към функционалното програмиране и за двама ни започна с поредица от лекции на Д. Н. Москвин през 2-рата година на университета. В момента Василий участва в програмата Google Summer of Code, в рамките на която внедрява алгебрични графики в Haskell под ръководството на екипа на проекта водорасло. Елизавета приложи придобитите умения за функционално програмиране в курсова работа, посветена на реализацията на алгоритъма за антиунификация с последващо приложение в теорията на типовете.

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

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

Снимка от Twitter ZuriHac

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

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

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

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

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

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

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

Pandoc

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

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

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

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

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

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

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

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

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

data Pandoc = Pandoc Meta [Block]

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

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

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

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

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

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

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

whileParser :: Parser Stmt
whileParser = whiteSpace >> statement

Първо трябва да преброите интервала, а след това оператора - който също има тип Parser Stmt.

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

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

Означава, че или трябва да се опитате да прочетете твърдението в скоби, или да опитате да прочетете няколко твърдения последователно.

Приложните функтори се използват предимно като преки пътища за монади. Например, оставете функцията 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 вече хванахме един неприятен бъг в компилатора на GHC Haskell - бидейки убит в неподходящия момент, той генерира неправилни обектни файлове и не ги компилира повторно при рестартиране. Скриптирането чрез системни извиквания направи възможно надеждното възпроизвеждане на грешката в едно изпълнение, докато произволните убийства възпроизвеждат грешката за около два часа.

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

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