インタプリタとコンパイラの続き

「最初からごまかしていた点」を直した実装（のつもり）：

let run lang (`Prog(lang', f)) x =
  (* `Prog(lang', f)は言語lang'で書かれたプログラムf。xはfへの入力。*)
  if lang = lang' then f x else
  failwith "invalid program"

let interpreter mlang slang =
  (* 言語mlangで書かれた、slangのためのインタプリタ *)
  `Prog(mlang, fun sprog -> run slang sprog)

let compiler mlang slang tlang =
  (* 言語mlangで書かれた、slangからtlangへのコンパイラ *)
  `Prog(mlang, fun sprog -> `Prog(tlang, run slang sprog))

(* 簡単な例：
# run `M (interpreter `M `S) (`Prog(`S, fun x -> x + 1)) 2 ;;
- : int = 3
# run `T (run `M (compiler `M `S `T) (`Prog(`S, fun x -> x + 1))) 2 ;;
- : int = 3
*)

(* bonotake氏の例：
# let cprog = compiler `C `A `B ;; (* Cで書かれた、AからBへのコンパイラ *)
val cprog :
  [> `Prog of
       [> `C ] *
       (_[< `Prog of _[> `A ] * ('_a -> '_b) ] ->
        [> `Prog of [> `B ] * ('_a -> '_b) ]) ] =
  `Prog (`C, <fun>)
# let eprog = compiler `E `C `D ;; (* Eで書かれた、CからDへのコンパイラ *)
val eprog :
  [> `Prog of
       [> `E ] *
       (_[< `Prog of _[> `C ] * ('_a -> '_b) ] ->
        [> `Prog of [> `D ] * ('_a -> '_b) ]) ] =
  `Prog (`E, <fun>)
# let dprog = run `E eprog cprog ;; (* cprogをDへコンパイル *)
val dprog :
  [> `Prog of
       [> `D ] *
       (_[< `Prog of _[> `A ] * ('_a -> '_b) ] ->
        _[> `Prog of _[> `B ] * ('_a -> '_b) ]) ] =
  `Prog (`D, <fun>)
# let aprog = `Prog(`A, fun x -> x + 1) ;; (* λx.x+1を表すAのプログラム *)
val aprog : [> `Prog of [> `A ] * (int -> int) ] = `Prog (`A, <fun>)
# let bprog = run `D dprog aprog ;; (* aprogをBへコンパイル *)
val bprog : [ `Prog of _[> `B ] * (int -> int) ] = `Prog (`B, <fun>)
# run `B bprog 2 ;; (* bprogを実行 *)
- : int = 3
*)

追加。bonotake氏のもう一つの例。Mの上でTのインタプリタを動かし、その上でSのインタプリタを動かす。

# run `M (interpreter `M `T) (interpreter `T `S) (`Prog(`S, fun x -> x + 1)) 2 ;;
- : int = 3

余談。この手の話はマシン語がボトムに来て終わってしまいがちですが、実際はCPUの内部でも解釈実行やJITコンパイルをしているし、マイクロコードを解釈実行するハードウェアも「物理」によって解釈実行されているのではないかと。