不動点コンビネータ
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))
なお、型無しラムダ計算におけるカリーのYコンビネータは、そのまま実装しようとすると、Haskellの型チェッカによって拒否される。
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コード実装である。
以下は Python での実装。
Java 8 や C++11 では無名関数(ラムダ式)が使えるので上記と同じ方法で実装できる。それよりも前の時代の Java や C++ では少々複雑だった。