2.5. Lambda Expressions

In the expression (let ((x (* 3 4))) (+ x x)), the variable x is bound to the value of (* 3 4). What if we would like the value of (+ x x) where x is bound to the value of (/ 99 11)? Where x is bound to the value of (- 2 7)? In each case we need a different let expression. When the body of the let is complicated, however, having to repeat it can be inconvenient.

Instead, we can use the syntactic form lambda to create a new procedure that has x as a parameter and has the same body as the let expression.

 (lambda (x) (+ x x)) ⇒ #<procedure>

The general form of a lambda expression is

 (lambda (var ...) exp₁ exp₂ ...)

The variables var … are the formal parameters of the procedure, and the sequence of expressions exp₁ exp₂ … is its body. (Actually, the true general form is somewhat more general than this, as you will see later.)

A procedure is just as much an object as a number, string, symbol, or pair. It does not have any meaningful printed representation as far as Scheme is concerned, however, so this book uses the notation #<procedure> to show that the value of an expression is a procedure.

The most common operation to perform on a procedure is to apply it to one or more values.

 ((lambda (x) (+ x x)) (* 3 4)) ⇒ 24

This is no different from any other procedure application. The procedure is the value of (lambda (x) (+ x x)), and the only argument is the value of (* 3 4), or 12. The argument values, or actual parameters, are bound to the formal parameters within the body of the lambda expression in the same way as let-bound variables are bound to their values. In this case, x is bound to 12, and the value of (+ x x) is 24. Thus, the result of applying the procedure to the value 12 is 24.

Because procedures are objects, we can establish a procedure as the value of a variable and use the procedure more than once.

 (let ((double (lambda (x) (+ x x))))   (list (double (* 3 4))         (double (/ 99 11))         (double (- 2 7)))) ⇒ (24 18 -10)

Here, we establish a binding for double to a procedure, then use this procedure to double three different values.

The procedure expects its actual parameter to be a number, since it passes the actual parameter on to +. In general, the actual parameter may be any sort of object. Consider, for example, a similar procedure that uses cons instead of +.

 (let ((double-cons (lambda (x) (cons x x))))   (double-cons 'a)) ⇒ (a . a)

Noting the similarity between double and double-cons, you should not be surprised to learn that they may be collapsed into a single procedure by adding an additional argument.

 (let ((double-any (lambda (f x) (f x x))))   (list (double-any + 13)         (double-any cons 'a))) ⇒ (26 (a . a))

This demonstrates that procedures may accept more than one argument and that arguments passed to a procedure may themselves be procedures.

As with let expressions, lambda expressions become somewhat more interesting when they are nested within other lambda or let expressions.

 (let ((x 'a))   (let ((f (lambda (y) (list x y))))     (f 'b))) ⇒ (a b)

The occurrence of x within the lambda expression refers to the x outside the lambda that is bound by the outer let expression. The variable x is said to occur free in the lambda expression or to be a free variable of the lambda expression. The variable y does not occur free in the lambda expression since it is bound by the lambda expression. A variable that occurs free in a lambda expression should be bound by an enclosing lambda or let expression, unless the variable is (like the names of primitive procedures) bound at top level, as we discuss in the following section.

What happens when the procedure is applied somewhere outside the scope of the bindings for variables that occur free within the procedure, as in the following expression?

 (let ((f (let ((x 'sam))            (lambda (y z) (list x y z))))) (f 'i 'am)) ⇒ (sam i am)

The answer is that the same bindings that were in effect when the procedure was created are in effect again when the procedure is applied. This is true even if another binding for x is visible where the procedure is applied.

 (let ((f (let ((x 'sam))            (lambda (y z) (list x y z)))))   (let ((x 'not-sam))     (f 'i 'am))) ⇒ (sam i am)

In both cases, the value of x within the procedure named f is sam.

Incidentally, a let expression is nothing more than the direct application of a lambda expression to a set of argument expressions. For example, the two expressions below are equivalent.

 (let ((x 'a)) (cons x x)) ≍ ((lambda (x) (cons x x)) 'a)

In fact, a let expression is a syntactic extension defined in terms of lambda and procedure application, which are both core syntactic forms. In general, any expression of the form

 (let ((var val) ...) exp₁ exp₂ ...)

is equivalent to the following.

 ((lambda (var ...) exp₁ exp₂ ...) val ...)

See Section 3.1 for more about core forms and syntactic extensions.

As mentioned above, the general form for lambda is a bit more complicated than the form we saw earlier, in that the formal parameter specification, (var …), need not be a proper list, or indeed even a list at all. The formal parameter specification can be in any of the following three forms.

a proper list of variables, (var₁ … var_n), such as we have already seen,
a single variable, var_r, or
an improper list of variables, (var₁ … var_n. var_r).

In the first case, exactly n actual parameters must be supplied, and each variable is bound to the corresponding actual parameter. In the second, any number of actual parameters is valid; all of the actual parameters are put into a single list and the single variable is bound to this list. The third case is a hybrid of the first two cases. At least n actual parameters must be supplied. The variables var₁ … var_n are bound to the corresponding actual parameters, and the variable var_r is bound to a list containing the remaining actual parameters. In the second and third cases, var_r is sometimes referred to as a "rest" parameter because it holds the rest of the actual parameters beyond those that are individually named.

Let's consider a few examples to help clarify the more general syntax of lambda expressions.

 (let ((f (lambda x x)))   (f 1 2 3 4)) ⇒ (1 2 3 4) (let ((f (lambda x x)))   (f)) ⇒ () (let ((g (lambda (x . y) (list x y))))   (g 1 2 3 4)) ⇒ (1 (2 3 4)) (let ((h (lambda (x y . z) (list x y z))))   (h 'a 'b 'c 'd)) ⇒ (a b (c d))

In the first two examples, the procedure named f accepts any number of arguments. These arguments are automatically formed into a list to which the variable x is bound; the value of f is this list. In the first example, the arguments are 1, 2, 3, and 4, so the answer is (1 2 3 4). In the second, there are no arguments, so the answer is the empty list (). The value of the procedure named g in the third example is a list whose first element is the first argument and whose second element is a list containing the remaining arguments. The procedure named h is similar but separates out the second argument. While f accepts any number of arguments, g must receive at least one and h must receive at least two.

Exercise 2.5.1.

Determine the values of the expressions below.

 a. (let ((f (lambda (x) x)))      (f 'a)) b. (let ((f (lambda x x)))      (f 'a)) c. (let ((f (lambda (x . y) x)))      (f 'a)) d. (let ((f (lambda (x . y) y)))      (f 'a))

Exercise 2.5.2.

How might the primitive procedure list be defined?

Exercise 2.5.3.

List the variables that occur free in each of the lambda expressions below. Do not omit variables that name primitive procedures such as + or cons.

 a. (lambda (f x) (f x)) b. (lambda (x) (+ x x)) c. (lambda (x y) (f x y)) d. (lambda (x)      (cons x (f x y))) e. (lambda (x)      (let ((z (cons x y)))        (x y z))) f. (lambda (x)      (let ((y (cons x y)))        (x y z)))