Arantium Maestum

プログラミング、囲碁、読書の話題

めざそう言語処理系の沼 〜shift/resetへの旅 〜 その11 Cond&リファクタリング

今回の変更は三点:

  • condによる条件分岐
  • Val.FnVal.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.CondCont.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.FnVal.RecFnを統一

以前、再帰関数を定義できるようにした時にVal.t型に新しくRecFnコンストラクタを追加した。関数を作成した後に、クロージャにその関数(あるいは相互再帰関係にある他の関数)を追加できるように、クロージャを表す型を(string * Val.t) listから(string * Val.t) list refに変更したいためだ。

しかしこのRecFnの定義は普通のFnでも使いまわせる。そうするとVal.tに対するパターンマッチの場合分けを少し減らし、大部分同じで微妙に違うFnRecFnに対する処理を統一できる。

最終的には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にいくつか不満があったので変更した。

修正点は以下のとおり:

  1. 戻り値である自由変数のリストをconcatしないようにする
  2. 変数環境Env.t型の引数を取らないようにする
  3. 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を使う必要がある。まあdedupeO(n)だしまあいいか、というところ。

次回

次回は文字列と入出力、そして複数の式を評価して最後の式の値をとるDo構文を追加する。