たらいまわし関数を Ruby で遅延評価してみた

「横浜へなちょこプログラミング勉強会」という集りが開催していた「ふつうのHaskellプログラミング」読書会というのが ATND に登録されていたので、飛び込み参加してみました。参加者のみなさまありがとうございます。

昨日は既に第3回目で、第5章の遅延評価から読み始めでした。そこでたらいまわし関数が出てきた時に、Ruby でも手動で遅延評価を書くことはできますよー、ただちょっと面倒ですけど、と発言したので実際やってみようと思います。参考になれば幸いです。

まずたらいまわし関数の定義がどういうものかというのを普通のメソッド定義で示します。

def tak(x, y, z)
  if x <= y
    y
  else
    tak(tak(x-1, y, z),
        tak(y-1, z, x),
        tak(z-1, x, y))
  end
end
x, y, z = ARGV.map{|i| Integer(i) }
tak = tak(x, y, z)
puts "tak(#{x}, #{y}, #{z}) = #{tak}"

なにをやってるのかよくわかりませんね。まあ実は何もしていないというか、ぐるぐる回って結局は x, y, z のどれかが帰ってくるだけです。
それだけのことなのに、これを少し大きな数を渡すととたんにものすごい時間がかかります。

それでこれを memoize してあげると、一度計算した引数の組合せは再計算しなくてすむのでとても早くなります。

module TaraiMemo
  @@cache = {}  # use [x, y, z] as key
  def self.tak_memoize(x, y, z)
    if @@cache.include?([x, y, z])
      return @@cache[[x, y, z]]
    end
    if x <= y
      result = y
    else
      result = tak_memoize(tak_memoize(x-1, y, z),
                           tak_memoize(y-1, z, x),
                           tak_memoize(z-1, x, y))
    end
    @@cache[[x, y, z]] = result
  end
end
x, y, z = ARGV.map{|i| Integer(i) }
tak = TaraiMemo.tak_memoize(x, y, z)
puts "tak(#{x}, #{y}, #{z}) = #{tak}"

いきなり Module を作って特異メソッドとして定義しているのはキャッシュをグローバル変数やトップレベルのインスタンス変数として定義することの罪悪感に耐えられなかったからです。それを除けば @@cache に結果を残しているのが増えているだけです。

さて、遅延評価のためには Proc オブジェクトで包めばいいんですよーと言ったのでそのとおりに書いてみました。

def lazy_integer(i)
  lambda{ i }
end

def lazy_minus(lazy1, lazy2)
  lambda{ lazy1.call - lazy2.call }
end

def tak_lazy(x, y, z)
  lambda{
    xval = x.call
    yval = y.call
    if xval <= yval
      yval
    else
      tak_lazy(tak_lazy(lazy_minus(x, lazy_integer(1)), y, z),
               tak_lazy(lazy_minus(y, lazy_integer(1)), z, x),
               tak_lazy(lazy_minus(z, lazy_integer(1)), x, y)).call
    end
  }
end
x, y, z = ARGV.map{|i| Integer(i) }
tak = tak_lazy(lazy_integer(x), lazy_integer(y), lazy_integer(z)).call
puts "tak(#{x}, #{y}, #{z}) = #{tak}"

このサンプルは数値も引き算の所も lambda で包んでしまいます。Proc オブジェクトを生成するのはそれなりに重い処理ですが、手元の trunk では memoize 版より少し高速になりました。

	tak(20, 10, 1)	tak(200, 100, 1)
memoize 版	0.032 sec	1.549 sec
lazy 版	0.024 sec	1.203 sec
通常版	止めた	止めた

通常版は我慢できず止めてしまいました。

少し解説を加えておくと、tak_lazy メソッドは「評価(call を呼ぶ)すると整数を返す Proc オブジェクトを3つ引数に取り、評価すると整数を返す Proc オブジェクトを返す」メソッドとして定義されています。よって tak_lazy を実行してもただ Proc オブジェクトが生成されるだけで何も実際には実行されていません。かえってきた Proc オブジェクトに call を呼ぶと x, y 引数が評価されます。else 節に注目すると、ネストした tak_lazy は Proc オブジェクトを返すので、call を呼んで整数にしています。しかしその引数に渡しているほうの tak_lazy はただ返された Proc オブジェクトをそのまま渡すだけで、その内容は必要になるまでは実行されないことがわかります。

というわけで、このように明示的に遅延評価を書くことは可能ですし、効果も(たらいまわし関数については)ありました。正直なところ Proc オブジェクトを生成するので memoize 版に較べてそんなに早くはならないかもしれないと思っていたのですが、ちゃんと高速になってて嬉しいです。