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 не реализована прямая конвертация для каждой пары форматов. Для поддержки столь обширного множества преобразований используется стандартное архитектурное решение: сначала весь документ переводится в специальное внутреннее промежуточное представление, а потом по этому внутреннему представлению генерируется документ в другом формате. Внутреннее представление разработчики называют «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 — библиотека, активно использующая концепты именно функционального программирования — моноиды, монады, аплликативные и альтернативные функторы — для написания произвольных парсеров. Всю мощь 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. По результатам нашей работы можно более просто и точно использовать аргументы этих системных вызовов при использовании библиотеки.
    Питерская Вышка
    Компания

    Комментарии 0

    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

    Самое читаемое