関数型プログラミング言語の定義＆実装の仕方の例で「需要があれば後で書く」と書いた、「より効率的な実装」です（数件:-)の需要があったので）。前の記事は読んでいると仮定します。
さて、前の実装では、関数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の定義は前回と同じです。
(* 環境を表す連想リスト（手抜きです） *)
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引数として空の環境[]を与えます。
# eval one_plus_two [] ;;
- : valu = VInt 3
# eval abs [] ;;
- : valu = VInt 42
# eval loop [] ;;
C-c C-cInterrupted.
# eval sum10000 [] ;;
- : valu = VInt 50005000
もちろん、クロージャの説明に使ったプログラム例もちゃんと動きます。
# 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の実装で導入しました（理論はそれ以前からありましたが）。
終わり。