2

I'm teaching myself lisp, mostly because I like the idea of being able to build programs from small axiomatic blocks. Learning lisp is a hobby project for me because i) it seems fun and ii) I want to see if it really does let me look at problems in a new way. To this end I'm working through Paul Graham's The Roots of Lisp article. I am using the SBCL implementation, though my issue occurs on other implementations also. I've encountered a problem trying to use parameters as operators in a lambda function:

((lambda (f) (f '(b c))) 
 '(lambda (x) (cons 'a x)))

Per section 2 of The Roots of Lisp, this should evaluate to (a b c). This makes sense, the second lambda is a parameter to the first. Assuming my understanding is correct, the expression simplifies to:

((lambda (x) (cons 'a x)) '(b c))

Fine. Running the latter works as expected. However, running the former, unsimplified, expression results in the error: The function COMMON-LISP-USER::F is undefined. Other SO questions (here and here) lead me to believe this is something to do with the function vs variable namespaces in CL, and I've tried the #' syntax in various ways, but I can't seem to get it to work the way I'd expect. What should I do?

Thanks!

Will Ness
  • 70,110
  • 9
  • 98
  • 181
blex-max
  • 45
  • 4

2 Answers2

4

You have two errors here:

  1. You shouldn't quote this expression '(lambda (x) (cons 'a x)), it has to evaluate to function.
  2. As Common Lisp is Lisp-2, you have to use funcall to get the function value of a symbol.

Correct code:

((lambda (f) (funcall f '(b c))) 
 (lambda (x) (cons 'a x)))
Martin Půda
  • 7,353
  • 2
  • 6
  • 13
  • Thanks, I wasn't expecting an answer so quickly. That being the case, why do you think Paul Graham has quoted the second lambda expression in my *The Roots of Lisp*? Would that work in some versions of lisp? Given how big a figure he seems to be in the lisp world I would be surprised to discover that he was simply wrong! – blex-max Jul 24 '22 at 15:36
  • another possibility is to use `coerce` with the `funcall`, keeping the lambda quoted, with `((lambda (f) (funcall (coerce f 'function) '(b c))) '(lambda (x) (cons 'a x)))`. Also, in Common Lisp your code is usually written as `((lambda (f) (funcall f '(b c))) #'(lambda (x) (cons 'a x)))`, with the `#'`. – Will Ness Jul 24 '22 at 17:19
  • 3
    Before Common Lisp, which standardized a lot of existing practices, a quoted lambda form could be interpreted as a function (this is the case in Emacs Lisp, if you fix the code by using funcall). The Roots of Lisp talks about the McCarthy version of Lisp (or a very similar reimplementation) – coredump Jul 24 '22 at 18:38
  • 1. You must quote it since the code is meant for `eval.`, not Common Lisp. 2. The language `eval.` implements is not a Lisp-2, but a dynamicly scoped McCharty lisp. Thus none of those were errors. The erroir is OP confusing host language and the interpreted language. – Sylwester Jul 31 '22 at 13:14
1

Having to quote lambdas is a feature in the articles lisp eval.. eval. is not Common Lisp but a lisp intepreter that works like the every first lisp from McCarthy's lisp paper.

In the roots of Lisp, just like McCarthy original paper, Paul Graham bootstraps a language description by showing properties of the language and under 2. Denoting functions also shows that functions can be parameters and that they are indeed quoted.

The reason for this is that the eval. does not have a term that evaluates lambda forms. Eg. if you were to not quote the evaluator will try to evaluate it as code and fail. This could be avoided by just adding one line making all lambda forms self evaluating. There is a commercial lisp called PicoLisp that has dynamic bindings and use very similar way to make anonymious functions today.

McCarthy defines eval in its own language since there was no excisting lisp to run it in. Paul uses Common Lisp since that is what he chose. Thus there is a big difference between the code language and what is expected as code to the eval. function. The very first Scheme was made under a Common Lisp predecessor and while the host language didn't have closures the interpreter had them as a core feature. In Lisp in small pieces you get to see lot of rewriting of a interpreter where you see giving a language some features often by its design will give it some disadvantages as well.

Just for fun, adding this to the eval. as first cond term will make it accept lamdbas unquoted:

((eq (car e) 'lambda) e)

Then this should work:

(eval. '((lambda (f) (f '(b c))) 
         (lambda (x) (cons 'a x)))
       '())

Now you could change that line to store the environment a and use that instead of the dynamic a when appying. That would make it a lexical lisp.

Sylwester
  • 47,942
  • 4
  • 47
  • 79