Rubyで遅延評価

いろんなところで既にやられているけど、自分でやってみたくなったので。

遅延評価とは、計算結果が実際に必要になるまで処理を遅延すること。

a = huge_proc()

b = large_proc()

print a

この仮想コードのhuge_procの呼び出しは、３行目のprintで出力されるまで遅延される。また、bは使われていないのでlarge_procは呼び出されない。

こういった仕組みがあれば、処理に時間がかかるが戻り値を使うかどうか分からない関数をムダに実行することがなくなるので、ある種の処理は非常に早くなる。これをRubyでやりたい。

実装

今回作ったユーティリティは、lazy{ 遅延させたい処理 }のように使い、戻り値として遅延オブジェクトを返す。

使い方は例えば、a = lazy{ x }と書けば、lazy自体はすぐに遅延オブジェクトを返し、aのメソッドが呼ばれたときに初めてxが実行される。

class Lazy
  def initialize
    @proc = Proc.new
    @obj = nil end

  def method_missing(method, *args, &block)
    if @proc
      @obj = @proc.call
      @proc = nil end
    @obj.__send__(method, *args, &block) end end

def lazy(&proc)
  Lazy.new(&proc) end

method_missingは、メソッドが無かった時に呼び出されるメソッドで、このメソッドはブロックの戻り値のオブジェクトのメソッドを呼び出す。これによって、遅延オブジェクトから実行結果のオブジェクトのメソッドを透過的に呼べる。

竹内関数によるベンチマーク

試しに、竹内関数（たらい回し関数）の遅延版と通常版と最適化版を作って、どちらも同じ引数(12,6,0)を指定して、速度の差を計測してみた。

def tak(x, y, z)
  if x <= y.to_i
    y
  else
    tak(tak(x-1, y, z), tak(y-1,z,x), tak(z-1,x,y)) end end

def ltak(x, y, z)
  lazy{
    if x <= y.to_i
      y
    else
      ltak(ltak(x-1, y, z), ltak(y-1,z,x), ltak(z-1,x,y)) end } end

def btak(x, y, z)
  if x <= y.to_i
    y
  else
    btak(btak(x-1, y, z), btak(y-1,z,x), lazy{ btak(z-1,x,y) }) end end

a = Benchmark.realtime{ tak(12,6,0).to_i } # => 9.08182191848755
b = Benchmark.realtime{ ltak(12,6,0).to_i } # => 0.00162792205810547
c = Benchmark.realtime{ btak(12,6,0).to_i } # => 0.000227928161621094
a / b # => 5578.78178090217
a / c # => 39845.1066945607
b / c # => 7.14225941422594

関数ltakは、takの内容をlazyで囲っただけで、takは素直な竹内関数の実装。btakは、takの第一引数と第二引数は必ず必要になる＝遅延する必要がないので第三引数だけを遅延したバージョンだ。

通常9秒かかるこの計算が、ltakだと10ミリ秒に、btakでは2ミリ秒になり、btakはtakに比べて39845倍の速度になった。

まとめ
当然だが、遅延オブジェクトの生成にもオーバヘッドがあるので、必要以上に使うことは却って速度の低下につながるので避けたい。
また、この類のコードは汎用性が高いので、もうすこし実装を詰めてもいいかもしれない。
例えば、is_a?等、Objectクラスのメソッドが適切に動くようにすれば、関数の内部の処理を考えずに遅延オブジェクトを渡したり返したり出来るだろう。