1.3 Formulating Abstractions with Higher-Order Procedures

Often the same programming pattern will be used with a number of different procedures. To express such pattersn as concepts, we will need to construct procedures that can accept procedures as arguments or return procedures as values. Procedures that manipulate procedures are called higher-oder procedures.

Procedures as Arguments

Consider the following three procedures. The first computes the sum of the integers from $a$ through $b$:

(define (sum-integer a b)
    (if (> a b) 0 (+ a (sum-integers (+ a 1) b))))

The second computes the sum of the cubes of the integers in a given range:

(define (sum-cubes a b)
    (if (> a b) 0 (+ (cube a) (sum-cube (+ a 1) b))))

The third computes the sum of a sequence of terms in the series

which converges very slowly to $\pi/8$:

(define (pi-sum a b)
    (if (> a b)
        0
        (+ (/ 1.0 (* a (+ a 2))) (pi-sum (+ a 4) b))))

These three procedures clearly share a common underlying pattern. We could generate each of the procedures by filling in slots in the same template:

(define (<name> a b)
    (if (> a b)
        0
        (+ (<term> a)
           (<name> (+ a 1) b))))

The presence of such a common pattern is strong evidence that there is a useful abstraction waiting to be brought to the suface. Indeed, mathematicians long ago identified the abstraction of summation of a series and invented “sigma notation”, for example

to express this concept. Simiarly, we would like our language to be powerful enough so that we can write a procedure the expresses the concept of summation itself rather than only procedures that compute particular sums. We can do so readily by taking the common template shown above and transforming the “slots” into formal parameters:

(define (sum term a next b)
    (if (> a b)
        0
        (+ (term a)
           (sum term (next a) next b))))

Notice that the sum takes as arugments the lower and upper bounds a and b together with the procedures term and next. Using the sum procedure to redefine the three sums above:

(define (inc n) (+ n 1))
(define (identity x) x)
(define (cube x) (* x x x))

(define (sum-integer a b)
    (sum identity a inc b))

(define (sum-cube a b)
     (sum cube a inc b))

(define (sum-pi a b)
    (define  (pi-term x)
        (/ 1.0 (* x (+ x 2))))
    (define (pi-next x)
        (+ x 4))
    (sum pi-term a pi-next b))

Once we have sum, we can use it as a building block in formulating further concepts. For instant, the definite integral of a function $f$ between the limits $a$ and $b$ can be approximated numerically using the formula

for small values of $dx$. We can express this directly as a procedure:

(define (integral f a b dx)
    (define (add-dx x) (+ x dx))
    (* (sum f (+ a (/ dx 2.0)) add-dx b) dx))

(integral cube 0 1 0.01)
; .24998750000000042

(integral cube 0 1 0.001)
; .249999875000001

(The exact value of the integral of cube between 0 and 1 is 1/4.)

Constructing Procedures Using Lambda

We introduce a special form lambda which lets us directly specify procedures without having to separately define them. In general, lambda is used to create procedures in the same way as define, except that no name is specified for the procedure:

(lambda (<formal-parameters>) <body>)

The resulting procedure is just as much a procedure as one that is created using define. The only difference is that it has not be associated with any name in the environment. And like any expression that has a procedure as its value, a labmda expression can be used in a combination or, more generally, in any context where we would normally use a procedure name.

Thus, our pi-sum procedure can be expressed without defining any auxiliary procedures as

(define (pi-sum a b)
    (sum (lambda (x) (/ 1.0 (* x (+ x 2))))
         a
         (lambda (x) (+ x 4))
         b))

Using let to create local variables

Another use of lambda is in creating local variables. We often need local variables in our procedures other than those that have been bound as formal parameters. For example, suppose we wish to compute the function

which can also be expressed as

We could use a lambda expression to specify an anonymous procedure for binding our local variables

(define (f x y)
    ((lambda (a b)
             (+ (* x (square a))
                (* y b)
                (* a b)))
     (+ 1 (* x y))
     (- 1 y)))

This construct is so useful that there is a special form called let to make its use more convenient. Using let, the procedure could be written as

(define (f x y)
    (let ((a (+ 1 (* x y)))
          (b (- 1 y)))
         (+ (* x (square a))
            (* y b)
            (* a b))))

The general form of a let expression is

(let ((<var1> <exp1>)
      (<var2> <exp2>)
      ...
      (<varn> <expn>))
     <body>)

The first past of the let expression is a list of name-expression pairs. The body of let is evaluated with these names bound as local variables. The way that this happens is that the let expression is interpreted as an alternative syntax for

((lambda (<var1> ... <varn>) <body>)
 <exp1>
 ...
 <expn>)

The let expression is simply syntactic sugar for the underlying lambda application. We can see from this equivalence that the scope of a variable specified by a let expression is the body of the let. This implies that:

Abstractions and first-class procedures

In general, programming languages impose restrictions on the ways in which computational elements can be elements can be manipulated. Elements with the fewest restrictions are said to have first-class status. Some of the “rights and privileges” of first-class elements are:

Lisp awards procedures full first-class status. This poses challenges for efficient implementation, but the resulting gain is expressive power is enormous.