[ruby-dev:566] Re: [563] Tail recursion (Re: optimize (...))

まつもと ゆきひろです

In message "[ruby-dev:565] Re:[563] Tail recursion (Re: optimize (...))"
    on 97/09/29, "EGUCHI Osamu" <[e-mail]> writes:

|えぐち です。

|雑な方法すが、time ruby .. では測った限りでは、 
|o = o + m も o += m も殆ど時間変わらないですね、
|ということは、これ以上の判断を追加すると
|  丸々遅くなると、、、（ボッ）ですね。^^;

あ，やっぱり．

|> call/returnの主なコストはsetjmp/longjmpですから，ある程度は
|> 重いにしても，こういうテールリカージョンを正当化する程には重
|> たくないような気がします．もっとも，fact(400)とかが実行でき
|> るようになることは嬉しいですけど．
|
|残念ながら fact(n) は n * fact(n - 1) が終端の式なので
|*(乗算) が残ってしまいループ化は困難です。人間ならば 
|	for (result = 1,i = 1;i <= n; n++) 
|	  result *= i;
|に簡単に出来ますがプログラムに、この種の変形を行わせるのは多分
|、、無理。

そうかあ．

|いまフレーム・ブロック・スコープなど環境をハードウェアスタックに
|つんでいますが、これを動的な配列なり、リストなりに置くようにする
|事で fact な問題は緩和されそうです。

ええ，それはそうなんですけど，やっぱりハードウェアスタックは
速いので，なかなか迷うところです．以前，ソフトウェアスタック
化を実装してみたところ，かなり遅くなりましたし．

# ずいぶん前なので数値を忘れてしまったのですが．

|しかし真剣に rb_eval() を非再帰構造にするとなると、 
|break/redo/next ３兄弟が制御構造 *ではなく* 関数であることや、
|例外・イテレータとの折り合いを付けるために、字句・構文・評価で
|情報の受け渡しを密接に行わなければならないのでかなり厄介です。

この辺を考えて1.1ではbreak/next/redo/retryは制御構造になって
ます．でも，問題はそれだけではありませんものね．

|私のイメージでは、rb_eval() を非再帰化するというと、
|構文木を今の異種リストから機械語の様なバイトコードに変更する
|と言うことのように思えるのですが、違いますか？

そこまでは考えていないんですけど，

   case NODE_WHILE:
     while (eval(node->cond)) {
       eval(node->body);
   }

のようになっているものを

   case NODE_JUMPIF:
     if (RTEST(result)) {
       node = node->jump;
       goto again;
     }
     break;

のようなものによって展開できたら良いなあ，と考えているのです．

                                まつもと ゆきひろ /:|)