Common lisp error: "should be lambda expression"

Question

I just started learning Common Lisp a few days ago, and I'm trying to build a function that inserts a number into a tree. I'm getting an error,

* - SYSTEM::%EXPAND-FORM: (CONS NIL LST) should be a lambda expression

From googling around, it seems like this happens when you have too many sets of parenthesis, but after looking at this for an hour or so and changing things around, I can't figure out where I could be doing this.

This is the code where it's happening:

(defun insert (lst probe)
    (cond ((null lst) (cons probe lst))
        ((equal (length lst) 1)
            (if (<= probe (first lst))
                (cons probe lst)
                (append lst (list probe))))
        ((equal (length lst) 2)
            ((cons nil lst) (append lst nil) (insertat nil lst 3)
                (cond ((<= probe (second lst)) (insert (first lst) probe))
                     ((> probe (fourth lst)) (insert (fifth lst) probe))
                     (t (insert (third lst) probe)))))))

I'm pretty sure it's occurring after the ((equal (length lst) 2), where the idea is to insert an empty list into the existing list, then append an empty list onto the end, then insert an empty list into the middle.

Answer 1

You are right; at the line marked with "error is here", there is a syntax error:

(defun insert (lst probe)
  (cond ((null lst) (cons probe lst))
        ((equal (length lst) 1)
         (if (<= probe (first lst))
             (cons probe lst)
             (append lst (list probe))))
        ((equal (length lst) 2)
         (#|Error is here|# (cons nil lst) (append lst nil) (insertat nil lst 3)
          (cond ((<= probe (second lst)) (insert (first lst) probe))
                ((> probe (fourth lst)) (insert (fifth lst) probe))
                (t (insert (third lst) probe)))))))

To the compiler/interpreter, the form reads as a function call to the "function" (cons nil list) which is not a function at all. The compiler complains here about the use of a compound form in the "operator" position, which is not a lambda (the only kind of compound form accepted in that position.)

((cons nil lst)                         #| <-- Form in operator position |#
 (append lst nil)                       #| <-- First argument form |#
 (insertat nil lst 3)                   #| <-- Second argument form |#
 (cond ((<= probe (second lst)) (insert (first lst) probe)) #| Third argument |#
       ((> probe (fourth lst)) (insert (fifth lst) probe))
       (t (insert (third lst) probe))))

I'd help with re-formulating the expression, but I am not sure what you want to accomplish here.

Answer 2

Correct! The problem is in the line right after that, where it says

((cons nil lst) (append lst nil) (insertat nil lst 3) ...

The issue is the two opening parentheses. Parentheses can change meaning in special contexts (like the cond form you're using), but in this context, the parentheses signify regular function application, just like you're probably used to. That means the first thing after the parentheses must be a function. From the perspective of the outer parentheses, the first thing is (cons nil lst), so that must be a function (which it's not).

Note that you can't just remove the parentheses, because the cons function returns a new list like you want but doesn't change the old list. You probably want something like this:

(setq lst (cons nil lst))
(setq lst (append lst nil))
(setq lst (insertat nil lst 3))
...

Answer 3

If you indent the function correctly, then you can see that there is an extra parenthesis in front of CONS NIL LST.

(defun insert (lst probe)
  (cond ((null lst) (cons probe lst))
        ((equal (length lst) 1)
         (if (<= probe (first lst))
             (cons probe lst)
           (append lst (list probe))))
        ((equal (length lst) 2)
         ((cons nil lst) (append lst nil) (insertat nil lst 3)
          (cond ((<= probe (second lst)) (insert (first lst) probe))
                ((> probe (fourth lst)) (insert (fifth lst) probe))
                (t (insert (third lst) probe)))))))

In most Lisp IDEs you can indent expressions. In LispWorks, select the whole expression and do m-x Indent Region.