Implementacja interpretera z tłumaczeniem bezpośrednim w języku funkcjonalnym, takim jak OCaml

Question

W języku C/C++ można zaimplementować bezpośredni interpreter gwintów z tablicą wskaźników funkcji. Tablica reprezentuje Twój program - tablicę operacji. Każda z funkcji operacja musi zakończyć się wezwaniem do następnej funkcji w tablicy, coś jak:

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

The BytecodeArray jest tablicą wskaźników funkcji. Gdybyśmy mieli tablicę tych operacji op_plus, to długość tablicy określałaby, w jaki sposób będziemy zwiększać zawartość danych. (oczywiście, musisz dodać operację kończącą jako ostatnią operację w tablicy).

Jak można wprowadzić coś takiego w OCaml? Być może próbuję tłumaczyć ten kod zbyt dosłownie: Używałem OCaml Array funkcji jak w C++. Problem z tym jest to, że Ciągle kończący się z czymś takim:

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

Gdzie op_array jest tablicą z definicją zawartą w powyższym zakresie, a następnie zdefiniować ją później być wypełnione z wieloma funkcjami op_plus ... jednak, funkcja op_plus używa poprzedniej definicji op_array. To problem z kurczakiem &.

Answer 1

Jeszcze jedna opcja (jeśli rozmiar jest znany wcześniej) - początkowo wypełnić tablicę z pustych instrukcji:

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

Answer 2

Nie powinieneś redefiniować op_array, powinieneś wypełnić instrukcje, modyfikując je na miejscu tak, aby były takie same, op_array, do których twoje funkcje już się odnoszą. Niestety nie można zmienić rozmiaru tablicy dynamicznie w OCaml.

Widzę dwa rozwiązania:

1) czy nie trzeba zmienić kolejność „instrukcji”, zdefiniować je we wzajemnej rekursji z tablicy op_array. OCaml pozwala na wzajemnie rekurencyjne funkcje i wartości, które zaczynają się od zdefiniowania zdefiniowanego konstruktora. Coś jak:

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

2) albo użyć dodatkowego zadnie: make op_array odniesienie do tablicy instrukcji, i odnoszą się do funkcji (op_array) (PC + 1)!.. Później, po zdefiniowaniu wszystkich instrukcji, możesz ustawić op_array na tablicę o odpowiednim rozmiarze, pełną instrukcji, które zamierzasz.

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

Answer 3

Inną alternatywą byłoby za pomocą CPS i uniknąć wyraźnego tablicę funkcji całkowicie. Optymalizacja połączeń z ogonami nadal obowiązuje w tym przypadku.

Nie wiem, jak wygenerować kod, ale załóżmy, że nie ma nieuzasadnionego założenia, że ​​w pewnym momencie masz zestaw instrukcji VM, które chcesz przygotować do wykonania. Każda instrukcja jest nadal reprezentowana jako funkcja, ale zamiast licznika programu otrzymuje funkcję kontynuacji.

Oto najprostszy przykład:

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 (spojrzenie na uzyskanymi typów):

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

Łatwo wprowadzić [warunkowy] rozgałęzienia w tym modelu. if kontynuacja jest zbudowana z dwóch argumentów: iftrue - kontynuacja i iffalse - kontynuacja, ale ma ten sam typ, co każda inna funkcja kontynuacji. Problem polega na tym, że nie wiemy, co stanowi kontynuację w przypadku odgałęzienia wstecznego (wstecz, ponieważ kompilujemy od ogona do głowy). Łatwo to pokonać poprzez destrukcyjne aktualizacje (choć być może bardziej eleganckie rozwiązanie jest możliwe, jeśli kompilujesz z języka wysokiego poziomu): po prostu zostaw "otwory" i wypełnij je później, gdy kompilator osiągnie cel oddziału.

Przykładowa realizacja (Zrobiłem stosowanie etykiet smyczkowych zamiast wskazówek instrukcji całkowitą, ale to nie ma znaczenia):

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 

Użyłem dwóch przejść dla jasności, ale to łatwo zauważyć, że może zrobić za jednym razem.

Oto prosty pętli, które mogą być tworzone i realizowane przez powyższym kodzie:

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

ślad Wykonanie:

# 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-mądry, reprezentacja CPS Prawdopodobnie będzie to szybsze niż oparte na tablicy, ponieważ w przypadku wykonywania liniowego nie ma żadnego kierunku. Funkcja kontynuacji jest przechowywana bezpośrednio w zamknięciu instrukcji. W implementacji opartej na tablicy musi najpierw zwiększyć licznik programu i wykonać dostęp do macierzy (z dodatkowym obciążeniem sprawdzania ograniczeń).

Zrobiłem kilka punktów odniesienia, aby to pokazać. Oto implementacja interpretera tablicy opartej:

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 

Zobaczmy jak to porównać do tłumacza CPS opartej wyżej (z całym śledzenie debugowania usuwane, oczywiście). Użyłem natywnego kompoma OCaml 3.12.0 na Linux/amd64. Każdy program był uruchamiany 5 razy.

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

Więc nawet w ciasnej pętli CPS działa znacznie lepiej niż tablica. Jeśli mamy rozwinąć pętlę i zastąpienie jednego sub dyspozycję z pięciu, zmień dane:

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

To ciekawe, że obie implementacje faktycznie pokonać SML kodu bajtowego tłumacza. Poniższa pętla trwa 17 sekund, aby wykonać na moim komputerze:

for i = 500_000_000 downto 0 do() done