不動点コンビネータ

不動点コンビネータ（ふどうてんコンビネータ、、不動点結合子、ふどうてんけつごうし）とは、与えられた関数の不動点（のひとつ）を求める高階関数である。不動点演算子（ふどうてんえんざんし、）、パラドキシカル結合子（）などとも呼ばれる。ここで関数"f"の不動点とは、"f"("x") = "x"を満たすような"x"のことをいう。
すなわち高階関数g が不動点コンビネータであるとは、
事を指す。
不動点コンビネータの定義は、任意の関数"f" に対し、
が成立する事であるとも言い換えられる。
第一級関数をサポートしているプログラミング言語では、不動点コンビネータを用いて識別子に束縛されない関数の再帰を定義することができる。そういったテクニックは、しばしば無名再帰と呼ばれる。
不動点コンビネータは高階関数であるため、その歴史はラムダ計算の発達と深く関係している。型無しラムダ計算（）においては、ハスケル・カリーのY = λf·(λx·f (x x)) (λx·f (x x))という不動点コンビネータがよく知られている。型無しラムダ計算には無数の不動点コンビネータが存在するが、一方で単純型付きラムダ計算などのより限定的な計算モデルでは、不動点コンビネータは必ずしも存在するとは限らない。
不動点コンビネータによる再帰の実現.
不動点コンビネータにより、第一級関数をサポートしているプログラミング言語において、明示的に再帰を書かずに再帰を実現する為に用いる事ができる。なお、一般にそういった言語では普通に再帰が使えるので、プログラミングにおいてはパズル的なテクニック以上の意味は無い。一方、循環なく関数の意味を定義する（できる）、ということは、計算理論の上では重要である。
まず、再帰関数の性質を簡単に振り返り、記号をいくつか定義する。関数"a" が再帰的に定義されているとき、"a"の定義式は何らかの高階関数"U" を用いて、
と書ける。たとえば"a(x)" がxの階乗を計算する関数である場合、"U"として
を取る事ができる。上述のように定義された"U" が(1)を満たすのは明らかであろう。
"U" を用いて高階関数formula_4を
と定義する。
（すなわち"V"は関数"f" を入力として受け取ると
関数「formula_6」を出力する高階関数である。
ラムダ計算の用語で言えば、"V" は"U" のカリー化formula_7にあたる。）
"V" の定義より、formula_8はそれ自身関数であり、任意の"x" に対し、
が成り立つ。ここでformula_10は関数formula_8に"x" を入力したときの値。
さて、g を不動点コンビネータとするとき、不動点コンビネータの定義より特に、
formula_12は"V" の定義域の元である事が分かる。
"V" の定義域は関数の集合だったので、これはすなわちformula_12はそれ自身関数である事を意味する。
この関数formula_12が(1)式で定義された再帰関数"a" と一致する事を示す事ができる（後述）。
よって以下のようにすれば不動点コンビネータg で再帰関数"a" を実現できる事になる：
formula_15 の証明.
最後にformula_12が(1)式で定義された再帰関数"a" と一致する事を示す。
不動点コンビネータの定義より、formula_12は
を満たす。
前述したようにformula_12はそれ自身関数なので、値"x"に対しformula_21を考える事ができる。
formula_21は以下を満たす：
すなわち
(1)と(5)を見比べると、(5)は(1)で"a"をformula_12 に置き換えたものに等しい事が分かる。
(1)は"a" の（再帰的な）定義式であったので、これはすなわちformula_12 が"a" の定義式を満たす事を意味する。
よって
が成立する事が分かった。
不動点コンビネータの例.
型無しラムダ計算や組合せ論理などの特定の数学的な計算形式化においては、すべての式は高階関数とみなすことができる。これらの形式化では、不動点コンビネータが存在することはすなわち、すべての関数が少なくとも1つの不動点を持つことを意味する。さらに、関数は複数の異なる不動点を持つことができる。
単純型付きラムダ計算などの他のいくつかの体系では、十分に型付けされた不動点コンビネータを書くことはできない。それらの体系で再帰をサポートするには、明示的に言語体系に組み込む必要がある。それでも再帰データ型によって拡張された単純型付きラムダ計算などでは不動点演算子を書くことができるが、ある種の「実用的な」不動点演算子（常にいずれかの適用を返すもの）は制限される。多相ラムダ計算（、システムF、）では多相不動点コンビネータは型∀a.(a→a)→aを持つ（"a"は型変数）。
Yコンビネータ.
型無しラムダ計算においてよく知られた（そしておそらく最もシンプルな）不動点コンビネータはYコンビネータと呼ばれる。これはハスケル・カリーによって発見されたもので、次のように定義される。
実際に関数"g"を適用することによって、この関数が不動点コンビネータとして動作するのが分かる。
これをそのままラムダ計算で使うと、評価戦略が値渡しだった場合には (Y g) が (g (Y g)) と展開された後も、引数の値を先に求めようとして (g (g (Y g))) →...→ (g ... (g (Y g))...) のように無限に展開され続けて止まらなくなってしまうので、次節で示すZコンビネータのように修正する。評価戦略が名前渡しの場合はこのまま使える。
このカリーによるコンビネータのみをYコンビネータとすることもあるが、実装などでは不動点コンビネータを指す名前として他の形であってもYという名前を使っていることもある（#グラフ簡約の節の注を参照せよ）。
SKIコンビネータ計算では次のようになる。
Zコンビネータ.
値渡し評価（適用順序）でも使用可能なバージョンのYコンビネータは、通常のYコンビネータの一部をη変換することで与えられる。
Python での実装。その他のプログラミング言語での実装は無名再帰を参照。
Z = lambda f: (lambda x: f(lambda *y: x(x)(*y)))(lambda x: f(lambda *y: x(x)(*y)))
Z(lambda f: lambda n: 1 if n == 0 else n * f(n - 1))(5)
チューリング不動点コンビネータ.
もう一つの一般的な不動点コンビネータは、チューリング不動点コンビネータである（発見者であるアラン・チューリングの名にちなむ）。
これはシンプルな値渡し形式も持つ。
SとKによる最もシンプルな不動点コンビネータ.
SKIコンビネータ計算のSとKによる最もシンプルな不動点コンビネータは、ジョン・トロンプによって発見された以下であり、
これは次のラムダ式と対応する。
その他の不動点コンビネータ.
型無しラムダ計算における不動点コンビネータは無数に存在するので、特に珍しいわけではない。2005年、メイヤー・ゴールドバーグ (Mayer Goldberg) は型無しラムダ計算の不動点コンビネータの集合が帰納的可算集合であることを示した。
次のようないくつかの不動点コンビネータ（ジャン・ウィレム・クロップによって組み立てられた）は、主として遊びに使われる。
ここで
非標準不動点コンビネータ.
型無しラムダ計算には不動点演算子と同じベーム木（）を持つラムダ式がある。すなわちそれらはλx.x(x(x ... ))と同じ無限の拡張を持つ。これは非標準不動点コンビネータ（）と呼ばれる。定義より、あらゆる不動点コンビネータは非標準でもあるが、すべての非標準不動点コンビネータが不動点コンビネータであるわけではない。それらのいくつかは「標準」の定義を満たさないからである。これらの変わったコンビネータは特にstrictly non-standard fixed point combinatorsと呼ばれる。例として、B = λx.xxかつM = λxyz.x(yz)としたときのコンビネータN = BM(B(BM)B)が挙げられる。非標準不動点コンビネータの集合は帰納的可算集合ではない。
不動点コンビネータの実装.
これまでの節で実装というよりは主に理論の観点から述べてきた、評価戦略が名前渡しの場合と値渡しの場合の違いは、実装においては、非正格(non-strict)なプログラミング言語（ないし処理系）と正格(strict)な言語の場合にほぼそのまま対応する。非正格な（遅延評価の、と言い換えてもだいたい同じ。具体的にはHaskellなどがそう）言語ないし処理系においては、ほぼ不動点コンビネータの意味そのままに循環的に実装できる。正格な場合は修正が必要であり、後述する。理論的には循環が無いことに意味があったが、実装においては循環的で普通は問題が無く、そのほうが効率的でもある。以下にHaskellによる不動点コンビネータの実装を示す。この不動点コンビネータはHaskellにおいては伝統的にcodice_1と呼ばれる。codice_1は多相不動点コンビネータであることに注意せよ（前述のシステムFに関する議論も参照）。なお、Haskellには型推論があるが、以下では曖昧さをなくすために型は明記する（一般に、こういった特殊な型を使う場合は型を明記したほうが良いし、推論の実装の限界のために明記が必要なこともある）。定義の後に使用例が続く。
なお、型無しラムダ計算におけるカリーのYコンビネータは、そのまま実装しようとすると、Haskellの型チェッカによって拒否される。