インタプリタとコンパイラ

僕も「インタプリタ＝コンパイラ」はさすがに言明自体が型エラーだと思いますが（終域が一致していない）、「インタプリタ≒コンパイラ＋実行系」ならまあOKかも…？

より正確には、「言語Xで記述されたプログラムPを実行した結果」をrun_X(P)と書くことにすると、「言語Sのための、言語Mで記述されたインタプリタ」とはrun_M( I(P) ) = run_S(P)なるIのことで、「言語Mで記述された、言語Sから言語Tへのコンパイラ」とはrun_T( run_M( C(P) ) ) = run_S(P)なるCのことなので、T=M（たとえば機械語）とすれば、run_M( I(P) ) = run_S(P) = run_M( run_M( C(P) ) )となって、Iとrun_M o Cの意味が同値に。T=Mでない場合も、TやMのプログラムを実行する方法を明示すれば同様かと。

余談ですが、小さい頃に読んだ本に「コンパイラは高級言語のプログラムをまとめてマシン語に翻訳します。一方で、インタプリタは一ステップごとに翻訳しながら実行します。」等と書いてあって、子供心に不思議に（というか何かおかしいと）思いました。

追記：（bonotake氏のものと違って）面白くも何ともないエセ「実装」例：

let run_s = function
  | `Source s -> `Executed s
  | _ -> failwith "not an S program"
let run_t = function
  | `Compiled s -> `Executed s
  | _ -> failwith "not a T program"
let run_m = function
  | `Interpret (`Source s) -> `Executed s
  | `Compile (`Source s) -> `Compiled s
  | _ -> failwith "not an M program"

実行例：

# run_m (`Interpret (`Source "hello")) = run_t (run_m (`Compile (`Source "hello"))) ;;
- : bool = true

追記２：大昔（十数年前？）の某所のコンパイラ演習（by 某部分評価やリフレクションの専門家の方）では、ほぼ全時間をかけてインタプリタを書き、最終回に「Pを与えられて、I(P)と同じ動作をするアセンブリを生成するものがコンパイラです」と言って終わった、という話も聞きます。

追記３：上のエセ実装があまりにもエセすぎたので、なかったことにしてやり直し：

let run lang (`Prog(lang', f)) =
  (* `Prog(lang, f)は「実行すると結果がf ()の値になる、言語langのプログラム」（手抜き） *)
  if lang = lang' then f () else
  failwith "invalid program"

let interpreter mlang slang sprog = (* mlangで記述された、sprogをslangで解釈するインタプリタ *)
  `Prog(mlang, fun () -> run slang sprog)

let compiler mlang slang tlang sprog = (* mlangで記述された、sprogをslangからtlangへ翻訳するコンパイラ *)
  `Prog(mlang, fun () -> `Prog(tlang, fun () -> run slang sprog))

簡単な例：

# run `M (interpreter `M `S (`Prog(`S, fun () -> "hello"))) ;;
- : string = "hello"
# run `T (run `M (compiler `M `S `T (`Prog(`S, fun () -> "hello")))) ;;
- : string = "hello"

bonotake氏の例：

# let cprog = compiler `C `A `B (`Prog(`A, fun () -> "hello")) ;;
val cprog :
  [> `Prog of [> `C ] * (unit -> [> `Prog of [> `B ] * (unit -> string) ]) ] =
  `Prog (`C, <fun>)
# let eprog = compiler `E `C `D cprog ;;
val eprog :
  [> `Prog of
       [> `E ] *
       (unit ->
        [> `Prog of
             [> `D ] * (unit -> [> `Prog of [> `B ] * (unit -> string) ]) ]) ] =
  `Prog (`E, <fun>)
# let dprog = run `E eprog ;;
val dprog :
  [> `Prog of [> `D ] * (unit -> [> `Prog of [> `B ] * (unit -> string) ]) ] =
  `Prog (`D, <fun>)
# let bprog = run `D dprog ;;
val bprog : [> `Prog of [> `B ] * (unit -> string) ] = `Prog (`B, <fun>)
# run `B bprog ;;
- : string = "hello"

もちろん、一連の話は最初からごまかしている点があって、インタプリタやコンパイラの入力であるプログラムの与えられるタイミングがおかしいです。