ZuriHac: Wir üben funktionale Programmierung

Im Juni dieses Jahres fand zum zehnten Mal eine Veranstaltung in der kleinen Schweizer Stadt Rapperswil statt, die ZuriHac. Diesmal versammelten sich mehr als fünfhundert Haskell-Enthusiasten, von Neulingen bis hin zu den Gründervätern der Sprache. Obwohl die Organisatoren diese Veranstaltung als Hackathon bezeichnen, ist sie dennoch keine Konferenz oder ein Hackathon im klassischen Sinne. Ihr Format unterscheidet sich von traditionellen Programmierer-Veranstaltungen. Wir haben von ZuriHac durch einen glücklichen Zufall erfahren, haben daran teilgenommen und sehen es jetzt als unsere Pflicht an, von dieser ungewöhnlichen Entdeckung zu berichten!

Alconost ist professionell tätig

Dieser Artikel wurde von zwei Studenten des 3. Jahres des Programms „Angewandte Mathematik und Informatik“ der National Research University Higher School of Economics — St. Petersburg: Wasilij Alfjorow und Elizaveta Vasilenko, vorbereitet. Unser Interesse an funktionaler Programmierung begann für uns beide mit einer Vorlesungsreihe von D. N. Moskin in unserem zweiten Jahr an der Universität. Derzeit nimmt Wasilij am Google Summer of Code teil, im Rahmen dessen er algebräische Graphen in Haskell unter der Anleitung des Alga-Projektteams implementiert. Alga. Elizaveta hat die erworbenen Fähigkeiten in funktionaler Programmierung in ihrer Abschlussarbeit angewendet, die sich mit der Implementierung eines Anti-Unifikationsalgorithmus beschäftigt, der anschließend in der Typentheorie verwendet wird.

Format der Veranstaltung

Die Zielgruppe besteht aus Projektinhabern mit Open-Source-Software, Programmierern, die an deren Entwicklung teilnehmen möchten, Forschern der funktionalen Programmierung und einfach Haskell-begeisterten Menschen. In diesem Jahr versammelten sich am Veranstaltungsort – der HSR Hochschule für Technik Rapperswil – Entwickler aus über fünfzig Open-Source-Projekten in Haskell aus der ganzen Welt, um über ihre Produkte zu berichten und neue Interessierte für deren Entwicklung zu gewinnen.

Fotos von Twitter ZuriHac

Das Konzept ist ganz einfach: Man muss im Voraus einige Sätze über sein Projekt schreiben und sie den Organisatoren schicken, die die Informationen über euer Projekt auf der Veranstaltungswebseite veröffentlichen. Außerdem haben die Projektautoren am ersten Tag dreißig Sekunden Zeit, um sehr kurz von der Bühne aus zu erzählen, woran sie arbeiten und was zu tun ist. Danach suchen interessierte Personen die Autoren auf und fragen detailliert nach den Aufgaben.

Wir haben derzeit keine eigenen offenen Projekte, aber wir möchten unbedingt zu bestehenden Projekten beitragen, deshalb haben wir uns als ordentliche Teilnehmer registriert. In den drei Tagen haben wir mit zwei Entwicklergruppen gearbeitet. Es stellte sich heraus, dass gemeinsames Lernen des Codes und der persönliche Austausch die Interaktion von Projektautoren und Mitwirkenden sehr produktiv macht – auf ZuriHac konnten wir uns in für uns neuen Bereichen zurechtfinden und zwei ganz unterschiedlichen Teams helfen, indem wir jeweils eine Aufgabe in jedem der Projekte abgeschlossen haben.

Neben wertvoller Praxis wurden auf der ZuriHac auch mehrere Vorträge und Workshops gehalten. Besonders in Erinnerung geblieben sind uns zwei Vorträge. In der ersten hielt Andrey Mokhov von der Universität Newcastle einen Vortrag über selektive anwendbare Funktoren – eine Typenklasse, die als Zwischenstufe zwischen anwendbaren Funktoren und Monden fungieren soll. In einem anderen Vortrag sprach einer der Gründer von Haskell, Simon Peyton Jones, darüber, wie die Typableitung 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 eingeteilt, je nach dem Erfahrungsgrad der Teilnehmer. Die Aufgaben, die den an der Entwicklung der Projekte teilnehmenden Teilnehmern angeboten wurden, hatten ebenfalls Kennzeichnungen mit Schwierigkeitsgraden. Die kleine, aber freundliche Gemeinschaft der funktionalen Programmierer freut sich über jeden Neuling in ihren Reihen. Für das Verständnis der Vorträge von Andrey Mokhov und Simon Peyton Jones war jedoch der im Studium absolvierte Kurs über funktionale Programmierung sehr hilfreich.

Die Registrierung für die Veranstaltung ist sowohl für ordentliche Teilnehmer als auch für Projektautoren kostenlos. Wir haben unsere Anträge Anfang Juni eingereicht und wurden ziemlich schnell von der Warteliste auf die Liste der bestätigten Teilnehmer übertragen.

Jetzt werden wir über die Projekte erzählen, an deren Entwicklung wir beteiligt waren.

Pandoc

Pandoc – das ist ein universeller Konverter für Textdokumente, praktisch von jedem Format in ein anderes. Zum Beispiel von docx nach pdf oder von Markdown nach MediaWiki. Der Autor, John MacFarlane, ist Professor für Philosophie an der Universität Kalifornien in Berkeley. Insgesamt ist Pandoc ziemlich bekannt, und einige unserer Bekannten waren überrascht, als sie erfuhren, dass Pandoc in Haskell geschrieben wurde.

Eine Liste der von Pandoc unterstützten Dokumentenformate. Auf der Website gibt es auch ein ganzes Diagramm, aber dieses Bild passt nicht in den Artikel.

Natürlich ist in Pandoc keine direkte Umwandlung für jedes Paar von Formaten implementiert. Um eine so umfassende Vielzahl von Konvertierungen zu unterstützen, wird eine standardmäßige architektonische Lösung verwendet: Zuerst wird das gesamte Dokument in eine spezielle interne Zwischendarstellung übersetzt, und dann wird aus dieser internen Darstellung ein Dokument in einem anderen Format erzeugt. Die interne Darstellung nennen die Entwickler „AST“, was für Abstract Syntax Tree steht, oder abstrakter Syntaxbaum. Die Zwischendarstellung kann sehr einfach betrachtet werden: Man muss lediglich als Ausgabeformat „native“ angeben.

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

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

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

Hier kann also gesehen werden, dass die interne Darstellung eine rekursive Struktur ist, in der sich in jedem inneren Knoten eine Liste befindet. Zum Beispiel befindet sich auf der obersten Ebene eine Liste mit einem Element – einer Überschrift der ersten Ebene mit den Attributen „hello-world“, [], []. Innerhalb dieser Überschrift verbirgt sich eine Liste aus der Zeichenkette „Hello,“ einem Leerzeichen und der Zeichenkette „World!“.

Wie zu sehen ist, weicht die interne Darstellung nicht stark von HTML ab. Sie stellt einen Baum dar, in dem jeder innere Knoten Informationen über die Formatierung seiner Nachkommen bereitstellt, während in den Blättern der Inhalt des Dokuments selbst zu finden ist.

Wenn man zur konkreten Implementierung herabsteigt, ist der Datentyp für das gesamte Dokument folgendermaßen definiert:

data Pandoc = Pandoc Meta [Block]

Hierbei sind Block die inneren Knoten, von denen oben die Rede ist, und Meta ist die Metainformation über das Dokument, wie z.B. Titel, Erstellungsdatum, Autoren – dies variiert je nach Format, und Pandoc versucht, solche Informationen bei der Konvertierung von Format zu Format so weit wie möglich zu erhalten.

Fast alle Konstruktortypen von Block — wie zum Beispiel Header oder Para (Absatz) — akzeptieren Attribute und eine Liste von niedrigeren Ebenen als Argumente — meist Inline. Zum Beispiel sind Space oder Str Konstruktoren vom Typ Inline, und auch das HTML-Tag wird in ein spezielles Inline umgewandelt. Es macht wenig Sinn, die vollständige Definition dieser Typen anzugeben, jedoch kann man sie hier einsehen. hier.

Interessanterweise ist der Typ Pandoc ein Monoid. Das bedeutet, dass es ein gewisses leeres Dokument gibt und dass Dokumente miteinander addiert werden können. Dies ist bei der Erstellung von Readern praktisch — man kann ein Dokument beliebig in Teile zerlegen, jeden Teil einzeln parsen und dann alles zu einem einzigen Dokument wieder zusammenfügen. Dabei wird die Metainformation aus allen Teilen des Dokuments gesammelt.

Bei der Konvertierung, sagen wir, von LaTeX nach HTML, verwandelt zunächst ein spezielles Modul namens LaTeXReader das Eingabedokument in einen AST, danach wandelt ein anderes Modul namens HTMLWriter den AST in HTML um. Dank dieser Architektur muss man nicht für jedes neue Format eine quadratische Anzahl von Konvertierungen schreiben — es reicht aus, für jedes neue Format einen Reader und einen Writer zu erstellen, und alle möglichen Konvertierungspaare werden automatisch unterstützt.

Es ist klar, dass eine solche Architektur auch ihre Nachteile hat, die von Fachleuten im Bereich Softwarearchitektur schon lange vorhergesagt wurden. Der wesentlichste Nachteil ist die Kosten für Änderungen am abstrakten Syntaxbaum. Wenn die Änderung erheblich ist, muss der Code in allen Readern und Writern geändert werden. Zum Beispiel ist eine der Herausforderungen, vor denen die Entwickler von Pandoc stehen, die Unterstützung komplexer Tabellenformate. Derzeit kann Pandoc nur die einfachsten Tabellen verarbeiten, mit Überschrift, Spalten und Werten in jeder Zelle. Zum Beispiel wird das Attribut colspan in HTML einfach ignoriert. Ein Grund für dieses Verhalten ist das Fehlen eines einheitlichen Schemas zur Darstellung von Tabellen in allen oder zumindest vielen Formaten — daher ist unklar, in welcher Form Tabellen in der internen Darstellung gespeichert werden müssen. Aber selbst nach der Auswahl einer bestimmten Darstellung müssen alle Reader und Writer, die mit Tabellen arbeiten, vollständig geändert werden.

Die Sprache 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, Monaden, applikative und alternative Funktoren — zur Erstellung beliebiger Parser verwendet. Die gesamte Leistungsfähigkeit von Parsec kann man in dem Beispiel HaskellWiki sehen, wo ein vollständiger Parser für eine einfache imperative Programmiersprache behandelt wird. Natürlich wird Parsec auch in Pandoc aktiv genutzt.

Kurz gesagt werden Monaden für das sequenzielle Parsen verwendet, wenn 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, und dann das Statement — das ebenfalls den Typ Parser Stmt hat.

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

statement :: Parser Stmt
statement = parens statement  sequenceOfStmt

Das bedeutet, dass entweder versucht werden muss, das Statement in Klammern zu lesen, oder nacheinander mehrere Statements gelesen werden müssen.

Applikative Funktoren werden hauptsächlich als Abkürzung für Monaden verwendet. Nehmen wir an, die Funktion tok liest ein Token (dies ist eine echte Funktion aus LaTeXReader). Lassen Sie uns so eine Kombination betrachten:

const  tok  tok

Sie wird zwei Tokens nacheinander lesen und das erste zurückgeben.

Für all diese Klassen gibt es in Haskell schöne symbolische Operatoren, was das Programmieren von Readern ASCII-Art-ähnlich macht. Bewundern Sie einfach diesen wunderbaren Code.

Unsere Aufgaben waren mit dem LaTeXReader verbunden. Die Aufgabe von Basil war die Unterstützung der Befehle mbox und hbox, die beim Schreiben von Paketen in LaTeX nützlich sind. Bei Elizabeth lag die Verantwortung in der Unterstützung des Befehls epigraph, der das Einfügen von Epigraphen in LaTeX-Dokumenten ermöglicht.

Hatrace

In UNIX-ähnlichen Betriebssystemen ist oft der Systemaufruf ptrace implementiert. Er ist nützlich beim Debuggen und Simulieren von Programmumgebungen und ermöglicht das Nachverfolgen von Systemaufrufen, die ein Programm tätigt. Zum Beispiel verwendet das sehr nützliche Tool strace intern genau ptrace.

Hatrace ist eine Bibliothek, die eine Schnittstelle für ptrace in Haskell bereitstellt. Das Besondere an ptrace ist, dass es sehr komplex ist und die direkte Verwendung ziemlich schwierig sein kann, insbesondere aus funktionalen Sprachen.

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 beendet wird, generiert er inkorrekte Objektdateien und kompiliert diese beim Neustart nicht neu. Das Skripting über Systemaufrufe ermöglichte es, den Fehler bei einem einzigen Run zuverlässig zu reproduzieren, während zufällige Beendigungen den Fehler in etwa zwei Stunden hervorriefen.

Wir haben der Bibliothek Schnittstellen für Systemaufrufe hinzugefügt – Elizaveta fügte brk hinzu, während Vasilij mmap hinzufügte. Durch unsere Arbeit können die Argumente dieser Systemaufrufe bei Verwendung der Bibliothek einfacher und genauer behandelt werden.

Quelle: habr.com