В июне этого года в небольшом швейцарском городке Рапперсвиле уже в десятый раз прошло мероприятие под названием ZuriHac. В этот раз на нём собрались более пятисот любителей Хаскелля, от новичков до отцов-основателей языка. Хотя организаторы называют это мероприятие хакатоном, всё же оно не является конференцией или хакатоном в классическом смысле. Его формат отличается от традиционных программистских. Мы узнали про ZuriHac по счастливой случайности, поучаствовали в нем, а теперь считаем своим долгом рассказать о необычной находке!
Эту статью подготовили двое студентов 3-го курса программы «Прикладная математика и информатика» НИУ ВШЭ — Санкт-Петербург: Василий Алфёров и Елизавета Василенко. Увлечение функциональным программированием для нас обоих началось с цикла лекций Д. Н. Москвина на 2-м курсе университета. В настоящий момент Василий участвует в программе Google Summer of Code, в рамках которой занимается реализацией алгебраических графов на языке Хаскелль под руководством команды проекта Alga. Елизавета применила полученные навыки функционального программирования в курсовой работе, посвящённой реализации алгоритма анти-унификации с последующим применением в теории типов.
Целевой аудиторией являются владельцы проектов с открытым исходным кодом, программисты, желающие поучаствовать в их развитии, исследователи функционального программирования и просто увлечённые Хаскеллем люди. В этом году в месте проведения – университете HSR Hochschule für Technik Rapperswil – собрались разработчики из более чем пятидесяти открытых проектов на языке Haskell со всего мира, чтобы рассказать о своих продуктах и заинтересовать в их развитии свежих людей.
Фото из Twitter ZuriHac
Схема очень простая: нужно заранее написать несколько предложений о своём проекте и отправить их организаторам, которые выложат информацию о вашем проекте на страничке мероприятия. Кроме того, в первый день у авторов проектов есть по тридцать секунд на то, чтобы очень кратко рассказать со сцены, чем они занимаются и что нужно сделать. Потом заинтересовавшиеся люди разыскивают авторов и подробно расспрашивают про задачи.
У нас пока собственных открытых проектов нет, но мы очень хотим внести свой вклад в уже существующие, так что мы зарегистрировались как обычные участники. В течение трёх дней мы работали с двумя группами разработчиков. Оказывается, совместное изучение кода и живое общение делает взаимодействие авторов проекта и контрибьюторов очень продуктивным – на ZuriHac мы смогли разобраться в новых для нас областях и смогли помочь двум совершенно разным командам, закрыв по задаче в каждом из проектов.
Помимо ценной практики, на ZuriHac также было прочитано несколько лекций и мастер-классов. Нам особенно запомнились две лекции. На первой из них Андрей Мохов из университета Ньюкасла рассказал о селективных аппликативных функторах — классе типов, который должен стать промежуточным между аппликативными функторами и монадами. На другой лекции один из основателей Хаскелля, Саймон Пейтон Джонс, рассказывал о том, как устроен вывод типов в компиляторе GHC.
Лекция Саймона Пейтона Джонса. Фото из Twitter ZuriHac
Мастер-классы, проводившиеся во время хакатона, были разделены на три категории в зависимости от уровня подготовки участников. Задачи, предлагавшиеся участникам, присоединившимся к разработке проектов, также имели пометки с уровнем сложности. Немногочисленное, но дружное сообщество функциональных программистов с радостью принимает в свои ряды новичков. Для понимания лекций Андрея Мохова и Саймона Пейтона Джонса, однако, нам очень пригодился пройденный в университете курс функционального программирования.
Как для обычных участников, так и для авторов проектов регистрация на мероприятие бесплатна. Мы подали заявки на участие в первых числах июня, после чего довольно быстро были переведены из списка ожидания в список подтверждённых участников.
А сейчас мы расскажем о проектах, в разработке которых мы принимали участие.
Pandoc — это универсальный преобразователь текстовых документов, фактически — из любого формата в любой. Например, из docx в pdf, или из Markdown в MediaWiki. Его автор Джон МакФарлейн — профессор философии в Калифорнийском университете в Беркли. Вообще, Pandoc довольно известен, и некоторые наши знакомые были удивлены, когда узнали, что Pandoc написан на Хаскелле.
Список форматов документов, поддерживаемых Pandoc. На сайте есть также целый граф, но эта картинка в статью не помещается.
Конечно же, в Pandoc не реализована прямая конвертация для каждой пары форматов. Для поддержки столь обширного множества преобразований используется стандартное архитектурное решение: сначала весь документ переводится в специальное внутреннее промежуточное представление, а потом по этому внутреннему представлению генерируется документ в другом формате. Внутреннее представление разработчики называют «AST», что расшифровывается как Abstract Syntax Tree, или абстрактное синтаксическое дерево. Посмотреть на промежуточное представление можно очень просто: для этого нужно лишь задать в качестве выходного формата «native»
Читатели, которые хотя бы немного работали с Хаскеллем, уже могут по этому небольшому примеру предположить, что Pandoc написан именно на Хаскелле: вывод этой команды — это представление внутренних структур Pandoc в виде строки, созданное по подобию того, как это обычно делается в Хаскелле, например, в стандартной библиотеке.
Итак, здесь можно увидеть, что внутреннее представление — это рекурсивная структура, в каждом внутреннем узле которой находится список. Например, на самом верхнем уровне находится список из одного элемента — заголовка первого уровня с аттрибутами “hello-world”,[],[]. Внутри этого заголовка спрятан список из строки “Hello,”, пробела и строки “World!”.
Как видно, внутреннее представление не сильно отличается от HTML. Оно представляет из себя дерево, где каждый внутренний узел сообщает какую-то информацию о форматировании своих потомков, а в листьях находится собственно содержимое документа.
Если опуститься на уровень конкретной реализации, тип данных для всего документа определён вот так:
Здесь 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.
Если описывать кратко, то монады используются для последовательного парсинга, когда сначала идёт одно, а потом другое. Например, в таком примере:
Сначала нужно считать пробел, а потом statement — который тоже имеет тип Parser Stmt.
Альтернативные функторы используются для отката в случае, если парсить не получилось. Например,
Означает, что нужно либо попробовать прочитать statement в скобках, либо последовательно попробовать прочитать несколько statement’ов.
Аппликативные функторы используются в основном как короткие пути для монад. Например, пусть функция tok читает какой-то токен (это реальная функция из LaTeXReader). Посмотрим на такую комбинацию
Она прочитает два токена подряд и вернёт из них первый.
Для всех этих классов в Хаскелле существуют красивые символьные операторы, что делает программирование Reader’ов похожим на ASCII-арт. Только полюбуйтесь на этот замечательный код.
Наши задачи были связаны с LaTeXReader’ом. Задача Василия была в поддержке команд \mbox и \hbox, полезных при написании пакетов в LaTeX. В ответственности Елизаветы была поддержка команды \epigraph, позволяющей оформлять эпиграфы в LaTeX документах.
В UNIX-подобных операционных системах часто реализован системный вызов ptrace. Он полезен при отладке и симуляции окружений программ, позволяя отслеживать системные вызовы, которые делает программа. Например, весьма полезная утилита strace использует внутри себя именно ptrace.
Hatrace — это библиотека, предоставляющая интерфейс для ptrace в Хаскелль. Дело в том, что сам ptrace сильно наворочен и использовать его напрямую довольно сложно, особенно из функциональных языков.
Hatrace при запуске работает как strace и принимает похожие аргументы. Его отличие от strace в том, что он также является библиотекой, предоставляющей более простой интерфейс, чем просто ptrace.
С помощью hatrace уже отловили один неприятный баг в компиляторе Хаскелля GHC — будучи убитым в неподходящий момент, он генерирует некорректные объектные файлы и не перекомпилирует их при перезапуске. Скриптование по системным вызовам позволило гарантированно воспроизводить ошибку за один запуск, когда случайные убивания воспроизводили ошибку примерно за два часа.
Мы добавляли в библиотеку интерфейсы системных вызовов — Елизавета добавляла brk, а Василий добавлял mmap. По результатам нашей работы можно более просто и точно использовать аргументы этих системных вызовов при использовании библиотеки.
О нас
Эту статью подготовили двое студентов 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. По результатам нашей работы можно более просто и точно использовать аргументы этих системных вызовов при использовании библиотеки.
