Common Lisp: Why does my tail-recursive function cause a stack overflow?

Question

I have a problem in understanding the performance of a Common Lisp function (I am still a novice). I have two versions of this function, which simply computes the sum of all integers up to a given n.

Non-tail-recursive version:

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

Tail-recursive version:

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

I am trying to run these functions in CLISP with input n = 1000000. Here is the result

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

*** - Program stack overflow. RESET

I can run both successfully in SBCL, but the non-tail-recursive one is faster (only by a little, but that seems strange to me). I've scoured Stackoverflow questions for answers but couldn't find something similar. Why do I get a stack overflow although the tail-recursive function is designed NOT to put all recursive function calls on the stack? Do I have to tell the interpreter/compiler to optimise tail calls? (I read something like (proclaim '(optimize (debug 1)) to set the debug level and optimize at the cost of tracing abilities, but I don't know what this does). Maybe the answer is obvious and the code is bullshit, but I just can't figure it out. Help is appreciated.

Edit: danlei pointed out the typo, it should be a call to addup3 in the first function, so it is recursive. If corrected, both versions overflow, but not his one

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

While it may be a more typical way to do it, I find it strange that tail recursion is not always optimised, considering my instructors like to tell me it's so much more efficient and stuff.

Answer 1

There is no requirement for a Common Lisp implementation to have tail call optimization. Most do, however (I think that ABCL does not, due to limitations of the Java virtual machine).

The documentation of the implementation should tell you what optimization settings should be chosen to have TCO (if available).

It is more idiomatic for Common Lisp code to use one of the looping constructs:

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

In this case, of course, it is better to use the "little Gauß":

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

Answer 2

Well, your addup3 just isn't recursive at all.

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

It calls whatever addup is. Trying a corrected version in 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}>.

As you'd expect.

Answer 3

Using GNU CommonLisp, GCL 2.6.12, compilation of addup2 will optimize tail calls, here is what I got:

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

Hope it helps.

Answer 4

In SBCL User Manual:

The compiler is “properly tail recursive.” [...] The elimination of tail-recursive frames can be prevented by disabling tail-recursion optimization, which happens when the debug optimization quality is greater than 2.

And works as is in the REPL of a fresh image:

(defun sum-no-tail (n)
  (if (zerop n)
      0
      (+ n (sum-no-tail (- n 1)))))

(defun sum-tail (n &key (acc 0))
  (if (zerop n)
      acc
      (sum-tail (- n 1) :acc (+ n acc))))

CL-USER> (sum-no-tail 10000)
50005000 (26 bits, #x2FB0408)
CL-USER> (sum-no-tail 100000)
Control stack guard page temporarily disabled: proceed with caution
; Debugger entered on #<SB-KERNEL::CONTROL-STACK-EXHAUSTED {10026620A3}>
[1] CL-USER> 
; Evaluation aborted on #<SB-KERNEL::CONTROL-STACK-EXHAUSTED {10026620A3}>
CL-USER> (sum-tail 100000)
5000050000 (33 bits, #x12A06B550)
CL-USER> (sum-tail 1000000)
500000500000 (39 bits, #x746A5A2920)
CL-USER> (sum-tail 10000000)
50000005000000 (46 bits, #x2D7988896B40)

Hope it helps in SBCL.