人気ブログランキング |

ラムダ計算 関数の意味

ラムダ式は全て関数だ。関数とは何らかの働きのことだ。働きは目に見えないのでその意味をすぐには理解できない。関数の意味はそれを何らかの対象に関数適用してみてはじめて分かる。例えば λx.x は恒等関数だが、その意味は、いろいろな対象にそれを関数適用してみないと分からない。λx.x を a という対象に関数適用してみると (λx.x)a = a だ。また、b という対象に関数適用すると (λx.x)b = b だ。

lambda> ((lx.x) a)
a
lambda> ((lx.x) b)
b

全ての対象について検証しなくても、2,3の対象について λx.x を関数適用すれば、恒等関数の意味が、どんな対象に関数適用してもその対象そのものを返す関数であり、その意味は「何もしない関数」であることが分かる。しかし、依然として「何もしない」という意味は目には見えない。いろいろな対象に関数適用したときの結果を頭のなかで再現してその意味が分かる。

しかし、ラムダ計算ではこの目に見えない「働き」をラムダ式という対象として扱うことができる。そのことが関数型プログラム言語のプログラムを簡潔で柔軟なものとしている。

関数の意味は目に見えないがゆえに、逆にその意味を知ることは関数型のプログラム言語を活用するための重要な鍵となる。ラムダ計算が何もできないプログラム言語であるにもかかわらず面白いのは、関数の意味という抽象的なものを端的に扱うことができるからだろう。

そこでラムダ計算に現れるいろいろな関数の意味を考えてみることにする。

λx.x の意味は恒等関数だったが、λx.y の意味はなんだろうか。それは定数関数だ。つまり、どんな対象にこれを関数適用しても値は常に y となる。

lambda> ((lx.y) a)
y
lambda> ((lx.y) b)
y

ラムダ計算では 0 を表すチャーチ数は λsz.z だが、この関数の意味は何だろうか。変数 s について見るとこれは恒等関数であって s にどのような値を与えても常に λz.z という恒等関数を返す。

lambda> ((ls.(lz.z)) a)
(lz.z)
lambda> ((ls.(lz.z)) b)
(lz.z)

さらに λz.z は恒等関数という関数なのでこれにも意味がある。つまり、どのような対象に関数適用しても値はその対象そのものになるということだ。したがって、λsz.z には、「どのような関数に適用しても、恒等関数というどのような対象に対しても何もしない関数を返す関数である」という複合的な意味があることが分かる。

それではチャーチ数の 1 についてはどうだろうか。λsz.sz はチャーチ数の1だが、これを関数 f に関数適用すると λz.fz となる。これは「対象に関数 f を関数適用する関数」を作り出すことを意味している。

lambda> ((ls.(lz.(s z))) f)
(lz.(f z))
lambda> ((lz.(f z)) a)
(f a)

チャーチ数の 2 についてはどうだろうか。λsz.s(sz) を関数 f に関数適用すると λz.(f (fz)) なので、これは対象z に関数 f を2回関数適用してできる関数を表している。したがって、これを対象 a に関数適用すると f (f a) という値が得られる。

lambda> ((ls.(lz.(s (s z)))) f)
(lz.(f (f z)))
lambda> ((lz.(f (f z))) a)
(f (f a))

それでは、自然数の次の自然数を求める後者関数 λwsz.s(wsz) にはどのような意味があるのだろうか。変数の w には自然数が与えられるので、これを2 に関数適用してみると (λwsz.s(wsz))2 = λsz.s (2sz) である。2 は引数の関数を2回関数適用する関数を作る関数なので λsz.s (λx.(s(sx))z) = λsz.s(s(sz)) である。この関数の意味は「関数 s を3回対象 z に関数適用する関数」である。これはチャーチ数の 3 にあたる。

lambda> ((lw.(ls.(lz.(s ((w s) z))))) (ls.(lz.(s (s z)))))
(ls.(lz.(s (s (s z)))))
lambda> ((ls.(lz.(s (s (s z))))) f)
(lz.(f (f (f z))))
lambda> ((lz.(f (f (f z)))) a)
(f (f (f a)))

このようにラムダ計算のラムダ式には意味がある。しかし、その意味は目に見えない「作用」なのでその関数の様々な用例を頭の中でシミュレーションしてみなければ分からない。この抽象性が関数言語プログラムの難しいところである。しかし、一旦関数の意味を理解してしまうと、その抽象性から様々な用例に再利用することができる。これが、関数型プログラム言語のソースコードが劇的に簡潔になる理由だ。

関数の目に見えない「作用」の意味をつかまえることで、関数言語を扱う楽しさは倍増する。

by tnomura9 | 2019-09-12 06:54 | Haskell | Comments(0)
<< ラムダ計算機 Ver 0.1 ラムダ計算で遊ぶ 3 >>