Using a lambda value from function as first element of list

Question

I'm reading over Peter Norvig's Paradigms of Artificial Intelligence Programming, and I've come across an issue I cannot resolve on my own (this is my introduction to Lisp). The issue is quite a small one, really, but obviously not one my little brain can solve.

Why is it that when a function's value is a lambda, it is an error to use that function as the first element to a list. For example:

Lisp:

(defun some-func ()
  #'(lambda (x) x))

;; At REPL
;; Does not work
> ((some-func) 1)
;; Does work
> ((lambda (x) x) 1)
;; Also works
> (funcall (some-func) 1)

I hope that makes sense!

Answer 1

This is a good question, and one where Common Lisp can be pretty confusing. The thing is that due to historical reasons, Common Lisp has two namespaces -- one for functions and another for values. To make this happen, there are two different evaluation rules for the head position of a function application and for the rest -- the first will evaluate a symbol as a function name, and the second will evaluate a symbol as a variable reference. There are obviously cases when the value is actually a function -- for example, if you write a mapcar function, you'll want to do something like

(defun my-mapcar (f l)
  (if (null l)
    '()
    (cons (f (car l)) (my-mapcar f (cdr l)))))

but this won't work -- it will complain about f being an unknown function. For these cases there is a special function called funcall, which receives a function and argument for the function, and will apply the function as usual -- and since funcall is a plain function, its arguments are all evaluated as usual (as values). So the above should be fixed by using it:

(defun my-mapcar (f l)
  (if (null l)
    '()
    (cons (funcall f (car l)) (my-mapcar f (cdr l)))))

As you probably suspect now, there are the mirror cases -- where you want to evaluate something as a function and not as a value. For example, this doesn't work:

(my-mapcar 1+ '(1 2 3))

because it refers to the 1+ variable and not the function. For these cases there is a special form called function that evaluates its contents as a function and returns it as a value:

(my-mapcar (function 1+) '(1 2 3))

and it can be abbreviated with #':

(my-mapcar #'1+ '(1 2 3))

That's not the end of this story -- to give a few examples:

• in some cases a simple quoted name can work as a function -- for example '1+ in the last example works -- but this is a kind of a hack that can see only globally bound names, so #' is almost always better

• a similar hack can be used with lambda -- so you can use (my-mapcar '(lambda (x) (1+ x)) '(1 2 3)), in fact, you could use (list 'lambda '(x) '(1+ x)) which is even worse (and IIRC, non-portable), but using (lambda (x) (1+ x)) works since it's implicitly wrapped in a #' (try expanding a lambda form as a macro and you'll see it). A related hack makes it fine to use a lambda expression as the head of a function application (which is one of the things you've tried).

• let etc bind local values, and in some cases you'll want to bind local functions instead -- for this, there are new binding constructs: flet and labels

If all of this looks weird and/or overly complicated, then you're not alone. It's one of the main differences between Common Lisp and Scheme. (The difference then leads to changes in common idioms in both languages: Scheme code tends to use higher order functions much more frequently than Common Lisp code. As usual with these kind of religious questions, some people argue in favor of what CL does, claiming that higher order functions are confusing so they like the explicit in-code reminder.)

Answer 2

((lambda (x) ...) ...) is a hardcoded special case in the evaluator rules. It's not evaluating the first element in the form and using the result as a general case. It's normal that you have to use funcall or apply to call a function that is the result of evaluating some other form.