Common Lisp: Dlaczego funkcja rekurencji ogona powoduje przepełnienie stosu?

Question

Mam problem ze zrozumieniem działania funkcji Common Lisp (nadal jestem nowicjuszem). Mam dwie wersje tej funkcji, która po prostu wylicza sumę wszystkich liczb całkowitych do danego n.

Non-tail-rekurencyjna wersja:

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

Tail-rekurencyjna wersja:

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

Próbuję uruchomić te funkcje w clisp z wejściem n = 1000000. Oto wynik

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

*** - Program stack overflow. RESET 

mogę uruchomić zarówno z powodzeniem w SBCL, ale jeden non-tail-rekurencyjne jest szybsza (tylko trochę, ale to wydaje się dziwne dla mnie). Przeszukałem pytania Stackoverflow w poszukiwaniu odpowiedzi, ale nie mogłem znaleźć czegoś podobnego. Dlaczego dostaję przepełnienie stosu, mimo że funkcja rekurencji ogona nie jest zaprojektowana tak, aby umieścić na stosie wszystkie wywołania funkcji rekurencyjnych? Czy muszę powiedzieć interpreterowi/kompilatorowi, aby zoptymalizować wywołania ogona? (Czytam coś w rodzaju (proclaim '(optimize (debug 1)), aby ustawić poziom debugowania i optymalizować koszt śledzenia umiejętności, ale nie wiem, co to robi). Może odpowiedź jest oczywista, a kod to bzdury, ale po prostu nie mogę tego rozgryźć. Pomoc jest doceniana.

Edytuj: danlei wskazał literówkę, powinno być to połączenie z addup3 w pierwszej funkcji, więc jest rekurencyjne. Jeżeli poprawione, zarówno wersje przepełnienie, ale nie jego jednego

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

Chociaż może to być bardziej typowy sposób to zrobić, uważam, że to dziwne, że ogon rekurencja nie zawsze jest zoptymalizowana, biorąc pod uwagę moje instruktorów podoba mi powiedzieć, że to o wiele bardziej wydajne i takie tam.

Answer 1

Nie ma wymogu, aby implementacja Common Lisp zapewniała optymalizację połączeń. Większość robi jednak (myślę, że ABCL nie, z powodu ograniczeń wirtualnej maszyny Java).

Dokumentacja wdrożenia powinna określać, jakie ustawienia optymalizacji należy wybrać, aby TCO (jeśli jest dostępny).

Jest bardziej idiomatyczne dla wspólnego kodu Lisp, aby wykorzystać jedną z typami pętli konstruktów:

(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)) 

W tym przypadku, oczywiście, lepiej jest użyć „trochę Gauss”:

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

Answer 2

Cóż, twój addup3 po prostu nie jest rekurencyjny w ogóle.

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

To wywołanie, niezależnie od numeru addup. Wypróbowanie poprawionej wersji w 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}>. 

Jak można się spodziewać.

Answer 3

Korzystanie z GNU CommonLisp, GCL 2.6.12, kompilacja addup2 zoptymalizuje rekurencja ogonowa, oto co mam:

>(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." 

Nadzieję, że to pomaga.