Texte, die meine Sicht auf Programmiersprachen verändert haben

• Eine Auswahl an Texten, Papers und Videos, die meine Sicht auf Programmiersprachen und Compiler grundlegend verändert haben
• Materialien, die mein Verständnis von praktischer GC-Implementierung, Optimizer-Design, Registerallokation und Regular-Expression-Engines stark erweitert haben
• Themen wie Z3 und abstrakte Domänen, SSA-Form und E-Graphs werden anhand echter Codebeispiele leicht verständlich erklärt
• Jedes Material vermittelt komplexe Konzepte knapp, dabei erweiterbar und leicht nachvollziehbar

---

Eine Einführung in Texte, die einen Perspektivwechsel bei Programmiersprachen und Compilern ausgelöst haben

• Von Zeit zu Zeit stoße ich auf Papers, Blogposts oder Videos zu Programmiersprachen und Compilern, die meine Sicht auf das Thema komplett verändern
• Bei manchen Texten war der Einfluss so stark, dass ich mich nicht einmal mehr daran erinnern kann, wie ich davor darüber gedacht habe.
• Im Folgenden eine Vorstellung solcher Materialien (ohne bestimmte Reihenfolge)

Zu GC, Optimizer, abstrakten Domänen und Registerallokation

• Andy Wingos a simple semi-space collector zeigt sehr gut, wie sich das Konzept eines Cheney-/Kopier-/kompaktierenden Garbage Collectors von der Theorie in die Praxis übertragen lässt
  • Die zentrale GC-Implementierung im Text ist sehr kompakt, erweiterbar und lässt sich an einem halben Tag verstehen
• CF Bolz-Tereicks Artikel Implementing a Toy Optimizer hat meine Sicht auf Instruction-Rewriting in Optimizern verändert
  • Statt einfacher Suchen-und-Ersetzen-Muster betont er den Einsatz von Forwarding Pointern und führt das Union-Find-Konzept ein
  • Die gesamte Toy-Optimizer-Reihe steckt in jedem Beitrag voller neuer und interessanter Ideen
• A Knownbits Abstract Domain for the Toy Optimizer, Correctly stellt gleichzeitig eine neue abstrakte Domäne und den Einsatz von Z3 vor
  • Es zeigt nicht nur, wie Z3 für verschiedene Beweise numerischer Operationen genutzt wird, sondern auch als Verifikations-Engine für Python-Code
  • Vorgestellt wird die Idee, dass die Korrektheit des Codes abgesichert ist, wenn Z3 kein Gegenbeispiel findet
• In Chris Fallins Cranelift, Part 3: Correctness in Register Allocation wird erklärt, wie man für jede Eingabe die korrekte Registerallokation direkt beweist
  • In einer Produktionsumgebung erhält man entweder eine korrekte Allokation oder einen sinnvollen Crash
  • Außerdem wird ein Ansatz eingeführt, der mit Fuzzing-Techniken den Zustandsraum durchsucht und Bugs aufspürt

Zu Parsing, Interpretern, JIT und abstrakten Strukturen

• Russ Cox’ Regular Expression Matching: the Virtual Machine Approach präsentiert die Implementierung einer Regular-Expression-Engine in etwa 50 Zeilen gut lesbarem Code
  • Dabei werden auch die Prinzipien von Coroutines, Fibers und Schedulern leicht verständlich erklärt
• Andrej Karpathys micrograd ist ein winziges Beispiel dafür, wie man neuronale Netze ohne externe Bibliotheken zum Laufen bringt, und hilft dabei, Grundstruktur und Prinzipien des Machine Learning zu verstehen
• Fil Pizlos How I implement SSA form stellt eine neue Methode vor, die Union-Find-Struktur zu verbessern
  • Bei der SSA-Transformation werden zusätzliche Pointer dabei als interne Identity Tags in Objekten verwaltet
  • Darüber hinaus liefert der Text weitere Denkanstöße zu Phi/Upsilon-Form, TBAA-artigen Heap-Effekten und mehr
• Fil Pizlos Speculation in JavaScriptCore behandelt detailliert die verschiedenen Optimizer-Implementierungsansätze in JavaScriptCore
  • Jedes erneute Lesen bringt neue Einsichten

Compiler-Design, Parser, IR-Strukturen und E-Graphs

• In Chandler Carruths Vortrag Modernizing Compiler Design for Carbon Toolchain (etwa ab Minute 29) wird erklärt, wie das Ziel überwältigend schneller Compile Times gesetzt und die Gesamtarchitektur entworfen wurde
  • Ab etwa Minute 40 wird die Struktur Ebene für Ebene aufgeschlüsselt
• Allison Kapturs A Python Interpreter Written in Python macht die Funktionsweise des internen Bytecode-Interpreters von CPython leicht verständlich
• Eli Benderskys Parsing expressions by precedence climbing stellt das Precedence-Climbing-Verfahren vor, das leichter zu verstehen ist und weniger Entwicklungsaufwand erfordert als ein traditioneller rekursiver Abstiegparser
• Takashi Kokubuns Ruby JIT Challenge zeigt Codegenerierung und eine neue Methode der Registerallokation (stack folding at compile-time)
• Abdulaziz Ghuloums An Incremental Approach to Compiler Construction (PDF) erklärt eine Single-Pass-Implementierung, mit der sich klassisches mehrstufiges Compiler-Design auf einmal erfassen lässt
  • Dabei werden die einzelnen Funktionen Schritt für Schritt End-to-End ergänzt
• Fernando Borrettis Lessons from Writing a Compiler beschreibt Strategien zur Compiler-Implementierung in klarer, sprachlich präziser Form
• Das Paper egg: Fast and extensible equality saturation verändert die Sicht auf Optimizer und die Reihenfolge von Passes grundlegend
  • Es schlägt die Denkweise vor, alle möglichen Versionen eines Ausdrucks als komprimierten Hypergraphen vorzuhalten und dann die beste Version auszuwählen
• Chris Fallins Cranelift: Using E-Graphs for Verified, Cooperating Middle-End Optimizations zeigt, dass E-Graphs auch in realen Produktions-Compilern effektiv funktionieren
• Phil Zuckers Acyclic Egraphs and Smart Constructors untersucht azyklische E-Graph-Strukturen und den Einsatz von Smart Constructors
  • Anfangs war der Text schwer zu verstehen, doch mit der Zeit wurde das Verständnis immer tiefer

AST-Speicherung, großskalige parallele dynamische Analyse und Sonstiges

• Bob Nystroms dieser Reddit-Kommentar und Adrian Sampsons Flattening ASTs
  • zeigen, wie sich ASTs fast so kompakt wie Bytecode speichern lassen, und
  • stoßen eine größere Diskussion darüber an, dass mit einer solchen Speicherung von IR-Knoten auch großskalige parallele lock-freie Analyse möglich wird
  • Auch Cliff Clicks Hinweis zur Geschwindigkeit von Buffer-Allokationen hat diese Denkweise beeinflusst

[GN⁺]

Hacker-News-Kommentare

• Ich mag diesen Beitrag wirklich sehr. Ich habe mich in letzter Zeit viel mit Informatikforschung beschäftigt, und selbst unter den hier erwähnten Dingen gibt es einiges, dem ich noch nicht begegnet bin. Ich möchte ein paar Arbeiten vorstellen, die ich mag und die hier fehlen: Ian Piumartas „Open, Extensible Object Models“ behandelt ein minimales objektorientiertes Metaobjektsystem, das Programmierern maximale Freiheit gibt. Im Grunde wird nur die Operation des Nachrichtensendens definiert, und alles andere kann zur Laufzeit verändert werden. Es wirkt wie eine praktische Version von „Art of the Metaobject Protocol“. John Ousterhouts „Scripting: Higher-Level Programming for the 21st Century“ behandelt die Dichotomie zwischen Systemprogrammiersprachen und Skriptsprachen. Wir wünschen uns immer eine perfekte Multiparadigmen-Sprache, mit der sich alles schnell und produktiv erledigen lässt, aber oft ist eine kompilierte, schnelle und komplexe Systemprogrammiersprache besser in Kombination mit einem bequemen und flexiblen interpretierten Frontend. Tatsächlich reicht oft schon die einfache Kombination aus C und Tcl. Das ist Pflichtlektüre für jeden, der Programmiersprachen entwickelt. Niklaus Wirths Project Oberon ist ein Beispiel für die Umsetzung eines kompletten Computersystems, vom High-Level-UI über Kernel und Compiler bis hin zu einer RISC-ähnlichen CPU-Architektur. Er hat ein starkes Plädoyer für „lean software“ gehalten und es auch tatsächlich umgesetzt. In einer Zeit wie heute, die von Dependency Hell und übermäßiger Abstraktion geprägt ist, ist das verlorene Handwerkskunst.

  • Ich stimme Ousterhouts Dichotomie und Schlussfolgerung nicht zu. Sein Kernpunkt ist, dass eine Sprache entweder eine Systemsprache (C) oder eine Skriptsprache (Tcl, Python) ist. Er behauptet, Systemsprachen seien stark typisiert und für Datenstrukturen/Algorithmen gedacht, während Skriptsprachen untypisiert seien und zum „Zusammenkleben“ dienten. Er behauptet auch, dass Skriptsprachen dank ihres „Nicht-Vorhandenseins von Typen“ knapper seien und schnellere Entwicklung erlaubten, aber ich halte das nicht für eine realistische Erklärung. Er vergleicht etwa Tcl-Code mit C++/MFC-Code und sagt, Tcl sei besser, aber in Wirklichkeit gefällt es ihm nur wegen der besseren Syntax. Die Behauptung, dass untypisierte Sprachen schneller machen, stimmt nicht; es ist nur eine Frage, wann man an die Grenzen stößt. Es ist besser, alle Typfehler vor der Ausführung zu prüfen, und statische Typanalyse ist in allen Sprachen möglich, aber kompliziert und schwierig. Als PL-Designer ist es eine legitime Entscheidung, Typprüfungen nur zur Laufzeit zu machen, weil das die Sprachentwicklung vereinfacht, aber das bedeutet nicht, dass es die bessere Wahl ist.

• Ich mag diesen Beitrag wirklich sehr. Texte über Programmiersprachen haben meine Sicht auf das Programmieren selbst verändert. Ich denke oft an das Zitat über „Sicherheit“ aus TAPL(Types and Programming Languages). Eine sichere Sprache ist eine Sprache, die verhindert, dass Programmierer sich selbst ins Knie schießen, und die ihre eigenen Abstraktionen schützt. Entscheidend ist also die Fähigkeit, die Integrität der von der Sprache bereitgestellten Abstraktionen und der von Programmierern aufgebauten höheren Abstraktionen zu garantieren. Wenn es zum Beispiel eine Abstraktion wie ein Array gibt, sollte sie nur durch explizite Updates veränderbar sein und nicht versehentlich durch Eingriffe in andere Datenstrukturen beschädigt werden können.

• Was interessante Entwicklungsgewohnheiten angeht … Aaron Hsu, bekannt für APL, schreibt Code in kalligrafischer Weise mit einem Füllfederhalter, wenn er seine Gedanken ordnet. Ich mache etwas Ähnliches und zeichne mit einem billigen Kugelschreiber Flussdiagramme von Python-Objekten, um meine Gedanken zu sortieren. So eine Art Billig-UML.

  • Ich greife auch zu einem Füllfederhalter, wenn ich mich mit den schwierigsten Problemen beschäftige. Mit einem Füllfederhalter zu schreiben fühlt sich an, als würde man einen völlig anderen Denkraum betreten. Wegen der begrenzten Bearbeitungsmöglichkeiten wird kohärenteres und lineareres Denken gefördert, gleichzeitig öffnet es Kreativität, weil man frei zwischen Englisch, Code, Mathematik, Diagrammen usw. wechseln kann.

  • Dass Handschrift das Gedächtnis verbessert, ist tatsächlich nachgewiesen. Auf dem Computer zu tippen, ist ungefähr so, als würde man Fingerabdrücke auf einem Griff hinterlassen. Ich hoffe, dass OCR so gut wird, dass man selbst bei ausschließlich handschriftlichen Aufzeichnungen perfekt speichern und suchen kann.

• Ich würde unbedingt empfehlen, sich Rich Hickeys Vorträge anzusehen, besonders die frühen. Bei mir haben solche Vorträge ebenfalls meine Sicht auf das Programmieren komplett verändert.

  • Für mich waren Rich Hickeys Vorträge zusammen mit Larry Walls „Programming Perl“ am einflussreichsten.

  • Ich würde scherzhaft empfehlen, den Vortrag „Simple made easy“ zu überspringen, weil ihn in den letzten zehn Jahren jeder Konferenzredner ständig zitiert hat und er inzwischen ein Klischee ist. Persönlich finde ich „Hammock driven development“ besser, aber ich würde ihn im Unternehmen nicht unbedingt empfehlen.

• Schade, dass Abdulaziz still geworden ist, nachdem er nach Kuwait zurückgekehrt war. Er war 2009 Maxine-VM-Praktikant und ein wirklich guter Mensch. Diese Arbeit ist ein echtes Juwel.

  • Das finde ich auch schade. Aber es scheint, als hätte er vor Kurzem eine Bäckerei eröffnet und als würde das Geschäft gut laufen. Insofern lebt er gewissermaßen seinen Traum.

• Vor Kurzem gab es einen guten Beitrag über closure-basierte Interpreter zur Beschleunigung von Interpretern. Ich habe diese Technik benutzt, um einen einfachen brainfuck-Interpreter zu bauen, und er war ziemlich schnell. Ich werde das wahrscheinlich nirgendwo sonst einsetzen, aber als Experiment war es lehrreich.

  • Ich frage mich, worin der Unterschied zwischen einem Array von Closures und einem Array liegt, in dem sich Funktionszeiger und Daten abwechseln. Letzteres fühlt sich in den meisten Sprachen unnatürlich an und passt eher zu einer Sprache wie C. Trotzdem denke ich, dass ein Array mit statischen Funktionen und Daten zusammen cache-freundlicher wäre.

• Ich wünschte, es gäbe solche Texte auch über höherstufige Sprachen wie JavaScript oder .NET. Dieser Autor ist sehr klug, arbeitet aber meist auf einer niedrigeren Ebene als die meisten Nutzer — oder vielleicht auf einer höheren?

• Auch die anderen Texte in seinem Blog sind wirklich hervorragend.

• Zu micrograd: Ich frage mich, ob es außer dem Sourcecode im Github-Repository noch mehr Dokumentation gibt.

  • Es gibt eine YouTube-Serie von Andrej Karpathy über den Entwicklungsprozess von micrograd.

• Ich sage das, weil ich diese Person mag, aber die Texte hier handeln nicht wirklich von PL (Programmiersprachen) selbst, sondern fast alle von Compilern (außer dem Garbage Collector). Ich mag Compiler natürlich auch, aber das ist ein anderes Thema als PL.

  • Ist damit vielleicht Programmiersprachen(-Implementierung) gemeint?