不動点コンビネータの作り方(λ抽象)

「λ抽象」とわざわざ付けたのは、SKIコンビネータとかでも不動点コンビネータは作れるよなあ、などとしょうがないことを考えただけであって、 λ抽象の方がだいぶ簡単に作れるとはいえどちらも本質的には同じものであるから、とりあえず簡単な方だけ紹介しようという目論見である。
SKIコンビネータで作りたいなら自動生成するなりプロの技で作るなりすればいいと思う。

基本方針

不動点コンビネータとは、
Fg -> g(Fg) となるようなλ抽象Fのことである。
後述するが、これによってλ計算で再帰を記述できるようになる。
(ちなみに、コンビネータとは自由変数を含まないλ抽象のこと……だと思う)

さて、簡約後の式にF自体が含まれているということは、Fは何か断片から全体を再生できる構造になっている必要がある。
より正確には、「コピーや再生、適用を担当する式」と「適用される側の式」の2段構えになっていて、かつ前者と後者はどちらか一方から再現できるのが良い。
まあ最初に思いつくのは前者と後者が全く同じ場合だし、他にクールな方法も思いつかないので、ここではその戦略でいく。
以下では、その断片をfとし、fを代入される予定の束縛変数をcとしよう。

Fg -> ffg

「繰り返し」の最も単純なパターン。まあ発想の単純さと完成したコンビネータの単純さに相関があるかは知らないが。

Fg -> ffg -> g(Fg) -> g(ffg) fab -> b(aab) より f = (λa.(λb.b(aab))) よって F = (λc.cc)(λa.(λb.b(aab)))

Fg -> fgf

これはちょっとひねくれている。とはいえ、することは上と同じだ。

Fg -> fgf -> g(Fg) -> g(fgf) fab -> a(bab) より f = (λa.(λb.a(bab))) よって F = (λc.(λg.cgc))(λa.(λb.a(bab)))

Fg -> fg(fg)

実はこれがなかなか良い。

Fg -> fg(fg) -> g(Fg) -> g(fg(fg)) fab -> a(bb) より f = (λa.(λb.a(bb))) このとき fg -> (λb.g(bb)) より F = (λg.fg(fg)) = (λg.(λb.g(bb))(λb.g(bb)))

これは特に「Yコンビネータ」と呼ばれる。
(普通は (λf.(λx.f(xx))(λx.f(xx))) と書かれる。)

不動点コンビネータの使い方(再帰)

面倒なので再帰としての簡単な使い方だけ書く。
まあこの記事を読みたいような人なら言うまでもないだろうけど。

function f(x) { if(p(x)) { A(x); } else { f(B(x)); } } という処理は、 Yfx -> f(Yf)x より、 f = (λn.(λx.px(Ax)(n(Bx)))) と表現できる。 (ただし、pxは真偽値を返し、true = (λxy.x)、false = (λxy.y) とする)