めざそう言語処理系の沼 〜shift/resetへの旅 〜 その７ 関数（レキシカル・スコープ）

前回実装したダイナミック・スコープの関数は、実装は楽だが使うにはけっこうピーキーである。より一般的なレキシカル・スコープに直すとする。

関数の定義を評価して「関数の値」を作成する時に、関数内に出てくる自由変数を検出して、定義時の変数環境でそれらに対応する値を取って、「関数の値」に保持させる。

関数呼び出し時にはこれら「自由変数と対応する値」のリストと仮引数・実引数のリストだけを変数環境に入れてから関数の本体の式を評価する。

「式の中の自由変数を取ってくる」というのが最大のポイントで、これが出来ればあとは比較的簡単。

前回との差分：

Comparing v0.6...v0.7 · zehnpaard/kontlang · GitHub

まずValモジュールで関数の値の定義をいじる：

type t =
...
| Fn of string * string list * (string * t) list * Exp.t

前回に比べて(string * t) listが加わっている。これが「関数内の自由変数と、それに対応する値」のリストだ。

Utilsモジュールを新しく作成した。インタプリタ固有の型（Val.tやExp.tなど）とは関係ない関数などを入れていく。今回はUtils.split3を定義：

let split3 xyzs =
  let rec f xs ys zs = function
  | [] -> xs, ys, zs
  | (x,y,z)::xyzs -> f (x::xs) (y::ys) (z::zs) xyzs
  in
  f [] [] [] xyzs

OCamlのスタンダードライブラリのListモジュールに定義されているsplitの型が

(a, b) list -> (a list, b list)

なのだが、Utils.split3は

(a, b, c) list -> (a list, b list, c list)

という型で、要素３のタプルのリストをリスト三つのタプルに変換する。

次にEnvモジュールにヘルパー関数を三つ追加：

let rec contains var = function
| [] -> false
| []::env' -> contains var env'
| ((var', _)::env')::env'' ->
    if var = var' then true
    else contains var @@ env'::env''

let add_var env v = extend_current v (Val.Int 0) env
let add_vars env vs =
  let vvs = List.map (fun v -> (v, Val.Int 0)) vs in
  extend_list vvs env

containsは変数環境にある変数が含まれているかどうかを調べる。

add_varとadd_varsは変数環境にダミー変数を追加する。つまり「ある変数に何かしらの値が束縛されている（値の内容は問わない）」という状況を作るための関数である。

最後はやはりExecuteモジュール。ある式の自由変数を取ってくるget_free：

let rec get_free env = function
| Exp.Int _ -> []
| Exp.Var s -> if (Env.contains s env) then [] else [s]
| Exp.Call(e, es) -> (get_free env e) @ (List.concat @@ List.map (get_free env) es) 
| Exp.If(e1, e2, e3) -> (get_free env e1) @ (get_free env e2) @ (get_free env e3)
| Exp.Let(ves, e2) ->
    let vs, es = List.split ves in
    (get_free (Env.add_vars env vs) e2) @ (List.concat @@ List.map (get_free env) es)
| Exp.Lets((s, e1)::ves, e2) ->
    (get_free env e1) @ (get_free (Env.add_var env s) @@ Exp.Lets(ves, e2))
| Exp.Lets ([], e2) -> get_free env e2
| Exp.Fn(params, body) -> get_free (Env.add_vars env params) body
| Exp.LetFn(fns, e) ->
    let fnames, paramss, bodys = Utils.split3 fns in
    let f params body = get_free (Env.add_vars env params) body in
    let free_in_fns = List.concat @@ List.map2 f paramss bodys in
    (get_free (Env.add_vars env fnames) e) @ free_in_fns

再帰的に式から自由変数を取り出していき、List.concat（あるいはその演算子である@）で繋げていってる。EnvやUtilsで新しく定義された関数もここで使われている。

今見返してみるといくつか問題点が見つかる：

• 自由変数がダブる。同じ自由変数が複数出てくる度に自由変数リストにも追加されてしまう
• 自由変数かどうかを調べるためだけに変数環境（文字列と値のリストのリスト）を使っていてそのためにダミー値まで追加しているが、定義済み変数のリスト（文字列のリスト）だけで本来事足りる
• いちいちconcatしまくっていて非常に効率が悪い

まあ自由変数のリストがそう大きくなることはないと思うのでそこまで気にするところでもないが、とりあえず「自由変数がダブる」ところは後ほど修正する。

Executeモジュールのeval：

let eval env cont = function
...
| Exp.Fn(params, body) as e ->
    let free = 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.LetFn(fns, e) ->
    let f (fname, params, body) =
      let free = get_free (Env.add_vars Env.empty params) body in
      let fvals = List.map (fun v -> v, Env.find v env) free in
      (fname, Val.Fn(fname, params, fvals, body))
    in
    Eval(Env.extend_list (List.map f fns) env, Cont.Env::cont, e)

get_freeを使って自由変数を取ってきて、さらに現在の変数環境で対応する値を取り、その変数*値のリストを関数の値に保持する、という変更。前回のダイナミック・スコープがほとんどなんの処理もしていなかったのと打って変わってけっこう複雑になっている。

最後にapply_cont関数：

let apply_cont env cont v = match cont with
...
| Cont.Call([], vs) :: cont' -> (match List.rev (v::vs) with
  ...
  | Val.Fn(s, ss, fvals, e) :: vs' ->
    let paramcount = List.length ss in
    let argcount = List.length vs' in
    if paramcount = argcount then
      let env' = Env.extend_list (fvals @ (List.combine ss vs')) env in
      Eval(env', Cont.Env::cont', e)
    else failwith @@ Printf.sprintf "Function %s called with incorrect number of args: expected %d received %d" s paramcount argcount

ダイナミック・スコープでは仮引数と実引数を変数環境に追加してから関数本体の式を評価していたのだが、今回は仮引数・実引数に加えて自由変数と対応する値も変数環境に加えている。

レキシカル・スコープの場合、既存の変数環境に加えるのではなく、まっさらな変数環境に仮引数・実引数、自由変数と対応する値だけ加えて評価してもいいのだが、そうすると関数呼び出しの評価が終わって元の変数環境に戻したい時にめんどくさい（継続に変数環境を格納する必要がある）。今回実装したように既存の変数環境に追加してもシャドーイングで評価結果は同じな上、今までどおりCont.Envだけで元の環境に戻せる利点がある。

以上でレキシカル・スコープへの変換終了。

こんな式も：

(letfn [f [x] (* x x)]
  (let [* +] (f 5)))

期待どおりに結果が２５になり、関数定義時になかった変数束縛に関数呼び出しの結果が影響されなくなっている。

次回は再帰関数を追加する。