Formulating Abstractions with Higher-Order Procedures

We have seen that procedures are, in effect, abstractions that describe compound operations on numbers independent of the particular numbers.

One of the things we should demand from a powerful programming language is the ability to build abstractions by assigning names to common patterns and then to work in terms of the abstractions directly.

• Procedures operations on numbers are powerful, but we can go further.
• To abstract more general programming patterns, we need to write procedures that take other procedures as arguments and return new procedures.
• These are called higher-order procedures.

Procedures as Arguments

Procedures that compute a sum all look the same:

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

This is a useful abstraction, just as sigma notation is useful in math because the summation of a series is so common.

The power of sigma notation is that it allows mathematicians to deal with the concept of summation itself rather than only with particular sums.

Mathematicians long ago created an abstraction for summations:

We can do the same in Scheme using a higher-order procedure:

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

(define (inc n) (+ n 1))
(define (sum-cubes a b) (sum cube a inc b))
(sum-cubes 1 10) => 3025

(define (identity x) x)
(define (sum-integers a b) (sum identity a inc b))
(sum-integers 1 10) => 55

(define (pi-sum a b)
  (define (pi-term x) (/ 1.0 (* x (+ x 2))))
  (define (pi-next x) (+ x 4))
  (sum pi-term a pi-next b))
(* 8 (pi-sum 1 1000)) ~> 3.139592655589783

The definite integral of a function \(f\) between 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

Exercises: 1.29, 1.30, 1.31, 1.32, 1.33

Constructing Procedures Using Lambda

lambda creates anonymous procedures. They are just like the procedures create by define, but without a name: (lambda (formal-parameters) body).

A lambda expression can be used as the operand in a combination. It will be evaluated to a procedure and applied to arguments (the evaluated operands). The name comes from the \(\lambda\)-calculus, a formal system invented by Alonzo Church.

Using let to create local variables

We often need local variables in addition to formal parameters. We can do this with a lambda expression that takes the local variables as arguments, but this is so common that there is a special form let to make it easier.

The general form of a let-expression is:

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

This is just syntactic sugar for:

((lambda (var1 var2 ... varn)
   body)
 exp1
 exp2
 ...
 expn)

• The scope of a variable in a let-expression is the body. This allows variables to be bound as locally as possible.
• The variables in the let-expression are parallel and independent. They cannot refer to each other, and their order does not matter.
• You can use let-expressions instead of internal definitions.

Exercises: 1.34

Procedures as General Methods

So far, we have seen:

• Compound procedures that abstract patterns of numerical operators (mathematical functions), independent of the particular numbers.
• Higher-order procedures that express a more powerful kind of abstraction, independent of the procedures involved.

Now we will take it a bit further.

Finding roots of equations by half-interval method

• The half-interval method: a simple but powerful technique for solving \(f(x) = 0\)
• Given \(f(a) < 0 < f(b)\), there must be at least one zero between \(a\) and \(b\).
• To narrow it down, we let \(x\) be the average of \(a\) and \(b\), and then replace either the left bound or the right bound with it.

(define (search f neg-point pos-point)
  (let ((midpoint (average neg-point pos-point)))
    (if (close-enough? neg-point pos-point)
        midpoint
        (let ((test-value (f midpoint)))
          (cond ((positive? test-value)
                 (search f neg-point midpoint))
                ((negative? test-value)
                 (search f midpoint pos-point))
                (else midpoint))))))

(define (close-enough? x y)
  (< (abs (- x y)) 0.001))

(define (half-interval-method f a b)
  (let ((a-value (f a))
        (b-value (f b)))
    (cond ((and (negative? a-value) (positive? b-value))
           (search f a b))
          ((and (negative? b-value) (positive? a-value))
           (search f b a))
          (else
           (error "values are not of opposite sign" a b)))))

We can use half-interval-method to approximate \(\pi\) as a root of \(\sin x = 0\):

(half-interval-method sin 2.0 4.0)
-> 3.14111328125

Finding fixed points of functions

• A number \(x\) is fixed point of a function if \(f(x) = x\).
• In some cases, repeatedly applying the function to an arbitrary initial guess will converge on the fixed point.
• The procedure we made earlier for finding square roots is actually a special case of the fixed point procedure.

(define tolerance 0.00001)
(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

We can use fixed-point to approximate the fixed point of the cosine function:

(fixed-point cos 1.0)
-> 0.73908222985224023

Exercises: 1.35, 1.36, 1.37, 1.38, 1.39

Procedures as Returned Values

Passing procedures as arguments gives us expressive power. Returning procedures from functions gives us even more. For example, we can write a procedure that creates a new procedure with average damping:

(define (average-damp f)
  (lambda (x) (average x (f x))))

If we use average-damp on square, we get a procedure that calculates the sum of the numbers from 1 to \(n\):

((average-damp square) 10) 
-> 55 

(+ 1 2 3 4 5 6 7 8 9 10) 
-> 55

In general, there are many ways to formulate a process as a procedure. Experienced programmers know how to choose procedural formulations that are particularly perspicuous, and where useful elements of the process are exposed as separate entities that can be reused in other applications.

Newton's method

The square-root procedure we wrote earlier was a special case of Newton's method. Given a function \(f(x)\), the solution to \(f(x) = 0\) is given by the fixed point of

Newton's method converges very quickly—much faster than the half-interval method in favorable cases. We need a procedure to transform a function into its derivative (a new procedure). We can use a small \(dx\) for this:

This translates to the following procedure;

(define (deriv f)
  (lambda (x) (/ (- (f (+ x dx)) (f x)) dx)))

Now we can do things like this:

(define (cube x) (* x x x))
(define dx 0.00001)
((deriv cube) 5)
-> 75.00014999664018

Abstractions and first-class procedures

• Compound procedures let us express general method of computing as explicit elements in our programming language.
• Higher-order procedures let us manipulate methods to create further abstractions.
• We should always be on the lookout for underlying abstractions that can be brought out and generalized. But this doesn't mean we should always program in the most abstract form possible; there is a level appropriate to each task.
• Elements with the fewest restrictions are first-class:
  • They may be named by variables.
  • They may be passed as arguments to procedures.
  • They maybe returned as the results of procedures.
  • They may be included in data structures.
• In Lisp, procedures have first-class status. This gives us an enormous gain in expressive power.

Exercises: 1.40, 1.41, 1.42, 1.43, 1.44, 1.45, 1.46