めざそう言語処理系の沼 〜shift/resetへの旅 〜 その８ 再帰

普通の関数が実装できたので、今度は再帰関数を定義できるようにする。

具体的にはこのような構文：

(letrec
  [factorial [n]
     (if (= 1 n)
         1
         (* n (factorial (- n 1))))]
  (factorial 6))

あるいは：

(letrec
  [(odd? [x]
      (if (= 0 x)
          false
          (even? (- x 1))))
    (even? [x]
       (if (= 0 x)
           true
           (odd? (- x 1))))]
  (odd? 101))

といった形で相互再帰もできるようになる。

前回との差分：

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

まずExp.tにLetRecを追加：

type t =
...
| LetRec of (string * string list * t) list * t

• 「再帰関数名」「仮引数」「関数の本体」のリスト
• letの本体である式

の二つの部分で構成されている。ちなみにLetFnの定義は

| LetFn of (string * string list * t) list * t

なのでLetRecとLetFnは式の保持する情報はまったく同じものとなる。

次にValモジュールに再帰関数の値を追加：

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

各要素の意味は

• 関数名
• 仮引数
• クロージャ
• 関数本体の式

となる。これもFnと比較してみると：

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

ほぼ同じだが、クロージャの部分がRecFnではrefになっているのが違い。再帰関数のクロージャには「自由変数と対応する値」だけではなく「letrecで定義された関数名とそれに対応する値」も追加されるのだがその「対応する値」にこのRecFn値も含まれる。そういうループ構造を実装するために、関数を作成後に変更できるミュータブルなrefを使っている。（他のやり方もある。Essentials of Programming Languagesの第3章を参照）

新しい式を追加したのでExecute.get_freeも変更：

let rec get_free env = function
...
| Exp.LetRec(fns, e) ->
    let fnames, paramss, bodys = Utils.split3 fns in
    let f params body = get_free (Env.add_vars env (fnames @ 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

• 再帰関数の要素のリストから「関数名」のリスト、「仮引数」のリスト、「関数本体」のリストを作成
• 「関数一つの自由変数を出す」関数を定義
• 定義されている再帰関数すべての自由変数を上記2行の結果を使って検出
• LetRec本体の式の自由変数を検出し、上記の「再帰関数の自由変数」のリストとconcat

となっている。

「『関数一つの自由変数を出す』関数を定義」の

    let f params body = get_free (Env.add_vars env (fnames @ params)) body in

で定義されたすべての再帰関数名fnamesも変数環境に追加し、再帰関数の自由変数から除外しているのもポイント。

Execute.eval：

let eval env cont = function
...
| Exp.LetRec(fns, e) ->
    let fnames, _, _ = Utils.split3 fns in
    let f fnames (fname, params, body) =
      let free = get_free (Env.add_vars Env.empty (fnames @ params)) body in
      let fvals = List.map (fun v -> v, Env.find v env) free in
      let fvalsr = ref fvals in
      let fn = Val.RecFn(fname, params, fvalsr, body) in
      ((fname, fn), fvalsr)
    in
    let fname_fns, fvalsrs = List.split @@ List.map (f fnames) fns in
    List.iter (fun fvalsr -> (fvalsr := (fname_fns @ !fvalsr))) fvalsrs;
    Eval(Env.extend_list fname_fns env, Cont.Env::cont, e)

おおさっぱな流れを解説すると：

• 再帰関数の要素のリストから再帰関数を作成
• 作成されたすべて再帰関数のクロージャに「作成されたすべての再帰関数の名前と値」を追加
• 変数環境に作成されたすべて再帰関数を追加して、letrec本体の式を評価

となっている。

「再帰関数の要素のリストから再帰関数を作成」するために定義されているf関数が過半数の行を占めている。（おっと、このf関数がfnamesを引数にとる意味がないな・・・）

ポイントとしては、再帰関数の名前と値のタプルだけでなく、その関数のクロージャも同時に返しているところ。すべての再帰関数の値をクロージャに追加しなければいけないので、「一つの再帰関数を作る」f関数内ではクロージャの更新はできない。

最後にExecute.apply_cont：

let apply_cont env cont v = match cont with
...
| Cont.Call([], vs) :: cont' -> (match List.rev (v::vs) with
...
  | Val.RecFn(s, ss, fvalsr, e) :: vs' ->
    let paramcount = List.length ss in
    let argcount = List.length vs' in
    if paramcount = argcount then
      let env' = Env.extend_list (!fvalsr @ (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を追加してからletrec本体の式を評価する。（引数の要素数が一致しない場合はエラー）。

くどいようだがVal.Fnのケースと比較してみる：

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

目を凝らさないとなかなかわからないと思うが、

let env' = Env.extend_list (!fvalsr @ (List.combine ss vs')) env in (* RecFn *)
let env' = Env.extend_list (fvals @ (List.combine ss vs')) env in (* Fn *)

この違いである。Fnだとそのままリストである「自由変数と対応する値」のfvalを直接concatしているのが、RecFnだとref型なので!fvalsrとしている。

今気づいたのだが、FnもRecFn側に寄せてクロージャをrefで持つようにすれば値の種類をわける必要もなく、この場合分けもいらなくなるな・・・（Exp.LetRecはいるがVal.RecFnはいらない）　どこかのタイミングで修正してみよう。

というわけで再帰も実装完了。「クロージャをミュータブルにする」という方針が決まっていれば比較的簡単に既存の非再帰関数のコードを修正できる。

次回はいくつかマイナー修正を加える。