バリケンのRuby日記 RSSフィード

2006-05-25

[] Rubyの「遅延評価」  Rubyの「遅延評価」 - バリケンのRuby日記 を含むブックマーク はてなブックマーク -  Rubyの「遅延評価」 - バリケンのRuby日記  Rubyの「遅延評価」 - バリケンのRuby日記 のブックマークコメント

なかださん(って、「A Strolling Programmer」のなかださん?)から昨日のエントリコメントをいただきました。ありがとうございます!

なるほどRubyだと「Y-Combinator」を使わなくても、「遅延評価」を使えば再帰的な関数を手続きオブジェクトにできるんだね。

fact = lambda { 
  f = lambda {|n|
    if n.zero?
      1
    else
      n * f.call(n - 1)
    end
  }
}.call

「遅延評価」については、essaさんのこのエントリの説明がわかりやすいよ。

せっかく「遅延評価」が出てきたから、今日は「遅延評価」を使って昨日の日記とは別のアプローチでY-Combinatorを求めてみるよ。

昨日と同様、「nの階乗」を求める例だよ。まずは自分自身を再帰的に呼んでいる基本形。

fact = lambda {|n|
  if n.zero?
    1
  else
    n * fact.call(n - 1)
  end
}

fact.call(10)

次に、手続きオブジェクトの中から変数をなくすために、外側にもうひとつlambdaを追加するよ。

fact_maker = lambda {|fact|
  lambda {|n|
    if n.zero?
      1
    else
      n * fact.call(fact).call(n - 1)
    end
  }
}

fact_maker.call(fact_maker).call(10)

ここで、「再帰の定義部分」と「再帰の評価部分」を分離することを考えるよ。まずは「再帰の定義部分」をfとして書き出してみるよ。

f = lambda {|h|
  lambda {|n|
    if n.zero?
      1
    else
      n * h.call(n - 1)
    end
  }
}

この「再帰の定義部分」をジッとながめてみよう。f自体は単なる関数オブジェクトだよね。

この関数を何とか外側から再帰的に呼び出すには、次のことをすればよさそうだよね。

  1. hに、q.call(q)となるような関数オブジェクトを送り込んでから
  2. fを呼ぶ

を、qを引数にとる関数として実装すれば、「再帰の評価部分」が定義できそうだよね。次のようになるよ。

f = lambda {|h|
  lambda {|n|
    if n.zero?
      1
    else
      n * h.call(n - 1)
    end
  }
}

fact_maker = lambda {|q|
  f.call(
    q.call(q)
  )
}

fact_maker.call(fact_maker).call(10)

一見うまくいきそうだけど、これでは再帰にならないんだよ。再帰になるには

  1. hに、q.call(q)となるような関数オブジェクトを送り込んでから
  2. fを呼ぶ

という順番が大事なんだ。でもさっきのコードだと、q.call(q)がf.callよりも先に呼ばれてしまうんだよ。

なんとかq.call(q)を評価しないでfの中に送り込みたいよね。そこで先ほどの「遅延評価」というテクニックを使うよ。

実は、q.call(q)はlambda {|x| q.call(q).call(x) }と全く同じことなんだよ。実際に動かしてみて確認してみてね。

ただし、実際には「この手続きオブジェクトが評価されるまでは、q.call(q)が評価されない」という違いがあるよ。

この「遅延評価」を使うと、fの中にq.call(q)を送り込むことが出来るよ。

f = lambda {|h|
  lambda {|n|
    if n.zero?
      1
    else
      n * h.call(n - 1)
    end
  }
}

fact_maker = lambda {|q|
  f.call(
    lambda {|m| q.call(q).call(m) } # q.call(q)と等価
  )
}

fact_maker.call(fact_maker).call(10)

あとはここまでくれば昨日と同じだよね。昨日と同じだとつまらないから、評価側を二回繰り返す書き方にしてみるよ。

f = lambda {|h|
  lambda {|n|
    if n.zero?
      1
    else
      n * h.call(n - 1)
    end
  }
}

fact_maker = lambda {|q|
  f.call(
    lambda {|m| q.call(q).call(m) } # q.call(q)と等価
  )
}.call(
  lambda {|q|
    f.call(
      lambda {|m| q.call(q).call(m) } # q.call(q)と等価
    )
  }
)

fact_maker.call(10)

で、このfact_makerのfを引数として渡すようにしてメソッドにすると、Y-Combinatorの完成だね。

f = lambda {|h|
  lambda {|n|
    if n.zero?
      1
    else
      n * h.call(n - 1)
    end
  }
}

def y_combinator(func)
  g = lambda {|q|
    func.call(
      lambda {|m| q.call(q).call(m) }
    )
  }.call(
    lambda {|q|
      func.call(
        lambda {|m| q.call(q).call(m) }
      )
    }
  )
  return g
end

fact = y_combinator(f)

fact.call(10)

「遅延評価」は関数型言語のテクニックだけど、このほかにも関数型言語にはいろんなテクニックがあるんだろうねえ。

こうしたテクニックって「デザインパターン」と一緒で、知らなければ知らないで多分きっと困ることはないと思うよ。

でも例えて言うなら「サッカーオーバーヘッドシュート」みたいなもので、使える場面は限られているけど、それができることでしか決められないゴールも確実にあって、それがゲームの結果を左右することもあるかもしれないよね。

だから最近、多くの人が関数型言語に熱をあげているのかも。

[] ザ・ゴール  ザ・ゴール - バリケンのRuby日記 を含むブックマーク はてなブックマーク -  ザ・ゴール - バリケンのRuby日記  ザ・ゴール - バリケンのRuby日記 のブックマークコメント

「遅延評価」の「本当に必要になるまでは作業しないことで、全体としてのパフォーマンスは向上する」ということから、昔読んだ「ザ・ゴール」に書かれていた「制約条件の理論」を思い出したよ。

ザ・ゴール ― 企業の究極の目的とは何か

ザ・ゴール ― 企業の究極の目的とは何か

スティーブ・ジョブズ氏のスピーチ」にもあったけど、「だからこそバラバラの点であっても将来それが何らかのかたちで必ず繋がっていくと信じなくてはならない。」って本当かも。

Ruby勉強も、いつか役に立つといいなあ。

トラックバック - http://rubyist.g.hatena.ne.jp/muscovyduck/20060525