めざそう言語処理系の沼 〜shift/resetへの旅 〜 その１４ ステップ実行インタプリタ
ここまで実装してきたインタプリタは
- 式を表す文字列をパースし
- 評価して
- 結果の値を表す文字列を返していた。
もちろんそれで正しいのだが、インタプリタの中でどのような挙動になって式が値に変換されているのかがわかりにくい。
限定継続のようにかなり微妙な動きをする（そして微妙なバグが潜り込みそうな）言語機能を実装する場合、もう少し細かく内部状態がわかる「デバッグモード」がほしい。
というわけで、新しくstepwiseというexecutableが作れるようにする。
このexecutableは文字どおりステップ実行のためのインタプリタで、Execute.evalやExecute.apply_contが走ってExecute.res型の途中結果をトランポリンに返すたびにその情報をプリント出力する。
前回からの差分：
Comparing v0.13...v0.14 · zehnpaard/kontlang · GitHub
今回の変更のために以下のことをしている
- 値と継続の定義を共通のモジュールに移す
- 継続をlist listに
- 継続と変数環境を文字列化できるようにする
- ステップ実行インタプリタ
前者二つは限定継続を実装するための下準備だが、三番目の「継続と変数環境を文字列化できるようにする」のために前倒しした（継続の文字列化のロジックを後で大きく修正するのを避けたかったので）。
値と継続の定義を共通のモジュールに移す
限定継続を実装すると「継続の一部」を値として取り扱う必要が出てくる。
一番素直な実装だと、Val.t型のバリアントの一つの内部データとしてCont.t型（あるいはその一部）を持たせることになる。しかし継続にはすでに「ここまで評価した結果」である値が保持されているので、相互再帰的になってしまう。
OCamlだと相互再帰的なデータ型が定義できるがその場合一つのモジュールで両方の型を定義するのが一番簡単。この件に関しては以前記事に書いた：
というわけでCont.tとVal.tを相互再帰的にするために、新しくValcontモジュールを作成して両者をここで定義する。さらにValcont内で別々のValとContモジュールを定義して、Val.ml内ではinclude Valcont.Val、Kont.mlではinclude Valcont.Contとしている。これで他のモジュールからは今までどおりValとContが使える。
本当はValcontモジュールがValとContモジュール以外からは隠蔽したくなるのだが、調べてみたところ難しいようだ。
今になって思えばこの変更はCont.tの文字列化にあまり影響しないので、この段階でやる必要はなかった・・・
継続をlist listに
限定継続を実装する下準備その２。
限定継続を扱えるようにする言語機能のshift/resetでは、reset式の中に入った部分式は継続がreset外とは区切られていて、その中でshiftが呼ばれるとその区切りのところまでの継続が捕捉されて値に変換される。
これまで継続はフラットな一つのリストとして実装してきた。ここに例えばCont.Resetを導入して「現在の限定継続は直近のCont.Resetまで」と定義してもいいのだが、別解として
- 継続は
Cont.cont list list型 resetに入ったら継続に空リストを追加- 他の式の継続はこの先頭のリストに追加していく
shiftはこの先頭をリストをとってくるだけ
という実装を思いついたので試してみたい。
これはCont.tの内部実装を大きく変えるところなので、Cont.to_stringを実装する前にやっておきたかった。
Cont.t型の変更：
type t = cont list let final = []
だったものが
type t = cont list list let final = [[]]
こうなる。単なるリストに比べて追加がめんどくさくなるので専用のCont.add関数を用意：
let add c = function | cont'::cont'' -> (c::cont')::cont'' | [] -> [[c]]
こういった変更に合わせてExecuteモジュールも変えていく。
let eval env cont = function ... | Exp.Call(e, es) -> Eval(env, Cont.Call(es, []) :: cont, e)
が
let eval env cont = function ... | Exp.Call(e, es) -> let cont' = Cont.add (Cont.Call(es, [])) cont in
になったり
let apply_cont env cont v = match cont with ... | Cont.Call(e::es, vs) :: cont' -> Eval(env, Cont.Call(es, v::vs) :: cont', e)
が
let apply_cont env cont v = match cont with ... | (Cont.Call(e::es, vs) :: cont')::cont'' -> let cont''' = Cont.add (Cont.Call(es, v::vs)) (cont'::cont'') in Eval(env, cont''', e)
になったりする。リストがネストしたぶん少し冗長になっている。
さらに
let apply_cont env cont v = match cont with ... | []::cont'' -> ApplyCont(env, cont'', v)
というケースが追加されている。これは「resetの中の式を評価し終わったので、その限定継続から抜ける」ことを表している。
ただしまだshift/resetが実装されていないので、継続に二つ以上のリストが含まれることはないのだが・・・
継続と変数環境を文字列化できるようにする
ステップ実行で評価途中のインタプリタの状態を表示するには、式や値だけではなく継続と変数環境も出力する必要がある。なのでCont.to_stringやEnv.to_stringを追加する。
地味なのでコードは割愛。
ステップ実行インタプリタ
これでステップ実行時に必要な情報を文字列化できるようになった。
あとはExecuteモジュールにtrampolineにちょっと手を加えたtrampoline'を作る。具体的にはevalやapply_contが返すExecute.res型を出力して一時停止するdisplay関数を定義して：
let display = function | Done v -> print_endline "Done"; print_endline (Val.to_string v); ignore @@ read_line () | Eval(env, cont, e) -> print_endline @@ "Evaluating expression " ^ Exp.to_string e; print_endline @@ "Cont Head:\t" ^ Cont.to_string_hd cont; print_endline @@ "Cont Full:\t" ^ Cont.to_string cont; print_endline @@ "Environment:\t" ^ Env.to_string env; ignore @@ read_line () | ApplyCont(env, cont, v) -> print_endline @@ "Applying continuation on value " ^ Val.to_string v; print_endline @@ "Cont Head:\t" ^ Cont.to_string_hd cont; print_endline @@ "Cont Full:\t" ^ Cont.to_string cont; print_endline @@ "Environment:\t" ^ Env.to_string env; ignore @@ read_line ()
trampoline'で次のステップに移る前にdisplayを呼び出す：
let rec trampoline' res = match res with | Done v -> display res; v | Eval(env, cont, e) -> display res; trampoline' @@ eval env cont e | ApplyCont(env, cont, v) -> display res; trampoline' @@ apply_cont env cont v
trampoline'を使ったrun'やeval_string'も定義して、最後にstepwise.mlを作成：
open Kontlang let rec read_eval_print exp_string = let s = read_line () in if s = "" then Execute.eval_string' exp_string |> print_endline else read_eval_print (Printf.sprintf "%s\n%s" exp_string s) let () = (print_string ">>> "; read_eval_print "")
これで実装完了。
使い方
dune exec ./stepwise.exe
で実行できる。（duneはOCamlのビルドツールで、上記のコマンドはduneにstepwise.exeをコンパイルして実行するよう指示している）
実行して(let [x 3] (+ (* 1 2) x))を評価させてみる：
kontlang$ dune exec ./stepwise.exe
>>> (let [x 3] (+ (* 1 2) x))
Evaluating expression (let [(x 3)] (+ (* 1 2) x))
Cont Head:
Cont Full:
Environment:
Evaluating expression 3
Cont Head: LET x [] [] (+ (* 1 2) x)
Cont Full: LET
Environment:
Applying continuation on value 3
Cont Head: LET x [] [] (+ (* 1 2) x)
Cont Full: LET
Environment:
Evaluating expression (+ (* 1 2) x)
Cont Head: ENV
Cont Full: ENV
Environment: [{x 3}]
Evaluating expression +
Cont Head: CALL [(* 1 2) x] []
Cont Full: CALL ENV
Environment: [{x 3}]
Applying continuation on value Op(+)
Cont Head: CALL [(* 1 2) x] []
Cont Full: CALL ENV
Environment: [{x 3}]
Evaluating expression (* 1 2)
Cont Head: CALL [x] [Op(+)]
Cont Full: CALL ENV
Environment: [{x 3}]
Evaluating expression *
Cont Head: CALL [1 2] []
Cont Full: CALL CALL ENV
Environment: [{x 3}]
Applying continuation on value Op(*)
Cont Head: CALL [1 2] []
Cont Full: CALL CALL ENV
Environment: [{x 3}]
Evaluating expression 1
Cont Head: CALL [2] [Op(*)]
Cont Full: CALL CALL ENV
Environment: [{x 3}]
Applying continuation on value 1
Cont Head: CALL [2] [Op(*)]
Cont Full: CALL CALL ENV
Environment: [{x 3}]
Evaluating expression 2
Cont Head: CALL [] [1 Op(*)]
Cont Full: CALL CALL ENV
Environment: [{x 3}]
Applying continuation on value 2
Cont Head: CALL [] [1 Op(*)]
Cont Full: CALL CALL ENV
Environment: [{x 3}]
Applying continuation on value 2
Cont Head: CALL [x] [Op(+)]
Cont Full: CALL ENV
Environment: [{x 3}]
Evaluating expression x
Cont Head: CALL [] [2 Op(+)]
Cont Full: CALL ENV
Environment: [{x 3}]
Applying continuation on value 3
Cont Head: CALL [] [2 Op(+)]
Cont Full: CALL ENV
Environment: [{x 3}]
Applying continuation on value 5
Cont Head: ENV
Cont Full: ENV
Environment: [{x 3}]
Applying continuation on value 5
Cont Head:
Cont Full:
Environment:
Applying continuation on value 5
Cont Head:
Cont Full:
Environment:
Done
5
5
「Cont Full」では継続すべてを（個々の部分は簡略した形で）表示し、「Cont Head」ではその一番先頭（左側）の詳細を表示している。
パッと見で直感的とは言えないが、慣れてくるとインタプリタの状態がかなりわかるようになる。例えば
Evaluating expression 1
Cont Head: CALL [2] [Op(*)]
Cont Full: CALL CALL ENV
Environment: [{x 3}]
であれば
- 次のステップは
1という式を評価すること - 現在関数呼び出し二つの内側にいる
- 直近の関数呼び出しでは、すでに関数に当たる部分が評価されていてその値は
*である - まだ未評価の引数があってその式は
2である（整数式も整数値も同じように表示されてしまうのがややこしい・・・） - 現在の変数環境には
xという変数に3という値が束縛されている
ということを表している。
限定継続のような複雑な機能を実装・デバッグする上でこういう情報は非常に役に立つ。
