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

2007/05/13

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

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

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

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

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

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

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のファイルを実行しても同じ効果があるようでした。

この記事の投稿者最新記事

smeghead 1970/01/01

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

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

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

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

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

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください。