A procedure can build the next procedure.
Composition, repetition, and average damping treat behavior as data: one procedure receives other procedures and returns a new transformation that can be named, passed, and applied later.
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.
(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)))- Output
- —
- Value
- —
- Diagnostic
- —
The composition program returns (49 37 15). The average-damping program returns (5 4 21).
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 shows these finite applications, not a general proof that two transformations are equivalent.
Change the program before you read the hint.
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 one hint
twice should return a procedure equivalent to composing f with itself; the expected values are 12 and 81.