Implementación de un intérprete de subproceso directo en un lenguaje funcional como OCaml

Question

En C/C++ puede implementar un intérprete de subprocesamiento directo con una matriz de punteros de función. La matriz representa su programa: una matriz de operaciones. Cada una de las funciones de operación debe terminar en una llamada a la función siguiente en la matriz, algo así como:

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

El BytecodeArray es una matriz de punteros de función. Si tuviéramos una matriz de estas operaciones op_plus, la longitud de la matriz determinaría la cantidad de veces que estaríamos incrementando el contenido de los datos. (por supuesto, necesitarías agregar algún tipo de operación de terminación como la última operación en la matriz).

¿Cómo se podría implementar algo así en OCaml? Puedo estar tratando de traducir este código demasiado literalmente: estaba usando una matriz OCaml de funciones como en C++. El problema con esto es que sigo terminando con algo como:

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

Dónde op_array se define una matriz en el ámbito arriba y luego redefinir lo que más tarde se llena con un montón de funciones op_plus ... sin embargo, la función op_plus usa la definición previa de op_array. Es un problema de huevos de pollo &.

Answer 1

Una de las opciones más (si el tamaño es conocido de antemano) - inicialmente llenar la matriz con las instrucciones de vacío:

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

Answer 2

No debe redefinir op_array, debe completarlo con instrucciones modificándolo en su lugar para que sea el mismo op_array al que ya se refieren sus funciones. Lamentablemente, no puede cambiar el tamaño de una matriz de forma dinámica en OCaml.

veo dos soluciones:

1) si no es necesario cambiar la secuencia de "instrucciones", definirlos en una recursión mutua con la matriz op_array. OCaml permite definir funciones y valores mutuamente recursivos que comienzan con la aplicación de un constructor. Algo así como:

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

2) o utilizar un direccionamiento indirecto adicional: hacer op_array una referencia a un conjunto de instrucciones, y se refieren en las funciones a (op_array) (PC + 1)!.. Más tarde, después de haber definido todas las instrucciones, puede hacer que op_array señale una matriz del tamaño correcto, con todas las instrucciones que desea.

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

Answer 3

Otra alternativa sería utilizar CPS y evitar matriz función explícita por completo. La optimización de llamada de cola todavía se aplica en este caso.

No sé cómo se genera el código, pero supongamos que no razonablemente, en algún momento tiene una serie de instrucciones de VM que desea preparar para su ejecución. Cada instrucción todavía se representa como una función, pero en lugar del contador del programa recibe la función de continuación.

Aquí es el ejemplo más sencillo:

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) 

uso (ver tipos inferidos):

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

ACTUALIZACIÓN:

Es fácil de introducir [condicional] ramificación en este modelo. if continuación se construye a partir de dos argumentos: iftrue-continuation y iffalse-continuation, pero tiene el mismo tipo que cualquier otra función de continuación. El problema es que no sabemos qué constituye estas continuaciones en caso de ramificación hacia atrás (hacia atrás, porque compilamos de la cola a la cabeza). Eso es fácil de superar con actualizaciones destructivas (aunque tal vez sea posible una solución más elegante si está compilando desde un lenguaje de alto nivel): simplemente deje "huecos" y llénelos más adelante cuando el compilador alcance el objetivo de sucursal.

aplicación de la muestra (he hecho uso de etiquetas de cadena en lugar de punteros de instrucción número entero, pero esto 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 

He usado dos pases para mayor claridad, pero es fácil ver que se puede hacerse en un solo pase.

Aquí es un bucle simple que puede ser compilado y ejecutado por el código de seguridad:

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

Ejecución de seguimiento:

# 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 

ACTUALIZACIÓN 2:

, la representación CPS En cuanto al rendimiento es probable que sea más rápido que basado en matriz, porque no hay indirección en caso de ejecución lineal. La función de continuación se almacena directamente en el cierre de instrucciones. En la implementación basada en arreglos, primero debe incrementar el contador del programa y realizar el acceso a la matriz (con una sobrecarga de control de límites adicionales).

He hecho algunos puntos de referencia para demostrarlo. Aquí es una implementación del intérprete de la serie basada en:

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 

Vamos a ver cómo se compara con el intérprete basado en CPS anterior (con todo el rastreo de depuración despojado, por supuesto). Usé el compilador nativo OCaml 3.12.0 en Linux/amd64. Cada programa se ejecutó 5 veces.

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

Por lo tanto, incluso en lazo cerrado, CPS tiene un rendimiento considerablemente mejor que la matriz. Si nos desenrolla bucle y reemplazamos uno sub instrucción con cinco, cifras cambian:

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

Es interesante que ambas implementaciones realidad golpearon OCaml intérprete de código de bytes. El siguiente bucle tarda 17 segundos para ejecutar en mi máquina:

for i = 500_000_000 downto 0 do() done