Higher-Order Procedures

This is a long-winded set of notes on section 1.3.1. I've tried to make it through SICP before, and this section is the place I usually stopped. This time, I'm pushing through until I make it. I may belabor points you find obvious, but I needed to make it excruciatingly explicit to understand it thoroughly.

Consider how similar the following three procedures are.

Sum integers from a to b

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

Sum the cube of integers from a to b

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

Estimate π with the series

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

Each of these procedures is a specific instance of a more general idea of summation.

For the first procedure, sum-integers, the function is f(x) = x, and the argument x increase by 1 each term.

For the second procedure, sub-cubes, the function is f(x) = x³. The argument x increase by 1 each term here too.

Finally, the series for ^π⁄₈. The function is a bit more complicated.

Which means the terms increase by a + 4

This particular sum also assumes we are starting with a = 1 and b is even.

So, for each summation we have

• A function f that we apply to each term
• A method for finding each subsequent argument x to supply our function f.

Saying the same thing a different way: to sum a series

We need a procedure that, given x₁, can calculate x₂. Given x₂, it calculates x₃, and so on. We feed the results of that procedure into a second procedure that calculates our function f(x).

Now you can see how you might generalize the original three procedures above by having two additional procedures, term and next. term calculates the function and gives you the numerical result you will be adding. next advances the series and gets the next value of x, which f will operate on.

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

In the case of sum-integers, the helper procedures are pretty easy. We saw above that f(x) = x, so we need an identity procedure

(define (identity x) x)

And we see that x should increase by on each term, so we make an increment procedure.

(define (inc x) (+ 1 x))

So defining sum-integers in terms of sum we have

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

For sum-cubes, f(x) = x³, and x increases by one each term. Since we already have cube and inc

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

Finally, our estimate for π/8. I define two new procedures for term and next, both of which are straightforward implementations of the observations made above about the function f(x) and how the function argument increases by x + 4.

(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))

The examples above provided specific implementations for the function f(x), which is always the same for every procedure call. We can design a procedure to take a function as an argument, so the function f(x) isn't hard-coded into the implementation. Suppose we want to estimate a definite integral with the following sum.

This method for estimating definite integrals is valid for lots of functions: x², x³, sin(x), log(x) etc. We can define our procedure to take a procedure as an argument. That procedure argument calculates some function f(x). This way, our procedure can calculate the definite integral for any function expressed as a procedure.

We advance to the next x by adding dx each time. The procedure for this estimate is

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

Another notable difference is that the first x to operate on is (a + ^dx⁄₂). Previous procedures started at x = a.