再帰中に別の再帰したら、末尾再帰にならない?(結論:clispではcompileしてないから最適化されてないだけでした)

id:smeghead:20070513:primeで再帰呼出し中に別の再帰呼出しを行なうように書いておいたら、デバッグ中にスタックオーバーフローのエラーが発生した。

ということは、再帰の重複はループに最適化されないのだろうか?

前エントリの create-prime-lst が再帰的に呼び出されていて、その関数の中で delete-multiple-from-search-lst が再帰的に呼び出されている。

リターンアドレスとかに関する知識が怪しいですが、delete-multiple-from-search-lstの再帰はループに最適化されるだろうけど create-prime-lstは最適化は可能なんだろうか?

ある再帰関数が最適化されたかどうかの判定方法を調べねば。

追記10070514:再帰で無限ループすればスタックオーバーフローするのか。。。

追記20070515

NANRIさんにヒントを頂いたので調べてみました。(ありがとうございます)

clispは、compile時に最適化されるらしいです。(マニュアルには挫折してhttp://d.hatena.ne.jp/shinichiro_h/20070115を見ました)

実際、「*** – Program stack overflow. RESET」が発生する状況を作った後、末尾再帰の関数の宣言後に下の様なコードを追加しコンパイルするとProgram stack overflowを回避することを確認しました。

(compile 'make-search-lst)

compile関数のかわりに、clisp コマンドの -c オプションを使って生成した拡張子fasのファイルを実行しても同じ効果があるようでした。

2 Comments

  • NANRIさん、コメントありがとうございます。
    今書いているのはclispで動かすことを想定しています。xyzzyで書いて、vimでインデントしてみたいなことをしてますが、弄り始めたばかりで快適な環境を見つけてない状況です。

    > マニュアルで確認するのが先決です。
    そうですよね。ちょっと http://clisp.sourceforge.net/ 見てきます。

    > ちなみに名前の挙がっているxyzzyのLispでは末尾再帰の最適化はありません。
    そうでしたか。xyzzyで書いてclispで動かすというのは、処理系への意識が必要ということですね。vimの中でlisp実行できないかな。(なんか変な方向の気もしますが)

  • Common Lisp系のコードに見えますが、Common Lispでは末尾再帰の最適化は保証されていません。まずお使いの処理系が末尾再帰の最適化をするのかどうか、するのだったらどういう場合にするのか(コンパイルとか最適化レベルとか)をマニュアルで確認するのが先決です。

    ちなみに名前の挙がっているxyzzyのLispでは末尾再帰の最適化はありません。

Leave a Comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.