Tutorial/Ressource für die Implementierung von VM

Ich möchte zu Selbstbildungszwecken eine einfache virtuelle Maschine für eine dynamische Sprache implementieren, am liebsten in C. So etwas wie die Lua VM oder Parrot oder Python VM, aber einfacher. Gibt es gute Ressourcen/Tutorials, um dies zu erreichen, abgesehen von der Betrachtung von Code- und Designdokumentationen der vorhandenen VMs?

Bearbeiten: Warum schließen Sie die Abstimmung? Ich verstehe nicht – ist das keine Programmierung. Bitte kommentieren Sie, wenn es ein spezifisches Problem mit meiner Frage gibt.

Ich nehme an, Sie wollen eher eine virtuelle Maschine als einen bloßen Interpreter. Ich denke, sie sind zwei Punkte auf einem Kontinuum. Ein Dolmetscher arbeitet an etwas, das der ursprünglichen Darstellung des Programms nahe kommt. Eine VM arbeitet mit primitiveren (und eigenständigen) Anweisungen. Dies bedeutet, dass Sie eine Kompilierungsphase benötigen, um das eine in das andere zu übersetzen. Ich weiß nicht, ob Sie zuerst daran arbeiten möchten oder ob Sie überhaupt schon eine Eingabesyntax im Sinn haben.

Für eine dynamische Sprache möchten Sie einen Ort, an dem Daten (als Schlüssel/Wert-Paare) und einige Operationen, die darauf einwirken, gespeichert werden. Die VM verwaltet den Speicher. Das darauf laufende Programm ist eine Folge von Anweisungen (inklusive Kontrollfluss). Sie müssen den Satz von Anweisungen definieren. Ich würde ein einfaches Set vorschlagen, um mit zu beginnen, wie:

• grundlegende arithmetische Operationen, einschließlich arithmetischer Vergleiche, Zugriff auf den Speicher
• grundlegender Kontrollfluss
• eingebauter Druck

Möglicherweise möchten Sie einen stapelbasierten Berechnungsansatz für die Arithmetik verwenden, wie es viele VMs tun. Es gibt noch nicht viel Dynamik in dem oben Gesagten. Um das zu erreichen, wollen wir zwei Dinge: die Fähigkeit, die Namen von Variablen zur Laufzeit zu berechnen (das bedeutet einfach String-Operationen), und eine gewisse Behandlung von Code als Daten. Dies kann so einfach sein wie das Zulassen von Funktionsreferenzen.

Die Eingabe in die VM erfolgt idealerweise im Bytecode. Wenn Sie noch keinen Compiler haben, könnte dieser aus einem einfachen Assembler generiert werden (der Teil der VM sein könnte).

Die VM selbst besteht aus der Schleife:

1. Look at the bytecode instruction pointed to by the instruction pointer.
2. Execute the instruction:
   * If it's an arithmetic instruction, update the store accordingly.
   * If it's control flow, perform the test (if there is one) and set the instruction pointer.
   * If it's print, print a value from the store.
3. Advance the instruction pointer to the next instruction.
4. Repeat from 1.

Der Umgang mit berechneten Variablennamen kann schwierig sein: Eine Anweisung muss angeben, in welchen Variablen sich die berechneten Namen befinden. Dies könnte dadurch erfolgen, dass Anweisungen auf einen Pool von Zeichenfolgenkonstanten verweisen, die in der Eingabe bereitgestellt werden.

Ein Beispielprogramm (in Assembler und Bytecode):

offset  bytecode (hex)   source
 0      01 05 0E         //      LOAD 5, .x
 3      01 03 10         // .l1: LOAD 3, .y
 6      02 0E 10 0E      //      ADD .x, .y, .x
10      03 0E            //      PRINT .x
12      04 03            //      GOTO .l1
14      78 00            //      .x: "x"
16      79 00            //      .y: "y"

Die implizierten Befehlscodes sind:

"LOAD x, k" (01 x k) Load single byte x as an integer into variable named by string constant at offset k.
"ADD k1, k2, k3" (02 v1 v2 v3) Add two variables named by string constants k1 and k2 and put the sum in variable named by string constant k3.
"PRINT k" (03 k) Print variable named by string constant k.
"GOTO a" (04 a) Go to offset given by byte a.

Sie benötigen Varianten, wenn Variablen von anderen Variablen benannt werden usw. (und es wird schwierig, über die Ebenen der Indirektion nachzudenken). Der Assembler betrachtet die Argumente wie “ADD .x, .y, .x” und generiert den korrekten Bytecode zum Hinzufügen von String-Konstanten (und nicht berechneten Variablen).

Nun, es geht nicht darum, eine VM in C zu implementieren, aber da es der letzte Tab war, den ich geöffnet hatte, bevor ich diese Frage sah, muss ich darauf hinweisen Artikel über die Implementierung eines QBASIC-Bytecode-Compilers und einer virtuellen Maschine in JavaScript mit der <canvas> Markierung für die Anzeige. Es enthält den gesamten Quellcode, um genügend QBASIC zu implementieren, um das “Nibbles” -Spiel auszuführen, und ist der erste in einer Reihe von Artikeln über den Compiler und den Bytecode-Interpreter. dieser beschreibt die VM, und er verspricht zukünftige Artikel, die auch den Compiler beschreiben.

Übrigens habe ich nicht dafür gestimmt, Ihre Frage zu schließen, aber die knappe Abstimmung, die Sie erhalten haben, war ein Duplikat einer Frage aus dem letzten Jahr, in der es darum ging, wie man etwas über die Implementierung einer virtuellen Maschine lernt. Ich denke, diese Frage (über ein Tutorial oder etwas relativ Einfaches) unterscheidet sich genug von dieser, dass sie offen bleiben sollte, aber Sie sollten sich vielleicht auf diese Frage beziehen, um weitere Ratschläge zu erhalten.

Eine weitere Ressource, die Sie sich ansehen sollten, ist die Implementierung von Lua-Sprache. Es ist eine registerbasierte VM, die einen guten Ruf für Leistung hat. Das Quellcode ist in ANSI C89 und ist im Allgemeinen sehr gut lesbar.

Wie bei den meisten Hochleistungs-Skriptsprachen sieht der Endbenutzer eine lesbare, dynamische Sprache auf hohem Niveau (mit Funktionen wie Closures, Tail Calls, unveränderlichen Zeichenfolgen, Zahlen und Hash-Tabellen als primäre Datentypen, Funktionen als erstklassige Werte und mehr). . Der Quelltext wird zur Ausführung durch eine VM-Implementierung in den Bytecode der VM kompiliert, deren Umriss so ziemlich der Beschreibung in Edmunds Antwort entspricht.

Es wurden große Anstrengungen unternommen, um die Implementierung der VM selbst sowohl portabel als auch effizient zu halten. Wenn noch mehr Leistung benötigt wird, a Just-in-Time-Compiler von VM-Bytecode zu nativen Anweisungen existiert für 32-Bit-x86 und befindet sich in der Beta-Version für 64-Bit.

Zum Starten (auch wenn nicht Caber C++) könnte man sich anschauen muParser.

Es ist ein mathematischer Ausdrucksparser, der a verwendet einfach virtuelle Maschine zum Ausführen von Operationen. Ich denke, dass auch Sie Zeit brauchen, um alles zu verstehen; Auf jeden Fall ist dieser Code einfacher als eine vollständige VM, die eine ausführen kann real komplettes Programm. (Übrigens entwerfe ich eine ähnlich lib in C# – es ist noch in den Anfängen, aber die nächsten Versionen werden die Kompilierung in .NET/VM IL ermöglichen oder vielleicht eine neue einfache VM wie muParser).

Eine andere interessante Sache ist NekoVM (es führt .n Bytecode-Dateien aus). Es ist ein Open-Source-Projekt in C geschrieben und es wird angenommen, dass seine Hauptsprache (.neko) von generiert wird Source-to-Source-Compiler Technologie. Im Geiste des letzten Themas siehe Haxe vom selben Autor (auch Open Source).

Wie Sie habe ich mich auch mit virtuellen Maschinen und Compilern beschäftigt, und ein gutes Buch, das ich empfehlen kann, ist Compiler-Design: Virtuelle Maschinen. Es beschreibt virtuelle Maschinen für imperative, funktionale, logische und objektorientierte Sprachen, indem es den Befehlssatz für jede VM zusammen mit einem Tutorial zum Kompilieren einer höheren Sprache für diese VM gibt. Ich habe die VM nur für die imperative Sprache implementiert und es war bereits eine sehr nützliche Übung.

Wenn Sie gerade erst anfangen, kann ich Ihnen eine weitere Ressource empfehlen PL101. Es handelt sich um eine Reihe interaktiver Lektionen in JavaScript, die Sie durch den Prozess der Implementierung von Parsern und Interpretern für verschiedene Sprachen führen.

Ich bin zu spät für die Party, aber ich würde Game Scripting Mastery empfehlen, das Ihre Hand nimmt, um eine funktionierende Skriptsprache und ihre VM von Null an zu schreiben. Und das mit sehr geringen Voraussetzungen.