[ruby-list:35735] Re: tail recursion elimination

At Sat, 10 Aug 2002 22:07:42 +0900,
> > ruby-talkを見ている方には重複してしまいますが，ruby-optimizerという
> > メソッドの最適化もどきを行う拡張モジュールを紹介させて下さい．
> > 
> >   http://www.ruby-lang.org/en/raa-list.rhtml?name=Optimization+Module
> 
> こういう内部構造に依存するものは、本体に組み込むべきという気が
> するので、ruby-devに行ったほうがいいかも。

ええ，内部構造についてはruby-dev/ruby-extなりで助けを求めることに
なると思います．そのときはよろしくお願いします．

> > 単純に解析木を組換えることでスピードを少し向上させるものです．また末尾
> > 再帰除去も行います．現在いくつか不具合はありますが，だいたいうまく動く
> > ようです．
> 
> 不具合というのはどんなところでしょうか。

tail-recursionの除去にもう少しきつい制限が必要なのです．現在は，

def fact_(x, c)
  if( x == 1 )              # (1)
    c.call(x)
  else
    fact_(x-1, proc{|n| x * c.call(n)})  # (2)
  end
end

という関数があると，(2)の式の前に

    x,c = x-1, proc{|n| x * c.call(n)}

という多重代入の式を挿入して，その後は(1)の内容を直接コピーして構文
木上でループを作っています．そのため，上記の式は実は，

def fact_(x, c)
again:
  if( x == 1 )
    c.call(x)
  else
    x,c = x-1, proc{|n| x * c.call(n)}
    goto again
  end
end

のような疑似コードで表せます．あとで局所変数が使われてしまいますね．
このように，引数にブロックをとる場合には末尾再帰除去をしないようにし
ようと思っています．

あとは，GCが起こるとたまにSegmentation Faultするので，どこかまずいの
かと探しているところです．

> それと1.7でコンパイルエラーになりました。あと、nodeDump.cはリン
> クする必要はないですよね。

nodeDumpはデバグ用に取り込みました．
まだまだ手直しが必要ですし，ソースいじりたい人もdoDump()関数があった
方がやりやすいかなと思いまして．もちろん，本体には直接必要ないです．

パッチありがとうございます．
-- 
Takaaki Tateishi <[e-mail]>