Implémentation d'un interpréteur à thread direct dans un langage fonctionnel tel que OCaml

Question

En C/C++, vous pouvez implémenter un interpréteur à thread direct avec un tableau de pointeurs de fonction. Le tableau représente votre programme - un tableau d'opérations. Chacune des fonctions d'opération doit se terminer par un appel à la fonction suivante dans le tableau, quelque chose comme:

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

Le BytecodeArray est un tableau de pointeurs de fonction. Si nous avions un tableau de ces opérations op_plus, alors la longueur du tableau déterminerait la fréquence d'incrémentation du contenu des données. (bien sûr, vous devez ajouter une sorte d'opération de terminaison comme dernière opération dans le tableau).

Comment pourrait-on mettre en œuvre quelque chose comme ça dans OCaml? Je peux essayer de traduire ce code trop littéralement: j'utilisais un tableau de fonctions OCaml comme dans le C++. Le problème avec ce que je continue à se retrouver avec quelque chose comme:

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

Où op_array est un tableau défini dans le champ ci-dessus, puis redéfinir ultérieurement être rempli d'un tas de fonctions op_plus ... Cependant, la fonction op_plus utilise la définition précédente de op_array. C'est un problème d'oeuf de poulet &.

Answer 1

Une option plus (si la taille est connue à l'avance) - remplir d'abord le tableau avec des instructions vides:

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

Answer 2

Vous ne devez pas redéfinir op_array, vous devez le remplir avec des instructions en le modifiant pour qu'il corresponde à la même chose que vos fonctions déjà référencées op_array. Malheureusement, vous ne pouvez pas modifier dynamiquement la taille d'un tableau dans OCaml.

Je vois deux solutions:

1) si vous n'avez pas besoin de changer la séquence des « instructions », les définir dans une récursion mutuelle avec le tableau op_array. OCaml permet de définir des fonctions et des valeurs mutuellement récursives qui commencent par l'application d'un constructeur. Quelque chose comme:

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

2) Ou utiliser une indirection supplémentaire: faire op_array une référence à un tableau d'instructions, et reportez-vous aux fonctions (op_array) (pc + 1)!.. Plus tard, après avoir défini toutes les instructions, vous pouvez faire op_array point à un tableau de la bonne taille, plein des instructions que vous avez l'intention.

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

Answer 3

Une autre alternative serait l'utilisation CPS et éviter tableau de fonction explicite tout à fait. L'optimisation de l'appel de queue s'applique toujours dans ce cas. Je ne sais pas comment générer le code, mais supposons à un moment donné que vous avez un tableau d'instructions VM que vous voulez préparer pour l'exécution. Chaque instruction est toujours représentée comme une fonction, mais à la place du compteur de programme, elle reçoit la fonction de continuation.

Voici l'exemple le plus simple:

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) 

Utilisation (regardez types inférées):

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

MISE À JOUR:

Il est facile d'introduire [conditionnelle] ramification dans ce modèle. if continuation est construit à partir de deux arguments: iftrue-continuation et iffalse-continuation, mais a le même type que toutes les autres fonctions de continuation. Le problème est que nous ne savons pas ce qui constitue ces suites en cas de ramification vers l'arrière (en arrière, car nous compilons de la queue à la tête). C'est facile à surmonter avec des mises à jour destructrices (bien que peut-être une solution plus élégante est possible si vous compilez depuis un langage de haut niveau): laissez simplement des "trous" et remplissez-les plus tard lorsque le compilateur atteint la cible.

exemple d'implémentation (je l'ai fait usage d'étiquettes de chaîne au lieu de pointeurs d'instruction entier, mais cela n'a guère d'importance):

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 

Je l'ai utilisé deux passes pour plus de clarté, mais il est facile de voir qu'il peut être fait en un seul passage.

Voici une boucle simple qui peut être compilé et exécuté par le code ci-dessus:

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

trace d'exécution:

# 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 

MISE À JOUR 2:

Côté performance, représentation CPS est susceptible d'être plus rapide que que basé sur un tableau, car il n'y a pas d'indirection en cas d'exécution linéaire. La fonction de continuation est stockée directement dans la fermeture de l'instruction. Dans l'implémentation basée sur le tableau, il doit d'abord incrémenter le compteur de programme et effectuer l'accès au tableau (avec un surcoût de vérification des bornes supplémentaires) en premier.

J'ai fait quelques benchmarks pour le démontrer. Voici une implémentation d'interprète basée sur la baie:

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 

Voyons voir comment il se compare à l'interprète à base CPS ci-dessus (avec tous debug traçage dépouillé, bien sûr). J'ai utilisé le compilateur natif OCaml 3.12.0 sous Linux/amd64. Chaque programme a été exécuté 5 fois.

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

Ainsi, même en boucle serrée, le CPS fonctionne considérablement mieux que le réseau. Si nous déroulons boucle et remplaçons une instruction sub avec cinq, les chiffres changent:

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

Il est intéressant de noter que les deux implémentations ont battu en fait OCaml interprète bytecode. La boucle suivante prend 17 secondes pour exécuter sur ma machine:

for i = 500_000_000 downto 0 do() done