第七回
「再帰関数の追加」

今回はインタプリタに再帰関数を追加します。
CPS変換する前にやっとくべきだったのですが忘れてました。
再帰関数とは、OCaml でいうところの
let rec f x = ...
                in ...
の f のことです。

まずはこれに相当する構文木を追加しましょう。
type expr_t = ...
                | Letrec of string * string * expr_t * expr_t
最初の string が関数名、次の string が引数です。
二つある expr_t のうち一つ目が関数本体、二つ目が in 以下の式です。

例えば
let rec fac x =
      if x = 0 then 1
      else x * fac (x - 1)
      in fac 3
は、
Letrec ("fac", "x",
              If (Equal (Variable "x", Number 0),
                  Number 1,
                  Times (Variable "x", App (Variable "fac",
                            Minus (Variable "x", Number 1)))),
              App (Variable "fac", Number 3))
となります。
そういえば = とか if はまだ実装してませんね……

=================================================================
問題 1（質問、相談可）
(1) =, <, >, <=, >=, <> を実装せよ。
    （引数を二つもらってきて、それらを比較し、VBool で返すものを作ります。）
(2) if を実装せよ。
    （引数を三つもらってきて、
    　まず一つ目の引数を評価し、True ならば二つ目の引数を、
    　False ならば三つ目の引数を評価するものを作ります。）
=================================================================

let rec は let と関数が両方出てくるので、既に作ってある let と fun が
組合わさったような処理になります。
つまり、
let fac = fun x ->
                if x = 0 then 1
                else x * fac (x-1)
            in fac 3
を実行するのと「ほぼ」同じ処理になります。
この式は既に実装したもので動かせる筈なので一度実行してみてください。
（何が起こるでしょうか？）

結果を言ってしまうと、今までの let と fun を組み合わせただけでは
再帰関数の実装はできません。
fun 文内に出てくる fac が未定義だからです。
以前実装した let 文は、let x = a in b という文があったら、
1. まず a を実行
2. 1.の結果を値とする x を定義。（環境を拡張）
3. b を実行
しますよね。
つまり、a を実行している段階では変数 x は定義されていないのです。
上の fac の例では、fun x -> if x = 0 then 1 else x * fac (x - 1) を表す
closure（関数と、自由変数の値が全て定義されている環境のセットのことだと思ってください。
VFun型みたいなのを想像してください。）を作る時の環境に fac が入っていないので、
この closure を呼び出すと、関数本体の解釈中に変数 fac が出て来た際、
「fac が未定義である」と怒られるわけです。
これが、今まで作った let と fun のみでは再帰関数を実装できない理由です。

しかし逆に言うと、再帰関数を実装するためには、再帰関数になる closure を作るときに、
その環境に「自分自身」を入れておけばいいだけです。
上の例では、fac に相当する closure を作る時、その環境に 「fac はこういう関数」という
情報があれば良いのです。
fac の closure = VFun("x", If(...), 環境E)
環境E = ("fac", fac の closure) :: それまでの環境
のような感じで。

しかし、ここでまた問題が発生します。
closure の中に自分自身(fac)の値を含む環境を入れて定義したいわけですが、
その環境の中で closure 自身が出て来てしまいます。定義が循環していて値を作れないのです。

これを解決するためにはいくつかの方法があります。

よく用いられる方法は、環境を(string * value_t) list ではなく
(string * value_t ref) list にするというものです。
つまり環境に入っている値を ref にしておき、後日、変更できるようにしておきます。
そうすると、上のような循環する構造も表すことができるようになります。

ですが、ここでは ref を使わなくてもすむ方法でやってみましょう。
再帰関数には再帰関数であるという印をつけておいて、再帰関数呼び出す時に、
必要な情報を環境に付け加えるという方法です。

まずは普通の関数に加えて再帰関数を表す値を追加しましょう。
type value_t = ...
                    | VRecFun of string * string * expr_t * (string * value_t) list
今までの VFun に比べ、先頭に string が一つ増えています。
ここに再帰関数の名前を入れます。
最後の環境には、VFun のときと同じく、この再帰関数が定義されたときの環境を入れておきます。
本来ならこの環境に「自分自身」の情報も入れておきたいところなのですが、
それをすると循環構造になってしまうので、それのみ除外した形で入れておきます。

環境に自分自身が入っていないと当然、再帰呼び出しをするときに困ります。
ですが、再帰呼び出しをするためには、その前に関数自身がどこかで呼び出されている筈です。
fac の例では 3 行目で再帰呼び出しがされるわけですが、その 3 行目が実行されるためには
一度どこかで fac 関数が呼び出されていないといけません。例では最後の行の fac 3 です。
そこで、再帰関数が呼び出されたら、そのときに環境に自分自身の情報を挿入するようにします。

具体的には、 VRecFun("f", "x", 本体, env) を呼び出すには、
VFun の場合と同じように env を引数で拡張しますが、
それに加えて "f" が VRecFun(...) 自身であるという情報も加えます。
こうすることで、本体実行中に "f" を使う事ができるようになります。

=================================================================
問題３（質問、相談可）
再帰関数を実装せよ。
いくつかの例について、再帰関数を使えていることを確認せよ。
=================================================================
ちなみにこの課題はインタプリタが CPS でも direct style でも出来ます。
いきなり CPS なんて……という人は CPS 変換する前のインタプリタに実装してみましょう。