1.3 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. (Section 1.3)

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. (Section 1.3)

• Procedures operating 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.

# 1.3.1 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. (Section 1.3.1)

# 1.3.2 Constructing Procedures Using Lambda⁠

lambda creates anonymous procedures. They are just like the procedures created 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 the arguments (the evaluated operands). The name comes from the λ-calculus, a formal system invented by Alonzo Church.

# Using let to create local variables

We often need local variables in addition to the 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.

# 1.3.3 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 the half-interval method

• The half-interval method : a simple but powerful technique for solving $f(x) = 0\htmlClass{math-punctuation}{\text{.}}$
• Given $f(a) < 0 < f(b)\htmlClass{math-punctuation}{\text{,}}$ there must be at least one zero between $a$ and $b\htmlClass{math-punctuation}{\text{.}}$
• To narrow it down, we let $x$ be the average of $a$ and $b\htmlClass{math-punctuation}{\text{,}}$ 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\htmlClass{math-punctuation}{\text{:}}$

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

# Finding fixed points of functions

• A number $x$ is a fixed point of a function if $f(x) = x\htmlClass{math-punctuation}{\text{.}}$
• 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.7390822985224023

# 1.3.4 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\htmlClass{math-punctuation}{\text{:}}$

((average-damp square) 10)
→ 55

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

# Newton’s method

The square-root procedure we wrote earlier was a special case of Newton’s method. Given a function $f(x)\htmlClass{math-punctuation}{\text{,}}$ the solution to $f(x) = 0$ is given by the fixed point of

$$x ↦ x - \frac{f(x)}{f'(x)}.$$

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:

$$f'(x) = \frac{f(x+dx) - f(x)}{dx}.$$

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 methods 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 may be 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.