「Yコンビネータ 」は不動点演算子について説明しているこの項目へ転送 されています。カリフォルニア州の企業については「Yコンビネータ (企業) 」をご覧ください。
不動点コンビネータ （ふどうてんコンビネータ、英 : fixed point combinator 、不動点結合子 、ふどうてんけつごうし）とは、与えられた関数 の不動点 （のひとつ）を求める高階関数 である。不動点演算子 （ふどうてんえんざんし、英 : fixed-point operator ）、パラドキシカル結合子 （英 : paradoxical combinator ）などとも呼ばれる。ここで関数
f
{\displaystyle f}
不動点 とは、
f
(
x
)
=
x
{\displaystyle f(x)=x}
x
{\displaystyle x}
すなわち高階関数
g
{\displaystyle {\boldsymbol {g}}}
任意の関数
f
{\displaystyle f}
p
=
g
(
f
)
{\displaystyle p={\boldsymbol {g}}(f)}
f
(
p
)
=
p
{\displaystyle f(p)=p}
事を指す。
あるいは全く同じことだが、不動点コンビネータの定義は、任意の関数
f
{\displaystyle f}
f
(
g
(
f
)
)
=
g
(
f
)
{\displaystyle f({\boldsymbol {g}}(f))={\boldsymbol {g}}(f)}
が成立する事であるとも言い換えられる。
第一級関数 をサポートしているプログラミング言語 では、不動点コンビネータを用いて識別子 に束縛 されない関数の再帰 を定義することができる。そういったテクニックは、しばしば無名再帰 と呼ばれる。[ 1] [ 2]
不動点コンビネータは高階関数であるため、その歴史はラムダ計算 の発達と深く関係している。型無しラムダ計算 （英 : untyped lambda calculus ）においては、ハスケル・カリー の Y = λf·(λx·f (x x)) (λx·f (x x))単純型付きラムダ計算 などのより限定的な計算モデル では、不動点コンビネータは必ずしも存在するとは限らない。
不動点コンビネータにより、第一級関数をサポートしているプログラミング言語において、明示的に再帰 を書かずに再帰を実現する為に用いる事ができる。なお、一般にそういった言語では普通に再帰が使えるので、プログラミングにおいてはパズル的なテクニック以上の意味は無い。一方、循環なく関数の意味を定義する（できる）、ということは、計算理論の上では重要である。
まず、再帰関数の性質を簡単に振り返り、記号をいくつか定義する。関数
a
{\displaystyle a}
a
{\displaystyle a}
U
{\displaystyle U}
a
(
x
)
=
U
(
a
,
x
)
{\displaystyle a(x)=U(a,x)}
(Eq. 1 )
と書ける。たとえば
a
(
x
)
{\displaystyle a(x)}
x
{\displaystyle x}
階乗 を計算する関数である場合、
U
{\displaystyle U}
U
(
f
,
x
)
=
{
1
if
x
=
0
x
f
(
x
−
1
)
otherwise
{\displaystyle U(f,x)={\begin{cases}1&{\text{if }}x=0\\xf(x-1)&{\text{otherwise}}\end{cases}}}
を取る事ができる。上述のように定義された
U
{\displaystyle U}
Eq. 1
U
{\displaystyle U}
V
{\displaystyle V}
V
:
f
↦
U
(
f
,
⋅
)
{\displaystyle V~:~f\mapsto U(f,\cdot )}
(Eq. 2 )
と定義する。
（すなわち
V
{\displaystyle V}
f
{\displaystyle f}
x
↦
U
(
f
,
x
)
{\displaystyle x\mapsto U(f,x)}
ラムダ計算 の用語で言えば、
V
{\displaystyle V}
U
{\displaystyle U}
カリー化
λ
f
.
(
λ
x
.
U
)
{\displaystyle \lambda f.(\lambda x.U)}
V
{\displaystyle V}
V
(
f
)
{\displaystyle V(f)}
x
{\displaystyle x}
V
(
f
)
(
x
)
=
U
(
f
,
x
)
{\displaystyle V(f)(x)=U(f,x)}
(Eq. 3 )
が成り立つ。ここで
V
(
f
)
(
x
)
{\displaystyle V(f)(x)}
V
(
f
)
{\displaystyle V(f)}
x
{\displaystyle x}
さて、g
g
(
V
)
{\displaystyle {\boldsymbol {g}}(V)}
V
{\displaystyle V}
V
{\displaystyle V}
g
(
V
)
{\displaystyle {\boldsymbol {g}}(V)}
g
(
V
)
{\displaystyle {\boldsymbol {g}}(V)}
a
{\displaystyle a}
よって以下のようにすれば不動点コンビネータg
a
{\displaystyle a}
U のプログラムを書く。V をEq. 2
a
=
g
(
V
)
{\displaystyle a={\boldsymbol {g}}(V)}
a
=
g
(
V
)
{\displaystyle a={\boldsymbol {g}}(V)}
最後に
g
(
V
)
{\displaystyle {\boldsymbol {g}}(V)}
Eq. 1
a
{\displaystyle a}
g
(
V
)
{\displaystyle {\boldsymbol {g}}(V)}
V
(
g
(
V
)
)
=
g
(
V
)
{\displaystyle V({\boldsymbol {g}}(V))={\boldsymbol {g}}(V)}
(Eq. 4 )
を満たす。
前述したように
g
(
V
)
{\displaystyle {\boldsymbol {g}}(V)}
x に対し
g
(
V
)
(
x
)
{\displaystyle {\boldsymbol {g}}(V)(x)}
g
(
V
)
(
x
)
{\displaystyle {\boldsymbol {g}}(V)(x)}
g
(
V
)
(
x
)
{\displaystyle {\boldsymbol {g}}(V)(x)}
=
V
(
g
(
V
)
)
(
x
)
{\displaystyle =V({\boldsymbol {g}}(V))(x)}
(Eq. 4
=
U
(
g
(
V
)
,
x
)
{\displaystyle =U({\boldsymbol {g}}(V),x)}
(Eq. 3
すなわち
g
(
V
)
(
x
)
=
U
(
g
(
V
)
,
x
)
{\displaystyle {\boldsymbol {g}}(V)(x)=U({\boldsymbol {g}}(V),x)}
(Eq. 5 )
Eq. 1 Eq. 5 Eq. 5 Eq. 1
a
{\displaystyle a}
g
(
V
)
{\displaystyle {\boldsymbol {g}}(V)}
Eq. 1
a
{\displaystyle a}
g
(
V
)
{\displaystyle {\boldsymbol {g}}(V)}
a
{\displaystyle a}
a
=
g
(
V
)
{\displaystyle a={\boldsymbol {g}}(V)}
が成立する事が分かった。
型無しラムダ計算や組合せ論理 などの特定の数学的な計算形式化においては、すべての式は高階関数とみなすことができる。これらの形式化では、不動点コンビネータが存在することはすなわち、すべての関数が少なくとも1つの不動点を持つ ことを意味する。さらに、関数は複数の異なる不動点を持つことができる。
単純型付きラムダ計算などの他のいくつかの体系では、十分に型付けされた不動点コンビネータを書くことはできない。それらの体系で再帰をサポートするには、明示的に言語体系に組み込む必要がある。それでも再帰データ型 によって拡張された単純型付きラムダ計算などでは不動点演算子を書くことができるが、ある種の「実用的な」不動点演算子（常にいずれかの適用を返すもの）は制限される。多相ラムダ計算 （英 : polymorphic lambda calculus 、システムF 、英 : System F ）では多相不動点コンビネータは型
∀
a
.
(
a
→
a
)
→
a
{\displaystyle \forall {a}.(a\rightarrow a)\rightarrow a}
a
{\displaystyle a}
型無しラムダ計算においてよく知られた（そしておそらく最もシンプルな）不動点コンビネータはY コンビネータと呼ばれる。これはハスケル・カリーによって発見されたもので、次のように定義される。
Y = (λf . (λx . f (x x)) (λx . f (x x)))
実際に関数g を適用することによって、この関数が不動点コンビネータとして動作するのが分かる。
Y g= (λf . (λx . f (x x)) (λx . f (x x))) g
(Y の定義より)
= (λx . g (x x)) (λx . g (x x))
(λfのβ簡約、主関数をgに適用)
= (λy . g (y y)) (λx . g (x x))
(α変換、束縛変数の名前を変える)
= g ((λx . g (x x)) (λx . g (x x)))
(λyのβ簡約、左の関数を右の関数に適用)
= g (Y g)
(第2式より)
これをそのままラムダ計算 で使うと、評価戦略 が値渡しだった場合には (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)))
値渡し評価（適用順序）でも使用可能なバージョンのY コンビネータは、通常のY コンビネータの一部をη変換することで与えられる。
Z = λf. (λx. f (λy. x x y)) (λx. f (λy. x x y))Python での実装。その他のプログラミング言語での実装は無名再帰 を参照。
Z = lambda f : ( lambda x : f ( lambda * y : x ( x )( * y )))( lambda x : f ( lambda * y : x ( x )( * y )))
# 利用方法（5の階乗の計算）
Z ( lambda f : lambda n : 1 if n == 0 else n * f ( n - 1 ))( 5 )
もう一つの一般的な不動点コンビネータは、チューリング不動点コンビネータである（発見者であるアラン・チューリング の名にちなむ）。
Θ = (λx. λy. (y (x x y))) (λx. λy. (y (x x y)))これはシンプルな値渡し形式も持つ。
Θ v
SKIコンビネータ計算 のSとKによる最もシンプルな不動点コンビネータは、ジョン・トロンプ によって発見された以下であり、
Y' = S S K (S (K (S S (S (S S K)))) K)これは次のラムダ式と対応する。
Y' = (λx. λy. x y x) (λy. λx. y (x y x))
型無しラムダ計算における不動点コンビネータは無数に存在するので、特に珍しいわけではない。2005年、メイヤー・ゴールドバーグ (Mayer Goldberg) は型無しラムダ計算の不動点コンビネータの集合が帰納的可算集合 であることを示した。[ 3]
次のようないくつかの不動点コンビネータ（ジャン・ウィレム・クロップ によって組み立てられた）は、主として遊びに使われる。
Yk = (L L L L L L L L L L L L L L L L L L L L L L L L L L)ここで
L = λabcdefghijklmnopqstuvwxyzr. (r (t h i s i s a f i x e d p o i n t c o m b i n a t o r))
型無しラムダ計算には不動点演算子と同じベーム木 （英 : Böhm tree ）を持つラムダ式がある。すなわちそれらは λx.x(x(x ... )) と同じ無限の拡張を持つ。これは非標準不動点コンビネータ （英 : non-standard fixed point combinators ）と呼ばれる。定義より、あらゆる不動点コンビネータは非標準でもあるが、すべての非標準不動点コンビネータが不動点コンビネータであるわけではない。それらのいくつかは「標準」の定義を満たさないからである。これらの変わったコンビネータは特に strictly non-standard fixed point combinators と呼ばれる。例として、B = λx.xx かつ M = λxyz.x(yz) としたときのコンビネータ N = BM(B(BM)B) が挙げられる。非標準不動点コンビネータの集合は帰納的可算集合ではない。[ 3]
これまでの節で実装というよりは主に理論の観点から述べてきた、評価戦略 が名前渡しの場合と値渡しの場合の違いは、実装においては、非正格(non-strict)なプログラミング言語 （ないし処理系）と正格(strict)な言語の場合にほぼそのまま対応する。非正格な（遅延評価 の、と言い換えてもだいたい同じ。具体的にはHaskell などがそう）言語ないし処理系においては、ほぼ不動点コンビネータの意味そのままに循環的に実装できる。正格な場合は修正が必要であり、後述する。理論的には循環が無いことに意味があったが、実装においては循環的で普通は問題が無く、そのほうが効率的でもある。以下にHaskellによる不動点コンビネータの実装を示す。この不動点コンビネータはHaskellにおいては伝統的にfixと呼ばれる。fixは多相不動点コンビネータであることに注意せよ（前述のシステムFに関する議論も参照）。なお、Haskellには型推論 があるが、以下では曖昧さをなくすために型は明記する（一般に、こういった特殊な型を使う場合は型を明記したほうが良いし、推論の実装の限界のために明記が必要なこともある）。定義の後に使用例が続く。
なお、型無しラムダ計算におけるカリーのYコンビネータ は、そのまま実装しようとすると、Haskellの型チェッカによって拒否される。[ 4]
fix :: (a -> a) -> a
fix f = f (fix f)
fix (const 9) -- constは第1引数を返し、第2引数を捨てる関数。9と評価される
factabs fact 0 = 1 -- factabsはラムダ計算の例のFから拝借
factabs fact x = x * fact (x-1)
(fix factabs) 5 -- 120と評価される
fixの適用は遅延評価されるので無限ループ にはならない。たとえばfix (const 9)が(const 9)(fix f)として展開されるとき、部分式fix fは評価されない。ところが、Haskellによるfixの定義を正格(strict)プログラミング言語に持ち込むと無限ループになる。なぜなら、fへ渡した引数は事前に展開され、無限の呼び出しの連続f (f ... (fix f) ... ))を生み出すからである。
ML のような正格言語においては、クロージャの使用を強制することによって無限再帰問題を回避することができる。fixの正格なバージョンは型
∀
a
.
∀
b
.
(
(
a
→
b
)
→
(
a
→
b
)
)
→
(
a
→
b
)
{\displaystyle \forall {a}.\forall {b}.((a\rightarrow b)\rightarrow (a\rightarrow b))\rightarrow (a\rightarrow b)}
fixの正格なバージョンのOCamlコード実装である。
let rec fix f x = f ( fix f ) x (* 余分なxに注目 *)
let factabs fact = function (* factabsはエクストラレベルのラムダ抽象 *)
0 -> 1
| x -> x * fact ( x - 1 )
let _ = ( fix factabs ) 5 (* "120" と評価される *)
以下は Python での実装。
def fix ( f ):
return lambda x : f ( fix ( f ))( x )
# 利用方法（5の階乗の計算）
fix ( lambda f : lambda n : 1 if n == 0 else n * f ( n - 1 ))( 5 )
Java 8 や C++11 では無名関数（ラムダ式）が使えるので上記と同じ方法で実装できる。それよりも前の時代の Java や C++ では少々複雑だった[ 5] [ 6]
再帰データ型（システムFω を参照）をサポートしているプログラミング言語では、型レベルで再帰を適切に計算することによってYコンビネータの型付けが可能になる。変数xを自己適用する必要性は同型の (Rec a -> a) を用いて定義される型 (Rec a) によって管理することができる。
例として、以下のHaskellコードは、型とともに同型写像のInとoutの2つの方向の名前を持つ。
In :: (Rec a -> a) -> Rec a
out :: Rec a -> (Rec a -> a)
そして次のように書くことができる。
newtype Rec a = In { out :: Rec a -> a }
y :: (a -> a) -> a
y = \f -> (\x -> f (out x x)) (In (\x -> f (out x x)))
OCamlによる等価なコードは以下。
type ' a recc = In of ( ' a recc -> ' a )
let out ( In x ) = x
let y f = ( fun x a -> f ( out x x ) a ) ( In ( fun x a -> f ( out x x ) a ))
グラフ簡約（en:Graph reduction を参照）による計算系では、不動点コンビネータへの適用(apply, application)は理論通り展開しても良いが、左の図のように循環のあるグラフに簡約するという一種の、のぞき穴的最適化 が知られている。また、これはカリーのYコンビネータ ではないが(この図のように)便宜的にYという名前で呼ばれていることもある[ 7]
不動点コンビネータは識別子に束縛されていない関数が自分自身を呼び出す一般的な方法であるが、言語によっては特別な名前などで自分自身を呼び出すことができる。詳細は無名再帰 を参照。
^ This terminology appear to be largely folklore , but it does appear in the following:
Trey Nash, Accelerated C# 2008 , Apress, 2007, ISBN 1590598733 , p. 462--463. Derived substantially from Wes Dyer 's blog (see next item).
Wes Dyer Anonymous Recursion in C# , February 02, 2007, contains a substantially similar example found in the book above, but accompanied by more discussion. ^ The If Works Deriving the Y combinator , January 10th, 2008
^ a b Goldberg, 2005
^ Haskell mailing list thread on How to define Y combinator in Haskell , 15 Sep 2006
^ The Y Combinator in Arc and Java - Javaコード^ bind - Fixed point combinators in C++ - Stack Overflow - C++コード^ たとえば、Turner の"A New Implementation Technique for Applicative Languages"（doi :10.1002/spe.4380090105 ）の Figure. 3 と、その直前の説明を見よ。
