lisp - '('(LIST) 'NIL 'NIL) should be a lambda expression in (hanoi('('(list)'()'())))

Question

I'm trying to implement the Towers of Hanoi.I'm not printing out anything between my recursive calls yet, but I keep getting an error saying

'('(LIST) 'NIL 'NIL) should be a lambda expression

I've read that the reason this happens is because of a problem with the parenthesis, however I cannot seem to find what my problem is. I think it's happening in the pass-list function when I am trying to call the hanoi function. My code:

(defun pass-list(list)
   (hanoi('('(list)'()'())))
)

(defun hanoi ('('(1) '(2) '(3)))

    (hanoi '('(cdr 1) '(cons(car 1) 2) '(3)))

    (hanoi '('(cons(car 3)1) '(2)'(cdr 3)))
 )

Answer 1

This code has many syntax problems; there are erroneous quotes all over the place, and it looks like you're trying to use numbers as variables, which will not work. The source of the particular error message that you mentioned comes from

(hanoi('('(list)'()'())))

First, understand that the quotes in 'x and '(a b c) are shorthand for the forms (quote x) and (quote (a b c)), and that (quote anything) is the syntax for getting anything, without anything being evaluated. So '(1 2 3) gives you the list (1 2 3), and '1 gives you 1. quote is just a symbol though, and can be present in other lists, so '('(list)'()'()) is the same as (quote ((quote (list)) (quote ()) (quote ()))) which evaluates to the list ((quote (list)) (quote ()) (quote ())). Since () can also be written nil (or NIL), this last is the same as ('(list) 'NIL 'NIL). In Common Lisp, function calls look like

(function arg1 arg2 ...)

where each argi is a form, and function is either a symbol (e.g., list, hanoi, car) or a list, in which case it must be a lambda expression, e.g., (lambda (x) (+ x x)). So, in your line

(hanoi('('(list)'()'())))

we have a function call. function is hanoi, and arg1 is ('('(list)'()'())). But how will this arg1 be evaluated? Well, it's a list, which means it's a function application. What's the function part? It's

'('(list)'()'())

which is the same as

'('(list 'NIL 'NIL))

But as I just said, the only kind of list that can be function is a lambda expression. This clearly isn't a lambda expression, so you get the error that you're seeing.

I can't be sure, but it looks like you were aiming for something like the following. The line marked with ** is sort of problematic, because you're calling hanoi with some arguments, and when it returns (if it ever returns; it seems to me like you'd recurse forever in this case), you don't do anything with the result. It's ignored, and then you go onto the third line.

(defun pass-list(list)
  (hanoi (list list) '() '()))

(defun hanoi (a b c)
  (hanoi (rest a) (cons (first a) b) c)  ; **
  (hanoi (cons (first c) a) b (rest c)))

If hanoi is supposed to take a single list as an argument, and that list is supposed to contain three lists (I'm not sure why you'd do it that way instead of having hanoi take just three arguments, but that's a different question, I suppose), it's easy enough to modify; just take an argument abc and extract the first, second, and third lists from it, and pass a single list to hanoi on the recursive call:

(defun hanoi (abc)
  (let ((a (first abc))
        (b (second abc))
        (c (third abc)))
    (hanoi (list (rest a) (cons (first a) b) c))
    (hanoi (list (cons (first c) a) b (rest c)))))

I'd actually probably use destructuring-bind here to simplify getting a, b, and c out of abc:

(defun hanoi (abc)
  (destructuring-bind (a b c) abc
    (hanoi (list (rest a) (cons (first a) b) c))
    (hanoi (list (cons (first c) a) b (rest c)))))