Y combinator の謎

Last Modified: Mon Oct 4 13:01:07 UTC 2010

有名な不動点演算子である Y combinator の謎に迫る。


まとめ:

Y combinator は、 不動点演算子 (不動点コンビネータ) と呼ばれるもののひとつである。 ある高階関数 f に Y を適用した値 Yf は、関数 f の不動点となる。 不動点演算子を使うと、名前のない関数でも自分自身を再帰的に呼び出すことができる:

これ以外にも、不動点演算子として Turingコンビネータ θ が知られている:

(追記) λ-式 (lambda expression) は、さしずめ『関数のヒモノ (干物)』のようなものである。 水 (=引数) をかけると元に戻って動きだす。究極的には、これにはただ2種類の操作しかない:

なお、Y演算子は Python で次のように書くこともできるが、 このほうがわかりにくい。

def Y(f):
  def _a(x):
    return f(x(x))
  return _a(_a)

λ計算を使うと、すべてのプログラムの実行は純粋な 文字列操作のみによってモデル化されるので、 上のようなプログラムでも何がどこに代入されているかを 考える必要がない。ここにλ計算の強みがある。


Yusuke Shinyama