groovyとラムダ式(5)：有名なラムダ式を書いてみる

（昨日からの続き）

ラムダ式には、ほとんど固有名詞が付いているような、有名(?)なヤツがあります。

• I ≡ λx.x
• B ≡ λf,g.λx.f(gx)
• C ≡ λf.λx, y.f(y, x)
• K ≡ λa.λx.a
• S ≡ λf,g.λx.f(x, gx)
• W ≡ λf.λx.f(x, x)

IとBはすでにId、Compとして出した（ただし、Comp(f, g)はB(g, f)）。C, K, S, Wをそのままgroovyクロージャで書いてみる。

// 後の例で使う

Sum = {|x, y| x + y}

F = {|x| x + 1}
// C, K, S, Wの定義

C = {|f| {|x, y| f(y, x)}}

K = {|a| {|x| a}}

S = {|f, g| {|x| f(x, g(x))}}

W = {|f| {|x| f(x, x)}}
// 例で試してみる

println C(Sum)(2, 3) // Sum(3, 2)

println K("Hello")("world")

println S(Sum, F)(2) // Sum(2, F(2)) = Sum(2, 3)

println W(Sum)(2) // Sum(2, 2)

5

Hello

5

4

諸々の事情で、S, Kなどはコンビネータ（combinator）と呼ばれてます。

さーて、真打ち登場、Curryの不動点コンビネータ（別名paradoxical combinator）Y。

• Y ≡ λx.VV where V ≡ λy.x(yy)

// Curryの不動点コンビネータ

Y = {|x|

  V = {|y| x(y(y))}

  V(V)

}

とりあえず定義だけならできるのですが、適用するとさすがにダメです*1。

// Curryの不動点コンビネータ：定義

Y = {|x|

  V = {|y| x(y(y))}

  V(V)

}
// 適用!!

P = Y(K)

 /* 山盛りのエラーメッセージ／スタックトレース */

（続く）

*1:工夫すると何とかなるかもしれないが。