Yコンビネータ。プログラミング言語の追っかけが好きな人間なら聞いたことがあるでしょう。
僕も、プログラミング言語を2回ほど自作したこともあるくらいミーハー(笑)な人間なので、
Yコンビネータという単語は知っていた。もちろん、それが何なのかは知らないままに。
今日、ランチの塩ラーメンを食べている途中で、ふとYコンビネータという単語が頭をよぎったので、
とうとう観念して勉強することにした。
さて、Yコンビネータを解説しているページはいくらでも出てくるのだが、
その中でも特にこのページがとてもわかりやすいと思った。
自分なりの解釈によると、要するにYコンビネータとはラムダ式だけを用いて再帰関数を導出するための公式。
「Yコンビネータ」を日本語で表すと「不動点演算子」。
つまり、引数に与えた関数をそのまま戻り値として返す関数。それってもちろん
function fakeYCombinator(f) { return f; }
のことじゃないよ。
条件分岐をラムダ式だけで表現するのは簡単。後は再帰をラムダ式で表現できれば再帰呼び出し、
すなわちループを実現できる。
(LISPではループを再帰でしか表現できない理由が、今やっとわかった)
そして、「条件分岐とループをラムダ式で表現できる」は「任意の処理フローをラムダ式だけで記述できる」と等価らしい。
僕は計算機数学は詳しくないので、ココはすなおにフーンと言っておきます。
任意の数値リテラルも、単位元とラムダ式だけで表現できる。
そう、"2"の定義が『1+1』であることと等価なように。
だからすべてのプログラムはラムダ式だけで表現できるということになる。
パフォーマンスを気にしなければ、の話だけど。
詳しくはλ計算を参照のこと。
