Yコンビネータ（不動点コンビネータ）

何のコードか（背景と何が有名か）

再帰関数を書くとき、私たちは当たり前のように自分の名前を使います。階乗なら fact(n) = if n=0 then 1 else n * fact(n-1) のように、定義の中で fact を呼ぶ。しかし関数に名前がなかったら——無名関数（ラムダ式）だけで再帰は書けるのか。

答えは「書ける」で、それを可能にするのが Yコンビネータ です。

Y = λf. (λx. f (x x)) (λx. f (x x))

このたった一行が有名なのは、名前による自己参照をまったく使わずに再帰を実現するからです。しかも純粋なラムダ計算——変数・関数・適用の3要素しか持たない最小の計算体系——の中だけで完結します。Yコンビネータの存在は、ラムダ計算が特別な再帰機構を持たなくてもチューリング完全であることの直接的な証拠でもあり、計算とは何かを問う理論の中心に置かれてきました。

「コンビネータ」とは自由変数を持たない閉じたラムダ式のこと。Y はその中でも不動点コンビネータ（fixed-point combinator）と呼ばれる一族に属します。

コードと仕組みの解説

横にスクロール

不動点とは、関数 f に対して f(a) = a を満たす値 a のこと。Yコンビネータの決定的な性質は、任意の f について次の等式が成り立つことです。

Y f = f (Y f)

つまり Y f は関数 f の不動点になっている。なぜこれが再帰を生むのか。等式を右辺へ何度でも展開できることに注目してください。

Y f = f (Y f) = f (f (Y f)) = f (f (f (Y f))) = ...

f が「1段ぶんの計算」を表すなら、Y f はその段を必要なだけ繰り返す。これがまさに再帰の姿です。

G G = (λx. f (x x)) G
    = f (G G)          -- x に G を代入

実際に階乗を作ってみます。まず、再帰呼び出しの箇所を引数 self として外に出した「1段ぶん」の関数を用意する。これ自体は再帰的でも自己参照的でもありません。

F = λself. λn. if (n = 0) then 1 else n * (self (n-1))

この F に Y を適用した Y F が、本物の階乗関数になります。Y F = F (Y F) なので、F の中の self に Y F（＝階乗そのもの）が渡り、self (n-1) が正しく1つ小さい階乗を計算する。名前 fact はどこにも登場していません。

正格評価では発散する — Zコンビネータを使う理由

ここに落とし穴があります。Yコンビネータがこの形のまま動くのは遅延評価（必要になるまで引数を評価しない、正規順序）の言語だけです。OCaml・Scheme・JavaScript・Python のような正格評価（値渡し、適用順序）の言語では、関数に渡す前に引数を最後まで評価します。すると Y f = f (Y f) の右辺 Y f を評価しようとして、また f (Y f) になり……と、f を一度も使わないまま x x の展開が止まらず、スタックオーバーフローで発散します。

解決策が Zコンビネータです。問題の自己適用 x x を、もう一段の関数（ラムダ）で包んでやる。

Z = λf. (λx. f (λv. x x v)) (λx. f (λv. x x v))

Y との違いは x x が λv. x x v になっている点だけ。これはイータ展開（eta-expansion）と呼ばれる変形で、x x と λv. x x v は「1つ引数 v を取れば同じ結果」という意味では等価です。ただし決定的な差があります。λv. x x v は関数（ラムダ）そのものなので、正格評価でも本体はすぐには評価されない。中の x x が実行されるのは、実際に引数 v が渡された瞬間まで遅らされます。こうして「必要になるまで自分を再生成しない」を実現し、正格評価でも発散しません。

逸話と経緯

Yコンビネータは、論理学者 ハスケル・カリー（Haskell Brooks Curry, 1900–1982）にちなみます。彼は1920年代後半からコンビネータ論理を研究し、ラムダ計算の発展と深く関わりました。関数型言語 Haskell、そしてカリー化（currying）に名を残すのも同じ人物です。

Yコンビネータは、しばしば paradoxical combinator（逆説コンビネータ） とも呼ばれます。この呼び名は、型のないラムダ計算に不動点コンビネータが存在することが、論理体系としての「不健全さ」と表裏一体であるという事実に由来します。任意の論理式に不動点を作れてしまうと、いわゆるカリーのパラドックスの構造が現れ、体系を証明の道具として無条件には使えなくなる——その危うさを指した名前です。

もう一点、名称の混同に注意が必要です。スタートアップ投資会社「Y Combinator」はこのラムダ計算の Y にちなんで命名されましたが、両者は無関係の別物です。本稿が扱うのはあくまで計算理論のほうの Y です。

遺産と教訓

Yコンビネータが今に残すものは、まず理論的な足場です。「ラムダ計算は再帰の特別な仕組みを内蔵していないのに、なぜ任意の計算ができるのか」という問いに、Y は構成的な答えを与えます。不動点コンビネータがあれば一般再帰が書ける。だからラムダ計算はチューリング完全である——この論法の要に Y が座っています。

実務面でも、Y の考え方は生きています。関数型言語の let rec や再帰の内部実装、遅延評価と正格評価で挙動が変わる場面、無名再帰をどう組むか——これらの根っこに Y と Z の対比があります。デバッガで再帰スタックが無限に伸びる現象を「評価順序の問題」として捉えられるのは、まさに Y が正格評価で発散する理由を知っているからです。

そして最大の教訓は、再帰の本質は「名前」ではなく「自己複製できる構造」にあるという洞察です。私たちは再帰を「関数が自分の名前を呼ぶこと」だと思い込みがちですが、Y は名前を一切使わずに再帰を作ってみせる。必要なのは自分自身のコピーを手に入れる手段（自己適用 x x）だけ。自己参照とは、名づけの問題ではなく構造の問題だった——この一行が示すのは、そういう計算の底にある事実です。

再帰やラムダ式・関数型プログラミングが実務でどう使われるかはプログラミングを、評価順序や実行モデルが挙動をどう左右するかはOSを参照してください。

一段で言うと

Yコンビネータは、名前を持たない関数に再帰の力を与える一行です。仕組みは Y f = f (Y f) という不動点の等式ひとつ。自己適用 x x が「自分をもう一度作る」動きになり、それを必要な回数だけ繰り返すことで再帰が生まれます。正格評価では発散するため、イータ展開で自己適用を隠した Z を使う——この実務上の分かれ道まで含めて、再帰と自己参照の正体を最短距離で見せてくれるのが、計算理論に残るこの短いコードです。