めざそう言語処理系の沼 〜shift/resetへの旅 〜 その11 Cond&リファクタリング
今回の変更は三点:
cond
による条件分岐Val.Fn
とVal.RecFn
を統一- 式の中の自由変数を検出する
get_free
をリファクタ
前回とのコード差分:
Comparing v0.10...v0.11 · zehnpaard/kontlang · GitHub
cond
による条件分岐
すでにif
による条件分岐は実装してあるが
if ... then ... else if ... then ... else ...
上記のような複数の条件を順次調べて分岐するようなロジックは
(if ... ... (if ... ... ...))
のような形になり、ネストがどんどん深くなっていってしまう。このように書けるようにしたい:
(cond [... ...] [... ...] [true ...])
(true
はelseと同じ意味になる)
まずExp
モジュールにExp.Cont
を追加:
type t = ... | Cond of (t * t) list
条件式と、その条件が真だった場合の結果となる式のタプルのリスト。
ある条件式を評価している間、「現在Cond
の一部を評価している」というコンテキストを保持する必要があるのでCont.t
にもコンストラクタを追加:
type cont = ... | Cond of Exp.t * (Exp.t * Exp.t) list
現在評価している条件式が真だった場合の結果となる式と、残りの条件式・結果式のタプルのリスト。以前評価した結果やそれに対応する式は必要ない(条件が一つ真だった時点でCont.Cond
は外した上で対応する結果式を評価するので)。
あとはExecute
モジュールでVal.Cond
やCont.Cond
のケースを追加:
let eval env cont = function ... | Exp.Cond((e1,e2)::ees) -> Eval(env, Cont.Cond(e2, ees)::cont, e1) | Exp.Cond _ -> failwith "Evaluating cond with no matching condition" let apply_cont env cont v = match cont with ... | Cont.Cond(e, ees) :: cont' -> (match v with | Val.Bool b -> Eval(env, cont', if b then e else Exp.Cond(ees)) | _ -> failwith "Non-boolean in condition position of Cond expression")
eval
ではVal.Cond
のデータの先頭からタプルを取り、継続にCont.Cond
を追加してからタプルの条件式の部分を評価。
apply_cont
では、条件式の評価結果が真なら結果式を、そうでないなら残った(条件式*結果式)タプルのリストで新しくExp.Cond
を作成してそれを評価する。
もし何も該当する条件がなかった場合は実行時エラーになる。nil
を返すようにしてもよかったのだが、この言語は他のところでも少し厳しめの実装になっているのでそっちに寄せた。
Val.Fn
とVal.RecFn
を統一
以前、再帰関数を定義できるようにした時にVal.t
型に新しくRecFn
コンストラクタを追加した。関数を作成した後に、クロージャにその関数(あるいは相互再帰関係にある他の関数)を追加できるように、クロージャを表す型を(string * Val.t) list
から(string * Val.t) list ref
に変更したいためだ。
しかしこのRecFn
の定義は普通のFn
でも使いまわせる。そうするとVal.t
に対するパターンマッチの場合分けを少し減らし、大部分同じで微妙に違うFn
とRecFn
に対する処理を統一できる。
最終的にはVal.Fn
の定義はこうなる:
type t = ... | Fn of string * string list * (string * t) list ref * Exp.t
あとはExecute
モジュールでの場合分けで、今まであったVal.Fn
の部分を削除してVal.RecFn
というコンストラクタをVal.Fn
に書き換えるだけ。(細かいので割愛)
get_free
をリファクタ
ある式のなかに出てくる自由変数を検出するget_free
にいくつか不満があったので変更した。
修正点は以下のとおり:
- 戻り値である自由変数のリストを
concat
しないようにする - 変数環境
Env.t
型の引数を取らないようにする get_free
関数をExecute
からExp
に移す
1の「戻り値である自由変数のリストをconcat
しないようにする」に関しては、get_free
が再帰的に部分式に適用された結果を愚直にconcat
で繋げていて効率が非常に悪い(そのconcat
部分だけでO(n log n)
)。それを避けるために「出てきた自由変数を追加するためのリスト」を引数に加える。部分式が複数ある場合、fold_left
などを使ってこのリストを使い回す。これでそのO(n log n)
部分をO(n)
に下げられる。
2の「変数環境Env.t
型の引数を取らないようにする」については、今まで式の中で出てきた変数が束縛されているかどうかを調べるのに、eval
で使っているのと同じ変数環境の型Env.t
を使っていた。なので例えば(let [x 5] (+ x x))
という式の自由変数を調べる時に、(+ x x)
のx
が束縛されていることを表すために変数環境に("x", Val.Nil)
のような変数とダミー値のタプルを入れていた。ダミー値が無駄だし、get_env
関数が不必要にEnv
モジュールに依存してしまう、ということで「現在束縛されている変数の集合」をExp.t
型のenv
引数ではなくただの文字列のリストであるbound
引数で表すことにした。
3「get_free
関数をExecute
からExp
に移す」については、2でEnv
への依存がなくなったのでget_free
の残る依存性はExp
に対するものだけ。さらに「式の自由変数を検出する」という関数の目的からも、Exp
モジュールに入っているのが一番自然なのでそのように変更。
最終的にExp.get_free
はこのようになった:
let rec get_free bound free = function | Int _ -> free | Var s -> if (List.mem s bound) then free else s::free | Call(e, es) -> List.fold_left (get_free bound) free @@ e::es | If(e1, e2, e3) -> List.fold_left (get_free bound) free [e1; e2; e3] | Cond(ees) -> let f free (e1, e2) = get_free bound (get_free bound free e1) e2 in List.fold_left f free ees | Let(ves, e2) -> let vs, es = List.split ves in let free' = List.fold_left (get_free bound) free es in get_free (vs @ bound) free' e2 | Lets((s, e1)::ves, e2) -> let free' = get_free bound free e1 in get_free (s::bound) free' @@ Lets(ves, e2) | Lets ([], e2) -> get_free bound free e2 | Fn(params, body) -> get_free (params @ bound) free body | LetFn(fns, e) -> let fnames, paramss, bodys = Utils.split3 fns in let f free params body = get_free (params @ bound) free body in let free' = List.fold_left2 f free paramss bodys in get_free (fnames @ bound) free' e | LetRec(fns, e) -> let fnames, paramss, bodys = Utils.split3 fns in let f free params body = get_free (fnames @ params @ bound) free body in let free' = List.fold_left2 f free paramss bodys in get_free (fnames @ bound) free' e
Execute
モジュールでの使い方は:
| Exp.Fn(params, body) as e -> let free = Utils.dedupe @@ Exp.get_free [] [] e in (* ここ *) let fvalsr = ref @@ List.map (fun v -> v, Env.find v env) free in ApplyCont(env, cont, Val.Fn("anon", params, fvalsr, body))
新しいget_free
の戻り値でも自由変数の重複はありえるのでUtils.dedupe
を使う必要がある。まあdedupe
もO(n)
だしまあいいか、というところ。
次回
次回は文字列と入出力、そして複数の式を評価して最後の式の値をとるDo
構文を追加する。