1.3.5 · Procedures as returned values

A procedure can build the next procedure.

Composition, repetition, and average damping treat behavior as data, so one procedure receives other procedures and returns a new transformation.

Guiding question

What becomes possible when the result of a procedure call is itself a procedure?

Read a lambda expression as a procedure value returned by another procedure
Distinguish constructing a transformation from applying the transformation
Compose procedures in an order that remains visible in the source
Build repeated behavior without copying the operation body
Recognize average damping as a procedure-producing transformation

compose receives two procedure values and returns a new procedure. Calling compose does not yet square or increment a number; it builds a transformation that remembers f and g. Only a later application supplies x, evaluates g on x, and then applies f to that result. repeated uses the same idea recursively, returning the identity transformation at zero and one more composition at every larger count.

average-damp also returns a procedure. The returned transformation evaluates the original f at x and averages that result with x. For the square-root transformation y ↦ 16/y, a guess of 2 becomes 5 while the fixed point 4 remains 4. The procedure constructor owns the reusable method; the supplied f determines the behavior being transformed.

SICP code356 of 1,048,576 UTF-8 bytes

(begin
  (define (compose f g)
    (lambda (x) (f (g x))))
  (define (repeated f count)
    (if (= count 0)
        (lambda (x) x)
        (compose f (repeated f (- count 1)))))
  (define (increment x) (+ x 1))
  (define (square x) (* x x))
  (list ((compose square increment) 6)
        ((compose increment square) 6)
        ((repeated increment 5) 10)))

Examples

Result—

Output: —
Value: —
Diagnostic: —

Execution trace0 / 0 events

Expected result

The composition program returns (49 37 15). The average-damping program returns (5 4 21).

Trace focus

Separate the calls that construct returned procedures from the later calls that apply them. In the composition example, compare square after increment with increment after square. In the damping example, find the call to the captured f before the average is formed. The trace records the call order and result of each finite application.

Try it yourself

Change the program and compare the result.

Define twice only in terms of compose, then return both ((twice increment) 10) and ((twice square) 3). Predict the two values before running the program.

Show hint

twice should return a procedure equivalent to composing f with itself; the expected values are 12 and 81.

Complete this lesson

0 of 18 lessons complete in this chapter0%