Emacs lisp: why does this sexp cause an invalid-function error?

Question

The sexp in question is

(((lambda (b)
  (lambda (a)
    (+ b a))) 3) 5)

which, to me, looks like it should evaluate to 8, and in other lisps (e.g. Racket) it does, but in elisp it instead throws this error:

Debugger entered--Lisp error: (invalid-function ((lambda (b) (lambda (a) (+ b a))) 3))

It appears to be telling me that

((lambda (b)
  (lambda (a)
    (+ b a))) 3)

Is not a valid function. This seems wrong, because when I evaluate that expression I get

(lambda (a) (+ b a))

which looks like a valid function to me. Does anyone have any idea why this happens? Does it have something to do with dynamic scoping?

Kubis

Answer 1

There are two issues here. The first is a matter of syntax, as other answers have pointed out. The second, which is mentioned in the question, is a matter of scoping issues.

The Syntactic Issue

In Emacs Lisp (and other Lisps in the Lisp-2 family), a function call looks like (f args...) where f is a either a symbol that has a function value, or a lambda expression. For instance,

(list 1 2 3)  
=> (1 2 3)

because list has a function binding. Also,

((lambda (x y) (list x x y y)) 1 2)
=> (1 1 2 2)

because (lambda (x y) (list x x y y)) is a lambda expression. What you can't do, though, is use something the value of which of is a function.

(let ((id (lambda (x) x)))
  (id 3))

signals a Lisp error: (void-function id). But we can call function values using funcall:

(let ((id (lambda (x) x)))
  (funcall id 3))
=> 3

Note: That's a reasonably good way of looking at it, but in fact things are a little more complicated. See 9.2 Kinds of Forms in the manual for the details and esoteric bits such as function indirection.

So, now we can address the syntax issue. The original code, reformatted a bit to indicate which functions are getting which arguments, is:

(((lambda (b)
    (lambda (a)
      (+ b a)))
  3)
 5)

As I understand it, the intent is to first call (lambda (b) ...) with the argument 3 to get back an anonymous function, (lambda (a) ...). In Emacs Lisp that would be:

((lambda (b)
   (lambda (a)
     (+ b a)))
 3)
=> (lambda (a) (+ b a))

Now, you also want to call the returned anonymous function with 5. We use funcall to do that:

(funcall ((lambda (b)
            (lambda (a)
              (+ b a)))
          3)
         5)

The Scoping Issue

Disappointingly, this code produces a Lisp error: (void-variable b). This is where we finally run into the issue of dynamic versus lexical scoping. Because the variable b was bound dynamically, its value is not preserved in the anonymous function (lambda (a) (+ b a)). We can check to see that this is what's happening by surrounding the whole form in something that binds b and seeing what happens:

(let ((b 100))
  (funcall ((lambda (b)
              (lambda (a)
                (+ b a)))
            3)
           5))
=> 105

I'm not much of an Emacs Lisp hacker, so I'm not sure of the best way to get lexical closures in Emacs. I read that Emacs 24 has it, but I'm still on 23 here. Based on this answer, though, we can use lexical-let to get the results we need:

(funcall ((lambda (b)
            (lexical-let ((b b))
              (lambda (a)
                (+ b a))))
          3)
         5)
=> 8

lexical-let establishes the lexical binding that we need, so that the anonymous function (lambda (a) ...) does have that 3 stuck into it. More specifically, we introduced a lexical binding of b, and it is that lexical binding that (lambda (a) …) references. In fact, if we look at the returned anonymous function now, it's not simply (lambda (a) (+ b a)), but is printed in a more complex (and less useful) way:

((lambda (b)
   (lexical-let ((b b))
     (lambda (a)
       (+ b a))))
 3)
=> (lambda (&rest --cl-rest--) (apply (lambda (G27322 a) (+ ... a)) (quote --b--) --cl-rest--))

As an aside, it doesn't matter that the lexically-bound variable b has the same name as the dynamically bound b; we could have used (lexical-let ((c b)) ... (+ c a) ...), instead.

Bluma

Wow, thanks for the thorough answer! (void-variable b) is what I was expecting, I just didn't know about the Lisp-2 issue. – Kubis

@JamesPorter Glad to help! I learned a bunch answering it, too! I knew about the Lisp-1 vs. Lisp-2 issue, had forgotten about the Emacs dynamic scoping issue, and learned some nifty things about Emacs evaluation model (the function indirection bit really is kind of interesting). – Bluma

Answer 2

Short answer: It's an effect of Lisp-1 vs. Lisp-2

Slightly longer answer: For application, Emacs Lisp calls the function value of the first symbol in a list, but lambda returns just a simple function object. That means that you would have to use funcall to make things work. funcall applies its second argument to the remaining arguments (much like apply, but the latter expexts its last argument to be a list).

(funcall (lambda (a) (funcall (lambda (b) (+ a b)) 5)) 3)
=> 8

Take a look at the emacs documentation (e.g. C-h f funcall) for more info.

Disentangle

The outermost form doesn't need to be rewritten though. Emacs Lisp, like Common Lisp, Scheme, and many other Lisps does allow lambda expressions in the function position. This means that, e.g., ((lambda (x) (+ x 3)) 5) produces 8. See lambda in the GNU Emacs Lisp manual. – Bluma

Oops, my mistake; I misread what @JamesPorter had written. The bit about ((lambda (x) ...) y) still holds (i.e., a lambda expression is OK in the function position), but that's the not the issue that the OP had. – Bluma

Actually, the translation you've provided isn't equivalent to the what the OP posted (aside from the fact that it runs and produces 8, and the code in the question doesn't). Since you're calling the inner lambda function within the call to the outer lambda function, the binding of a is still in effect. The OP's original code (with appropriate funcalls) would have returned an anonymous function, (lambda (a) ...) intended to close over the value of b, and then call it with 5. At this point, there's an issue with dynamic scoping, because b won't actually be bound. – Bluma

Answer 3

The car of (((lambda (b) (lambda (a) (+ b a))) 3) 5) is neither a symbol with a valid function definition associated, nor the symbol lambda, so it's not a valid function call.

Grenada

Answer 4

FWIW, another rearrangement would give you this:

((lambda (b)
   ((lambda (a)
      (+ b a))
    3))
 5)

=> 8

(but I don't think that's what you were trying to do)

Gobelin