Yコンビネータを読み解く
この記事のお気持ち
という，この呪文がなんなのか，理解したい．
なぜこの呪文を理解したいのか．それは僕たちが生きているから．
生きてるって素晴らしいから．
そして，Yコンビネータの概念を理解すると再帰についての知見が得られるから．さらには関数型プログラミング言語の論理的背景の主軸であるラムダ計算について一定の知見が得られるから．知見はあの世に持っていけないから．生きているからこそ知見に意味があるから．
Yコンビネータ
結論から言うと，上記の呪文には"Yコンビネータ"という名前がある．
Yってなんだよ．僕は知らない．Yの意味がわからなくても，Yコンビネータが何かはわかる．すごい．コンビネータってなんだよ．これは知らないといけない．Yコンビネータはコンビネータの一種なので，コンビネータの意味がわからないとYコンビネータの意味もわからない．かなしい．
不動点コンビネータ
Yコンビネータにおける”コンビネータ”とは不動点コンビネータのことだ．略称だ．かっこいい．また知らない言葉が出てきた．不動点．不動点ってなに．英語でいうと fixed-point．かっこいい．英語はかっこいい．
不動点
不動点というのは数学のことばだ．数学のことばなのでちゃんとした定義がある．ちゃんとしてる定義は形式的な定義だ．
これで不動点がちゃんと定義できた．本当はこういう定義を書くとき，一階述語論理の論理式*1で表記するのが定番なんだけど，読者を限定するのがさみしいので日本語で書いた．僕はさみしがりやだから．あと面倒で．
じゃあ，上の定義を具体的に考えてみよう．
あ，でもその前に，またひとつ分かんないことばが出てきた．写像．写像(map)ってなに．写像っていうのは，ここではいわゆる”関数”と同一視していい．関数ってことばが分からない人は，ごめんだけど，教科書で調べてきて．以下，写像と関数は素朴に同じものだとして話を進める．
話を戻して，不動点ってものの具体例を見てみよう．定義1より，つまり を満たすような
を考えればいい．
という関数 が与えられたとき，
となって， という条件を満足するから，
はこの関数
の不動点だ．より直感的に理解するために，グラフを考えてみよう．グラフはいいぞ．かっこいいし．簡単のために，いったん上にあげた具体的な関数のことは忘れよう．別に覚えててもいいけど，混乱しそうだから忘れてもらえると助かる．
定義1.より，不動点というのは を満たす
のことだった．早速これをグラフにしてみよう．慣習に従って，平行軸に
，垂直軸に
をとると，
は
の直線と同一視できる．ここにてきとうな関数
を導入して，重ねあわせてみよう．
それぞれ青とオレンジで描かれた2つのグラフの交点が，関数 の不動点だ．
コンビネータ(1)
英語で書くとcombinator．コンビネータとは，関数だ．とはいえ，関数にもいろいろある．コンビネータとはそんな，いろいろある関数のうちで，引数に関数を取れる関数のことだ．引数に関数を取れる．かっこいい．こういうかっこいい関数のことを高階関数(high-order function)という．たとえば，関数 があって，
が高階関数なら，
は別の関数
を引数として呼び出していい．この例だと，
に
が代入されるわけだから，関数としては
みたいな形になる．もちろん自分自身を呼び出してもいい．すると
となる．コンビネータとは，要するにこうした高階関数の一種だ．でも，コンビネータが高階関数とまったく同じものだったら，わざわざ名前をつけたりしない．名前がついてるということは，区別したいからだ．区別に意味があるから別の名前が必要になる．じゃあ，コンビネータはどんなふうに高階関数一般と区別されているんだろう．ここで定義をみてみよう．
- 定義2.3
- 定義2.1および定義2.2によって定義される任意の関数はコンビネータである．
なるほど．こうやってコンビネータの定義をじっくり読んでいると，いくつか気になることがある．まず，定義2.1より，コンビネータが高階関数の部分集合だってことは分かった．だけど，自由変数ってなんだ．変数に自由とか不自由とかがあるのか．現代人じゃあるまいし．それと，もっと不思議なのが定義2.2だ．"コンビネータ"の定義をしているのに，定義の記述の中にまた"コンビネータ"っていうことばが出てきている．詭弁の匂いがする．なんだか誤魔化されている気がする．そして気になる定義2.3の存在．なんの意味があるんだ．実はこれは立派な定義になっていて，定義2.1と定義2.2を併せてちゃんと読むと，”落としどころ"が見えてくる．すると，定義2.3が味わい深い，小粋な仕事をしていることも分かる．普通，こういう定義の方法を再帰的定義(recursive definition)と言ったりする．たぶん高校生の頃，数学的帰納法*2によってある命題が任意の自然数について成り立つ様子を見たと思う．それに似ている気がしないかな．見覚えがない人は，たびたびごめんだけど，教科書で調べてきて．
ともかく，コンビネータの定義を理解するためには，定義2.1で出てきた”自由変数”の意味が分からないといけない，ことは分かった．どうやら，変数にも種類がある．名前がついているんだから，そこには区別がある．そしてその区別はきっと有意味なはずだ．無意味な名前はいずれ消えていく*3．
自由変数 - 束縛変数
形式言語の世界では，変数を自由変数と束縛変数という2種類に分類して考える．形式言語というのは，自然言語ではなく，かつ，その文法が形式的(≒論理学的)に決まっている言語のことをいう．数学のことばやプログラミング言語は形式言語だ．変数，ということばの中で”数”という字を使っているけれど，別に変数は数でなくても構わない．数でなくても構わないことを強調したいとき，日本語では変項ということばを使う．英語ではいずれの訳語も”variable”だ．以下では簡単のために変数という表記に統一する．
先に書いたように，自由変数(free variable)と束縛変数(bound variable)は形式言語の構成要素だ．形式言語はその文法が形式的，論理学的に決まっているのだから，これらの変数についてもその用法は形式的，論理学的に決まっている．ということで，定義のお時間です．
- 定義3.1
の要素
が自由変数であるとき，
は述語である．
- 定義3.2
- 定義3.3
- 定義3.4
また知らんことばが出てきた．述語とか命題とか．ここで，つらつら述語と命題の違いを説明してもいいんだけど，定義を見る限り"述語 - 自由変数" ，”命題 - 束縛変数" という対応関係はかなり綺麗だ．自由変数の意味が分かれば述語の意味も分かりそうだし，束縛変数の意味がわかれば命題の意味もわかりそう．じゃあ，この対応を利用して，具体例の方からそれぞれのことばの意味に迫っていこう．
- 前提
- 例1
- 例2
- すべての
例1 は自由変数 についての述語だ．
には好きな数を代入できる．たとえば
とすると，これは
という偽の命題になる．例1 の段階での
は真/偽(=真理値)が決まっていない”述語”だった．
を代入したことでできた
は，
となり，偽の真理値をもつ”命題”になった．もちろん，
だったら真理値は真だ．自由変数の”自由”というのは，値を代入する自由のことだったらしい．そして，”自由に代入していい部分(=自由変数)をもつ(有意味な)文”のことを，述語と呼ぶことも分かった．ここで定義3.3，定義3.4を引っ張ってくると，命題とは”自由に代入していい部分をもたない(有意味な)文”ということになりそうだ．ここまでの文脈を汲むと，自由に代入していい部分を持たない文は命題と呼ばれ，真理値なる値をもつ．真理値には真(True)，偽(False)の2種類があり，かつ，2種類しかない．
例2 は，一方， についての命題だ．このような文
を構成する
のことを束縛変数という．このようなってどのようなだよ．見てのとおり，例2 における
は単に見かけの変数で，自由な代入は許されていない．"すべての
について" という表現に束縛されていて，
は身動きが取れない．試しに
と代入してみるとこれは，”すべての
について
”というヤバい文になってしまう．直前の文
の真理値が自明に偽である以上，文
は代入した値の影響を受けず，最初から偽な命題だったということになる．
こうしてみると，ふつうの意味で”変数”ということばを使うとき，意図されているのは自由変数のことだと気がつく．たとえばプログラミングではふつう，代入可能な値についてのみ変数と呼ぶ．だからプログラミングで変数といえばやっぱり自由変数のことだ．自由と束縛．理論的には極めて妥当に思える変数についてのこうした命名だけど，実装の方から解釈するとどうにも不自然でかなり混乱する．その理由は，後ほど，ラムダ計算という概念を導入したときにでも説明しようかなと思っている*4．
よしよし，変数を自由変数と束縛変数とに区別して考えるのは分かった．なんで区別するのか，区別するとどう嬉しいのかはまだ分からないけど，区別が必要なことまでは分かった．そもそもなんで変数の区別について考えていたんだっけ．それは，コンビネータの定義2.1に自由変数ということばが登場したからだった．コンビネータの定義をそれぞれ見直してみよう．文の中に知らないことばがなくなって，ちゃんと意味が分かるようになった．やったぜ．
コンビネータ(2)
あえて言及しなかったんだけど，コンビネータ(1)の”(1)”，たぶん気になりましたよね．見出しをご覧ください．つまりそういうことです．ということで，自由変数の意味を押さえた上で，もう一度，定義2.1を確認してみる．
これをほぐすと，おおよそ以下のような日本語になる．
- 定義2.1.1
- 関数
が関数を引数に取れる関数であり，かつ，
おお，かなり見通しが良くなった．では次に，定義2.1とその同値変形である定義2.1.1を踏まえて，定義2.2をほぐしていこう．
定義2.2の下線部は，引数を変数の部分だと解釈すると，以下のように変形できる．
定義3.4よりこの文はあきらかに，
という文と同値となる．定義しといてよかった束縛変数．さて，ここまでに揃った定義を使って，コンビネータを再定義しておこう．
- 定義2.1.1
- 関数
ふむ，なんだかいけそうな気がしてきた．何がとはいえないが，何かがいけそうな気がしてきた．さあ，コンビネータの定義が腑に落ちてきたところで，じゃあなんのためにコンビネータについて思い巡らせてきたのかを思い出したい．思い出した．不動点コンビネータが何かを分かりたかったんだ．ほほう，”不動点/コンビネータ”とな．不動点についてはさっき定義したし，コンビネータについてはいま定義した．いけそうな気がする．無性にいけそうなこの気持ちを抱いて，さあ，次は不動点コンビネータを定義していこう．
