前の日曜日に書いた記事 に関連するんだけど，
あれって，ラムダ計算では有名な
Y-Combinator
あるいは
不動点演算子
(fixed point combinator)
ってものに関係するらしい．
更に，プログラミング言語の制約で
そのままではstack overflowが
発生してしまうのを回避するため，
遅延評価を組み込んだものは更に
Z-Combinator
って言うらしい．
これって何かって言うと，
ある関数を入力した時に
その関数の不動点関数を
出力する関数
ってことらしい．
で，これを式で書くと，
ある関数F(x)とし，
Y(x)をY-combinatorとすると，
Y(F(x)) = F(Y(F(x)))
という感じで表される．
つまり，
Y(F(x)) = fp(x)
とすると，
Yによって関数Fから関数fpが出力され，
さらに，
fp(x) = F(fp(x))
から，fpはＦの不動点となっている．
で，こいつが何者かということなんだけど，
ラムダ計算ではすべてが関数でプログラムできる
っていう原則？があるんだけど，
そこで，再帰処理，
つまり，制御処理のループを
表現するものとして
このY-Combinatorがある
ってことらしい．
まあ，詳細はきちんとしたものを
読んで理解する必要があるけどね．
一応，さすらいびとが理解するために
参考にしたサイトだけでもここに上げておくよ．
おとうさんにもわかるYコンビネータ！(絵解き解説編) - よくわかりません
あと，参考資料として
Y-Combinatorの
いろいろな言語での実装を
紹介しているサイトも．