Exercise 1.46 asks us to combine several of the concepts we've learned throughout the first chapter of SICP into a procedure that generalizes the iterative improvement strategy. Iterative improvement is the process where we start with an initial guess, test if the guess is good enough, then improve the guess and start the process over again with the new guess. Our

`iterative-improve`

procedure will take two procedures as arguments and return a procedure as its value. The first argument will define a method for telling whether a guess is good enough, and the second will define a method for improving a guess. The returned procedure will take a guess as its argument and will keep improving that guess until it is good enough. Finally, we will rewrite the `sqrt`

procedure from section 1.1.7 and the `fixed-point`

procedure from section 1.3.3 using `iterative-improve`

.A good starting point is to take a look at the original versions of the two procedures mentioned in the exercise and see what they have in common.

`; sqrt procedure and sub-procedures from SICP 1.1.7`

(define (sqrt x)

(sqrt-iter 1.0 x))

(define (sqrt-iter guess x)

(if (good-enough? guess x)

guess

(sqrt-iter (improve guess x)

x)))

(define (improve guess x)

(average guess (/ x guess)))

(define (average x y)

(/ (+ x y) 2))

(define (good-enough? guess x)

(< (abs (- (square guess) x)) 0.001))

(define (square x) (* x x))

; fixed-point procedure from SICP 1.3.3

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

Besides the similarities that you might expect from the description in the exercise, these two procedures also both make use of helper functions to perform the required iteration,

`sqrt-iter`

and `try`

. We'll need a helper function in `iterative-improve`

as well, and this will be the function that will be returned by the procedure. (We can't use a lambda to define the returned procedure like past exercises in this section because the returned procedure in this case needs to call itself recursively. To do that, it needs a name.)`(define (iterative-improve good-enough? improve)`

(define (iter-imp guess)

(if (good-enough? guess)

guess

(iter-imp (improve guess))))

iter-imp)

The solution doesn't require a lot of explanation. We define the procedure

`iter-imp`

that takes a guess as its only parameter. If the guess is good enough (as judged by the function passed in as the first argument to `iterative-improve`

) we just return the guess. If not, we call `iter-imp`

again with a new guess that we get by calling the `improve`

function that was passed in as the second parameter to `iterative-improve`

.Let's see how we can redefine

`sqrt`

in terms of `iterative-improve`

.`(define (sqrt x)`

((iterative-improve (lambda (guess)

(< (abs (- (square guess) x))

0.001))

(lambda (guess)

(average guess (/ x guess))))

1.0))

Here I've taken the implementation of the procedures for

`good-enough?`

and `improve`

almost exactly from the earlier `sqrt`

solution, but I've recast them as lambdas. Since `iterative-improve`

returns a procedure, we give it an initial guess of 1.0 to start things off. This implementation of `sqrt`

works much the same as the original.`> (sqrt 4)`

2.0000000929222947

> (sqrt 16)

4.000000636692939

> (sqrt 100)

10.000000000139897

> (sqrt 1000)

31.622782450701045

The reimplementation of

`fixed-point`

is very similar.`(define (fixed-point f first-guess)`

((iterative-improve (lambda (guess)

(< (abs (- (f guess) guess))

0.00001))

(lambda (guess)

(f guess)))

first-guess))

The

`good-enough?`

procedures for `sqrt`

and `fixed-point`

are nearly identical. The `improve`

procedure for `fixed-point`

is simpler though, because to improve a guess when finding a fixed point, you just apply the function whose fixed point you're trying to find to the guess.To test the new

`fixed-point`

procedure, we can use the procedure we defined in exercise 1.35 to approximate the golden ratio.`> (fixed-point (lambda (x) (+ 1 (/ 1 x))) 2.0)`

1.6180371352785146

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

## 7 comments:

In your fixed-point, why do why pass (lambda (x) (f x)) as the second argument to iterative-improve? It seems you could just pass f directly.

Alex,

Yes, that works. This was a case of me over thinking things slightly. Thanks for pointing it out.

You can indeed implement iterative-improve with lambda, and without the use of a helper function. Just:

change your 2nd line to

(lambda (guess)

change your 5th line to

((iterative-improve good-enough? improve) (improve guess)))))

and delete the last line.

Thanks a lot for these posts; they've helped me many times now.

I too recursively called iterative-improve in the definition of iterative-improve.

That being said i like Bill's version better. I tried to clean mine up with a let but scheme doesn't let me use the symbol created in the let in the body of the expression of the let.

For some reason I never thought of called define *sigh*

You say:We can't use a lambda to define the returned procedure like past exercises in this section because the returned procedure in this case needs to call itself recursively. To do that, it needs a name.This is just not true! You can use our trusty U-combinator here ^.^

In case the code below is formatted poorly, you can view a full code paste here

(define (iterative-improve good-enough? improve first-guess)

((lambda (f) (f f first-guess))

(lambda (f guess)

(if (good-enough? guess) guess (f f (improve guess))))))

(define (iterative-sqrt x)

(iterative-improve (lambda (y) (< (abs (- (square y) x)) 0.001))

(lambda (y) (average y (/ x y)))

1.0))

(iterative-sqrt 100) ; 10.000000000139897

You say: We can't use a lambda to define the returned procedure like past exercises in this section because the returned procedure in this case needs to call itself recursively. To do that, it needs a name.

This is just not true! You can use lambda here ^.^

; input: a procedure for telling whether a guess is good enough

; a procedure for improving a guess

; output: a procedure that takes a guess as argument and keeps improving the guess until it is good enough

(define (iterative-improve good-enough? improve-guess)

(lambda (guess) ; returns a procedure that takes one argument -- guess

(if (good-enough? guess)

guess ; if guess is good enough, return guess, of course

((iterative-improve good-enough? improve-guess) (improve-guess guess))))) ; otherwise, use improved-guess for next guess

; sqrt procedure in terms of iterative-improve

(define (sqrt x)

((iterative-improve (lambda (guess) (< (abs (- (* guess guess) x)) 0.001))

(lambda (guess) (/ (+ guess (/ x guess)) 2))) 1.0))

(sqrt 100) ; 10.000000000139897

I ended up taking another approach.

The problem mentioned was that without a name the function could not both be returned anonymously and call itself by name recursively.

I split the iteration and initial invocation parts, and gave the iteration a local name using a define. You can then put the initial invocation in the lambda.

(define (iterative-improve good-enough? improve-guess)

(define (iter guess)

(if (good-enough? guess)

guess

(iter (improve-guess guess))))

(lambda (initial-guess)(iter initial-guess)))

Post a Comment