lambda²

Disclaimer: this article is by no means basic - it get hairy very quickly. Some acquaintance with Common Lisp is required.

One of the most powerful (and at the same time, most intimidating) features of Lisp is the concept of lambda - an anonymous function. Here is a basic example:

(lambda (x) (+ 1 x)) This is an anonymous function that adds 1 to its argument. It can be called this way:

((lambda (x) (+ 1 x)) 5) => 6

And this way (explicitly specifying that it's a function call):

(funcall (lambda (x) (+ 1 x)) 5) => 6

What I call lambda² is an anonymous function returning another anonymous function, like this:

(lambda (x) (lambda (y) (+ x y)))

Consider the following:

((lambda (y) ((lambda (x) (* y x)) 10)) 2) => 20

The function (lambda (y) ((lambda (x) (* y x)) 10)) is called with the argument 2, so this is actually equivalent to:

(funcall (lambda (y) ((lambda (x) (* y x)) 10)) 2) => 20

What does this do ? It substitutes y for 2, and executes the body of the function. The body of the function is actually a call of the function (lambda (x) (* y x)) with the argument 10. But recall that y is substituted for 2, so it's the call of (lambda (x) (* 2 x)) on 10. Which is 20, of course.

Note that this is not the same as:

(((lambda (y) (lambda (x) (* x y))) 10) 2)

This doesn't actually result in anything, in fact it's an error ! There is a difference between:

(lambda (y) ((lambda (x) (* y x)) 10))

And:

((lambda (y) (lambda (x) (* x y))) 10)

The former is a function (an anonymous one), but the latter isn't. The latter is actually a function call, that returns (lambda (x) (* x 10)). So, while the former can be directly called on some argument, the latter can't be, it must be first executed, and its returned result then can be directly called on some argument. What's missing is an explicit funcall:

(funcall ((lambda (y) (lambda (x) (* x y))) 10) 2) => 20

As you see, lambda expressions get get pretty hairy and it's easy to lose your path among "functions" and "meta-functions" (functions that return functions). However, having understood these concepts and the subtleties involved, the power and flexibility in your hands is immense.