Arantium Maestum

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

めざそう言語処理系の沼 〜shift/resetへの旅 〜 その9 微調整

今回は細かいところを調整しただけ。

前回との差分:

Comparing v0.8...v0.9 · zehnpaard/kontlang · GitHub

調整ポイントは:

  • レキシカル・スコープで関数作成時にクロージャに束縛する自由変数の重複を排除
  • Exp.Letsを評価する時、変数に束縛されるべき式をすべて評価し終わった後に継続にCont.Envを追加していたのを、実引数評価の前に追加するよう変更
  • Cont.Letで変数に束縛されるべき式をすべて評価し終わった後、それらをList.revしていたのをやめた

地味かつ現行の機能にはなんの変化もないリファクタリング

クロージャに束縛する自由変数の重複を排除

関数作成時に自由変数を全部検出するのだが、今までの実装だと例えば

(fn [y]
  (+ x y (+ x x) z))

などといった式の場合、自由変数が[+ x + x x z]のような重複のあるリストになってしまって非効率。重複は排除したい。

Utilsモジュールにdedupe関数を追加:

let dedupe xs =
  let hsh = Hashtbl.create 1024 in
  let rec f acc = function
  | [] -> acc
  | x::xs' ->
    if Hashtbl.mem hsh x then f acc xs'
    else (Hashtbl.add hsh x 0; f (x::acc) xs')
  in
  f [] xs

ミュータブルなデータ構造であるHashtblを使っているが、この関数の外には漏れないので問題なし。ほぼSetとして使っているが、イミュータブルなSetに比べてHashtblはいろいろと性能がいい。OCaml公式サイトのチュートリアルにも

Sets and maps are very useful in compilation and meta-programming, but in other situations hash tables are often more appropriate

と書かれている。今回はSetのような永続性はいらないのでHashtblを使う。

こうやって定義したUtils.dedupeを、Execute.evalget_freeが使われているところに加える:

let eval env cont = function
...
| Exp.Fn(params, body) as e ->
    let free = Utils.dedupe @@ get_free Env.empty e in (* ここ *)
    let fvals = List.map (fun v -> v, Env.find v env) free in
    ApplyCont(env, cont, Val.Fn("anon", params, fvals, body))

他にも二箇所ほどあるが、使い方は同じ。これでクロージャに追加する前に重複を排除できる。

Exp.Lets評価時にCont.Envを追加するタイミング

前回までのコードだとExp.Letsを評価する時に:

let eval env cont = function
...
| Exp.Lets((s, e1)::ves, e2) -> Eval([]::env, Cont.Lets(s, ves, e2) :: cont, e1)

evalのタイミングで[]::envと空リストを変数環境に追加しているが:

let apply_cont env cont v = match cont with
...
| Cont.Lets(s, [], e2) :: cont' ->
    Eval(Env.extend_current s v env, Cont.Env::cont', e2)

let*式から出たらそのリストを外す必要がある」と継続にCont.Envを追加するのはapply_cont関数内で、Cont.Letsの未評価の式がなくなった時点だ。現在エラー以外でevalからapply_contの流れが止まることはないので問題が表面化しないのだが

  1. 変数環境に空リストを追加するのと継続にCont.Envを追加するのとは対応しているのに、こんなに離れてしまっているのは気持ち悪い
  2. 限定継続が追加されるとevalapply_contの流れが中断される恐れがある

という二点を踏まえて修正しておく。

let eval env cont = function
...
| Exp.Lets((s, e1)::ves, e2) -> Eval([]::env, Cont.Lets(s, ves, e2)::Cont.Env::cont, e1)

let apply_cont env cont v = match cont with
...
| Cont.Lets(s, [], e2) :: cont' ->
    Eval(Env.extend_current s v env, cont', e2)

Cont.Envが追加される場所がevalに移すだけで修正完了。

Cont.LetList.revするのをやめる

これはどういうことかというと

(let [(x 10)
      (x 5)]
  (* x 2))

のような式がある場合、下にある変数束縛の方が優先されるべき(なので結果は10)。

変数環境に追加するリストは[(x 10) (x 5)]ではなく[(x 5) (x 10)]である必要がある。

元の:

| Cont.Let(s, [], vvs, e2) :: cont' ->
    let env' = Env.extend_list (List.rev ((s, v)::vvs)) env in
    Eval(env', Cont.Env::cont', e2)

だとList.revが余計。実際には先頭から評価してリストに加えていったものを、そのまま変数環境に加えるのが正しい順序になる。

それを踏まえてこう変える:

| Cont.Let(s, [], vvs, e2) :: cont' ->
    let env' = Env.extend_list ((s, v)::vvs) env in
    Eval(env', Cont.Env::cont', e2)

List.revを消しただけ。これで環境内で変数の出てくる順序が正しくなる。

それ以外

それ以外はコンストラクタの間のスペースを消したり、パーサの部分表記を統一したり、といったこまごました変更。やはり機能には影響なし。

次回は言語にconscarcdrを追加してLispらしいリストを作れるようにする。