Techniken zur Entwicklung von Interpretern

 (craftinginterpreters.com)
3 Punkte von GN⁺ 2024-07-13 | 1 Kommentare | Auf WhatsApp teilen
  • Crafting Interpreters ist ein Buch, das so aufgebaut ist, dass Leser, die selbst eine Sprache entwickeln möchten, die vollständige Implementierung einer Skriptsprache von Anfang bis Ende nachvollziehen können
  • Es behandelt in einem durchgängigen Zusammenhang Konzepte des Sprachdesigns wie Parsing und Semantik bis hin zu Aspekten der Laufzeitimplementierung wie Bytecode-Darstellung und Garbage Collection
  • Leser beginnen bei main() und implementieren selbst eine Sprache mit dynamischer Typisierung, lexikalischem Scope, First-Class-Funktionen, Closures, Klassen und Vererbung
  • Da einige tausend Zeilen sauberer und schneller Code vollständig selbst geschrieben werden, liegt der Schwerpunkt stärker auf dem Verständnis der internen Funktionsweise als auf dem Endergebnis
  • Verfügbar als Druckausgabe, eBook, PDF und im Web; im Web können alle Kapitel, ergänzende Texte und Illustrationen kostenlos gelesen werden

Umfang der Implementierung im Buch

  • Crafting Interpreters richtet sich an Leser, die ihre eigene Programmiersprache entwickeln möchten oder verstehen wollen, wie Sprachen entworfen und implementiert werden
  • Das Buch behandelt gemeinsam die zentralen Themen, die für die Implementierung einer voll funktionsfähigen Skriptsprache nötig sind
    • Parsing
    • Semantik
    • Bytecode-Darstellung
    • Garbage Collection
  • Die Implementierung beginnt bei main() und wird schließlich zu einer Sprache mit den folgenden Funktionen erweitert
    • umfangreiche Syntax
    • dynamische Typisierung
    • lexikalischer Scope
    • First-Class-Funktionen
    • Closures
    • Klassen
    • Vererbung

Leseweise und Ergebnis

  • Statt den Beispielcode nur anzusehen, schreiben Leser jede Zeile selbst und verfolgen so die interne Struktur des Sprachprozessors
  • Der endgültige Code umfasst einige tausend Zeilen und ist auf eine saubere und schnelle Implementierung ausgelegt
  • Anstatt übergeordnete Konzepte und Low-Level-Implementierung getrennt zu erklären, ist das Buch so gestaltet, dass beides gemeinsam im Prozess der Fertigstellung einer Sprache verstanden wird

Verfügbare Formate

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-07-13
Hacker-News-Kommentare

  • Ich bin der Autor. Die positive Resonanz auf mein Buch zu sehen, wärmt mir wirklich das Herz. Ich habe viel Zeit und Liebe hineingesteckt, und zu sehen, dass es die erhoffte Wirkung hatte, ist sehr erfüllend.

    • Ich bin ein autodidaktischer Software Engineer und habe erst mit 21 angefangen zu programmieren. In meinem ersten Job bekam ich die Aufgabe, eine einfache Abfragesprache und ihren Interpreter zu bauen. Ich hatte überhaupt keine Ahnung, was ein Interpreter ist, aber 2017 fand ich dieses Buch online, baute in 3–4 Tagen einen funktionierenden Prototyp und konnte nach 1–2 Wochen sogar ein echtes Produkt daraus machen.
      Dieses Material hat mir enorm viel Selbstvertrauen gegeben, und ich erinnere mich bis heute an dieses Projekt als eine meiner liebsten Arbeiten.
    • Danke, dass du das Buch geschrieben hast. Ich bin gerade fast am Ende von Teil 1 und folge dem Ganzen einfach aus Spaß in Haskell. In jedem Kapitel merke ich, dass der „clevere Trick“, den ich mir ausgedacht hatte, angesichts der späteren Anforderungen doch nicht so clever war.
      Ich frage mich auch, ob du darüber nachdenkst, ein Folgebuch zu einem Compiler oder JIT für Lox zu schreiben. Und der lexical analygator ist großartig; er ist mit Quellenangabe mehrfach in internen Präsentationen bei uns aufgetaucht, und eine Zeit lang gab es sogar Whiteboard-Fanart dazu.
    • Game Programming Patterns ist ebenfalls hervorragend. Beide Bücher fühlen sich im Stil ehrlich und direkt an.
      Manche Autoren scheinen zu glauben, sie müssten so tun, als sei dieses Feld reine schwarze Magie; vielleicht war ich aber auch einfach nicht gut genug, um die GoF-Design-Patterns zu verstehen.
    • Ich habe das Buch noch nicht ganz abgeschlossen, bin aber wirklich dankbar, dass du es online kostenlos veröffentlicht hast. Ich habe die gedruckte Ausgabe, das PDF und die Kindle-Version gekauft und empfehle anderen ebenfalls, den Autor auf diese Weise zu unterstützen.
    • Dieses Buch und Writing An Interpreter In Go sind Bücher, die ich unbedingt lesen möchte, sobald ich mehr Zeit habe. Ich habe einige Ideen, eine einfache Satz-/Typesetting-Sprache zu bauen.

  • Beim Erstellen von Crumb (https://github.com/liam-ilan/crumb) habe ich Crafting Interpreters gelesen, und besonders die Abschnitte zu Scopes und lokalen Variablen waren unverzichtbar.
    Die Balance zwischen technischer Umsetzung und konzeptuellem Verständnis ist sehr gut, sodass es auch dann enorm hilft, wenn man vom vorgegebenen Pfad des Buchs abweichen möchte. Diese Art technischer Texte ist so hochwertig, dass sie als Zielbild dienen kann.

    • Du hast zwar „angehender Engineer“ gesagt, aber wenn man sieht, dass du Crumb gebaut hast, gibt es schon gute Neuigkeiten.
    • Man kann dich bereits Engineer nennen. Du musst nicht bescheiden sein, und man wird nicht erst dadurch Engineer, dass man einen Informatikabschluss fertig macht.
      Die Dokumentation ist gut, und das Projekt ist klasse.
    • Sieht beeindruckend aus. Mich würde interessieren, wie du entschieden hast, welche Datentypen du einbaust.

  • Was mir an diesem Buch am besten gefallen hat, ist, dass es einen dazu bringt, zwei unterschiedliche Interpreter für dieselbe Sprache zu schreiben.
    Dadurch versteht man die komplexeren und subtileren Teile des Entstehungsprozesses einer Programmiersprache deutlich besser. In der ersten Hälfte des Buchs begegnet man den großen Ideen zuerst und macht sich mit ihnen vertraut; wenn sie im zweiten Interpreter erneut auftauchen, kann man die interessanten Teile wirklich aufnehmen. Ein wirklich erstaunliches Buch.

  • Da hier auch andere Compiler-Ressourcen erwähnt werden: Ich habe es noch nicht ganz durchgesehen, aber die Videos von Immo Landwerth, in denen er einen Compiler in C# baut und dabei IL, Debug-Symbole usw. erzeugt, fand ich ebenfalls gut.
    Das Material ist etwa fünf Jahre alt, daher ist es nicht die neueste C#-Syntax und dürfte etwa aus der Zeit von .NET Core 3 stammen, aber für die meisten Arbeiten sollte das kein großes Problem sein. Allerdings können viele Warnungen zur Nullable-Referenztypen-Thematik auftauchen.
    https://www.youtube.com/playlist?list=PLRAdsfhKI4OWNOSfS7EUu...

  • Ich finde, die meisten Programmierer sollten dieses Buch irgendwann einmal vollständig durcharbeiten. Als ich das getan habe, habe ich sehr viel besser verstanden, was intern in Compilern oder Sprachwerkzeugen tatsächlich passiert.
    Es gehört zu den am besten geschriebenen technischen Guides, denen ich je gefolgt bin, und hat mir sehr geholfen, die Konzepte wirklich zu verinnerlichen. Diese Konzepte sind nicht nur bei Compilern nützlich, sondern auch an vielen anderen Stellen.

    • Mich würde interessieren, wo sie außerhalb von Compilern nützlich sind. Zum Beispiel vielleicht beim Parsen von Datenformaten.

  • Ein nebensächlicher, aber vielleicht ebenso wichtiger Vorteil dieses Buchs ist, dass es Klarheit lehrt.
    Text, Code, Struktur und Tempo sind alle klar und auf den Punkt. Das Wort „Crafting“ passt genau: Es fühlt sich an wie ein Buch, das ein Handwerker für Handwerker geschrieben hat.

  • Meiner Ansicht nach sollte dieses Buch der zweite oder dritte Schritt auf der Reise zu Programmiersprachen-Compilern sein.
    Der erste Schritt ist, ohne Wissen über Interpreter oder Sprachdesign selbst einen Interpreter für eine einfache, selbst entworfene Sprache zu schreiben. Der zweite Schritt ist, ihn erneut zu schreiben und dabei weniger Fehler zu machen.
    Wenn man das nicht tut, ist es schwer, die Feinheiten des Themas wirklich zu würdigen, und man geht leicht über Konzepte hinweg, die zunächst nicht wichtig aussehen.

    • Für mich hat dieses Buch solche Themen entmystifiziert und mir eher ermöglicht, den zweiten und dritten Schritt überhaupt zu beginnen.
      Es ist in Ordnung, nicht jede Technik von Grund auf selbst neu zu erfinden. Auf den Schultern von Riesen zu stehen, ist etwas Natürliches.
    • Ich wusste nicht, wo ich anfangen sollte, und hielt solche Projekte für etwas Magisches, das meine Fähigkeiten übersteigt. Nachdem ich aber Crafting Interpreters gelesen hatte, merkte ich, dass mein Denken nur einen kleinen Schubs brauchte.
      Hätte ich nicht zuerst etwas wie CI gelesen, hätte ich wahrscheinlich nie versucht, selbst einen Interpreter zu schreiben, und wäre nicht bis zum dritten Schritt gekommen.
    • Ich erinnere mich, dass ich, als ich gerade anfing Java zu lernen, eine eigene Sprache bauen wollte. Ohne nachzuschlagen implementierte ich einen Operator-Präzedenz-Algorithmus, indem ich durch die Token-Liste ging und jedes Mal den Teilausdruck mit der höchsten Priorität suchte.
      Es gab keine Rekursion; ich habe Dinge direkt auf einen Stack gelegt und wieder heruntergenommen. Das Problem war, dass ich Parsing nicht richtig verstand und den Großteil der Sprache mit string.split und string.replace implementierte. Wie zu erwarten entstanden dadurch Konzepte, die sich nicht verschachteln ließen. Schade, dass ich den Quellcode nicht aufgehoben habe.
    • Ich habe es ganz genauso gemacht. Als ersten Schritt habe ich eine TeX-ähnliche Sprache gebaut und Makrodefinitionen sowie Ersetzungen implementiert.
      Nach nur wenigen Tagen stieß ich auf so viele Bugs, dass ich eine etwas akademischere Haltung einnahm und anfing, Bücher zu lesen. Trotzdem war es ein großartiger erster Schritt; ohne diesen Versuch hätte ich vielleicht nicht einmal erkannt, dass dieses Thema ein ganzes Buch füllen kann.

  • Ich habe wirklich großen Respekt vor Menschen mit so viel Hingabe und vor allen, die die Entwicklungsinfrastruktur am Laufen halten, aber ich bin froh, dass meine Phase „Ich will eine Sprache bauen“ nur ein kurzes Interesse geblieben ist.
    Der Arbeitsaufwand ist wirklich enorm.

    • Es muss nicht unbedingt ein enormer Arbeitsaufwand sein. Lisp-in-Lisp aus dem ursprünglichen SICP-Buch oder ein in Haskell geschriebener Interpreter für Lambda-Kalkül passen sogar auf einen Bildschirm.

  • Ich frage mich, ob jemand gute Ressourcen kennt, um eine statisch typisierte Sprache mit Dingen wie parametrischem Polymorphismus und grundlegender Typinferenz zu bauen.

    • Ich wurde schon mehrfach gebeten, so ein Buch zu schreiben, aber ein Hauptgrund, warum ich es bisher nicht getan habe, ist, dass das Thema zu offen ist.
      Bei Crafting Interpreters hatte ich das Gefühl, eine kleine, in sich geschlossene Sprache bauen zu können, die fast alle Konzepte enthält, die ich vermitteln wollte: Variablenscopes, Funktionen, Closures, Klassen und dynamisches Dispatch, Kontrollfluss usw.
      Bei Typsystemen gibt es dagegen zu viele Abzweigungen im Designraum und keinen klaren „besten“ Weg. Ob es Subtyping gibt, ob Generics gelöscht oder reifiziert werden, ob generischer Code zur Compile-Zeit spezialisiert wird, ob Typinferenz lokal ist oder Hindley-Milner folgt – all das sind Verzweigungen.
      Egal, wofür man sich entscheidet, man verpasst wichtige Inhalte der nicht gewählten Zweige und kann Leser enttäuschen, die einen anderen Weg erwartet haben. Vielleicht wäre ein breiter angelegtes Überblicksbuch wie Types and Programming Languages passender, aber dann verliert man den Spaß daran, eine einzige konsistente Sache aufzubauen.
    • Es gibt Modern Compiler Implementation in ML von A. W. Appel.
      Es gibt auch C- und Java-Ausgaben desselben Buchs, aber ich halte sie für schwächer. Ich würde eher mit der ML-Ausgabe arbeiten.
    • Der Kern von parametrischem Polymorphismus und Typinferenz ist letztlich die Implementierung von Algorithm W. Man kann online Toy-Implementierungen finden und selbst damit herumexperimentieren.
      Ich habe gesehen, dass die Implementierung unter https://github.com/wh5a/Algorithm-W-Step-By-Step/blob/master... in einem sehr alten Stil geschrieben war, habe sie modernisiert und aufgeräumt und daraus https://gist.github.com/kccqzy/fa8a8ae12a198b41c6339e8a5c459... gemacht. Danach habe ich mehrere Teile absichtlich „kaputtgemacht“, um zu sehen, wie der Algorithmus bricht.
    • Etwas theoretischer, aber der Compiler-Kurs auf Coursera langsam durchzuarbeiten, war für mich ein großer Wendepunkt. Manche Videos musste ich mir mehrfach ansehen.
      Ich kann sehr empfehlen, eine Informatikaufgabe, von der man glaubt, sie sei nur für Zauberer machbar, auf zugängliche Weise selbst auszuprobieren. Wenn man ein oder zwei davon geschafft hat, merkt man, dass es zwar schwierig ist, aber meist vor allem darum geht, sich Stück für Stück durchzukämpfen – und das gibt enorm viel Selbstvertrauen. Wer diesen Weg gehen möchte, kann mich unter zellyn@(most things) kontaktieren.

  • Ich habe gerade Teil 2 abgeschlossen, und es ist wirklich ein gutes Buch. Es hilft enorm beim Verständnis, wenn man pro Kapitel ein oder zwei der vorgeschlagenen Aufgaben selbst macht.