不動点コンビネータ

不動点コンビネータの例

型無しラムダ計算や組合せ論理などの特定の数学的な計算形式化においては、すべての式は高階関数とみなすことができる。これらの形式化では、不動点コンビネータが存在することはすなわち、すべての関数が少なくとも1つの不動点を持つことを意味する。さらに、関数は複数の異なる不動点を持つことができる。
単純型付きラムダ計算などの他のいくつかの体系では、十分に型付けされた不動点コンビネータを書くことはできない。それらの体系で再帰をサポートするには、明示的に言語体系に組み込む必要がある。それでも再帰データ型によって拡張された単純型付きラムダ計算などでは不動点演算子を書くことができるが、ある種の「実用的な」不動点演算子（常にいずれかの適用を返すもの）は制限される。多相ラムダ計算（英: polymorphic lambda calculus、システムF、英: System F）では多相不動点コンビネータは型∀a.(a→a)→aを持つ（aは型変数）。

非標準不動点コンビネータ

型無しラムダ計算には不動点演算子と同じべーム木（英: 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)が挙げられる。非標準不動点コンビネータの集合は帰納的可算集合ではない。

不動点コンビネータの実装

これまでの節で実装というよりは主に理論の観点から述べてきた、評価戦略が名前渡しの場合と値渡しの場合の違いは、実装においては、非正格(non-strict)なプログラミング言語（ないし処理系）と正格(strict)な言語の場合にほぼそのまま対応する。非正格な（遅延評価の、と言い換えてもだいたい同じ。具体的にはHaskellなどがそう）言語ないし処理系においては、ほぼ不動点コンビネータの意味そのままに循環的に実装できる。正格な場合は修正が必要であり、後述する。理論的には循環が無いことに意味があったが、実装においては循環的で普通は問題が無く、そのほうが効率的でもある。以下にHaskellによる不動点コンビネータの実装を示す。この不動点コンビネータはHaskellにおいては伝統的にfixと呼ばれる。fixは多相不動点コンビネータであることに注意せよ（前述のシステムFに関する議論も参照）。なお、Haskellには型推論があるが、以下では曖昧さをなくすために型は明記する（一般に、こういった特殊な型を使う場合は型を明記したほうが良いし、推論の実装の限界のために明記が必要なこともある）。定義の後に使用例が続く。
なお、型無しラムダ計算におけるカリーのYコンビネータは、そのまま実装しようとすると、Haskellの型チェッカによって拒否される。
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)を持つべきである。要するに、これは関数を取って返す関数でのみ動く。例として、以下は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" と評価される *)
これと同じアイデアは（この場合は「貧乏人のクロージャ (poor man's closures) 」として使われる）メソッド内部のインナークラス（Javaではローカルインナークラスと呼ばれる）をサポートしている正格言語で（単相）不動点コンビネータを実装するのに用いることができる。Javaの場合、そのようなクラスが無名だとしても構文はなお扱いにくい（Javaコード）。たとえば、C++の関数オブジェクトでは呼び出し構文は単純化されるが、それらはまだ生成されている段階である。できればboost::bindのような補助関数を用いることが望ましい（C++コード）。

再帰型による符号化の例

再帰データ型（システム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) = xlet 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という名前で呼ばれていることもある。

他の手段による無名再帰

不動点コンビネータは識別子に束縛されていない関数が自分自身を呼び出す一般的な方法であるが、言語によっては特別な名前などで自分自身を呼び出すことができる。たとえばJavaScriptでは自分自身を参照することができるような名前が用意されており次のように書くことができる。
// 120を返す(function(x){
    return x == 0
         ? 1
         : x * arguments.callee(x - 1); // arguments.calleeは自分自身を指す})(5);
（なお、ECMAScript5のstrict modeではarguments.calleeの使用は禁止されている）