Schema zu WebAssembly kompilieren – Eli Benderskys Website
Eines meiner ältesten Open-Source-Projekte – Bob – hat vor ein paar Monaten seinen 15. Geburtstag gefeiert. Bob ist eine Suite von Implementierungen der Programmiersprache Scheme in Python, einschließlich eines Interpreters, eines Compilers und einer VM. Damals habe ich mich mit CPython-Interna befasst und war sehr neugierig, wie CPython-ähnliche Bytecode-VMs funktionieren. Bob führte ein Experiment durch, um dies herauszufinden, indem er eines von Grund auf für das R5RS-Schema implementierte.
Einige Monate später fügte ich Bob eine C++-VM hinzu, als Übung, um zu lernen, wie solche VMs in einer Low-Level-Sprache implementiert werden, ohne die gesamte Laufzeitunterstützung, die Python bietet; vor allem ohne den eingebauten GC. Die C++-VM in Bob implementiert ihren eigenen Mark-and-Sweep-GC.
Nach vielen ruhigen Jahren (mit nur ein paar kosmetischen Änderungen, Portierungen auf GitHub, Updates auf Python 3 usw.) verspürte ich kurz vor den Feiertagen den Drang, wieder an Bob zu arbeiten. Konkret habe ich beschlossen, der Suite einen weiteren Compiler hinzuzufügen – diesen von Scheme direkt zu WebAssembly.
Die Ziele dieser Bemühungen waren zweierlei:
- Experimentieren Sie mit der Herabstufung einer echten Hochsprache wie Scheme auf WebAssembly. Experimente wie das jüngste Let’s Build a Compiler kompilieren Spielzeugsprachen auf C-Ebene (keine Laufzeit). Scheme verfügt über integrierte Datenstrukturen, lexikalische Abschlüsse, Speicherbereinigung usw. Es ist viel anspruchsvoller.
- Sammeln Sie praktische Erfahrungen mit der WASM GC-Erweiterung. Ich habe mehrere Beispiele für die Verwendung von WASM GC im Wasm-Wat-Samples-Repository, aber ich wollte es unbedingt für etwas „Echtes“ ausprobieren.
Nun, es ist jetzt erledigt; Hier ist ein aktualisierter Schaltplan des Bob-Projekts:
Der neue Teil ist der vertikale Pfad ganz rechts. Eine WasmCompiler-Klasse reduziert geparste Scheme-Ausdrücke bis hin zum WebAssembly-Text, der dann in eine Binärdatei kompiliert und mit Standard-WASM-Tools ausgeführt werden kann.
Höhepunkte
Der interessanteste Aspekt dieses Projekts war die Arbeit mit WASM GC zur Darstellung von Scheme-Objekten. Solange wir alle Werte richtig einpacken/verpacken
refs, die zugrunde liegende WASM-Ausführungsumgebung kümmert sich um die Speicherverwaltung.
Für Bob werden einige wichtige Scheme-Objekte wie folgt dargestellt:
;; PAIR holds the car and cdr of a cons cell.
(type $PAIR (struct (field (mut (ref null eq))) (field (mut (ref null eq)))))
;; BOOL represents a Scheme boolean. zero -> false, nonzero -> true.
(type $BOOL (struct (field i32)))
;; SYMBOL represents a Scheme symbol. It holds an offset in linear memory
;; and the length of the symbol name.
(type $SYMBOL (struct (field i32) (field i32)))
$PAAR ist von besonderem Interesse, da es beliebige Objekte in seinen Feldern enthalten kann; (ref null eq) bedeutet „ein nullbarer Verweis auf etwas, das Identität hat“. ref.test kann verwendet werden, um für eine bestimmte Referenz den Laufzeittyp des Werts zu überprüfen, auf den sie verweist.
Sie fragen sich vielleicht: Was ist mit numerischen Werten? Hier hat WASM einen Trick – den i31
Der Typ kann verwendet werden, um einen Verweis auf eine Ganzzahl darzustellen, ohne ihn jedoch tatsächlich einzurahmen (ein Bit wird verwendet, um ein solches Objekt von einem echten Verweis zu unterscheiden). Wir benötigen also keinen separaten Typ, um Verweise auf Zahlen zu speichern.
Auch die $SYMBOL Typ sieht ungewöhnlich aus – wie wird er mit zwei Zahlen dargestellt? Der Schlüssel zum Rätsel liegt darin, dass WASM keine integrierte Unterstützung für Strings bietet; Sie sollten manuell mithilfe von Offsets zum linearen Speicher implementiert werden. Der Bob WASM-Compiler gibt die Zeichenfolgenwerte aller gefundenen Symbole in den linearen Speicher aus und verfolgt dabei den Offset und die Länge jedes einzelnen Symbols. Das sind die beiden eingegebenen Zahlen $SYMBOL. Dies ermöglicht auch die relativ einfache Implementierung der String-Interning-Funktion von Scheme; Mehrere Instanzen desselben Symbols werden nur einmal zugewiesen.
Betrachten Sie diesen trivialen Scheme-Ausschnitt:
Der Compiler gibt die Symbole „foo“ und „bar“ wie folgt in den linearen Speicher aus:
(data (i32.const 2048) "foo")
(data (i32.const 2051) "bar")
Und wenn wir im Rest des ausgegebenen Codes nach einer dieser Adressen suchen, finden wir:
(struct.new $SYMBOL (i32.const 2051) (i32.const 3))
Als Teil des Codes zum Erstellen der Konstante Nachteile Liste, die das Argument darstellt schreiben; Adresse 2051 und Länge 3: Das ist das Symbol Bar.
Apropos schreibendie Implementierung dieses Builtins war sehr interessant. Aus Kompatibilitätsgründen mit den anderen Bob-Implementierungen in meinem Repository: schreiben
muss in der Lage sein, rekursive Darstellungen beliebiger Scheme-Werte zu drucken, einschließlich Listen, Symbolen usw.
Anfangs zögerte ich, all diese Funktionen manuell in WASM-Text zu implementieren, aber alle Alternativen stießen auf Herausforderungen:
- Dies auf den Host zu verlagern ist schwierig, da die Hostumgebung keinen Zugriff auf WASM GC-Referenzen hat – diese sind völlig undurchsichtig.
- Die Implementierung in einer anderen Sprache (vielleicht C?) und die Reduzierung auf WASM ist aus einem ähnlichen Grund ebenfalls eine Herausforderung – die andere Sprache verfügt wahrscheinlich nicht über eine gute Darstellung von WASM-GC-Objekten.
Also habe ich in den sauren Apfel gebissen und – mit etwas KI-Hilfe für die mühsamen Teile – einfach eine Implementierung von geschrieben schreiben direkt im WASM-Text; es war nicht wirklich so schlimm. Ich importiere nur zwei Funktionen vom Host:
(import "env" "write_char" (func $write_char (param i32)))
(import "env" "write_i32" (func $write_i32 (param i32)))
Obwohl es nicht schwierig ist, Ganzzahlen direkt aus WASM auszugeben, dachte ich, dass dieses Projekt bereits über genügend Code verfügt und dass hier etwas Host-Hilfe willkommen wäre. Im Übrigen nur die unterste Stufe write_char verwendet wird. So werden beispielsweise boolesche Werte in der kanonischen Scheme-Notation ausgegeben (#T Und #F):
(func $emit_bool (param $b (ref $BOOL))
(call $emit (i32.const 35)) ;; '#'
(if (i32.eqz (struct.get $BOOL 0 (local.get $b)))
(then (call $emit (i32.const 102))) ;; 'f'
(else (call $emit (i32.const 116))) ;; 't'
)
)
Abschluss
Das war ein wirklich unterhaltsames Projekt und ich habe einiges über die realistische Codeausgabe an WASM gelernt. Schauen Sie sich gerne den Quellcode von WasmCompiler an – er ist sehr gut dokumentiert. Obwohl es insgesamt etwas mehr als 1000 LOC sind, handelt es sich bei mehr als der Hälfte davon tatsächlich um WASM-Textschnipsel, die die integrierten Typen und Funktionen implementieren, die für eine grundlegende Scheme-Implementierung erforderlich sind.
