第五回
「関数(closure)の追加」

今回はインタプリタに関数（λ式）を追加します。
OCaml での (fun x -> ... ) に相当するものを書けるようにするわけです。
まずは、入力の構文木を拡張します。

type expr_t = ...
                    | Fun of string * expr_t
                    | App of expr_t * expr_t

Fun がλ式、App が関数呼び出しです。
例えば fun x -> x は
Fun ("x", Variable "x") のようになります。
また、この関数を３で呼び出すには
App (Fun ("x", Variable "x"), Number 3)
となります。

λ式はとりあえず１つしか引数を持たない関数とします。
２つ以上引数を受け取りたければ、
fun x -> fun y -> ...
のような形にしましょう。
例えば、fun x y -> x + y を計算したい場合、
fun x -> fun y -> x + y とします。

さて、前回変数を加えたときは expr_t を拡張しただけでしたが、
今回は value_t にも手を加えます。
関数は値だからです。
（実際に OCaml でも、fun x -> x 等を（引数を渡さずにそのまま）実行すると、
　整数などの値を渡すとそのまま返ってくるのと同様、そのまま関数が返って来ます。）
そこで、value_t を次のように拡張します。

type value_t = ...
                    | VFun of string * expr_t * (string * value_t) list

VFun の最初の引数(string)は引数名、
二つ目の引数(expr_t)は関数本体の式、
(body と言ったりします。fun文の、矢印より右側の部分に相当します。)
三つ目の引数((string * value_t) list)は環境です。
fun x -> x なら、 VFun("x", Variable "x", [...そのときの環境...])
となります。
三つ目に環境を受け取ってくる理由については後ほど。

関数（λ式）が呼び出されると、β簡約が起こります。
つまり (λx.M) V -> M[x := V] です。
(ここでのM[x := V]は、先輩の論文での M[V/x] と同じ意味です。)
これをインタープリタで処理できるようにします。
たとえば
App (Fun("x", Variable "x"), Number 3) のような項が与えられたら、
関数本体の Variable "x" の中の "x" を Number 3 で置き換えるわけです。
この例では関数本体の中に "x" が一カ所しか出て来ず、
そこを書き換えれば良いので簡単そうです。
しかし、一般には関数本体はもっと複雑で大きなものになり、その中を全て調べて
目的の変数を見つけたら全て置き換えていかなければなりません。
さらに、この処理は関数呼び出しが行われるたびにしなくてはいけません。

この面倒くさい置き換えを避けるために考えた方法が、
「関数呼び出し時に本体を調べて置き換えを行うのではなく、
　置き換える変数と値を環境に取っておいて、該当の変数が使われるときに置き換える」
というものです。
つまり関数呼び出しは、「どの変数が何に置き換わるか」という情報を環境に追加し、
その環境のもので関数本体を実行するようにします。
で、これをそのまま実装したものがだいたい、
インタプリタの関数呼び出し部分の実装になります。

環境は、これから実行しようとする式の中に出てくる自由変数の値を保持しているものです。
このことについて、インタプリタ中で関数を実行するときに少し気をつけなくてはいけません。
たとえば、 x = 3 という環境のもとで fun y -> x + y を実行したとしましょう。
返ってくるのは関数なので VFun です。具体的には
VFun ("y", Plus(Variable "x", Variable "y"), ...)
のような形です。これを見ると y は引数ですが、x という自由変数が出てきます。
引数名と、関数本体だけでは x の値が何か分かりません。
そこで、三つ目の変数として、「この関数が定義されたときの環境」を入れておくわけです。
この環境を見ることで、関数本体の自由変数（上の例での x ）の値が分かるようにします。

ですので、実際には関数呼び出しが行われるときには、
VFun の三つ目の引数に入れられた環境に、引数の情報を付加した上で、
（上の例での y の情報。関数呼び出しの際に渡された値が 1 だとすると、
　("y", 1) を環境の先頭に追加する。）
関数本体を実行していきます。

===================================================================
問題（質問、相談可）

1. 関数と関数呼び出しを実装せよ。

2. 以下の式を実行すると何が返ってくるか。実際にインタプリタでそのよう
に動作していることを確認せよ。

(1) (fun x -> x) 4

(2) let x = 3 in
    (fun y -> x + y) 4

(3) let f = let x = 3 in
              fun y -> x + y in
              f 4

(4) let f = let x = 3 in
              fun y -> x + y in
              let x = 5 in
              f 4

(5) let x = 3 in
              let f = fun y -> x + y in
              f 4

(6) let x = 3 in
      let f = fun y -> x + y in
      let x = 5 in
      f 4
===================================================================

この問題では、もちろん関数の中の x の値が何になるべきかが問題です。
普通の言語では x の値は「関数が定義された時点での値」を保持します。
これを lexical scoping と呼びます。
「まっとうな」プログラミング言語はすべてこれを採用しています。

一方、古い言語では「使う時点での値」になるものもあります。
これを dynamic scoping と呼びます。
dynamic scoping では、(4) や (6) の関数の中の x は 5 になり、
(3) はエラーになります。