ZuriHac: Wir üben funktionale Programmierung.

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

Über uns

Эту статью подготовили двое студентов 3-го курса программы «Прикладная математика и информатика» НИУ ВШЭ — Санкт-Петербург: Василий Алфёров и Елизавета Василенко. Увлечение функциональным программированием для нас обоих началось с цикла лекций Д. Н. Москвина на 2-м курсе университета. В настоящий момент Василий участвует в программе Google Summer of Code, в рамках которой занимается реализацией алгебраических графов на языке Хаскелль под руководством команды проекта Alga. Elisabeth hat die erlernten Fähigkeiten im funktionalen Programmieren in ihrer Abschlussarbeit angewendet, die sich mit der Implementierung eines Anti-Unifikationsalgorithmus und dessen Anwendung in der Typentheorie befasst.

Veranstaltungsformat

Die Zielgruppe besteht aus Projektleitern von Open-Source-Projekten, Programmierern, die an deren Entwicklung teilnehmen möchten, Forschern im Bereich funktionales Programmieren und einfach Haskell-begeisterten Personen. In diesem Jahr versammelten sich im Veranstaltungsort – der HSR Hochschule für Technik Rapperswil – Entwickler aus mehr als fünfzig Open-Source-Projekten in Haskell aus der ganzen Welt, um über ihre Produkte zu berichten und neue Interessenten für deren Weiterentwicklung zu gewinnen.

Foto von Twitter ZuriHac

Das Schema ist ganz einfach: Man muss im Voraus ein paar Sätze über sein Projekt schreiben und diese an die Organisatoren senden, die die Informationen über Ihr Projekt auf der Event-Seite veröffentlichen. Außerdem haben die Projektverantwortlichen am ersten Tag jeweils dreißig Sekunden Zeit, um von der Bühne aus ganz kurz zu erklären, woran sie arbeiten und was getan werden muss. Danach suchen interessierte Personen die Autoren auf und fragen ausführlich nach den Aufgaben.

Wir haben derzeit keine eigenen offenen Projekte, möchten aber sehr gerne zu bestehenden beitragen, daher haben wir uns als normale Teilnehmer registriert. Während der drei Tage haben wir mit zwei Entwicklergruppen gearbeitet. Es hat sich herausgestellt, dass das gemeinsame Lernen von Code und persönliche Interaktion die Zusammenarbeit zwischen Projektverantwortlichen und Mitwirkenden sehr produktiv macht – bei ZuriHac konnten wir uns in für uns neue Bereiche einarbeiten und zwei ganz unterschiedlichen Teams helfen, indem wir in jedem der Projekte eine Aufgabe erledigt haben.

Neben wertvollen praktischen Erfahrungen wurden auf der ZuriHac auch mehrere Vorträge und Workshops gehalten. Besonders im Gedächtnis geblieben sind uns zwei Vorträge. Im ersten sprach Andrey Mokhov von der Universität Newcastle über selektive anwendbare Funktoren – eine Typpalette, die als Bindeglied zwischen anwendbaren Funktoren und Monaden fungieren soll. In dem anderen Vortrag erzählte einer der Begründer von Haskell, Simon Peyton Jones, wie der Typausdruck im GHC-Compiler funktioniert.

Vortrag von Simon Peyton Jones. Foto von Twitter ZuriHac

Die während des Hackathons durchgeführten Workshops wurden in drei Kategorien unterteilt, je nach Erfahrungsgrad der Teilnehmer. Die Aufgaben, die den Teilnehmern, die an der Entwicklung von Projekten beteiligt sind, angeboten wurden, hatten ebenfalls Schwierigkeitsstufen. Die kleine, aber einladende Gemeinschaft der funktionalen Programmierer heißt Neulinge mit Freude willkommen. Um die Vorträge von Andrey Mokhov und Simon Peyton Jones zu verstehen, war jedoch der im Studium absolvierte Kurs über funktionale Programmierung sehr hilfreich.

Sowohl für reguläre Teilnehmer als auch für Projektverfasser ist die Registrierung für die Veranstaltung kostenlos. Wir haben Anfang Juni Anträge auf Teilnahme eingereicht und wurden danach relativ schnell von der Warteliste in die Liste der bestätigten Teilnehmer überführt.

Nun möchten wir Ihnen die Projekte vorstellen, an deren Entwicklung wir beteiligt waren.

Pandoc

Pandoc — ist ein universeller Umwandler für Textdokumente, praktisch von jedem Format in jedes andere. Zum Beispiel von docx in pdf oder von Markdown in MediaWiki. Sein Autor, John MacFarlane, ist Professor für Philosophie an der University of California in Berkeley. Pandoc ist allgemein recht bekannt, und einige unserer Bekannten waren überrascht zu erfahren, dass Pandoc in Haskell geschrieben ist.

Hier ist eine Liste der von Pandoc unterstützten Dokumentenformate. Auf der Website gibt es auch ein vollständiges Diagramm, aber dieses Bild passt nicht in den Artikel.

Natürlich bietet Pandoc keine direkte Konvertierung für jedes Format-Paar an. Für die Unterstützung eines so umfangreichen Spektrums von Konvertierungen wird ein standardmäßiges architektonisches Verfahren verwendet: Zuerst wird das gesamte Dokument in eine spezielle interne Zwischenrepresentation übersetzt, und anschließend wird auf Basis dieser internen Darstellung ein Dokument im gewünschten Format generiert. Diese interne Darstellung nennen die Entwickler „AST“, was für Abstract Syntax Tree steht, oder abstrakter Syntaxbaum. Um sich die Zwischenrepräsentation anzusehen, ist es ganz einfach: Man muss lediglich das Ausgabeformat auf „native“ setzen.

$ cat example.html
<h1>Hallo, Welt!</h1>

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

Leser, die auch nur ein wenig mit Haskell gearbeitet haben, können aus diesem kleinen Beispiel schließen, dass Pandoc tatsächlich in Haskell geschrieben ist: Die Ausgabe dieses Befehls ist eine Darstellung der internen Strukturen von Pandoc in Form eines Strings, ähnlich dem, wie es in Haskell normalerweise in der Standardbibliothek gemacht wird.

Hier kann man sehen, dass die interne Darstellung eine rekursive Struktur darstellt, bei der jeder innere Knoten eine Liste enthält. Beispielsweise liegt auf der obersten Ebene eine Liste mit einem Element – einem ersten Header mit den Attributen “hello-world”,[],[]. Innerhalb dieses Headers verbirgt sich eine Liste, die aus der Zeichenkette “Hello,”, einem Leerzeichen und der Zeichenkette “World!” besteht.

Die interne Darstellung unterscheidet sich nicht stark von HTML. Sie stellt einen Baum dar, in dem jeder innere Knoten Informationen über das Formatieren seiner Nachfolger bereitstellt, während die Blätter tatsächlich den Inhalt des Dokuments enthalten.

Wenn man auf die Stufe einer konkreten Implementierung heruntergeht, wird der Datentyp für das gesamte Dokument so definiert:

data Pandoc = Pandoc Meta [Block]

Hier ist Block genau das, was die vorher erwähnten inneren Knoten sind, während Meta die Metainformationen über das Dokument enthält, wie Titel, Erstellungsdatum, Autoren – je nach Format ist dies unterschiedlich, und Pandoc versucht, solche Informationen beim Konvertieren von Format zu Format so gut wie möglich zu erhalten.

Fast alle Block-Typen, wie Header oder Para (Absatz), akzeptieren Attribute und eine Liste von tiefer eingestuften Knoten als Argumente – in der Regel Inline. Zum Beispiel sind Space oder Str Konstruktoren vom Typ Inline, und auch das HTML-Tag wird in einen speziellen Inline-Konstruktor umgewandelt. Wir halten es nicht für sinnvoll, eine vollständige Definition dieser Typen zu geben, aber man kann sie hier einsehen. hier.

Interessanterweise ist der Typ Pandoc ein Monoid. Das bedeutet, dass es ein leeres Dokument gibt und dass Dokumente miteinander kombiniert werden können. Dies ist besonders nützlich beim Schreiben von Readern – man kann ein Dokument nach einer beliebigen Logik in Teile aufteilen, jede einzeln parsen und schließlich alles wieder zu einem einzigen Dokument zusammenfügen. Dabei wird die Metainformation sofort aus allen Teilen des Dokuments gesammelt.

Bei der Konvertierung, beispielsweise von LaTeX nach HTML, wandelt zunächst ein spezielles Modul namens LaTeXReader das Eingabedokument in einen AST um. Anschließend konvertiert ein weiteres Modul, der HTMLWriter, den AST in HTML. Dank dieser Architektur ist es nicht notwendig, eine quadratische Anzahl an Konvertierungen zu schreiben — es genügt, für jedes neue Format einen Reader und einen Writer zu entwickeln, und alle möglichen Konvertierungspaare werden automatisch unterstützt.

Es ist offensichtlich, dass eine solche Architektur auch ihre Nachteile hat, die bereits von Fachleuten im Bereich der Softwarearchitektur vorhergesagt wurden. Der bedeutendste Nachteil ist die Kosten für Änderungen am Syntaxbaum. Wenn die Änderung erheblich ist, muss der Code in allen Readern und Writern angepasst werden. Zum Beispiel steht eine der Herausforderungen für die Entwickler von Pandoc darin, komplexe Tabellenformate zu unterstützen. Derzeit kann Pandoc nur einfache Tabellen mit einer Überschrift, Spalten und Werten in jeder Zelle verarbeiten. Zum Beispiel wird das Attribut colspan in HTML einfach ignoriert. Einer der Gründe für dieses Verhalten ist das Fehlen eines einheitlichen Schemas zur Darstellung von Tabellen in allen oder zumindest vielen Formaten – entsprechend ist unklar, in welcher Form Tabellen in der internen Darstellung gespeichert werden müssen. Aber auch nach der Wahl einer spezifischen Darstellung müssen alle Reader und Writer, die die Arbeit mit Tabellen unterstützen, vollständig geändert werden.

Die Programmiersprache Haskell wurde nicht nur aus großer Liebe der Autoren zur funktionalen Programmierung gewählt. Haskell ist bekannt für seine umfangreichen Möglichkeiten zur Textverarbeitung. Ein Beispiel dafür ist die Bibliothek parsec — eine Bibliothek, die aktiv Konzepte der funktionalen Programmierung — Monoid, Monad, Applikative und alternative Funktoren — zur Erstellung beliebiger Parser nutzt. Die gesamte Leistungsfähigkeit von Parsec wird deutlich in dem Beispiel mit HaskellWiki, wo ein vollständiger Parser einer einfachen imperativen Programmiersprache behandelt wird. Natürlich wird Parsec auch aktiv in Pandoc verwendet.

Kurz gesagt, Monaden werden für sequenzielles Parsen verwendet, wobei zuerst das eine und dann das andere kommt. Zum Beispiel in folgendem Beispiel:

whileParser :: Parser Stmt
whileParser = whiteSpace >> statement

Zuerst muss der Leerraum gelesen werden, gefolgt von der Anweisung — die ebenfalls den Typ Parser Stmt hat.

Alternative Funktoren werden verwendet, um im Falle eines Parsingfehlers zurückzurollen. Zum Beispiel,

statement :: Parser Stmt
statement = parens statement  sequenceOfStmt

Bedeutet, dass entweder versucht werden muss, die Anweisung in Klammern zu lesen, oder es nacheinander mehrere Anweisungen gelesen werden.

Аппликативные функторы используются в основном как короткие пути для монад. Например, пусть функция tok читает какой-то токен (это реальная функция из LaTeXReader). Посмотрим на такую комбинацию

const <$> tok <*> tok

Она прочитает два токена подряд и вернёт из них первый.

Для всех этих классов в Хаскелле существуют красивые символьные операторы, что делает программирование Reader’ов похожим на ASCII-арт. Только полюбуйтесь на этот замечательный код.

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

Hatrace

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

Hatrace – eine Bibliothek, die eine Schnittstelle für ptrace in Haskell bereitstellt. Das Besondere ist, dass ptrace sehr komplex ist und die direkte Nutzung ziemlich schwierig, insbesondere aus funktionalen Sprachen, erfolgt.

Hatrace funktioniert beim Start wie strace und akzeptiert ähnliche Argumente. Der Unterschied zu strace besteht darin, dass es auch eine Bibliothek ist, die eine einfachere Schnittstelle als nur ptrace bietet.

Mit Hatrace wurde bereits ein unangenehmer Fehler im Haskell-Compiler GHC gefunden – wenn er zu einem ungünstigen Zeitpunkt gestoppt wird, generiert er fehlerhafte Objektdateien und kompiliert diese beim Neustart nicht erneut. Das Skripting von Systemaufrufen hat es ermöglicht, den Fehler bei einem einzigen Lauf zuverlässig zu reproduzieren, wenn zufällige Stopps den Fehler etwa alle zwei Stunden reproduzierten.

Wir haben der Bibliothek Schnittstellen für Systemaufrufe hinzugefügt – Elizaveta fügte brk hinzu, während Vasiliy mmap implementierte. Dank unserer Arbeit können die Argumente dieser Systemaufrufe einfacher und präziser genutzt werden, wenn die Bibliothek verwendet wird.

Quelle: habr.com