Yコンビネータによる再帰 のバックアップ(No.2)

更新


公開メモ

Yコンビネータによる再起

http://qiita.com/mrpepper/items/6a538ef0b2d11fc311ac

こちらの記事を読んで、Yコンビネータによる再起の方法を知りました。

が、一見しただけだとどんな仕組みで動作しているのかが分からなかったので、勉強してみました。

ここではYコンビネータの数学的な話などは全部置いておいて、 コードとしてなぜこれが動くのか、を理解したいと思います。

言語としては Coffee Script を使っています。

http://coffeescript.org/ こちらの一番上で TRY COFFEESCRIPT にコードを貼って、右上の run で走らせることができます。

まずは通常の再起処理コード

恐らくもっとも有名な、階乗計算のコードはこんな感じ。

LANG:coffeescript
factorial = (n)->
    if n == 1
      return 1
    else
      return n * factorial(n-1)

alert factorial(4) 
# displays 4! == 24

1の階乗は1。

nの階乗はn-1の階乗にnを掛けた物。

という素直な実装です。

Yコンビネータを使ったコード

上記サイトのコードを少し変更して、以下のような物を試してみたところ、 驚くべきことに(!) 正しく 24 が表示されました。

LANG:coffeescript(linenumber)
y_combi = (func)->
  return ((p)->
    return (n)->
      return func(p(p))(n)
  )((p)->
    return (n)->
      return func(p(p))(n)
  )

factorial_y = y_combi (reccurse)->
  return (n)->
    if n == 1
      return 1
    else
      return n * reccurse(n-1)

alert factorial_y(4) 
# displays 4! == 24

factorial_y を精査する

factorial_y は reccurse という関数を受け取って、 「引数 n を取る関数」を返す関数に y_combi を適用した形に直されています。

そして、再帰呼び出しをする

LANG:coffeescript
      return n * factorial(n-1)

が、仮引数で渡される reccurse に置き換えられて

LANG:coffeescript
      return n * reccurse(n-1)

となっています。

reccurse を呼び出すことで自分自身を再帰呼び出しできるような 引数が外部から与えられると期待しているようですね。

y_combi を精査する

1行目から分かるように、y_combi は func を渡すと何かを返す関数です。

func には factorial_y の (reccurse)-> 以下のような関数が与えられます。

y_combi から何が返されるか、を読むのは、なかなか骨が折れますね。

y_combi の中身は

LANG:coffeescript(linenumber)
y_combi = (func)->
  return ((p)->
    ...

  )((p)->
    ...

  )

という形になっていますので、2行目の (p)-> から始まる関数に、 5行目の (p)-> から始まる関数を引数として与えた結果を返すと読めます。

2つの ... の内容は等しいので、2行目の (p)-> から始まる関数と、 5行目の (p)-> から始まる関数の内容は等しいです。

ですので、こう書き直しても同じ動作をします。

LANG:coffeescript
y_combi = (func)->
  core = (core)-> (n)-> func(core(core))(n)
  return core(core)

関数型変数の core と、λ式の仮引数の core の名前をわざと同じにしたせいで、 スコープがややこしいかもしれませんが、実際には引数にも core 自身が渡されるため、 結果的に core と書かれた部分にはすべて等しい値が入ります。

func に core(core) を与えて呼び出していますので、 factorial_y の中の reccurse には core(core) が入ることになります。

core(core) は (n)-> func(core(core))(n) を返すので、

func(core(core))(n) の中で呼ばれる reccurse(n-1) は core(core)(n-1) のことで、 これは func(core(core))(n-1) を返します。

func(core(core))(n-1) の中で呼ばれる reccurse(n-2) は core(core)(n-2) のことで、 これは func(core(core))(n-2) を返します。

func(core(core))(n-2) の中で呼ばれる reccurse(n-3) は core(core)(n-3) のことで、 これは func(core(core))(n-3) を返します。

という具合で、確かに正しく求まりそうなことがようやく理解できました。

実行効率

これ、確かに動きそうですが、実行効率はどうでしょう。

factorial が n 重の関数再帰呼び出しで計算可能です。

Yコンビネータを使った方では、func, core が適切に設定されている前提では

LANG:coffeescript
factorial_y = (n)-> func(core(core))(n)

ですので、見た目の複雑さに反してこちらも n 回の再起で済みますが、 同時に core(core) の計算を n 回行っている分だけ余計な計算が必要です。

思ったほどは効率に影響がないので、末尾再起の最適化などが実装されると、 ばりばり使っても問題ないのかもしれません?

コメント・質問





Counter: 7267 (from 2010/06/03), today: 1, yesterday: 0