Хабрахабр

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

В июне этого года в небольшом швейцарском городке Рапперсвиле уже в десятый раз прошло мероприятие под названием ZuriHac. В этот раз на нём собрались более пятисот любителей Хаскелля, от новичков до отцов-основателей языка. Хотя организаторы называют это мероприятие хакатоном, всё же оно не является конференцией или хакатоном в классическом смысле. Его формат отличается от традиционных программистских. Мы узнали про ZuriHac по счастливой случайности, поучаствовали в нем, а теперь считаем своим долгом рассказать о необычной находке!

О нас

Эту статью подготовили двое студентов 3-го курса программы «Прикладная математика и информатика» НИУ ВШЭ — Санкт-Петербург: Василий Алфёров и Елизавета Василенко. Увлечение функциональным программированием для нас обоих началось с цикла лекций Д. Н. Москвина на 2-м курсе университета. В настоящий момент Василий участвует в программе 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 не реализована прямая конвертация для каждой пары форматов. Посмотреть на промежуточное представление можно очень просто: для этого нужно лишь задать в качестве выходного формата «native» Внутреннее представление разработчики называют «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!"]]

Читатели, которые хотя бы немного работали с Хаскеллем, уже могут по этому небольшому примеру предположить, что Pandoc написан именно на Хаскелле: вывод этой команды — это представление внутренних структур Pandoc в виде строки, созданное по подобию того, как это обычно делается в Хаскелле, например, в стандартной библиотеке.

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

Оно представляет из себя дерево, где каждый внутренний узел сообщает какую-то информацию о форматировании своих потомков, а в листьях находится собственно содержимое документа. Как видно, внутреннее представление не сильно отличается от HTML.

Если опуститься на уровень конкретной реализации, тип данных для всего документа определён вот так:

data Pandoc = Pandoc Meta [Block]

Здесь Block — это именно внутренние вершины, про которых говорится выше, а Meta — это метаинформация про документ, вроде заголовка, даты создания, авторов — для разных форматов это разное, и Pandoc старается по возможности сохранять такую информацию при переводе из формата в формат.

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

Это значит, что есть какой-то пустой документ, и что документы можно складывать между собой. Интересно, что тип Pandoc является моноидом. При этом метаинформация соберётся со всех частей документа сразу. Этим удобно пользоваться при написании Reader’ов — можно разбивать документ на части произвольной логикой, парсить каждую в отдельности, а потом собрать всё вместе в один документ.

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

Самым существенным является стоимость внесения изменений в синтаксическое дерево. Понятно, что такая архитектура имеет и свои недостатки, давно предсказанные специалистами в области архитектуры программного обеспечения. Например, одна из стоящих перед разработчиками Pandoc задач — поддержка сложных форматов таблиц. Если изменение достаточно серьёзное, придётся менять код во всех Reader’ах и Writer’ах. Скажем, аттрибут colspan в HTML будет просто игнорироваться. Сейчас Pandoc умеет только в самые простые таблицы, с заголовком, столбцами и значением в каждой ячейке. Но и после выбора конкретного представления нужно будет изменить абсолютно все Reader’ы и Writer’ы, поддерживающие работу с таблицами. Одной из причин такого поведения является отсутствие единой схемы представления таблиц во всех или хотя бы многих форматах — соответственно, неясно, в каком виде нужно хранить таблицы во внутреннем представлении.

Haskell известен широкими возможностями в обработке текстов. Язык Haskell был выбран не только от большой любви авторов к функциональному программированию. Всю мощь Parsec можно увидеть в примере с HaskellWiki, где разбирается полный парсер простого императивного языка программирования. Одним из примеров является библиотека parsec — библиотека, активно использующая концепты именно функционального программирования — моноиды, монады, аплликативные и альтернативные функторы — для написания произвольных парсеров. Разумеется, 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-арт.

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

Hatrace

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

Дело в том, что сам ptrace сильно наворочен и использовать его напрямую довольно сложно, особенно из функциональных языков. Hatrace — это библиотека, предоставляющая интерфейс для ptrace в Хаскелль.

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

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

По результатам нашей работы можно более просто и точно использовать аргументы этих системных вызовов при использовании библиотеки. Мы добавляли в библиотеку интерфейсы системных вызовов — Елизавета добавляла brk, а Василий добавлял mmap.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть