From: EGUCHI Osamu <eguchi@...>
Date: 1997-09-29T12:58:38+09:00
Subject: [ruby-dev:565] Re:[563] Tail recursion (Re: optimize (...))

えぐち です。

----------
> 件名 : [ruby-dev:563] Re: Tail recursion (Re: optimize (...))
> 
> まつもと ゆきひろです
> 
> In message "[ruby-dev:558] Tail recursion (Re: optimize (...))"
>     on 97/09/27, "EGUCHI Osamu" <eguchi@shizuokanet.or.jp> writes:
> 
> |えぐち です。
> 
> |> 結局 obj += m は obj = obj + m に戻して評価してますからねえ．
> |> それほど効果は出ないかも．
> |
> |eval のトラバースがちょっと減るですね、
> 
> ええ，それがどれだけ重いかですね．そんなに重くないように思っ
> ているのですが，nd_type()はビットマスクとかありますけど．

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

> 
> |> |また、メソッドのテールリカージョンは可能だとおもいます。
> 
> |可能なのはクラス#メソッドが一致でかつ特異メソッドがない場合です。
> |これは eval の時までわからないです。
やっぱり ￣￣￣￣￣￣￣￣￣￣￣￣￣￣ ですね。

> |逆に eval が手抜きできるわけですが、検査コストは大きいでしょうか？
> |また、これをしてまで call/return のオーバーヘッドは大きいのか不明です。
> 
> ああ，すいません．テールリカージョンといえば普通はこっちです
> よね．これに関しては全てのメソッドが動的結合して，本当にテー
> ルリカージョンできるかコンパイル時に決定できない事情があるの
> で，検査コストの方が大きいように感じていて，まじめに検討した
> 事がありません．

rb_eval() で call する寸前にハッシュ値で検査しようと言うたくらみです。
この検査コストが報われるかはわかりません。（break 関数などの処理も問題）

パーサで見つけてプログラマに「ヒント」を与える方が現実的かもしれませんが、
「うそ」を教える可能性が、特異メソッドなどの関係であります。＜だめだこれ

> 
> call/returnの主なコストはsetjmp/longjmpですから，ある程度は
> 重いにしても，こういうテールリカージョンを正当化する程には重
> たくないような気がします．もっとも，fact(400)とかが実行でき
> るようになることは嬉しいですけど．

残念ながら fact(n) は n * fact(n - 1) が終端の式なので
*(乗算) が残ってしまいループ化は困難です。人間ならば 
	for (result = 1,i = 1;i <= n; n++) 
	  result *= i;
に簡単に出来ますがプログラムに、この種の変形を行わせるのは多分
、、無理。

> 私が検討した事のあるテールリカージョンは，最後のメソッド呼出
> で呼出フレームを積まない方です．こちらは本来の意味ではテール
> リカージョンではないんですが，Schemeの仕様ではこういうのもテー
> ルリカージョンと呼んでいるようです．

なるほど、

> こちらは正当的テールリカージョンよりも実現性が高いのですが，
> 今のままの実装では難しくて，rb_evalの非再帰化が必要だなあと
> 感じている所です．

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

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

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

	えぐち