めざそう言語処理系の沼 〜shift/resetへの旅 〜 その２ 継続渡しスタイル

前回に続いて、機能としては整数と四則演算だけのインタプリタの話。

今回は機能はそのままで、式を評価して値を返すeval関数を継続渡しスタイルに変換する。

そもそも継続渡しスタイルだと何が嬉しいのか。

インタプリタの実行手順を考えると、関数呼び出しを評価する時：

let rec eval env = function
...
| Exp.Call (e, es) -> (match eval env e with
  | Val.Op (_, fn) -> fn @@ List.map (eval env) es

オペレータやオペランドがeval env ...で評価された後に何を実行するか（次はオペランドを一つ評価するのか、あるいはすべてのオペランドが評価し終わってオペレータを適用する段階なのか）は、インタプリタのスタックを巻き戻してeval呼び出し元のコンテキストに戻ってみないとわからない。

ここで二つの問題が生じている。一つはコンテキストを保持するためにスタックが消費されていること。もう一つはコンテキストの情報が「ホスト言語のスタック」に保持されているせいでインタプリタが自在にコンテキストを扱えないこと。

最初の問題はスタックオーバーフローを起こす要因となる。この情報をデータ化してしまえば、スタックをどんどん追加しない末尾再帰の形に持っていける。

二番目の問題に関しては、この「コンテキストの情報」をインタプリタが扱えるようにしないと、「コンテキストの破棄」である例外や「複数コンテキストを交互に実行」という並行処理などの言語機能が実装しにくい。

継続を取り出してデータ化し、インタプリタ自体は必ず末尾再帰するように変更することで、このコンテキストをいろいろといじれるようになる。その最たる例が「言語機能として継続を扱えるようにする」ことで、ユーザ側で例外や並行処理を実装できるようになる。

OCamlでは関数は第１級の存在なので、継続も無名関数として表現してもいいのだが、限定継続として中身をいじったりしたいのと、計算の途中で継続を文字列として出力したりしたくなるので、代数的データ型として定義しておく。ちなみにこういう「高階関数を代数的データ型として表す」手法をdefunctionalizationというらしい。

前回とのコード差分：

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

ポイントとしては、まず継続をCont.mlでデータ型として定義：

type cont =
| Call of Exp.t list * Val.t list

type t = cont list

let final = []

現在の非常に簡単な言語だと継続が必要になるのは関数呼び出しの時だけ。「まだ評価していない式」のリストと「評価済みの値」のリストを持つCont.Callが唯一のコンストラクタであるCont.contが定義されている。

実際の継続を表すCont.t型はCont.cont list。空のリストが継続の終端で、式を評価して値が出た時点で継続が空リストならプログラムは終了。

この継続を踏まえてExecute.mlも変更：

let rec eval env cont = function
| Exp.Int n -> apply_cont env cont @@ Val.Int n
| Exp.Var s -> apply_cont env cont @@ Env.find s env
| Exp.Call (e, es) -> eval env (Cont.Call (es, []) :: cont) e
and apply_cont env cont v = match cont with
| [] -> v
| Cont.Call ([], vs) :: cont' -> (match List.rev (v::vs) with
  | Val.Op (_, fn) :: vs' -> apply_cont 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

前回はevalだけだったが、今回はevalとapply_contの相互再帰になっている。

Exp.IntとExp.Varは式評価時に継続は追加されず、値をそのまま今までの継続に渡す形でapply_contが呼ばれる。Exp.Callの時だけ、まずオペランドのリストを持ったCont.Callが継続に追加された上でオペレータだけがevalを再帰呼び出しすることで評価される。

apply_contでは継続の終端である空リストかCont.Callが先頭にあるか、Cont.Callがある場合、未評価の式が残っているか、で場合分けしている：

• 終端である場合はそのまま値を（プログラム全体の結果として）返す
• 未評価の式が残っていないCont.Callの場合、まず評価済み値のリストをリバースさせ、そのリストの先頭がVal.Opであればそのまま関数適用、Val.Opでなければエラー
• Cont.Callで未評価の式が残っている場合、apply_contの引数である値を「評価済み値」のリストに追加（ここで元の式の順と逆になってしまうことに注意）した新しいCont.Callを作り、次の未評価の式をその継続でevalする

これでプログラムのコンテキストをデータ化できた。すべての再帰・相互再帰呼び出しが末尾再帰になっていて、evalに渡される式と変数環境と継続あるいはapply_contに渡される値と変数環境と継続でプログラム実行のコンテキストがすべて保持できている。

次回は相互再帰をトランポリン化して、実行途中のプログラムの状態がデータとしてevalやapply_contから返されるようにする。