不動点コンビネータ
不動点コンビネータは識別子に束縛されていない関数が自分自身を呼び出す一般的な方法であるが、言語によっては特別な名前などで自分自身を呼び出すことができる。詳細は無名再帰を参照。
が成立する事であるとも言い換えられる。
第一級関数をサポートしているプログラミング言語では、不動点コンビネータを用いて識別子に束縛されない関数の再帰を定義することができる。そういったテクニックは、しばしば無名再帰と呼ばれる。
不動点コンビネータは高階関数であるため、その歴史はラムダ計算の発達と深く関係している。型無しラムダ計算(英: untyped lambda calculus)においては、ハスケル・カリーのY = λf·(λx·f (x x)) (λx·f (x x))という不動点コンビネータがよく知られている。型無しラムダ計算には無数の不動点コンビネータが存在するが、一方で単純型付きラムダ計算などのより限定的な計算モデルでは、不動点コンビネータは必ずしも存在するとは限らない。
型無しラムダ計算においてよく知られた(そしておそらく最もシンプルな)不動点コンビネータはYコンビネータと呼ばれる。これはハスケル・カリーによって発見されたもので、次のように定義される。
Y = (λf . (λx . f (x x)) (λx . f (x x)))
実際に関数gを適用することによって、この関数が不動点コンビネータとして動作するのが分かる。
これをそのままラムダ計算で使うと、評価戦略が値渡しだった場合には (Y g) が (g (Y g)) と展開された後も、引数の値を先に求めようとして (g (g (Y g))) →...→ (g ... (g (Y g))...) のように無限に展開され続けて止まらなくなってしまうので、次節で示すZコンビネータのように修正する。評価戦略が名前渡しの場合はこのまま使える。
このカリーによるコンビネータのみをYコンビネータとすることもあるが、実装などでは不動点コンビネータを指す名前として他の形であってもYという名前を使っていることもある(#グラフ簡約の節の注を参照せよ)。
SKIコンビネータ計算では次のようになる。
Y = S (K (S I I)) (S (S (K S) K) (K (S I I)))