6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 6.5.1l But to get back to our square root idea, we can now easily Using fixed points compute square root, by using the concept of fixed points. In (fixed-point (lambda(x)(+ 1(1 x))) 1)-->1.6180 this case, we just find the fixed point of the procedure that maps .or=1+1/x whenx-a+ 5)/2 values of y to x/y. Notice how fixed- point takes as input a procedure and a number, and returns a number as value lambda(y)(/x y) capturing that higher order computational pattern Also notice how crisply we have captured the computation of square root. It is simply reduced to the concept of a fixed point of an appropriate function 6001S Using fixed points Slide 6.5.12 (fixed-point (lambda(x)+1(1 x)))1)-->1.6180 If we go ahead and use this procedure, we unfortunately or x=1+1/x when x=(+v5)/2 discover that while the definition captures the concept of a dein·( agEt x) square root, the actual computation doesn't quite do the right thing. Since we start the fixed point computation off with an 1 ambda红y)(/xy)) initial value of 1, it's next guess will be 2, as you can see by looking back at the code for try. And thus it's next guess will Unfortunately if we try(qrt 2), this oscillates between 1, 2,, 2 be 1, and the process will simply oscillate between these two values 6001 SICP Slide 6.5.13 So damp out the oscillation So I have a problem, but it is not a coding problem, rather it is a (define (average-damp f) conceptual problem. Since I have an undamped oscillation here. (lambda (x I need to damp it down, similar to what you've seen in physics average x (E x)))) courses One nice way to damp down an oscillation is to take the function that is oscillating, and average it with its input. In other words, for any function f, we can get a new function that is the average of an input value x and f applied to that input value Here is a procedure that captures this idea, but notice its form. It takes as input a procedure that maps numbers to numbers, much lke what we have seen before. But it produ procedure! Thus, average-damp produces a function that can be applied to any input value6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 6.5.11 But to get back to our square root idea, we can now easily compute square root, by using the concept of fixed points. In this case, we just find the fixed point of the procedure that maps values of y to x/y. Notice how fixed-point takes as input a procedure and a number, and returns a number as value, capturing that higher order computational pattern. Also notice how crisply we have captured the computation of square root. It is simply reduced to the concept of a fixed point of an appropriate function. Slide 6.5.12 If we go ahead and use this procedure, we unfortunately discover that while the definition captures the concept of a square root, the actual computation doesn't quite do the right thing. Since we start the fixed point computation off with an initial value of 1, it's next guess will be 2, as you can see by looking back at the code for try. And thus it's next guess will be 1, and the process will simply oscillate between these two values. Slide 6.5.13 So I have a problem, but it is not a coding problem, rather it is a conceptual problem. Since I have an undamped oscillation here, I need to damp it down, similar to what you've seen in physics courses. One nice way to damp down an oscillation is to take the function that is oscillating, and average it with its input. In other words, for any function f, we can get a new function that is the average of an input value x and f applied to that input value. Here is a procedure that captures this idea, but notice its form. It takes as input a procedure that maps numbers to numbers, much like what we have seen before. But it produces as output a procedure! Thus, average-damp produces a function that can be applied to any input value