環境とクロージャを用いた、より効率的な関数型プログラミング言語の定義＆実装の仕方の例

[関数型プログラミング言語の定義＆実装の仕方の例](http://qiita.com/esumii/items/0eeb30f35c2a9da4ab8a)で「需要があれば後で書く」と書いた、「より効率的な実装」です（数件:-)の需要があったので）。前の記事は読んでいると仮定します。

さて、前の実装では、関数``function(x){E}``を値``v``に適用すると、本体である式``E``の抽象構文木をすべて辿って、その中の変数``x``をすべて``v``で置き換えた式を作っていました（``subst``）。これは明らかに非効率的です。関数を呼び出すたびに、本体の抽象構文木を作り直しているのですから！

そこで、変数に本当に値を代入して新しい式を作り直すかわりに、どの変数にどういう値が与えられた（**束縛**(binding)と言います）のか、覚えておくデータ構造を用意します。これを**環境**(environment)と言います。

環境は連想リストでもハッシュテーブルでも探索木でも、変数から値への対応（写像）を表していれば、何でも実装することができます。ただし、ある関数呼び出しで``x``が``v``に束縛されたからと言って、別の関数呼び出しの``x``も同じ``v``になるとは限らないので、非破壊的（関数的）なデータ構造が必要です。

環境を用いて、``Eval``の（実装ではなく数学的な）定義を書き下すと、以下のようになります。

```
Eval(i, env) = i

Eval(x, env) = 環境envにおける変数xの値を返す

Eval(E1-E2, env) =
  Eval(E1, env) = i かつ Eval(E2, env) = j として、
  i から j を引いた整数を返す

Eval(if E1 <= E2 then E3 else E4, env) =
  Eval(E1, env) = i かつ Eval(E2, env) = j として、
  i <= j ならば Eval(E3, env) を、そうでなければ Eval(E4, env) を返す

Eval(function(x){E}, env) = (function(x){E}, env)（後で説明する「クロージャ」）

Eval(E1(E2), env) =
  Eval(E1, env) = (function(x){E}, env') かつ Eval(E2, env) = v として、
  env' に x から v への対応を付け加えた環境を env'' とし、
  Eval(E, env'') を返す
```

まず、変数``x``の評価では、環境``env``から``x``の値を見つけ出し、それを返します。これは環境のそもそもの目的からして当たり前ですね。

次に、関数``function(x){E}``の評価は、前回は関数そのものをそのまま返してしましたが、今回は**関数と現在の環境``env``を組にして**返します。この組のことを**クロージャ**(closure)と言います。

どうしてクロージャを作る必要があるのでしょうか？　次のようなプログラム例を考えてみてください。

```
let y = 3 in
let f = function(x){x-y} in
let y = 7 in
f(42) - y
```

```let x = E1 in E2```という形の式は```(function(x){E2})(E1)```と定義されていたことを思い出してください（構文糖衣）。

上のプログラム（式）の実行結果（値）はいくつになるべきでしょうか？　前回の代入に基づく意味論や実装で考えると、まず1行目の```let y = 3 in```により、``function(x){x-y}``の``y``に``3``が代入されるはずです。

```
let f = function(x){x-3} in
let y = 7 in
f(42) - y
```

```f(42) - y```の``y``は、```let y = 3 in```の``y``とは**別の``y``なので代入されない**ことに注意してください。前回の定義でも、``Subst(function(x){E},x,v) = function(x){E}``だったので、確かにそうなります！

次に、```let f = function(x){x-3} in```に従い、``f``に``function(x){x-3}``を代入します。

```
let y = 7 in
(function(x){x-3})(42) - y
```

``let y = 7 in``により``y``に``7``が代入されます。

```
(function(x){x-3})(42) - 7
```

``(function(x){x-3})(42)``を計算すると``42-3``すなわち``39``になるので、答は``39-7``すなわち``32``です。

上のプログラム例の評価で、**``function(x){x-y}``の``y``には``7``ではなく``3``が代入された**ことに注意してください。このように、関数の本体の中の引数以外の変数（自由変数(free variable)と言います）の値は、その関数が**呼び出されるときの値（``y = 7``）ではなく、定義されたときの値（``y = 3``）**になります。これを静的束縛(static binding)ないしレキシカルスコープと言います。

関数が呼び出されるときではなく、定義されたときの値が必要なため、関数の定義と一緒にそのときの環境を覚えておく、すなわちクロージャを作る必要があるのです。

ちょっとややこしかったかもしれませんが、繰り返すと要点は以下の2つです。

* 「関数と、それが定義されたときの環境との組」がクロージャ
* 関数の本体は、呼び出し時ではなく定義時の環境で評価

後者をふまえると、関数呼び出しの評価``Eval(E1(E2), env)``において、呼び出し時の環境``env``ではなく、クロージャに保存されている関数定義時の環境``env'``に基づいて本体を評価している理由もわかると思います。

難しい話になってしまいましたがOCamlで実装します！ ``exp``の定義は前回と同じです。

```ocaml:
(* 環境を表す連想リスト（手抜きです） *)
type env = (string * valu) list

(* evalの結果（値）を表すデータ型 *)
and valu = VInt of int
  | Closure of string * exp * env

let rec eval e0 env =
  match e0 with Int i -> VInt i
  | Var x -> List.assoc x env
  | Sub(e1, e2) ->
      let VInt i = eval e1 env in
      let VInt j = eval e2 env in
      VInt(i - j)
  | If(e1, e2, e3, e4) ->
      let VInt i = eval e1 env in
      let VInt j = eval e2 env in
      if i <= j then eval e3 env else eval e4 env
  | Fun(x, e) -> Closure(x, e, env)
  | App(e1, e2) ->
      let Closure(x, e, env') = eval e1 env in
      let v = eval e2 env in
      let env'' = (x, v) :: env' in
      eval e env''
```

プログラム例も前回と同じですが、evalの第2引数として空の環境``[]``を与えます。

```ocaml:
# eval one_plus_two [] ;;
- : valu = VInt 3
# eval abs [] ;;
- : valu = VInt 42
# eval loop [] ;;
  C-c C-cInterrupted.
# eval sum10000 [] ;;
- : valu = VInt 50005000
```

もちろん、クロージャの説明に使ったプログラム例もちゃんと動きます。

```ocaml:
# let clo =
    _Let("y", Int 3,
         _Let("f", Fun("x", Sub(Var "x", Var "y")),
              _Let ("y", Int 7,
                    Sub(App(Var "f", Int 42), Var "y")))) ;;
val clo : exp =
  App
   (Fun ("y",
     App
      (Fun ("f",
        App (Fun ("y", Sub (App (Var "f", Int 42), Var "y")), Int 7)),
      Fun ("x", Sub (Var "x", Var "y")))),
   Int 3)
# eval clo [] ;;
- : valu = VInt 32
```

ちなみに初期のLISPは、関数の定義時ではなく呼び出し時の環境で本体が評価される動的束縛(dynamic binding)でした。これは意図した動作ではなくバグだったようです。クロージャは後にJavaでも著名になったGuy Steele Jr.らがSchemeの実装で導入しました（[理論はそれ以前からありました](https://en.wikipedia.org/wiki/Closure_(computer_programming)#History_and_etymology)が）。

終わり。