再帰中に別の再帰したら、末尾再帰にならない？(結論: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：再帰で無限ループすればスタックオーバーフローするのか。。。
追記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のファイルを実行しても同じ効果があるようでした。
- しめじ(smeghead)
- Phel-lang のコアライブラリに自作の文字列操作ライブラリが取り込まれました(OSSの醍醐味の話) 2024/04/21
- 「今週のPHP」の更新をいち早く確認する技術 2024/03/24
- PHPコードにコンパイルされるLispである Phel-lang が興味深い 2024/03/16
- PHPerKaigi 2024 に参加してきました 2024/03/10
- ビジネスロジックとは何か？ 2024/02/13
NANRIさん、コメントありがとうございます。
今書いているのはclispで動かすことを想定しています。xyzzyで書いて、vimでインデントしてみたいなことをしてますが、弄り始めたばかりで快適な環境を見つけてない状況です。
> マニュアルで確認するのが先決です。
そうですよね。ちょっと http://clisp.sourceforge.net/ 見てきます。
> ちなみに名前の挙がっているxyzzyのLispでは末尾再帰の最適化はありません。
そうでしたか。xyzzyで書いてclispで動かすというのは、処理系への意識が必要ということですね。vimの中でlisp実行できないかな。(なんか変な方向の気もしますが)
Common Lisp系のコードに見えますが、Common Lispでは末尾再帰の最適化は保証されていません。まずお使いの処理系が末尾再帰の最適化をするのかどうか、するのだったらどういう場合にするのか（コンパイルとか最適化レベルとか）をマニュアルで確認するのが先決です。
ちなみに名前の挙がっているxyzzyのLispでは末尾再帰の最適化はありません。