ZuriHac: практикуємося у функціональному програмуванні

У червні цього року в невеликому швейцарському містечку Рапперсвілі вже вдесяте пройшов захід під назвою ZuriHac. Цього разу на ньому зібралося понад п'ятсот любителів Хаскелля, від новачків до батьків-засновників мови. Хоча організатори називають цей захід хакатоном, все ж таки він не є конференцією чи хакатоном у класичному сенсі. Його формат відрізняється від традиційних програмістських. Ми дізналися про ZuriHac завдяки щасливому випадку, взяли участь у ньому, а тепер вважаємо своїм обов'язком розповісти про незвичайну знахідку!

Про нас

Цю статтю підготували двоє студентів 3-го курсу програми «Прикладна математика та інформатика» НДУ ВШЕ – Санкт-Петербург: Василь Алферов та Єлизавета Василенко. Захоплення функціональним програмуванням обох почалося з циклу лекцій Д. Н. Москвина на 2-му курсі університету. Зараз Василь бере участь у програмі Google Summer of Code, в рамках якої займається реалізацією графів алгебри мовою Хаскелль під керівництвом команди проекту Водорость. Єлизавета застосувала отримані навички функціонального програмування в курсовій роботі, присвяченій реалізації алгоритму антиуніфікації з подальшим застосуванням у теорії типів.

формат заходу

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

Фото з Twitter ZuriHac

Схема дуже проста: потрібно заздалегідь написати кілька пропозицій про свій проект та надіслати їх організаторам, які викладуть інформацію про ваш проект на сторінці заходу. Крім того, в перший день автори проектів мають по тридцять секунд на те, щоб дуже коротко розповісти зі сцени, чим вони займаються і що потрібно зробити. Потім зацікавлені люди шукають авторів і докладно розпитують про завдання.

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

Крім цінної практики, на ZuriHac також було прочитано кілька лекцій та майстер-класів. Нам особливо запам'яталися дві лекції. На першій з них Андрій Мохов з університету Ньюкасла розповів про селективні аплікативні функтори — клас типів, який має стати проміжним між аплікативними функторами та монадами. На іншій лекції один із засновників Хаскелля, Саймон Пейтон Джонс, розповідав про те, як влаштований висновок типів у компіляторі GHC.

Лекція Саймона Пейтона Джонса. Фото з Twitter ZuriHac

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

Як для звичайних учасників, так і для авторів проектів, реєстрація на захід безкоштовна. Ми подали заявки на участь у перших числах червня, після чого досить швидко були переведені зі списку очікування до списку підтверджених учасників.

А зараз ми розповімо про проекти, у розробці яких брали участь.

Пандок

Пандок — це універсальний перетворювач текстових документів, фактично з будь-якого формату в будь-який. Наприклад, з 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 "Hello,",Space,Str "World!"]]

Читачі, які хоча б трохи працювали з Хаскеллем, вже можуть за цим невеликим прикладом припустити, що Pandoc написаний саме на Хаскеллі: висновок цієї команди - це подання внутрішніх структур Pandoc у вигляді рядка, створене на кшталт того, як це зазвичай робиться в Хаскеллі, наприклад, у стандартній бібліотеці.

Отже, тут можна побачити, що внутрішнє уявлення — це рекурсивна структура, у кожному внутрішньому вузлі якої є список. Наприклад, на верхньому рівні знаходиться список з одного елемента - заголовка першого рівня з аттрибутами "hello-world", [], []. Усередині цього заголовка захований список з рядка “Hello,”, пробілу та рядка “World!”.

Як видно, внутрішнє уявлення не дуже відрізняється від HTML. Воно є деревом, де кожен внутрішній вузол повідомляє якусь інформацію про форматування своїх нащадків, а в листі знаходиться власне вміст документа.

Якщо опуститися на рівень конкретної реалізації, тип даних для всього документа визначено так:

data Pandoc = Pandoc Meta [Block]

Тут Block – це саме внутрішні вершини, про які йдеться вище, а Meta – це метаінформація про документ, на кшталт заголовка, дати створення, авторів – для різних форматів це різне, і Pandoc намагається по можливості зберігати таку інформацію під час перекладу з формату у формат.

Майже всі конструктори типу Block - наприклад, Header або Para (параграф) - приймають як аргументи атрибути і список вершин нижчого рівня - Inline, як правило. Наприклад, Space або Str - це конструктори типу Inline, також у свій спеціальний Inline перетворюється HTML-тег. Ми не бачимо сенсу наводити повне визначення цих типів, проте зауважимо, що його можна подивитися ось тут.

Цікаво, що тип Pandoc є моноідом. Це означає, що є якийсь порожній документ і що документи можна складати між собою. Цим зручно користуватися при написанні Reader'ів — можна розбивати документ на частини довільною логікою, ширяти кожну окремо, а потім зібрати все разом в один документ. При цьому метаінформація збереться з усіх частин документа одночасно.

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

Зрозуміло, що така архітектура має свої недоліки, давно передбачені фахівцями в галузі архітектури програмного забезпечення. Найсуттєвішим є вартість внесення змін до синтаксичного дерева. Якщо зміна досить серйозна, доведеться змінювати код у всіх Reader'ах та Writer'ах. Наприклад, одне з завдань, що стоять перед розробниками Pandoc - підтримка складних форматів таблиць. Зараз Pandoc вміє тільки в найпростіші таблиці, із заголовком, стовпцями та значенням у кожному осередку. Скажімо, аттрибут colspan у HTML просто ігноруватиметься. Однією з причин такої поведінки є відсутність єдиної схеми представлення таблиць у всіх або хоча б багатьох форматах - відповідно, неясно, в якому вигляді потрібно зберігати таблиці у внутрішньому поданні. Але і після вибору конкретного уявлення потрібно буде змінити всі Reader'и і Writer'и, що підтримують роботу з таблицями.

Мова Haskell була обрана не тільки від великого кохання авторів до функціонального програмування. Haskell відомий широкими можливостями обробки текстів. Одним із прикладів є бібліотека парсек — бібліотека, яка активно використовує концепти саме функціонального програмування — моноїди, монади, аплікативні та альтернативні функтори для написання довільних парсерів. Всю міць 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 у Хаскеллі. Справа в тому, що сам ptrace сильно наворочений і використовувати його досить складно, особливо з функціональних мов.

Hatrace під час запуску працює як strace і приймає схожі аргументи. Його відмінність від strace в тому, що він також є бібліотекою, що надає простіший інтерфейс, ніж просто ptrace.

За допомогою hatrace вже відловили один неприємний баг у компіляторі Хаскелля GHC - будучи вбитим у невідповідний момент, він генерує некоректні об'єктні файли і не перекомпілює їх при перезапуску. Скриптування за системними викликами дозволило гарантовано відтворювати помилку за один запуск, коли випадкові вбивання відтворювали помилку приблизно за дві години.

Ми додавали до бібліотеки інтерфейси системних викликів - Єлизавета додавала brk, а Василь додавав mmap. За результатами нашої роботи можна більш просто та точно використовувати аргументи цих системних викликів під час використання бібліотеки.

Джерело: habr.com