In C / C ++ können Sie einen direkten Thread-Interpreter mit einem Array von Funktionszeigern implementieren. Das Array repräsentiert Ihr Programm - eine Reihe von Operationen. Jede der Operationsfunktionen muss mit einem Aufruf der nächsten Funktion im Array enden, etwa wie folgt:
%Vor%Das BytecodeArray ist ein Array von Funktionszeigern. Wenn wir ein Array dieser op_plus-Operationen hätten, würde die Länge des Arrays bestimmen, wie oft wir den Inhalt der Daten erhöhen würden. (Sie müssen natürlich eine abschließende Operation als letzte Operation im Array hinzufügen.)
Wie würde man so etwas in OCaml umsetzen? Ich könnte versuchen, diesen Code zu wörtlich zu übersetzen: Ich benutzte ein OCaml Array von Funktionen wie in C ++. Das Problem dabei ist, dass ich immer wieder mit etwas wie:
fertig werde %Vor%Dabei ist op_array ein Array, das im obigen Bereich definiert ist und später neu definiert wird, um mit einer Reihe von op_plus-Funktionen gefüllt zu werden ... die Funktion op_plus verwendet jedoch die vorherige Definition von op_array. Es ist ein Problem mit Hühnchen und Ei.
Eine andere Alternative wäre die Verwendung von CPS und die Vermeidung von explizitem Funktionsarray. In diesem Fall gilt weiterhin die Tail Call-Optimierung.
Ich weiß nicht, wie Sie den Code generieren, aber machen wir uns keine unangemessene Annahme, dass Sie irgendwann ein Array von VM-Anweisungen haben, die Sie zur Ausführung vorbereiten möchten. Jeder Befehl wird immer noch als Funktion dargestellt, aber anstelle des Programmzählers erhält er eine Fortsetzungsfunktion.
Hier ist das einfachste Beispiel:
%Vor%Verwendung (siehe abgeleitete Typen):
%Vor%UPDATE:
Es ist einfach, [bedingte] Verzweigungen in diesem Modell einzuführen. if continuation wird aus zwei Argumenten konstruiert: iftrue-continuation und iffalse-continuation, hat aber den gleichen Typ wie jede andere Fortsetzungsfunktion. Das Problem ist, dass wir nicht wissen, was diese Fortsetzungen im Falle einer Rückwärtsverzweigung ausmacht (rückwärts, weil wir von Schwanz zu Kopf kompilieren). Das ist leicht mit destruktiven Updates zu bewältigen (obwohl eine elegantere Lösung möglich ist, wenn Sie aus einer höheren Sprache kompilieren): lassen Sie einfach "Löcher" und füllen Sie sie später, wenn der Compiler das Verzweigungsziel erreicht.
Beispielimplementierung (Ich habe String-Labels anstelle von Integer-Instruction-Zeigern verwendet, aber das spielt kaum eine Rolle):
%Vor%Ich habe zwei Durchgänge aus Gründen der Übersichtlichkeit verwendet, aber es ist leicht zu sehen, dass dies in einem Durchgang möglich ist.
Hier ist eine einfache Schleife, die mit dem obigen Code kompiliert und ausgeführt werden kann:
%Vor%Ausführungsablauf:
%Vor%UPDATE 2:
Im Hinblick auf die Leistung ist die CPS-Darstellung wahrscheinlich schneller als Array-basiert, da es bei linearer Ausführung keine Indirektion gibt. Die Fortsetzungsfunktion wird direkt im Anweisungsabschluss gespeichert. In der array-basierten Implementierung muss der Programmzähler inkrementiert werden und zuerst der Array-Zugriff (mit einem zusätzlichen Überschreibungs-Overhead) durchgeführt werden.
Ich habe einige Benchmarks gemacht, um das zu demonstrieren. Hier ist eine Implementierung eines Array-basierten Interpreters:
%Vor%Schauen wir uns mal an, wie es mit dem CPS-basierten Interpreter oben verglichen wird (natürlich ohne die Debug-Verfolgung). Ich habe OCaml 3.12.0 nativen Compiler auf Linux / AMD64 verwendet. Jedes Programm wurde 5 Mal ausgeführt.
%Vor% Selbst im Tight-Loop-Modus schneidet CPS deutlich besser ab als Array. Wenn wir die Schleife auflösen und einen sub -Befehl durch fünf ersetzen, ändern sich die Zahlen:
Es ist interessant, dass beide Implementierungen den OCaml-Bytecode-Interpreter schlagen. Die folgende Schleife benötigt 17 Sekunden, um auf meinem Rechner ausgeführt zu werden:
%Vor% Sie sollten op_array nicht neu definieren, Sie sollten es mit Anweisungen füllen, indem Sie es an Ort und Stelle so ändern, dass es dasselbe op_array ist, auf das sich Ihre Funktionen bereits beziehen. Leider können Sie die Größe eines Arrays in OCaml nicht dynamisch ändern.
Ich sehe zwei Lösungen:
1) Wenn Sie die Reihenfolge der "Anweisungen" nicht ändern müssen, definieren Sie sie in einer gegenseitigen Rekursion mit dem Array op_array . OCaml erlaubt es gegenseitig rekursive Funktionen und Werte, die mit der Anwendung eines Konstruktors beginnen, zu definieren. Etwas wie:
2) Oder verwenden Sie eine zusätzliche Indirektion: Machen Sie op_array zu einem Verweis auf ein Array von Anweisungen und verweisen Sie in den Funktionen auf (! op_array). (pc + 1). Später, nachdem Sie alle Anweisungen definiert haben, können Sie op_array auf ein Array der richtigen Größe mit den von Ihnen gewünschten Anweisungen setzen.
Tags und Links functional-programming ocaml interpreter