Implementierung eines Direct-Threaded-Interpreters in einer funktionalen Sprache wie OCaml

Question

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 Betriebsfunktionen müssen in einem Aufruf an die nächste Funktion in der Matrix beenden, so etwas wie:

void op_plus(size_t pc, uint8_t* data) { 
    *data += 1; 
    BytecodeArray[pc+1](pc+1, data); //call the next operation in the array 
} 

Die 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 implementieren? 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 wie mit etwas enden halten:

let op_plus pc data = Printf.printf "pc: %d, data_i: %d \n" pc data; 
         let f = (op_array.(pc+1)) in   
         f (pc+1) (data+1) ;; 

Wo op_array ein Array im Rahmen oben definiert ist und es dann später neu zu definieren mit einem Bündel von op_plus Funktionen gefüllt werden ... aber Die Funktion op_plus verwendet die vorherige Definition von op_array. Es ist ein Huhn & Ei Problem.

Answer 1

Eine weitere Option (wenn die Größe vorher bekannt ist) - zunächst das Array mit Leeren Anweisungen füllen:

let op_array = Array.create size (fun _ _ -> assert false) 
let op_plus = ... 
let() = op_array.(0) <- op_plus; ... 

Answer 2

Sie sollten op_array nicht neu definieren, Sie sollten es mit Anweisungen ausfüllen, indem Sie es an Ort und Stelle ändern, so dass es dasselbe ist op_array, 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 in einem 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:

let rec op_plus pc data = ... 
and op_array = [| ... |] 

2) oder eine zusätzliche Indirektion verwenden: op_array ein Verweis auf eine Reihe von Anweisungen machen, und bezieht sich in den Funktionen (op_array) (PC + 1)!.. Später, nachdem Sie alle Anweisungen definiert haben, können Sie op_array auf ein Array der richtigen Größe zeigen, das die von Ihnen beabsichtigten Anweisungen enthält.

let op_array = ref [| |] ;; 
let op_plus pc data = ... ;; 
op_array := [| ... |] ;; 

Answer 3

Eine weitere Alternative wäre CPS verwenden und ganz explizite Funktion Array zu vermeiden. In diesem Fall gilt weiterhin die Tail-Call-Optimierung.

Ich weiß nicht, wie Sie den Code generieren, aber lassen Sie uns nicht unvernünftig davon ausgehen, dass Sie irgendwann eine Reihe von VM-Anweisungen haben, die Sie für die 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:

type opcode = Add of int | Sub of int 

let make_instr opcode cont = 
    match opcode with 
    | Add x -> fun data -> Printf.printf "add %d %d\n" data x; cont (data + x) 
    | Sub x -> fun data -> Printf.printf "sub %d %d\n" data x; cont (data - x) 

let compile opcodes = 
    Array.fold_right make_instr opcodes (fun x -> x) 

Usage (Blick auf abgeleitete Typen):

# #use "cpsvm.ml";; 
type opcode = Add of int | Sub of int 
val make_instr : opcode -> (int -> 'a) -> int -> 'a = <fun> 
val compile : opcode array -> int -> int = <fun> 
# let code = [| Add 13; Add 42; Sub 7 |];; 
val code : opcode array = [|Add 13; Add 42; Sub 7|] 
# let fn = compile code;; 
val fn : int -> int = <fun> 
# fn 0;; 
add 0 13 
add 13 42 
sub 55 7 
- : int = 48 

UPDATE:

Es ist einfach [bedingt] in diesem Modell Verzweigung einzuführen. if Fortsetzung wird aus zwei Argumenten konstruiert: iftrue-Fortsetzung und iffalse-Fortsetzung, aber hat 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 das Verzweigungsziel vom Compiler erreicht wird.

Beispielimplementierung (ich habe die Verwendung von String-Labels anstelle von ganzzahligen Befehlszeiger gemacht, aber das spielt kaum eine Rolle):

type label = string 

type opcode = 
     Add of int | Sub of int 
    | Label of label | Jmp of label | Phi of (int -> bool) * label * label 

let make_instr labels opcode cont = 
    match opcode with 
    | Add x -> fun data -> Printf.printf "add %d %d\n" data x; cont (data + x) 
    | Sub x -> fun data -> Printf.printf "sub %d %d\n" data x; cont (data - x) 
    | Label label -> (Hashtbl.find labels label) := cont; cont 
    | Jmp label -> 
     let target = Hashtbl.find labels label in 
     (fun data -> Printf.printf "jmp %s\n" label; !target data) 
    | Phi (cond, tlabel, flabel) -> 
     let tcont = Hashtbl.find labels tlabel 
     and fcont = Hashtbl.find labels flabel in 
     (fun data -> 
      let b = cond data in 
      Printf.printf "branch on %d to %s\n" 
       data (if b then tlabel else flabel); 
      (if b then !tcont else !fcont) data) 

let compile opcodes = 
    let id = fun x -> x in 
    let labels = Hashtbl.create 17 in 
    Array.iter (function 
     | Label label -> Hashtbl.add labels label (ref id) 
     | _ ->()) 
     opcodes; 
    Array.fold_right (make_instr labels) opcodes id 

ich zwei Pässe für Klarheit verwendet habe, aber es ist leicht zu sehen, dass es in einem Durchgang durchgeführt werden.

Hier ist eine einfache Schleife, die oben durch den Code kompiliert und ausgeführt werden können:

let code = [| 
    Label "entry"; 
    Phi (((<) 0), "body", "exit"); 
    Label "body"; 
    Sub 1; 
    Jmp "entry"; 
    Label "exit" |] 

Execution Trace:

# let fn = compile code;; 
val fn : int -> int = <fun> 
# fn 3;; 
branch on 3 to body 
sub 3 1 
jmp entry 
branch on 2 to body 
sub 2 1 
jmp entry 
branch on 1 to body 
sub 1 1 
jmp entry 
branch on 0 to exit 
- : int = 0 

UPDATE 2:

Performance-weise, CPS Darstellung ist wahrscheinlich schneller als Array-basierte, weil es keine indirekte Richtung im Falle der linearen Ausführung gibt. Die Fortsetzungsfunktion wird direkt im Anweisungsabschluss gespeichert. In der Array-basierten Implementierung muss der Programmzähler zuerst inkrementiert werden und der Array-Zugriff (mit einem Extra-Überschreibungs-Overhead) zuerst durchgeführt werden.

Ich habe einige Benchmarks gemacht, um es zu demonstrieren. Hier ist eine Implementierung von Array-basierten Interpreter:

type opcode = 
     Add of int | Sub of int 
    | Jmp of int | Phi of (int -> bool) * int * int 
    | Ret 

let compile opcodes = 
    let instr_array = Array.make (Array.length opcodes) (fun _ data -> data) 
    in Array.iteri (fun i opcode -> 
     instr_array.(i) <- match opcode with 
     | Add x -> (fun pc data -> 
      let cont = instr_array.(pc + 1) in cont (pc + 1) (data + x)) 
     | Sub x -> (fun pc data -> 
      let cont = instr_array.(pc + 1) in cont (pc + 1) (data - x)) 
     | Jmp pc -> (fun _ data -> 
      let cont = instr_array.(pc) in cont (pc + 1) data) 
     | Phi (cond, tbranch, fbranch) -> 
      (fun _ data -> 
       let pc = (if cond data then tbranch else fbranch) in 
       let cont = instr_array.(pc) in 
       cont pc data) 
     | Ret -> fun _ data -> data) 
     opcodes; 
    instr_array 

let code = [| 
    Phi (((<) 0), 1, 3); 
    Sub 1; 
    Jmp 0; 
    Ret 
    |] 

let() = 
    let fn = compile code in 
    let result = fn.(0) 0 500_000_000 in 
    Printf.printf "%d\n" result 

Mal sehen, wie es auf die CPS-basierten Interpreter vergleicht oben (mit allen Debug-gestrippt Tracing, natürlich). Ich habe OCaml 3.12.0 nativen Compiler auf Linux/AMD64 verwendet. Jedes Programm wurde 5 Mal ausgeführt.

array: mean = 13.7 s, stddev = 0.24 
CPS: mean = 11.4 s, stddev = 0.20 

Also auch in engen Schleife führt CPS wesentlich besser als Array. Wenn wir Schleife abrollen und mit fünf eine sub Anweisung ersetzen, Zahlen ändern:

array: mean = 5.28 s, stddev = 0.065 
CPS: mean = 4.14 s, stddev = 0.309 

Es ist interessant, dass beide Implementierungen tatsächlich OCaml Bytecode-Interpreter schlagen. Die folgende Schleife dauert 17 Sekunden auf meinem Rechner auszuführen:

for i = 500_000_000 downto 0 do() done