ruby-list

"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

このままでもよいのですが、不要な遅延評価が１つあるので、それを除い
たものが冒頭の 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] でもちょっと
話題になってました。灯台下暗し。

Thread

Prev Next

In This Thread

Prev Next

[#34988] BigFloat の to_i メソッドについて — Sako Hiroshi <sakoh@...2.so-net.ne.jp>

[#34989] mailing list archive? — maili31s@... (SugHimsi == SUGIHARA Hiroshi)

[#34991] a = 4 ; p((a < 3) or (a > 5)) — Take_tk <ggb03124@...>

[#34994] コマンドライン引数の # — 渋川よしき <yoshiki@...>

[#35003] Is Ruby default in Jaguar? — maili31s@... (SugHimsi==SUGIHARA Hiroshi)

[#35005] FILE_READPTR — Daisuke Aoki <dai@...>

[#35028] win32.c 中の my* 関数について — 小西 弘将 <konishih@...6.so-net.ne.jp>

[#35035] [irb] sub-irb vs cb — rubikitch <rubikitch@...>

[#35036] Re: Is Ruby default in Jaguar? — taiki0419@...

[#35041] [ANN] RDindex-1.1.9 — rubikitch <rubikitch@...>

[#35043] [ANN] rpkg / usage.sgml.ja — dellin <dellin@...>

[#35049] true はリテラル？ — Take_tk <ggb03124@...>

[#35052] ruby_lib/html/ — Wakou Aoyama <wakou@...>

[#35054] 「 Ruby/GTK プログラミング入門」 — Noritsugu Nakamura <nnakamur@...>

[#35058] Y Combinator — sinara@...

[#35065] 影舞 on Windows — "T.Fukagawa" <tfukaga@...>

[#35067] かりー化 — Masahiro Sakai (酒井政裕) <zvm01052@...>

[#35072] Mac OS X で mysql-ruby 実行時エラー — Takashi Hoshizawa <t_hoshizawa@...>

[#35080] Ruby から libglade 。 — "D.Miyawaki" <aaf18900@...06.odn.ne.jp>

[#35081] ISO 8601 と Time#wday — Take_tk <ggb03124@...>

[#35087] Re: Y Combinator — 正木 功 <GEC01122@...>

[#35098] patch for darwin — Yuji Yamano <yyamano@...>

[#35102] ANNOUNCE: REXML のドキュメントの和訳を公開しました。 — Kouhei Sutou (須藤功平) <kou@...>

[#35108] Ruby の一連の成果を CD-ROM に — Kentaro Hatori <hatori@...>

[#35109] DOS プロンプトからリダイレクションつきの system — TOYOFUKU Chikanobu <toyofuku@...>

[#35112] — "hideo kuramochi" <chj87900@...>

[#35113] Re: Marshallers summary — "NAKAMURA, Hiroshi" <nakahiro@...>

[#35128] Windows 版 Ruby で XML プログラミングを始めたい — 鈴木 祐亮 <yuupon@...1.dti2.ne.jp>

[#35134] 朝、トーストを食べていると不意に — Shin-ichiro HARA <sinara@...>

[#35158] TMail::Mail.decoded でエラー — "Morikawa [encore-ann]" <i@...>

[#35165] ソースコードの隠蔽 — OJ <oj@...7.com>

[#35169] Stack overflow で SEGV の取り扱いについて — 小西 弘将 <konishih@...6.so-net.ne.jp>

[#35172] 名刺ジェネレータ ncgen 公開の案内 — NISHI Takao <zophos@...9.com>

[#35183] Glade で GUI 構築 — "D.Miyawaki" <aaf18900@...06.odn.ne.jp>

[#35207] tar.gz の展開 — "NAKANO Kouichi" <knuckle@...8.dion.ne.jp>

[#35215] ruby-shell-mode — "Shirai,Kaoru" <shirai@...1jp.com>

[#35219] RAA から OptionParser が取れません — TAMBARA Masahiko <m-tamb@...>

[#35242] rb_define_class — EMOTO Masahiko <emo@...>

[#35247] [ann] 『 Ruby de CGI 』発売 — 堀川 久 <vzw00011@...>

[#35249] setup.rb: packages/foo/ext/lib — "Akinori MUSHA" <knu@...>

[#35250] Mac OS X ではプリインストール？ — Take_tk <ggb03124@...>

[#35252] ((Time.now)..(Time.now+60)) — Take_tk <ggb03124@...>

[#35253] ((1.2)..(3.4)).to_a — Take_tk <ggb03124@...>

[#35264] HTML generation library — Wakou Aoyama <wakou@...>

[#35273] rd-mode.el - a bit fix — "Shirai,Kaoru" <shirai@...1jp.com>

[#35310] requests for current blade archives — maili31s@... (SugHimsi == SUGIHARA Hiroshi)

[#35312] [irb] irb_soruce — rubikitch <rubikitch@...>

[ruby-list:35058] Y Combinator

Thread

In This Thread

[#35028] win32.c 中の my* 関数について — 小西弘将 <konishih@...6.so-net.ne.jp>

[#35087] Re: Y Combinator — 正木　功 <GEC01122@...>

[#35128] Windows 版 Ruby で XML プログラミングを始めたい — 鈴木祐亮 <yuupon@...1.dti2.ne.jp>

[#35169] Stack overflow で SEGV の取り扱いについて — 小西弘将 <konishih@...6.so-net.ne.jp>

[#35247] [ann] 『 Ruby de CGI 』発売 — 堀川久 <vzw00011@...>