"Y Combinator" とは何かというと

  proc{|g|
    proc{|f|
      g[f[f]]
    }[
      proc{|f|
        g[proc{|y| f[f][y]}]
      }
    ]
  }

という Proc オブジェクトのことで、再帰的な関数を Proc オブジェクト
として表現するための道具です。さしあたって階乗 fact とフィボナッチ
数(列) fib をこれで計算する実験をしてみます。

-----^ fact.rb
Y = proc{|g|
  proc{|f|
    g[f[f]]
  }[
    proc{|f|
      g[proc{|y| f[f][y]}]
    }
  ]
}

fact = proc{|f| proc{|n| n == 0 ? 1 : n * f[n-1]}}
fib = proc{|f| proc{|n| n <= 1 ? n : f[n-1] + f[n-2]}}

p Y[fact][5] #=> 120
p Y[fib][10] #=> 55
-----$ fact.rb

私は、この Y の存在を酒井さんの日誌「日々の流転」

  http://www.sfc.keio.ac.jp/~s01397ms/d/

から知ったのですが、あまりに超不思議??なのでここで紹介します。


この Y の作り方ですが、ヒビルテで教えてもらった

  http://www.ececs.uc.edu/~franco/C511/html/Scheme/ycomb.html

に詳しく書かれています。これをちょと変形しつつ要約しましょう。

普通、再帰関数は

-----^ fact0.rb
def factorial(n); n == 0 ? 1 : n * factorial(n-1); end
def fibonacci(n); n <= 1 ? n : fibonacci(n-1) + fibonacci(n-2); end
p factorial(5) #=> 120
p fibonacci(10) #=> 55
-----$ fact0.rb

のように、自分の定義から自分を呼ぶように書かれます。これを
Proc に移し換えると、

-----^ fact1.rb
fact0 = proc{|n| n == 0 ? 1 : n * fact0[n-1]}
fib0 = proc{|n| n <= 1 ? n : fib0[n-1] + fib0[n-2]}
p fact0[5] #=> 120
p fib0[10] #=> 55
-----$ fact1.rb

ということになるでしょう。これは正しく動作します。しかし、Proc
は「名前のない関数」という側面があるので、ここは是非、自分の名
前を利用しない再帰関数を Proc で実現したいところです。これがそ
もそもの動機です。

そこでまず、fact0 や fib0 を

  proc{|f| proc{|n| n == 0 ? 1 : n * f[n-1]}}
  proc{|f| proc{|n| n <= 1 ? n : f[n-1] + f[n-2]}}

のように抽象的に扱い、これらを代入すると自動的に再帰させてくれ
るような Proc オブジェクトが作れないかと考えます。そしてそれに
成功したのが先の Y なわけです。

今から fact1.rb を変形して Y を順に作って行きましょう。

まず、ブロックの外のローカル変数のスコープがブロックの中まで及
ぶのをいいことに(?)自分の名前をブロック本体でも参照していたと
ころを、自分そのものをブロックパラメータとして渡すように変形し
ます。つまりこの関数を呼ぶとき必ず func[func] という形で呼ぶと
いう約束にします。(ここはちょっと難しいかもしれないです。)

-----^ fact2.rb
fact1 = proc{|f| proc{|n| n == 0 ? 1 : n * f[f][n-1]}}
fib1 = proc{|f| proc{|n| n <= 1 ? n : f[f][n-1] + f[f][n-2]}}
p fact1[fact1][5] #=> 120
p fib1[fib1][10] #=> 55
-----$ fact2.rb

次は、func[func] という形を S という Proc オブジェクトで表現し
ます。これはキーの打数を節約する意味しかないと思っていいです。

-----^ fact3.rb
S = proc{|x| x[x]}
fact1 = proc{|f| proc{|n| n == 0 ? 1 : n * S[f][n-1]}}
fib1 = proc{|f| proc{|n| n <= 1 ? n : S[f][n-1] + S[f][n-2]}}
p S[fact1][5] #=> 120
p S[fib1][10] #=> 55
-----$ fact3.rb

ここで、fact と fact1 を比べると

  fact  = proc{|f| proc{|n| n == 0 ? 1 : n * f[n-1]}}
  fact1 = proc{|f| proc{|n| n == 0 ? 1 : n * S[f][n-1]}}

であり、f が S[f] になっただけの違いです。そこで次のように
fact -> fact2, fib -> fib2 を f -> S[f] という変換で作って
みます。

-----^ fact4-f.rb
S = proc{|x| x[x]}

fact = proc{|f| proc{|n| n == 0 ? 1 : n * f[n-1]}}
fib = proc{|f| proc{|n| n <= 1 ? n : f[n-1] + f[n-2]}}

fact2 = proc{|f| fact[S[f]]}
fib2 = proc{|f| fib[S[f]]}

S[fact2]
S[fib2]
-----$ fact4-f.rb

すると S[fact2][5], S[fib2][10] を計算するまでもなく、S[fact2],
S[fib2] を計算させた時点で無限ループに陥ります。そこで、S[f] の
ところを  proc{|x| S[f][x]} に換えます。というのは一般には

  E

を

  proc{|x| E[x]}

に書き換えることが可能ですが、E 自体が今回の S[f] のような式だ
った場合、後者はその評価を後回しにすることができます。例えばこ
こでは、fact[F][0] の値は 0 に決まっているので、F を評価しなく
てもよく、この「遅延評価」が有効なのです。(ここが一番難しいか
な。)

-----^ fact4.rb
S = proc{|x| x[x]}

fact = proc{|f| proc{|n| n == 0 ? 1 : n * f[n-1]}}
fib = proc{|f| proc{|n| n <= 1 ? n : f[n-1] + f[n-2]}}

fact2 = proc{|f| fact[proc{|x| S[f][x]}]}
fib2 = proc{|f| fib[proc{|x| S[f][x]}]}

p S[fact2][5] #=> 120
p S[fib2][10] #=> 55
-----$ fact4.rb

これはうまく動きます。

後は、fact -> S[fact2], fib -> S[fib2] という変換を一気にする
Proc オブジェクト Y を作ってやればいいのです。

-----^ fact5.rb
S = proc{|x| x[x]}
Y = proc{|g| S[proc{|f| g[proc{|z| S[f][z]}]}]}

fact = proc{|f| proc{|n| n == 0 ? 1 : n * f[n-1]}}
fib = proc{|f| proc{|n| n <= 1 ? n : f[n-1] + f[n-2]}}

p Y[fact][5] #=> 120
p Y[fib][10] #=> 55
-----$ fact5.rb

このままでもよいのですが、不要な遅延評価が1つあるので、それを除い
たものが冒頭の fact.rb の Y です。(除かない方が速いかも。)


ちなみに、もっとわかりやすい Y の表現がないものかと考えてみたので
すが、なかなかいいのが無くて、、、

-----^ fact6.rb
S = proc{|x| x[x]}
D = proc{|x| proc{|y| proc{|z| x[y][z]}}}
T = proc{|x| proc{|y| proc{|z| y[x[z]]}}}
Y = T[T[D[S]]][S]

fact = proc{|x| proc{|n| n.zero? ? 1 : n * x[n - 1]}}
fib = proc{|f| proc{|n| n <= 1 ? n : f[n-1] + f[n-2]}}

p Y[fact][5] #=> 120
p Y[fib][10] #=> 55
-----$ fact6.rb

これは x[y] の評価を遅延する D と一種の 3 つ組の合成関数 T を使った
つもりですが、わかりやすくなったのかどうか。

もっとうまい Y Combinator の表現があったら教えてください。


ところで、念のためと思って検索したら、[ruby-talk:20469] でもちょっと
話題になってました。灯台下暗し。