めざそう言語処理系の沼 〜shift/resetへの旅 〜 その3 トランポリン化

前回継続渡しスタイルで末尾再帰化したインタプリタにさらに手を加えてトランポリン化する話。

一般的に、トランポリン化は「末尾再帰のない言語でスタックオーバーフローを起こさずに深い再帰をシミュレートする」手法だと言える。再帰的な関数呼び出しを遅延的に捉えたthunkを返すようにし、whileループで返ってきた値がthunkなら実行し続け、thunkでないものが返ってきた時点で終了、という流れでスタックを消費せずに再帰的なプログラムが書ける。

しかしOCamlにはそもそも末尾再帰がある。スタックオーバーフローを起こしたくないからといってトランポリン化する必要はない。

なら何故トランポリン化するのかというと、evalとapply_contを使うたびに計算の途中経過を返すようにしておきたいからだ。

それもあって、今回もdefunctionalizationのお世話になる。具体的には相互再帰的関数呼び出しを無名関数として返すのではなく、代数的データ型で引数も含めて返すようにする。

前回とのコード差分：

Comparing v0.2...v0.3 · zehnpaard/kontlang · GitHub

変更したのはExecute.mlモジュールのみ。

まずはeval、apply_contが返すthunkを表すデータ型：

type t =
| Done of Val.t
| Eval of Env.t * Cont.t * Exp.t
| ApplyCont of Env.t * Cont.t * Val.t

次に呼び出す関数がない場合はDoneで値、ある場合はEval、ApplyContと必要な引数が返されるようにする。

eval関数：

let eval env cont = function
| Exp.Int n -> ApplyCont (env, cont, Val.Int n)
| Exp.Var s -> ApplyCont (env, cont, Env.find s env)
| Exp.Call (e, es) -> Eval (env, (Cont.Call (es, []) :: cont), e)

前回のようにapply_contやevalを相互再帰的に呼び出すかわりにExecute.t型を返す。

apply_contも似たような形に：

let apply_cont env cont v = match cont with
| [] -> Done v
| Cont.Call ([], vs) :: cont' -> (match List.rev (v::vs) with
  | Val.Op (_, fn) :: vs' -> ApplyCont (env, cont', (fn vs'))
  | _ -> failwith "Calling non-op in operator position")
| Cont.Call (e::es, vs) :: cont' -> Eval (env, (Cont.Call (es, v::vs) :: cont'), e)

継続が終端な場合はDoneを返す。

ループのためのtrampolineとそれを使ったrun関数：

let rec trampoline = function
| Done v -> v
| Eval (env, cont, e) -> trampoline @@ eval env cont e
| ApplyCont (env, cont, v) -> trampoline @@ apply_cont env cont v

let run e = trampoline (Eval (Builtins.load Env.empty, Cont.final, e))

trampolineの実装に末尾再帰を使っているが、そもそも末尾再帰のシミュレートが目的ではないので問題なし。また普通のトランポリン化だとeval、apply_contはthunkとして匿名関数を返し、trampolineではその匿名関数を呼び出すことが多いが、Done | Eval | ApplyContのコンストラクタを持つデータ型で表現している（前述のとおりdefunctionalizationという手法）。

今回は実装していないが、trampolineに手を加えると「実行ステップを一つずつ進めて、途中での継続や変数環境の状態を調べられる」インタプリタが書けたりする。今後インタプリタが複雑化してきたときにはデバッグ用にそんなモードを用意する予定。

例えばこんな変更が可能：

let inspect = function
| Done v -> ()
| Eval (env, cont, e) ->
    print_endline @@ Env.to_string env;
    print_endline @@ Cont.to_string cont;
    print_endline @@ Exp.to_string e;
    ignore @@ read_line ()
| ApplyCont (env, cont, v) ->
    print_endline @@ Env.to_string env;
    print_endline @@ Cont.to_string cont;
    print_endline @@ Val.to_string v;
    ignore @@ read_line ()

let rec trampoline_inspect = function
| Done v -> v
| Eval (env, cont, e) as x ->
    inspect x;
    trampoline_inspect @@ eval env cont e
| ApplyCont (env, cont, v) as x ->
    inspect x;
    trampoline_inspect @@ apply_cont env cont v

こうするとtrampoline_inspectが呼び出されるたびに現在のプログラムの状態が出力され、ユーザから何らかの入力を受けとってから次のステップを実行する。デバッグモードとしてなかなか有用（Env.to_stringやCont.to_stringを実装していないので現段階では動かないが・・・）

最後にeval_string：

let eval_string s =
  Lexing.from_string s
  |> Parser.f Lexer.f
  |> run
  |> Val.to_string

evalのかわりにrunを使うようになっただけ。これでインタプリタのトランポリン化が完了。

前回、今回と続いて、言語機能は加えずにインタプリタの実装を変更してきた。次回は真偽値、論理式、ifなどの機能を言語に追加する。