Section 24

Intermezzo 4: Defining Functions on the Fly

Many uses of abstract functions require the definition of auxiliary functions. Consider filter1, which consumes a filtering function, a list, and a filtering item. In the previous section alone, we encountered three uses of filter1 with three different auxiliary functions: squared?, <ir, and eq-ir?.

Since these auxiliary functions are only used as arguments to filter1, we should employ the program organization guidelines from the preceding intermezzo (18). That is, we should use a local-expression to indicate that the application of filter1 and the auxiliary function definition belong together. Here is one possible arrangement for the filter1-eq-ir? combination:

;; find : list-of-IRs symbol  ->  boolean
(define (find aloir t)
  (local ((define (eq-ir? ir p)
	    (symbol=? (ir-name ir) p)))
    (filter1 eq-ir? aloir t)))

An alternative arrangement places the local-expression where the function is needed:

;; find : list-of-IRs symbol  ->  boolean
(define (find aloir t)
  (filter1 (local ((define (eq-ir? ir p)
		     (symbol=? (ir-name ir) p)))
	     eq-ir?)
           aloir t))

This alternative is feasible because the names of functions -- like eq-ir? -- are now legitimate expressions and can play the role of local's body. Thus the local-expression introduces a function definition and returns the function as its result.

Because good programmers use abstract functions and organize their programs in a tidy manner, it is not surprising that Scheme provides a short-hand for this particular, frequent use of local. The short-hand is called a lambda-expression and greatly facilitates the introduction of functions like eq-ir?, squared?, or <ir. The following two subsections introduce the syntax and semantics of lambda-expressions. The last subsection discusses its pragmatics.

Syntax of lambda

A lambda-expression is just a new form of expression:

Here are three useful examples:

1. (lambda (x c) (> (* x x) c))

2. (lambda (ir p) (< (ir-price ir) p))

3. (lambda (ir p) (symbol=? (ir-name ir) p))

They correspond to squared?, <ir, and eq-ir?, respectively, the three motivating examples discussed above.

A lambda-expression defines an anonymous function, that is, a function without a name. The sequence of variables behind lambda are the function's parameters; the third component is the function's body.

Scope and Semantics of lambda

As discussed in the introduction, a lambda-expression is just a short-hand for a local-expression. In general, we can think of

(lambda (x-1 ...  x-n) exp)

(local ((define (a-new-name x-1 ... x-n) exp))
  a-new-name)

The short-hand explanation suggests that

(lambda (x-1 ...  x-n) exp)

Similarly, the explanation implies basic facts that govern the evaluation of lambda-expressions:

1. A lambda-expression is a value because functions are values.

2. The application of lambda-expressions to values proceeds according to our usual laws of function application, assuming we expand the short-hand first.

Here is a sample use of lambda:

  (filter1 (lambda (ir p) (< (ir-price ir) p))
           (list (make-ir 'doll 10))
	   8)

The application of filter1 consumes the lambda-expression, a (short) list of inventory records, and a threshold. Given our suggestion, the evaluation can be understood by an expansion of the lambda-expression into a corresponding local-expression:

...
= (filter1 (local ((define (<ir ir p) (< (ir-price ir) p))) <ir)
           (list (make-ir 'doll 10))
	   8)
= (filter1 <ir 
           (list (make-ir 'doll 10))
	   8)

For the last step, the local definition of <ir is lifted and added to the top-level definitions. From here, the evaluation proceeds as in section 19.2.

While it is natural to think of lambda as a short-hand, the last two points also suggest a way of understanding lambda-expressions directly. In particular, we can adapt the law of application to lambda-expressions:

  ((lambda (x-1 ... x-n) exp)   
   val-1 ... val-n)  
  
  

  = exp
    with all occurrences of x-1 ... x-n
    replaced by val-1 ... val-n
  

Let us reconsider the above example in this light:

  (filter1 (lambda (ir p) (< (ir-price ir) p))
           (list (make-ir 'doll 10))
           8)

As usual, this application is replaced by the body of filter1
with all parameters replaced by their values. This step places a
lambda-expression into the function position of an application:

= (cond
    [((lambda (ir p) (< (ir-price ir) p))
      (make-ir 'doll 10) 8) 
     (cons (first (list (make-ir 'doll 10)))
       (filter1 (lambda (ir p) (< (ir-price ir) p))
	        (rest (list (make-ir 'doll 10)))
	        8))]
    [else
      (filter1 (lambda (ir p) (< (ir-price ir) p))
  	       (rest (list (make-ir 'doll 10)))
	       8)])

= (cond
    [(< (ir-price (make-ir 'doll 10)) 8)
     (cons (first (list (make-ir 'doll 10)))
       (filter1 (lambda (ir p) (< (ir-price ir) p))
	        (rest (list (make-ir 'doll 10)))
	        8))]
    [else
      (filter1 (lambda (ir p) (< (ir-price ir) p))
  	       (rest (list (make-ir 'doll 10)))
	       8)])

= ...

From here, the evaluation proceeds as usual. Still, even this short-hand evaluation shows that, while using lambda-expressions in programs is convenient, replacing it with a named function (often) simplifies calculations.

Exercise 24.0.7.   Decide which of the following phrases are legal lambda-expressions:

1. (lambda (x y) (x y y))

2. (lambda () 10)

3. (lambda (x) x)

4. (lambda (x y) x)

5. (lambda x 10)

Explain why they are legal or illegal.    Solution

Exercise 24.0.8.   Draw arrows from the underlined occurrences of x to their binding occurrences in each of the following three lambda-expressions:

1.   
   

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

2.   
   

   (lambda (x y)
     (+ x
        (local ((define x (* y y)))
          (+ (* 3 x)
   	  (/ 1 x)))))
   

3.   
   

   (lambda (x y)
     (+ x
        ((lambda (x)
   	(+ (* 3 x)
   	   (/ 1 x)))
         (* y y))))
   

Also draw a box for the corresponding scope of each underlined x and holes in the scope where necessary.    Solution

Exercise 24.0.9.   Evaluate the following expressions by hand:

1.   
   

   ((lambda (x y)
      (+ x (* x y)))
    1 2)
   

2.   
   

   ((lambda (x y)
      (+ x
         (local ((define x (* y y)))
   	(+ (* 3 x)
   	   (/ 1 x)))))
    1 2)
   

3.   
   

   ((lambda (x y)
      (+ x
         ((lambda (x)
   	 (+ (* 3 x)
   	    (/ 1 x)))
          (* y y))))
    1 2)
   

   Solution

Pragmatics of lambda

The guideline for using lambda-expressions is straightforward:

If we were to apply the guideline to the programs in the preceding sections, we would quickly see how much lambda simplifies the use of abstracted functions. For that reason, Scheme offers many abstracted functions in its libraries. In future sections, we will encounter many more examples where lambda-expressions are convenient.