## **Note: this wiki is now retired and will no longer be updated!**

**The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.**

# SICP exercise 1.44

## Problem

The idea of smoothing a function is an important concept in signal processing. If *f* is a
function and *dx* is some small number, then the smoothed version of *f* is the function whose value at a point
*x* is the average of *f*(*x* - *dx*), *f*(*x*), and *f*(*x* + *dx*). Write a procedure `smooth` that takes as input a procedure
that computes *f* and returns a procedure that computes the smoothed *f*. It is sometimes valuable to
repeatedly smooth a function (that is, smooth the smoothed function, and so on) to obtained the *n-fold smoothed function*. Show how to generate the *n-fold* smoothed function of any given function using `smooth` and `repeated` from exercise 1.43.

## Solution

The implementation of `smooth` is straightforward; it's just a procedure that returns a procedure that calculates the average of *f*(*x* - *dx*), *f*(*x*), and *f*(*x* + *dx*).

(define dx 0.00001) (define (smooth f) (define (ave a b c) (/ (+ a b c) 3)) (lambda (x) (ave (f (- x dx)) (f x) (f (+ x dx)))))

Let's test it with an impulse function, i.e, a function which is
zero for all input values except exactly one input value *a*, where it is non-zero. This
`impulse-maker` procedure returns a procedure whose value is `y` at input
value `a`, and zero everywhere else:

(define (impulse-maker a y) (lambda (x) (if (= x a) y 0)))

Here's an impulse function whose value is 6 at *x*=0:

(define my-impulse-function (impulse-maker 0 6))

Test it:

(my-impulse-function -1)

*Output:*

`
`

0

(my-impulse-function 0)

*Output:*

`
`

6

(my-impulse-function (+ 0 dx))

*Output:*

`
`

0

Now let's smooth it at *x*=0: we expect this combination to have the
value 2, as (0 + 6 + 0)/3 = 2.

((smooth my-impulse-function) 0)

*Output:*

`
`

2

Good.

Successive smoothings should gradually reduce the impulse function to a smoothed "hump" where the largest value of the smoothed function (at x=0) gradually converges to zero. Here's how we apply those successive smoothings by hand. The results shown are from Chicken Scheme 3.1 on a MacBook Pro running Mac OS X 10.5.

((smooth (smooth my-impulse-function)) 0)

*Output:*

`
`

2

((smooth (smooth (smooth my-impulse-function))) 0)

*Output:*

`
`

1.55555555555556

((smooth (smooth (smooth (smooth my-impulse-function)))) 0)

*Output:*

`
`

1.40740740740741

((smooth (smooth (smooth (smooth (smooth my-impulse-function))))) 0)

*Output:*

`
`

1.25925925925926

The exercise asks for a procedure which implements an n-fold smoothing function. This procedure
should return another procedure that calculates the n-fold smoothed function of any
given input function. This is just the composition of *s* and *f* that
results in <math>s(s(s\cdots(s(f))))</math>, where *s* is the smoothing function,
and it occurs *n* times. We can use `repeated` from the exercise 1.43 to
implement it:

(define (compose f g) (lambda (x) (f (g x)))) (define (inc x) (+ x 1)) (define (repeated f n) (define (repeated-iter i result) (if (= i n) result (repeated-iter (inc i) (compose f result)))) (repeated-iter 1 f))

Note that the n-fold smoothing function generator should return a
**procedure**, not a numeric value, where the function looks like
`(lambda (x) (s(s(s...(s(f))))) x)`, per the constructed-by-hand examples
above. What we need to do is to use the `compose` procedure to compose multiple
occurrences of smooth, *n* times. We can use `repeated` for this.
Then we apply the result of these *n* compositions of
`smooth` to the procedure that calculates the function we wish to smooth. **That** resulting procedure can then be
applied to a numerical argument when we want to evaluate the
smoothed function at that argument.

(define (n-fold-smooth f n) ((repeated smooth n) f))

`n-fold-smooth` first composes n `smooth`s, creating a procedure which, when expanded,
looks like

(lambda (x) (smooth (smooth (smooth... (smooth x)))))

It then
applies that procedure to `f` to produce another procedure which expands to

(lambda (x) ((smooth (smooth (smooth... (smooth f)))) x))

Now let's test our generator. We should get the same answers that we got with our constructed-by-hand examples:

((n-fold-smooth my-impulse-function 1) 0)

*Output:*

`
`

2

((n-fold-smooth my-impulse-function 2) 0)

*Output:*

`
`

2

((n-fold-smooth my-impulse-function 3) 0)

*Output:*

`
`

1.55555555555556

((n-fold-smooth my-impulse-function 4) 0)

*Output:*

`
`

1.40740740740741

((n-fold-smooth my-impulse-function 5) 0)

*Output:*

`
`

1.25925925925926

Note that in this exercise, we used `compose` not to create a
composition of procedures which take numeric arguments, as we did in
exercise 1.43 with the `square` procedure; but rather to create a
composition of procedures which take **procedure** arguments. The
same method of composition works for both types of procedures!