Stack overflow from recursive function call in Lisp

Question

I am learning Lisp from the book "The Land of Lisp" by Conrad Barski. Now I have hit my first stumbling block, where the author says:

Calling yourself in this way is not only allowed in Lisp, but is often strongly encouraged

after showing the following example function to count the items in a list:

(defun my-length (list)
  (if list
    (1+ (my-length (cdr list)))
    0))

When I call this function my-length with a list containing a million items, I get a stack overflow error. So either you never expect to have a list that long in Lisp (so maybe my use case is useless) or there is another way to count items in such a long list. Can you maybe shine some light on this? (I am using GNU CLISP on Windows, by the way).

Answer 1

TCO (tail call optimization) in CLISP using the example from Chris Taylor:

[1]> (defun helper (acc list)
       (if list
           (helper (1+ acc) (cdr list))
           acc))

(defun my-length (list)
  (helper 0 list))

HELPER

Now compile it:

[2]> (compile 'helper)
MY-LENGTH
[3]> (my-length (loop repeat 100000 collect t))

*** - Program stack overflow. RESET

Now, above does not work. Let's set the debug level low. This allows the compiler to do TCO.

[4]> (proclaim '(optimize (debug 1)))
NIL

Compile again.

[5]> (compile 'helper)
HELPER ;
NIL ;
NIL
[6]> (my-length (loop repeat 100000 collect t))
100000
[7]> 

Works.

Allowing the Common Lisp compiler to do TCO is most often controlled by the debug level. With a high debug level, the compiler generates code which uses a stack frame for each function call. This way each call can be traced and will be seen in a backtrace. With a lower debug level the compiler may replace tail calls with jumps in the compiled code. These calls then will not be seen in a backtrace - which usually makes debugging harder.