Ich freue mich sehr, die Fertigstellung meines ersten Compilers für eine Programmiersprache bekannt zu geben! Malcc ist ein inkrementeller Lisp AOT- Compiler, der in C geschrieben wurde.

Ich werde kurz über die langjährige Entwicklung und das, was ich dabei gelernt habe, sprechen. Alternativer Artikeltitel: "Wie schreibe ich einen Compiler in zehn Jahren oder weniger?"

(Am Ende gibt es TL; DR , wenn Sie sich nicht für den Hintergrund interessieren).

Compiler-Demo

tim ~/pp/malcc master 0 → ./malcc Mal [malcc] user> (println "hello world") hello world nil user> (+ 1 2) 3 user> (def! fib2 (fn* (n) (let* (f (fn* (n1 n2 c) (if (= cn) n2 (f n2 (+ n1 n2) (+ c 1))))) (f 0 1 1)))) <lambda> user> (fib2 25) 75025 user> ^D% tim ~/pp/malcc master 0 → ./malcc examples/hello.mal hello world tim ~/pp/malcc master 0 → ./malcc --compile examples/hello.mal hello gcc -g -I ./tinycc -I . -o hello hello.c ./reader.c ./printer.c ./hashmap.c ./types.c ./util.c ./env.c ./core.c ./tinycc/libtcc.a -ledit -lgc -lpcre -ldl tim ~/pp/malcc master 0 → ./hello hello world tim ~/pp/malcc master 0 → 

Erfolgreiche Ausfälle

Fast zehn Jahre lang habe ich davon geträumt, einen Compiler zu schreiben. Ich war schon immer fasziniert von der Arbeit der Programmiersprachen, insbesondere der Compiler. Obwohl ich mir den Compiler als dunkle Magie vorstellte und verstand, dass es für einen bloßen Sterblichen wie mich unmöglich war, ihn von Grund auf neu zu erstellen.

Aber ich habe es trotzdem versucht und studiert!

Erstens der Dolmetscher

2011 begann ich mit der Arbeit an einem einfachen Dolmetscher für die fiktive Sprache Airball (Airball kann als „Muff“ übersetzt werden). Mit Namen können Sie den Grad meiner Unsicherheit bewerten, dass es funktionieren wird. Es war ein ziemlich einfaches Ruby-Programm, das Code analysierte und durch einen abstrakten Syntaxbaum (AST) ging. Als der Dolmetscher noch funktionierte, habe ich ihn in Lydia umbenannt und in C umgeschrieben, um ihn schneller zu machen.



Ich erinnere mich, dass mir Lydias Syntax sehr klug erschien! Ich genieße immer noch seine Einfachheit.

Obwohl Lydia alles andere als ein perfekter Compiler war, inspirierte es mich, weiter zu experimentieren. Ich wurde jedoch immer noch von Fragen gequält, wie der Compiler funktioniert: In was soll kompiliert werden? Muss ich Assembler lernen?

Zweitens der Bytecode-Compiler und Interpreter

Als nächsten Schritt begann ich 2014 mit der Arbeit an Schema-VM , einer virtuellen Maschine für Schema, die in Ruby geschrieben wurde. Ich dachte, dass eine virtuelle Maschine mit eigenem Stack und Bytecode eine Übergangsphase von einem Interpreter mit AST-Pässen und einem vollwertigen Compiler wäre. Und da das Schema formal definiert ist , besteht keine Notwendigkeit, etwas zu erfinden.

Ich habe über drei Jahre lang mit Schema-VM herumgespielt und viel über das Kompilieren gelernt. Am Ende wurde mir klar, dass ich dieses Projekt nicht beenden konnte. Der Code verwandelte sich in echtes Chaos, aber ein Ende war nicht in Sicht. Ohne einen Mentor oder eine Erfahrung schien ich im Dunkeln zu wandern. Wie sich herausstellte, stimmt die Sprachspezifikation nicht mit dem Handbuch überein. Lektion gelernt!

Bis Ende 2017 habe ich Schema-VM auf der Suche nach etwas Besserem verschoben.

Treffen mit Mal

Irgendwann im Jahr 2018 stieß ich auf Mal , einen Lisp-Dolmetscher im Clojure-Stil.

Mal wurde von Joel Martin als Trainingsinstrument erfunden. Seitdem wurden mehr als 75 Implementierungen in verschiedenen Sprachen entwickelt! Als ich mir diese Implementierungen ansah, stellte ich fest, dass sie wirklich helfen: Wenn ich nicht weiterkomme, kann ich in der Ruby- oder Python-Version nach Hinweisen suchen. Endlich spricht wenigstens jemand meine Sprache!

Ich dachte auch, wenn ich einen Interpreter für Mal schreiben könnte, könnte ich die gleichen Schritte wiederholen - und einen Compiler für Mal erstellen.

Mal Dolmetscher auf Rust

Zuerst begann ich, den Interpreter gemäß der exemplarischen Vorgehensweise zu entwickeln . Zu dieser Zeit habe ich Rust aktiv studiert (ich werde es für einen anderen Artikel belassen), also habe ich meine eigene Implementierung von Mal in Rust geschrieben: Mal- Rust. Weitere Informationen zu diesem Experiment finden Sie hier.

Es war ein perfektes Vergnügen! Ich weiß nicht, wie ich Joel dafür danken oder loben soll, dass er einen hervorragenden Leitfaden für Mal erstellt hat. Jeder Schritt wird ausführlich beschrieben , es gibt Flussdiagramme, Pseudocode und Tests ! Alles, was ein Entwickler benötigt, um eine Programmiersprache von Anfang bis Ende zu erstellen.

Gegen Ende des Tutorials gelang es mir, meine in Mal geschriebene Mal-Implementierung für Mal zusätzlich zu meiner Rust-Implementierung auszuführen. (zwei Tiefenstufen, wow). Als sie zum ersten Mal arbeitete, sprang ich vor Aufregung auf einen Stuhl!

Compiler Mal C.

Sobald ich die Lebensfähigkeit von Mal-Rust bewiesen hatte, begann ich sofort zu erforschen, wie man einen Compiler schreibt. Zum Assembler kompilieren? Kann ich Maschinencode direkt kompilieren?

Ich habe den in Ruby geschriebenen x86-Assembler gesehen. Er faszinierte mich, aber der Gedanke, mit einem Assembler zusammenzuarbeiten, ließ mich aufhören.

Irgendwann bin ich auf diesen Kommentar in Hacker News gestoßen, der den Tiny C Compiler als "Compilation Backend" bezeichnete. Es schien eine großartige Idee zu sein!

TinyCC verfügt über eine Testdatei, die zeigt, wie mit libtcc C-Code aus dem C-Programm kompiliert wird. Dies ist der Ausgangspunkt für „Hallo Welt“.

Als ich wieder auf die exemplarische Vorgehensweise von Mal zurückkam und mich an meine Kenntnisse von C erinnerte, konnte ich in ein paar Monaten freier Abende und Wochenenden den Mal-Compiler schreiben. Es war eine wahre Freude.



Wenn Sie es gewohnt sind, durch Tests zu entwickeln, bewerten Sie die Verfügbarkeit einer vorläufigen Testreihe. Tests führen zu einer funktionierenden Implementierung.

Ich kann nicht viel über diesen Prozess sagen, es sei denn, ich wiederhole: Das Mal-Handbuch ist ein wahrer Schatz. Bei jedem Schritt wusste ich genau, was zu tun war!

Schwierigkeiten

Rückblickend sind hier einige Schwierigkeiten beim Schreiben des Mal-Compilers, an dem ich basteln musste:

1. Makros müssen im laufenden Betrieb kompiliert werden und zur Kompilierungszeit ausgeführt werden können. Das ist etwas verwirrend.
   
2. Sowohl für den Compiler-Code als auch für den endgültigen Code des kompilierten Programms muss eine „Umgebung“ (ein Baum von Hashes / assoziativen Arrays / Wörterbüchern mit Variablen und deren Werten) bereitgestellt werden. Auf diese Weise können Sie zur Kompilierungszeit Makros definieren.
   
3. Da die Umgebung zur Kompilierungszeit verfügbar ist, hat Malcc beim Kompilieren zunächst undefinierte Fehler festgestellt (Zugriff auf eine nicht definierte Variable), und an einigen Stellen hat dies die Erwartungen der Testsuite verletzt. Um die Tests zu bestehen, habe ich diese Funktion deaktiviert. Es wäre großartig, es als zusätzliches Flag des Compilers wieder hinzuzufügen, da Sie auf diese Weise viele Fehler im Voraus abfangen können.
4. Ich habe C-Code kompiliert, indem ich in drei Zeilen der Struktur geschrieben habe:
   • top : Code der obersten Ebene - hier sind die Funktionen
   • decl : Deklaration und Initialisierung der im Body verwendeten Variablen
   • body : Körper, in dem die Hauptarbeit erledigt wird
5. Den ganzen Tag fragte ich mich, ob ich meinen eigenen Müllsammler schreiben könnte, aber ich beschloss, diese Übung für später zu verlassen. Die Speicherbereinigungsbibliothek Boehm-Demers-Weiser ist einfach zu verbinden und auf vielen Plattformen verfügbar.
   
6. Es ist wichtig, dass Sie sich den Code ansehen, den Ihr Compiler schreibt. Immer wenn der Compiler auf eine DEBUG Umgebungsvariable stieß, gab er kompilierten C-Code zurück, in dem Fehler angezeigt werden konnten.

Was würde ich sonst tun?

1. C-Code zu schreiben und zu versuchen, die Einrückung beizubehalten, war nicht einfach, dann würde ich die Automatisierung nicht ablehnen. Es scheint mir, dass einige Compiler hässlichen Code schreiben und dann von einer speziellen Bibliothek "dekoriert" werden, bevor sie ausgegeben werden. Es muss studiert werden!
   
2. Das Hinzufügen zu Zeilen während der Codegenerierung ist etwas chaotisch. Sie könnten in Betracht ziehen, einen AST zu erstellen und ihn dann in die letzte Zeile des C-Codes zu konvertieren. Dies sollte den Code in Ordnung bringen und Harmonie schaffen.

Nun Ratschläge

Ich mag es, dass der Compiler fast ein Jahrzehnt gebraucht hat. Nein wirklich. Jeder Schritt auf dem Weg ist eine angenehme Erinnerung daran, wie ich allmählich ein immer besserer Programmierer wurde.

Das heißt aber nicht, dass ich "fertig" bin. Es gibt immer noch Hunderte von Methoden und Werkzeugen, die Sie lernen müssen, um sich als echter Compilerautor zu fühlen. Aber ich kann zuversichtlich sagen: "Ich habe es getan."

Hier ist der gesamte Prozess in einer übersichtlichen Form, wie Sie Ihren eigenen Lisp-Compiler erstellen:

1. Wählen Sie die Sprache, in der Sie sich wohl fühlen. Sie möchten nicht gleichzeitig eine neue Sprache lernen und eine andere neue Sprache schreiben.
   
2. Schreiben Sie nach dem Mal-Handbuch einen Dolmetscher.
   
3. Freut euch!
   
4. Befolgen Sie die Anweisungen erneut, aber anstatt den Code auszuführen, schreiben Sie Code, der den Code ausführt. (Nicht nur das Umgestalten des vorhandenen Interpreters. Sie müssen bei Null anfangen, obwohl das Kopieren und Einfügen nicht verboten ist.)

Ich glaube, dass diese Methode mit jeder Programmiersprache verwendet werden kann, die in eine ausführbare Datei kompiliert wird. Zum Beispiel können Sie:

1. Schreiben Sie den Mal-Interpreter auf Go .
2. Ändern Sie Ihren Code in:
   
   • Erstellen Sie eine Zeile Go-Code und schreiben Sie ihn in eine Datei.
   • Kompilieren Sie diese resultierende Datei mit go build .

Im Idealfall ist es besser, den Go-Compiler als Bibliothek zu steuern, aber dies ist auch eine Möglichkeit, einen Compiler zu erstellen!

Mit Hilfe von Mals Führer und Ihrem Einfallsreichtum können Sie all dies tun. Wenn auch ich könnte, dann kannst du!