λ式とクロージャ

手続きと閉包

前提

ここでは手続きまたは関数ともに純粋なものを扱う。

関数は渡される引数が同じであれば常に同じ値を返す
関数は変動する外部の変数を参照しない
関数には副作用がない

結論

ある関数・手続き・λ式がクロージャであるかは実装に依り、かつその関数の自由変数の参照がその関数を内包している関数の環境に閉じているか、で決まる。

λ式とは？

"ひとしき"  でゎなぃ。。。

匿名関数・無名関数のこと。手続きの抽象、またはプログラム上での表現。

例えば次のような手続きを考える。

def double(x):
    return x + x

これは手続きである。詳細には基本的な手続きを組み合わせ、かつ名前を付けた手続きである。

または匿名関数として

(lambda x: x + x)

のようにも書ける。

手続きの抽象？高階関数

なぜ手続きの抽象を扱うか。それは手続きの抽象を扱うことがプログラミングにおいて大きな力となるからである。

手続きの組み合わせにより複雑な手続きを抽象化することができる。

foldr (+) 0 $ map (^ 2) [1..100] -- 1, 4, 9 … 10000 の並びの総和
foldr (*) 1 [1..5] -- 5!

さらに手続きの合成を考えることもできる。

userDeckIds = [2, 3, 5]
userDeck = map (makeMonsterFromBaseParams . fromIdToCardBaseStatus) userDeckIds

クロージャ(閉包)

手続きを自由変数と共に表現する実装のこと。かつその自由変数の参照がその定義時の関数の環境で閉じている。

自由変数

function(b) { return a; }

という関数を考える。この時の a が自由変数である。

別の関数

function(a) { return a; }

の a は自由変数ではない。

自由変数の評価はその関数が適用される際のコンテキストと実装に依存する。

クロージャと自由変数

"自由変数の参照が閉じている" とはどういうことだろうか。次のような関数を考えるとすぐにわかる。

var K = function(a) { return function(b) { return a; }; };

ここで K(0) を評価し返ってくる関数がクロージャである。返り値の関数内の自由変数 a は外からは参照できない。

もう一つ例を。

var I = function(a) { return a; };
K(I);

この返り値である関数もクロージャである。

自由変数を持っているがクロージャではない手続き

さきほどの K(0) を評価して得た関数がクロージャではない状況とはどういうことか。いくつかの可能性が考えられるが、ここで実装を動的スコープだと仮定すると

function f() { return a; }
function g() {
    var a = 9;
    return f();
}

g() を適用すると 9 が返ってくる。適用時の関数外部の環境で評価される。

または単に "手続きは自由変数を持たない" という実装にすることも可能である。

実装から見たクロージャ

次のような式を考える。

((lambda (x)
   (+
     ((lambda (x) x) 2)
     x))
   4)

レキシカルスコープ(構文スコープ)をサポートする時、上部のλ式における x と内部のλ式における x の束縛は違うようになってほしい(前者は 4, 後者は 2)。このためにλ式の評価時に対応する関数の環境を評価器のなんらかのスタックに積み、適用時にその環境の変数と値の対応を解決し消去する。

名前付き手続きの場合、

(define f (lambda
            (x)
            (lambda (y) x)))

(define g (f 0))
(g (1))

名前と定義時の環境を対応させて保存しておき、適用時に取り出し、評価時の環境に上乗せする必要がある。

クロージャもっとクロージャ

True = -> a { -> b { a } }
False = -> a { -> b { b } }
If = -> b { -> t { -> f { b.(t).(f) } } }
Bool = -> b { -> t { -> f { b ? t : f } } }

If.(True)
  .(1)
  .(0)

If.(False)
  .(1)
  .(0)

If.(Bool.(0 == 0))
  .('ok')
  .('no')

Y = -> f { -> g { f.(-> a { g.(g).(a) }) }.(-> g { f.(-> a { g.(g).(a) }) }) }
Z = -> f { -> g { -> a { f.(g.(g)).(a) } }.(-> g { -> a { f.(g.(g)).(a) } }) }

Fib = -> f { -> n { n < 2 ? n : (f.(n - 1) + f.(n - 2)) } }
Fact = -> f { -> n { n == 0 ? 1 : n * f.(n - 1) } }

Y.(Fact).(5)
Z.(Fib).(7)


I = -> a { a }
K = -> a { -> b { a } }
S = -> f { -> a { -> b { f.(a).(b) } } }

True_ = K
False_ = K.(I)
If_ = S

Y_ = S.(K.(S.(I).(I))).(S.(S.(K.(S)).(K)).(K.(S.(I).(I))))

アッ… これは…

taiki45/lambda_and_closure.md