Rubyの末尾再帰最適化を理解する

ブログを下記に移転しました。デザイン変更により移転先では記事が一層読みやすくなっていますので、よろしければ移動をお願い致します。

- - - - -

RubyではSchemeなどとは異なって
末尾再帰の最適化を勝手にしてはくれません

でもid:athosさんが
Rubyで末尾再帰最適化を実現するコードを書いてくれました

自分の実力だと一見しただけでは何をしているか理解できなかったので
少し自分用にコードを整理してその処理を追ってみます

 class Module
   def tco(meth)
     called = false
     tmp = nil
 
     orig_meth = "orig_#{meth}"
     alias_method orig_meth, meth
     private orig_meth
 
     define_method(meth) do |*args|
       unless called
         called = true
         args = tmp until result = send(orig_meth, *args)
         result
       else
         tmp = args
         false
       end
     end
   end
 end

 class Sum
   def sum1(n, acc=0)
     return acc if n == 0
     sum1(n-1, acc+n)
   end
 
   def sum2(n, acc=0)
     return acc if n == 0
     sum2(n-1, acc+n)
   end
   tco :sum2
 end
 
 s = Sum.new
 s.sum2(100000) # => 5000050000
 s.sum1(100000) # => 
 # ~> -:25: stack level too deep (SystemStackError)

tcoクラスメソッドに対象のメソッドを渡せばその最適化がなされます
tcoメソッドでは具体的には以下の処理をしています

元メソッド(sum2)の別名(orig_sum2)を定義する(alias_method)
元メソッド名を持った新メソッドを定義する(define_method)
新メソッドにおいて別名定義した元メソッドを反復的に呼び出す

これによってsum2が呼ばれると以下の処理がなされます

新メソッドが呼ばれ、その中で元メソッドが呼ばれる(unless節)
元メソッドの呼び出しは、その引数nが0(resultが有意な値)になるまでここで反復的に繰り返される
元メソッドの再度の呼び出しにより、今度は新メソッドのelse節が実行される(called=true)
ここでその引数argsが次の元メソッドの反復呼び出しに渡されるよう保持する
元メソッドの呼び出しにおいて引数nが0になると、accが返りresultに渡される
これによってuntilループを抜けて、このメソッドの返り値としてresultが得られることとなる

なるほど！