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.

Coupon

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)

Fivefold

As pointed out by danlei, the first function has a typo, it should call itself, and not addup, which is essentially the function you described. If I correct the typo, it overflows as well. Still, I'm puzzled that the do construct is more capable than the recursive one. I don't seem to find anything regarding TCO for CLISP when googling and browsing the spec at clisp.org. Wouldn't it be strange if tail recursion is not more powerful than ordinary recursion? – Coupon

You should not be surprised. Tail call optimization just makes a recursive definition run in constant (stack) space, so that it can be as fast as an iterative definition. There is no magic involved that could make it faster than that. – Fivefold

In Barski's Land of Lisp, I just read that indeed CLISP only optimises tail calls, when one compiles the function. In fact, the tail recursive one is a little faster, so no mystery here. – Coupon

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.

Osman

Oh god, how silly. I'm really bad at detecting these kind of typos. Thanks. The addup function which I did not include above, does the same, but with a do construct. It wasn't meant to be called though. – Coupon

Don't worry, we all make mistakes like this from time to time and they are hard to spot. – Osman

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.

Earthlight

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.

Punchboard