ZuriHac: Funktionale Programmierung üben

Im Juni dieses Jahres fand in der Schweizer Kleinstadt Rapperswil zum zehnten Mal eine Veranstaltung namens ZuriHac statt. Diesmal versammelten sich mehr als fünfhundert Haskell-Liebhaber von Anfängern bis zu den Gründervätern der Sprache. Obwohl die Organisatoren diese Veranstaltung als Hackathon bezeichnen, handelt es sich immer noch nicht um eine Konferenz oder einen Hackathon im klassischen Sinne. Das Format unterscheidet sich von der herkömmlichen Programmierung. Wir haben durch einen glücklichen Zufall von ZuriHac erfahren, daran teilgenommen und betrachten es nun als unsere Pflicht, über einen ungewöhnlichen Fund zu berichten!

Über uns

Dieser Artikel wurde von zwei Studenten des 3. Studienjahres des Programms für Angewandte Mathematik und Informatik der Higher School of Economics in St. Petersburg erstellt: Vasily Alferov und Elizaveta Vasilenko. Die Leidenschaft für funktionale Programmierung für uns beide begann mit einer Reihe von Vorlesungen von D. N. Moskvin im 2. Studienjahr. Derzeit nimmt Vasily am Google Summer of Code-Programm teil, in dessen Rahmen er sich unter Anleitung des Alga- Projektteams mit der Implementierung algebraischer Diagramme in der Sprache Haskell befasst. Elizabeth wandte die erworbenen Fähigkeiten der funktionalen Programmierung in den Kursen an, die der Implementierung des Anti-Unification-Algorithmus mit anschließender Verwendung in der Typentheorie gewidmet waren.

Ereignisformat

Die Zielgruppe sind die Eigentümer von Open Source-Projekten, Programmierer, die an ihrer Entwicklung teilnehmen möchten, Forscher der funktionalen Programmierung und nur Menschen, die sich für Haskell begeistern. In diesem Jahr brachte die HSR Hochschule für Technik Rapperswil University Entwickler aus mehr als fünfzig Open-Source-Haskell-Projekten aus der ganzen Welt zusammen, um über ihre Produkte zu sprechen und neue Leute für ihre Entwicklung zu interessieren.



Foto von Twitter ZuriHac

Das Schema ist sehr einfach: Sie müssen im Voraus einige Vorschläge zu Ihrem Projekt schreiben und diese an die Organisatoren senden, die Informationen zu Ihrem Projekt auf der Veranstaltungsseite veröffentlichen. Darüber hinaus haben die Autoren der Projekte am ersten Tag 30 Sekunden Zeit, um kurz von der Bühne zu erzählen, was sie tun und was zu tun ist. Dann suchen Interessenten nach Autoren und fragen detailliert nach Aufgaben.

Wir haben noch keine eigenen offenen Projekte, aber wir möchten wirklich zu bestehenden beitragen, deshalb haben wir uns als reguläre Teilnehmer registriert. Drei Tage lang haben wir mit zwei Entwicklungsteams zusammengearbeitet. Es stellt sich heraus, dass das gemeinsame Studium des Codes und der Live-Kommunikation die Interaktion der Projektautoren und Mitwirkenden sehr produktiv macht. Bei ZuriHac konnten wir neue Bereiche für uns herausfinden und zwei völlig unterschiedlichen Teams helfen, indem wir die Aufgabe in jedem der Projekte abschließen.

Neben wertvoller Praxis wurden bei ZuriHac auch mehrere Vorlesungen und Meisterkurse gehalten. Wir erinnern uns besonders an zwei Vorträge. Bei der ersten Rede sprach Andrei Mokhov von der Universität Newcastle über selektive anwendungsbezogene Funktoren - eine Typklasse, die zwischen anwendungsbezogenen Funktoren und Monaden liegen sollte. In einem anderen Vortrag sprach einer der Gründer von Haskell, Simon Peyton Jones, darüber, wie Typinferenz im GHC-Compiler funktioniert.



Vortrag von Simon Peyton Jones. Foto von Twitter ZuriHac

Die während des Hackathons abgehaltenen Meisterklassen wurden je nach Ausbildungsstand der Teilnehmer in drei Kategorien eingeteilt. Aufgaben, die Teilnehmern angeboten wurden, die sich an der Entwicklung von Projekten beteiligten, hatten auch Notizen mit Schwierigkeitsgraden. Die kleine, aber freundliche Community funktionaler Programmierer freut sich, Neulinge in ihren Reihen willkommen zu heißen. Um die Vorlesungen von Andrei Mokhov und Simon Peyton Jones zu verstehen, war der an der Universität bestandene Kurs der funktionalen Programmierung für uns sehr nützlich.

Sowohl für normale Teilnehmer als auch für Projektautoren ist die Registrierung für die Veranstaltung kostenlos. Wir haben uns Anfang Juni um die Teilnahme beworben, danach wurden wir schnell von der Warteliste auf die Liste der bestätigten Teilnehmer übertragen.

Und jetzt werden wir über Projekte sprechen, an deren Entwicklung wir teilgenommen haben.

Pandoc

Pandoc ist in der Tat ein universeller Konverter von Textdokumenten - von jedem Format zu jedem. Zum Beispiel von docx nach pdf oder von Markdown nach MediaWiki. Sein Autor John MacFarlane ist Professor für Philosophie an der University of California in Berkeley. Im Allgemeinen ist Pandoc ziemlich berühmt, und einige unserer Freunde waren überrascht, als sie erfuhren, dass Pandoc in Haskell geschrieben wurde.



Liste der von Pandoc unterstützten Dokumentformate. Die Seite hat auch eine ganze Grafik, aber dieses Bild passt nicht in den Artikel.

Natürlich implementiert Pandoc nicht für jedes Formatpaar eine direkte Konvertierung. Um solch einen umfangreichen Satz von Transformationen zu unterstützen, wird eine Standardarchitekturlö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 generiert. Entwickler nennen die interne Darstellung "AST", was für Abstract Syntax Tree oder Abstract Syntax Tree steht . Sie können die Zwischendarstellung sehr einfach betrachten: Dazu müssen Sie nur "native" als Ausgabeformat festlegen

$ cat example.html <h1>Hello, World!</h1> $ pandoc -f html -t native example.html [Header 1 ("hello-world",[],[]) [Str "Hello,",Space,Str "World!"]] 

Leser, die zumindest ein wenig mit Haskell gearbeitet haben, können bereits davon ausgehen, dass Pandoc speziell in Haskell geschrieben ist: Die Ausgabe dieses Befehls ist eine interne Strukturdarstellung von Pandoc als Zeichenfolge, die ähnlich wie in Haskell erstellt wird. Zum Beispiel in der Standardbibliothek.

Hier können Sie also sehen, dass die interne Darstellung eine rekursive Struktur ist, in der in jedem internen Knoten eine Liste vorhanden ist. Auf der obersten Ebene befindet sich beispielsweise eine Liste mit einem Element - dem Header der ersten Ebene mit den Attributen „Hallo Welt“, [], []. In dieser Kopfzeile befindet sich eine Liste der Zeichenfolge "Hallo", ein Leerzeichen und der Zeichenfolge "Welt!".

Wie Sie sehen können, unterscheidet sich die interne Darstellung nicht wesentlich von HTML. Es ist ein Baum, in dem jeder interne Knoten einige Informationen über die Formatierung seiner Nachkommen meldet und die Blätter den tatsächlichen Inhalt des Dokuments enthalten.

Wenn Sie auf die Ebene einer bestimmten Implementierung gehen, wird der Datentyp für das gesamte Dokument wie folgt definiert:

 data Pandoc = Pandoc Meta [Block] 

Hier sind Block genau die oben erwähnten internen Peaks, und Meta sind Metainformationen zum Dokument, wie Titel, Erstellungsdatum, Autoren - dies ist für verschiedene Formate unterschiedlich, und Pandoc versucht, diese Informationen zu speichern, wann immer dies möglich ist, wenn von Format zu Format übertragen wird.

Fast alle Konstruktoren des Blocktyps - z. B. Header oder Para (Absatz) - verwenden Attribute und eine Liste von Scheitelpunkten einer niedrigeren Ebene - Inline in der Regel als Argumente. Beispielsweise sind Space oder Str Designer des Inline-Typs, und das HTML-Tag wird auch in sein spezielles Inline-Tag konvertiert. Wir sehen keinen Grund, diese Typen vollständig zu definieren, stellen jedoch fest, dass sie hier zu sehen sind .

Interessanterweise ist der Pandoc-Typ ein Monoid. Dies bedeutet, dass es eine Art leeres Dokument gibt und dass Dokumente untereinander gestapelt werden können. Dies ist praktisch, wenn Sie Reader schreiben. Sie können ein Dokument mit beliebiger Logik in Teile zerlegen, jedes einzeln analysieren und dann alles zu einem Dokument zusammenfügen. In diesem Fall werden Metainformationen aus allen Teilen des Dokuments gleichzeitig gesammelt.

Wenn Sie beispielsweise von LaTeX nach HTML konvertieren, konvertiert zuerst ein spezielles Modul namens LaTeXReader das Eingabedokument in AST, dann konvertiert ein anderes Modul namens HTMLWriter AST in HTML. Dank dieser Architektur ist es nicht erforderlich, eine quadratische Anzahl von Konvertierungen zu schreiben. Es reicht aus, Reader und Writer für jedes neue Format zu schreiben, und alle möglichen Konvertierungspaare werden automatisch unterstützt.

Es ist klar, dass diese Architektur auch ihre Nachteile hat, die von Experten auf dem Gebiet der Softwarearchitektur lange vorhergesagt wurden. Am bedeutendsten sind die Kosten für Änderungen am Syntaxbaum. Wenn die Änderung schwerwiegend genug ist, müssen Sie den Code in allen Readern und Writern ändern. Eine der Herausforderungen für Pandoc-Entwickler besteht beispielsweise darin, komplexe Tabellenformate zu unterstützen. Jetzt kann Pandoc nur noch in den einfachsten Tabellen mit einer Überschrift, Spalten und einem Wert in jeder Zelle. Angenommen, das Colspan-Attribut in HTML wird einfach ignoriert. Einer der Gründe für dieses Verhalten ist das Fehlen eines einzelnen Tabellendarstellungsschemas in allen oder zumindest vielen Formaten - dementsprechend ist nicht klar, in welcher Form Tabellen in der internen Darstellung gespeichert werden sollen. Aber auch nach Auswahl einer bestimmten Ansicht müssen unbedingt alle Leser und Schreiber geändert werden, die das Arbeiten mit Tabellen unterstützen.

Haskell wurde nicht nur aus großer Liebe der Autoren zur funktionalen Programmierung ausgewählt. Haskell ist bekannt für seine leistungsstarken Textverarbeitungsfunktionen. Ein Beispiel ist die Parsec- Bibliothek - eine Bibliothek, die die Konzepte der funktionalen Programmierung - Monoide, Monaden, anwendbare und alternative Funktoren - aktiv nutzt, um beliebige Parser zu schreiben. Die volle Leistung von Parsec zeigt das HaskellWiki- Beispiel , das den vollständigen Parser einer einfachen imperativen Programmiersprache analysiert. Natürlich wird Parsec auch in Pandoc aktiv eingesetzt.

Kurz gesagt, Monaden werden zum sequentiellen Parsen verwendet, wenn eine zuerst und dann die andere kommt. Zum Beispiel in diesem Beispiel:

 whileParser :: Parser Stmt whileParser = whiteSpace >> statement 

Zuerst müssen Sie ein Leerzeichen und dann eine Anweisung berücksichtigen, die auch den Parser Stmt-Typ hat.

Alternative Funktoren werden verwendet, um ein Rollback durchzuführen, wenn die Analyse fehlgeschlagen ist. Zum Beispiel

 statement :: Parser Stmt statement = parens statement <|> sequenceOfStmt 

Bedeutet, dass Sie entweder versuchen müssen, die Anweisung in Klammern zu lesen, oder nacheinander versuchen müssen, mehrere Anweisungen zu lesen.

Anwendbare Funktoren werden hauptsächlich als Abkürzungen für Monaden verwendet. Lassen Sie die Token-Funktion beispielsweise eine Art Token lesen (dies ist die eigentliche Funktion von LaTeXReader). Schauen wir uns eine solche Kombination an

 const <$> tok <*> tok 

Sie liest zwei Token hintereinander und gibt den ersten zurück.

Haskell hat schöne symbolische Operatoren für alle diese Klassen, wodurch das Programmieren von Lesern wie ASCII-Kunst aussieht. Bewundern Sie einfach diesen wunderbaren Code.

Unsere Aufgaben bezogen sich auf LaTeXReader. Vasilys Aufgabe war es, die Befehle \ mbox und \ hbox zu unterstützen, die beim Schreiben von Paketen in LaTeX hilfreich sind. Elizabeth war für die Unterstützung des \ epigraph-Teams verantwortlich, das die Ausführung von Epigraphs in LaTeX-Dokumenten ermöglicht.

Hatrace

Unter UNIX-ähnlichen Betriebssystemen wird der Aufruf des ptrace-Systems häufig implementiert. Es ist nützlich beim Debuggen und Simulieren von Programmumgebungen, damit Sie die Systemaufrufe verfolgen können, die das Programm ausführt. Zum Beispiel verwendet das sehr nützliche Dienstprogramm strace ptrace in sich.

Hatrace ist eine Bibliothek, die eine Schnittstelle für ptrace in Haskell bietet. Tatsache ist, dass ptrace selbst sehr ausgefeilt ist und es ziemlich schwierig ist, es direkt zu verwenden, insbesondere aus funktionalen Sprachen.

Hatrace läuft beim Start wie strace und akzeptiert ähnliche Argumente. Der Unterschied zu strace besteht darin, dass es sich auch um eine Bibliothek handelt, die eine einfachere Oberfläche als nur ptrace bietet.

Hatrace hat bereits einen unangenehmen Fehler im Haskell GHC-Compiler festgestellt: Wenn er zum falschen Zeitpunkt beendet wird, werden falsche Objektdateien generiert und beim Neustart nicht neu kompiliert. Durch die Skripterstellung bei Systemaufrufen konnte der Fehler garantiert in einem Durchgang reproduziert werden, wenn zufällige Fehler den Fehler in etwa zwei Stunden reproduzierten.

Wir haben der Bibliothek Systemaufrufschnittstellen hinzugefügt - Elizabeth hat brk hinzugefügt, und Vasily hat mmap hinzugefügt. Nach den Ergebnissen unserer Arbeit können wir die Argumente dieser Systemaufrufe bei Verwendung der Bibliothek einfacher und genauer verwenden.