自己適用

関数型プログラム言語の理論的基礎は、ラムダ計算だ。ラムダ計算と言っても、そう難しいことを行っているわけではなく、関数のうち、値や関数の代入可能な変数を指定するだけだ。

例えば x + y という式があるとする。これには、いろいろな解釈が可能だ。x という数値と y という数値の和とも考えられるし、y という値が固定している変数 x についての1変数関数とも考えられる。また、x という値が固定している変数 y についての関数とも、変数 x, y の2変数関数とも考えられる。x + y という表記からではその意味が決定できない。

ラムダ記法は、上の曖昧さを明確にするために考えられた方法だ。λx という記号によってxが変数であることを明示できる。上の x + y の場合、λx. (x + y) と記述することによって、この式が x の1変数関数であることを明記できる。

また、上の例の場合 x = 2 をこの関数に代入することを、λx. (x + y) (2) で表すことができる。実際に代入した結果は 2 + y という値になる。

λ計算では、f(x) のカッコを省略して fx と書く習慣がある。λx . fx という記述は、変数 x を関数 f に適用させた1変数関数を表す。

前準備が長くなったが、Curryの不動点演算子(Yコンビネータ)を理解する上で欠かせないのが、λx. xx という関数の自己適用だ。λ記法では、xx は x * x ではない。しいて言えば x ( x ) とでも表したほうがいいかもしれない。関数 x を 自分自身に適用して得られる関数が xx だ。関数を自分自身に適用するというのはイメージしにくいが、例えば x = f(y) = y * y だったとしよう。すると、

λx. xx (f(y)) = f(f(y)) = f(y * y) = (y * y) * (y * y) = y^4

となる。このようにλ記法では、関数の引数に関数を適用させる高階関数を記述することができる。さらに、この高階関数を利用すると、関数をそれ自身に適用させるという自己適用という離れ業も記述することができる。λ記法では、値と関数を区別しないし、引数への値の適用は、単なる記号の書き換えで行われるからだ。

xx の様にラムダ式を並べたものが関数適用であること、また、λ記号で指定された束縛変数が引数の値で置き換えることができることを理解しておくと、どのような関数に対しても不動点を提供するYコンビネータの不可解な作用を理解できる。

ラムダ計算について調べてみると、関数というプログラムの動作の原理が、記号の置き換えだけで検討できることが分かる。関数型言語の動作は、変数の置き換えという記号の置き換えだけで説明することができるのだ。

たとえば、階乗を計算するプログラムは、

fact 0 = 1
fact n = n * fact (n-1)

だが、このプログラムで実際に fact 5 が計算される過程を見ると、それが全て記号の置き換えでなされていることが分かる。

fact 5
= 5 * fact 4
= 5 * (4 * fact 3)
= 5 * (4 * (3 * fact 2))
= 5 * (4 * (3 * (2 * fact 1)))
= 5 * (4 * (3 * (2 * (1 * fact 0)))
= 5 * (4 * (3 * (2 * (1 * 1))))
= 120

関数型プログラム言語の動作は記号の置き換えだと考えておくと、暗号的な関数型言語のプログラムの理解がしやすくなる。
[PR]
by tnomura9 | 2011-06-02 11:54 | Haskell | Comments(0)
<< Curry の不動点演算子 中央値 >>