Common Lisp：テール再帰関数がスタックオーバーフローを引き起こすのはなぜですか？

Question

私はCommon Lisp関数（私はまだ初心者です）のパフォーマンスを理解する上で問題があります。私はこの関数の2つのバージョンを持っています。これは与えられた最大の整数の合計を単に計算します。n

非末尾再帰バージョン：

(defun addup3 (n) 
    (if (= n 0) 
    0 
    (+ n (addup (- n 1))))) 

末尾再帰バージョン：

(defun addup2 (n) 
    (labels ((f (acc k) 
       (if (= k 0) 
        acc 
        (f (+ acc k) (- k 1))))) 
    (f 0 n))) 

私は入力n = 1000000とCLISPでこれらの関数を実行しようとしています。ここで結果

[2]> (addup3 1000000) 
500000500000 
[3]> (addup2 1000000) 

*** - Program stack overflow. RESET 

私はSBCLの両方で正常に実行することができますが、非末尾再帰一つは高速です（少しだけによって、それは私には奇妙に思えます）。私は答えのためのStackoverflowの質問を洗ったが、何か似たものを見つけることができませんでした。テール再帰関数はすべての再帰関数呼び出しをスタックに入れないように設計されていますが、なぜスタックオーバーフローが発生しますか？テールコールを最適化するためにインタプリタ/コンパイラに指示する必要がありますか？ （私は(proclaim '(optimize (debug 1))のようなものを読んで、デバッグレベルを設定し、トレース能力を犠牲にして最適化しましたが、私はこれが何であるか分かりません）。 多分答えは明らかでコードは間違っていますが、わかりません。 ヘルプは高く評価されています。

編集：danleiはタイプミスを指摘し、最初の関数でaddup3を呼び出す必要があります。再帰的です。場合は修正し、両方のバージョンのオーバーフローではなく、彼の1

(defun addup (n) 
     "Adds up the first N integers" 
     (do ((i 0 (+ i 1)) 
       (sum 0 (+ sum i))) 
      ((> i n) sum))) 

それはそれを行うには、より一般的な方法かもしれないが、私は私のインストラクターが、それはだを教えしたいと考えると、末尾再帰が常に最適化されていないこと、それは奇妙な見つけますはるかに効率的で物事。

Answer 1

Common Lispの実装でテールコールの最適化を行う必要はありません。しかし、ほとんどの場合、（私は、ABCLはJava仮想マシンの限界のためにそうではないと思う）。

実装のドキュメントでは、TCO（使用可能な場合）を得るために最適化設定を選択する必要があります。もちろん、「少しガウス」を使用することをお勧めします。この場合、

(loop :for i :upto n 
     :sum i) 

(let ((sum 0)) 
    (dotimes (i n) 
    (incf sum (1+ i)))) 

(do ((i 0 (1+ i)) 
    (sum 0 (+ sum i))) 
    ((> i n) sum)) 

：

ループ構造のいずれかを使用するCommon Lispのコードのためのより多くの慣用的である

(/ (* n (1+ n)) 2) 

Answer 2

あなたのaddup3はちょうど再帰的ではありません全くです。

(defun addup3 (n) 
    (if (= n 0) 
    0 
    (+ n (addup (- n 1))))) ; <-- 

addupのいずれかを呼び出します。 SBCLで修正されたバージョンを試す：

CL-USER> (defun addup3 (n) 
      (if (= n 0) 
       0 
       (+ n (addup3 (- n 1))))) 
ADDUP3 
CL-USER> (addup3 100000) 
Control stack guard page temporarily disabled: proceed with caution 
; .. 
; Evaluation aborted on #<SB-SYS:MEMORY-FAULT-ERROR {C2F19B1}>. 

Answer 3

GNU CommonLisp、GCL 2.6を使用しています。12、コンパイルaddup2は、テールコールを最適化します。ここに私が持っているものがあります：

>(compile 'addup2)                  

Compiling /tmp/gazonk_3012_0.lsp. 
End of Pass 1. 

;; Note: Tail-recursive call of F was replaced by iteration. 
End of Pass 2. 
OPTIMIZE levels: Safety=0 (No runtime error checking), Space=0, Speed=3 
Finished compiling /tmp/gazonk_3012_0.lsp. 
Loading /tmp/gazonk_3012_0.o 
start address -T 0x9556e8 Finished loading /tmp/gazonk_3012_0.o 
#<compiled-function ADDUP2> 
NIL 
NIL 

>>(addup2 1000000)                                    

500000500000 
>(addup3 1000000) 

Error: ERROR "Invocation history stack overflow." 
Fast links are on: do (si::use-fast-links nil) for debugging 
Signalled by IF. 
ERROR "Invocation history stack overflow." 

Broken at +. Type :H for Help. 
    1 Return to top level. 

>>(compile 'addup3)                                   

Compiling /tmp/gazonk_3012_0.lsp. 
End of Pass 1. 
End of Pass 2. 
OPTIMIZE levels: Safety=0 (No runtime error checking), Space=0, Speed=3 
Finished compiling /tmp/gazonk_3012_0.lsp. 
Loading /tmp/gazonk_3012_0.o 
start address -T 0x955a00 Finished loading /tmp/gazonk_3012_0.o 
#<compiled-function ADDUP3> 
NIL 
NIL 
>>(addup3 1000000)                                    

Error: ERROR "Value stack overflow." 

希望します。