Implementazione di un interprete a thread diretto in un linguaggio funzionale come OCaml

Question

In C/C++ è possibile implementare un interprete a thread diretto con una serie di puntatori di funzione. La matrice rappresenta il tuo programma: una serie di operazioni. Ciascuna delle funzioni operative deve terminare una chiamata alla funzione successiva nella matrice, qualcosa come:

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

Il BytecodeArray è un array di puntatori a funzione. Se avessimo un array di queste operazioni op_plus, la lunghezza dell'array determinerebbe il modo in cui incrementeremmo il contenuto dei dati. (ovviamente, avresti bisogno di aggiungere una sorta di operazione di chiusura come ultima operazione nell'array).

Come si potrebbe implementare qualcosa di simile in OCaml? Potrei provare a tradurre questo codice troppo alla lettera: stavo usando una matrice OCaml di funzioni come nel C++. Il problema di questo è che continuo finire con qualcosa come:

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) ;; 

Dove op_array è una matrice definita nel suddetto scopo e quindi ridefinire successivamente per essere riempito con un gruppo di funzioni op_plus ... tuttavia, la funzione op_plus usa la definizione precedente di op_array. È un problema di uova di pollo &.

Answer 1

Un'altra opzione (se la dimensione è noto in anticipo) - inizialmente riempire l'array con istruzioni nulli:

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

Answer 2

Non è necessario ridefinire il numero op_array, è necessario aggiungerlo con le istruzioni modificandolo in modo che sia lo stesso op_array a cui si riferiscono già le funzioni. Sfortunatamente, non è possibile modificare dinamicamente la dimensione di un array in OCaml.

Vedo due soluzioni:

1) se non è necessario modificare la sequenza delle "istruzioni", li definisce in una ricorsione mutua con la matrice op_array. OCaml consente funzioni e valori reciprocamente ricorsivi che iniziano con l'applicazione di un costruttore da definire. Qualcosa di simile:

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

2) o utilizzare un riferimento indiretto aggiuntivo: fare op_array un riferimento ad una serie di istruzioni, e si riferiscono nelle funzioni a (op_array) (pc + 1)!.. Successivamente, dopo aver definito tutte le istruzioni, è possibile effettuare il punto op_array in un array della giusta dimensione, completo delle istruzioni che si desidera.

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

Answer 3

Un'altra alternativa sarebbe utilizzando CPS, evitando esplicito matrice funzione del tutto. In questo caso vale ancora l'ottimizzazione della coda.

Non so come si genera il codice, ma facciamo un'ipotesi non irragionevole che a un certo punto si disponga di un array di istruzioni VM che si desidera preparare per l'esecuzione. Ogni istruzione è ancora rappresentata come una funzione, ma invece del contatore del programma riceve la funzione di continuazione.

Ecco l'esempio più semplice:

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 (sguardo alle tipologie dedurre):

# #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:

E 'facile introdurre [condizionale] ramificazione in questo modello. La continuazione di if è composta da due argomenti: iftrue-continuation e iffalse-continuation, ma ha lo stesso tipo di ogni altra funzione di continuazione. Il problema è che non sappiamo cosa costituisca queste continuazioni in caso di ramificazione all'indietro (all'indietro, perché compiliamo da coda a testa). Questo è facile da superare con aggiornamenti distruttivi (anche se è possibile che una soluzione più elegante sia possibile se si sta compilando da un linguaggio di alto livello): basta "buchi" e riempirli più tardi quando il compilatore raggiunge il target di diramazione.

implementazione del campione (ho fatto uso di etichette stringa invece di puntatori istruzioni integer, ma questo poco importa):

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 

Ho usato due passaggi per chiarezza, ma è facile vedere che si può essere fatto in un solo passaggio

Ecco un semplice ciclo che può essere compilato ed eseguito dal codice di cui sopra:

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

traccia di esecuzione:

# 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:

delle prestazioni, la rappresentazione CPS è probabile che sia più veloce rispetto alla matrice, perché non c'è riferimento indiretto in caso di esecuzione lineare. La funzione di continuazione viene memorizzata direttamente nella chiusura dell'istruzione. Nell'implementazione basata su array, deve prima incrementare il contatore del programma ed eseguire l'accesso alla matrice (con un limite aggiuntivo che controlla l'overhead).

Ho fatto alcuni benchmark per dimostrarlo. Ecco un'implementazione di interprete basata su array:

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 

Vediamo come si confronta con l'interprete CPS-based sopra (con tutte le analisi del debug spogliato, ovviamente). Ho usato il compilatore nativo di OCaml 3.12.0 su Linux/amd64. Ogni programma è stato eseguito 5 volte.

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

Quindi, anche in loop ristretto, CPS offre prestazioni notevolmente migliori rispetto all'array. Se srotoliamo ciclo e sostituire uno sub istruzione con cinque, figure cambiano:

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

E 'interessante il fatto che entrambe le implementazioni effettivamente battere OCaml bytecode interprete. Il seguente ciclo dura 17 secondi per l'esecuzione sulla mia macchina:

for i = 500_000_000 downto 0 do() done