Sunday, August 22, 2010

SICP 1.46: Iterative improvement

From SICP section 1.3.4 Procedures as Returned Values

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.

Alex Marandon said...

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.

Bill the Lizard said...

Alex,

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

Anonymous said...

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.

Mark said...

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*

Naomi Kyoto said...

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

Di Tian said...

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

Colin Dabritz said...

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