Why does this Lisp function keep giving me a stack overflow?

Question

This function here:

(defun test (a)
               (if (equal a nil) 0)
               (if (listp (car a)) (print "a")
                 (print "b"))
               (test (cdr a))
               )

I want it to return 0 if a is nil which is the base case. then if the element in the front of the list is a list, print the letter a otherwise print b then call function again. Why doesn't the base case prevent the infinite loop?

Answer 1

Your code ends up with a stack overflow because you recurse into test regardless of the result of the nil-check.

(defun test (a)
  (if (equal a nil) 0)  ; <-- problem is partly here...
  (if (listp (car a))
      (print "a")
      (print "b"))
  (test (cdr a)))       ; <-- ...and partly down here

Even if (equal a nil) evaluates to T and the surrounding if therefore evaluates to 0, you basically ignore this result, because the next step you do is checking if a is a list regardless of the outcome of the previous nil-check. Eventually you call test again without taking the result of your comparisons into consideration.

Keep in mind that the result of a function in Lisp is the result of the last evaluated expression, meaning that if you want your function to return 0 you have to make 0 the last evaluated expression.

The following code behaves as you specified:

(defun test (a)
  (if (null a)
      0
      (progn
        (if (listp (car a))
            (print "a")
            (print "b"))
        (test (cdr a)))))

• Note that you can use null to do a nil-check.
• If a is not nil, then and only then, a is examined further. For this purpose progn lets you evaluate a sequence of expressions and eventually evaluates to the result of its last expression.

Answer 2

The other answers have explained your problem very well; just 2 notes:

cond

At least one style guide advises againt the use of if and prefers cond; this would have avoided the "fall-through problem":

(defun test (a)
  (cond
   ((equal a nil) 0)
   (t (if (listp (car a)) 
        (print "a")
        (print "b"))
      (test (cdr a)))))

return

You can return early from a function; your code would have worked with a return-from clause:

(defun test (a)
  (if (equal a nil) (return-from test 0))
  (if (listp (car a)) 
    (print "a")
    (print "b"))
  (test (cdr a)))

Answer 3

Because your base case is still followed by the printing and recursion. It didn't return straight afterwards.

Perhaps you wanted this:

(defun test (a)
  (if (null a)
      0
      (progn (if (listp (car a))
                 (print "a")
                 (print "b"))
             (test (cdr a)))))