((lambda (f) (f '(b c))) '(lambda (x) (cons 'a x)))
I've been following along with Paul Graham's excellent "The Roots of Lisp" in my second attempt at writing an interpreter (+Matt Giuca will remember the 10ft hole I dug myself in last time). This time everything works, except this expression explodes on me.
I suspect it's a typo. Common Lisp chokes on this kind of expression, but Scheme is fine so long as the second lambda isn't quoted.
TL;DR: It's not a typo. It's correct but confusing, and I think it exposes a design flaw in this Lisp dialect. (And note that this is specific to this particular and quite hypothetical Lisp dialect, not mainstream Lisps like CL and Scheme.)
My initial intuition was that it's a typo too. Surely the expression (lambda ...) creates a function object which would then be passed as an argument to the left-hand function, much like you would express in Python:
(lambda f: f(['b', 'c']))(lambda x: ['a'] + x)
Surely quoting the right-hand lambda would create not a function object, but a literal list expression describing the lambda, which wouldn't work at all...
But no, something very strange is going on here (now the details are coming back to me).
"Real" Lisps (CL and Scheme) probably behave more like Python, with lambdas producing actual functors, but this "little Lisp" (much closer to McCarthy's original Lisp, but not identical) is much simpler and more primitive and its lambdas behave differently.
This little Lisp doesn't actually have function objects as a first-class type. The only values in the execution environment are atoms and s-expressions (pairs). "lambda" is not actually a function (if you directly eval a lambda expression, you get a "no such variable: lambda" error). Lambda is a special form which only exists as a literal list.
So if you evaluate this expression in Graham's Lisp -- note the right lambda is unquoted: ((lambda (f) (f '(b c))) (lambda (x) (cons 'a x)))
You should get "no such variable: lambda", because it will be recursively trying to evaluate the expression (lambda (x) (cons 'a x)), a call to the "lambda" function, which doesn't exist.
By quoting that expression on the right, you are passing the literal list object (lambda (x) (cons 'a x)) as the parameter f. So during the execution of the left lambda, the environment dictionary should include {'f': (lambda (x) (cons 'a x))}. Now when we go to evaluate the expression (f '(b c)), we look up f in the dictionary and replace it with ((lambda (x) (cons 'a x)) '(b c)), and then finally we apply that lambda: (cons 'a '(b c)).
The real WTF here (the reason it's so confusing) is that Graham's Lisp special-cases bare unquoted lambdas on the left of a function call expression! If we ask ourselves, in a function call expression (f x), does f get interpreted literally, or does it get evaluated? The answer depends on whether f is a lambda.
In the expression (f x), where f is an atom, we evaluate both f and x; looking up f in the dictionary to get its "function object" (actually just a lambda expression), and then applying it. But in the expression ((lambda ...) x), we do not evaluate the left hand side; we just treat it as a lambda. That's why you don't have to quote a literal lambda on the left side of a function application. Why in this example, the left lambda is unquoted but the right lambda is quoted. I'm not sure if this was a problem with McCarthy's Lisp or something introduced here by Graham.
I would suggest a semantic change to make this language more palatable: always evaluate the LHS of an application expression, which means you need to quote both lambdas:
('(lambda (f) (f '(b c))) '(lambda (x) (cons 'a x)))
As an exercise to the reader, figure out how you would update the "eval" function in Section 4 to follow these new semantics (I think it actually simplifies things because you remove one special case, but I haven't tried it).
Matt Giuca
Confirmed that McCarthy's original Lisp (described in Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I, 1960) has the exact same semantics.
To further highlight the problem here, consider the expression: ((f x) y)
If f is a curried function that returns a function... this doesn't actually work because this Lisp only accepts two special cases of function application:
(f x) where f is an atom, or ((lambda (...) (...)) x)
You cannot put any arbitrary expression on the LHS of an application, even if that expression returns a function. You must first assign the result of the expression into a variable, then put that variable on the LHS of the application. Not composable.
David Coles
Thanks for that terrific explanation. I think since I'd been so far down the path of implementing the built-in operators with Python functions that it didn't even occur to me that eval returning something other than an Atom or a List was verboten.
I still think it's useful in showing that it's possible to do computation without invoking a new type, but as you've pointed out it makes the syntax a bit hairy.
Honestly I think I'm more bothered by the operators `cond` and `quote` (the equivalent of statements in Python) not being functions. However I can see that without them you wouldn't have much of a language and if they were part of the lexical syntax then you'd lose the beauty code and data being interchangeable as lists.
Matt Giuca
The interesting part of the exercise (for me) is the "eval" implementation, written there in Lisp, which shows you the precise semantics of the language, implemented in itself.
The exercise, for me, was essentially porting the "eval" function (and the supporting functions) from Lisp into Python and therefore having a precisely equivalent Lisp interpreter written in Python. That way, you don't get tempted to bring your own intuition about what "lambda" should do, for instance. You just port exactly what's written and then realise what you've created after the fact.
Yes I see what you mean about those primitives feeling a bit broken in that they do things that an ordinary function can't do (i.e., they care about the lexical form of their arguments where no other function can do that). "atom" is the same; (atom x) gives a different result to (atom (f y)), even if (f y) returns the same value as x. But if it helps, a) those things are special because they have to be; they are essentially the syntax of the language, and b) more advanced Lisps let you write your own macros that also care about the lexical structure of their arguments (essentially functions that automatically quote their arguments).
