6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 6.5.8 Finding fixed points of functions Here is a good way to find fixed points. Given a guess, evaluate quare root of x is defined by x=x/vx f of that guess, then f of the result, then f of that result, until we ss that is good enoug y=vx,then f()=y and such a y is called a fixed point of f. Given a guess x, let new guess by fix, Keep computing f of last guess. till close enough Slide 6.5.9 Finding fixed points of functions That has a familiar ring to it, as it sounds somewhat like what Squarerootof xis definedby/x=x/vx we did in the earlier lecture when we talked about square roots The procedure fixed-point has two parameters, a Thinkof as a transfomation/: y--thenif wecan finda procedure f and a guess. In the body of fixed-point y=vx, thenf(y)=y, andsucha yis calleda fixedpointof s a common way of finding fixe we use the auxiliary procedure try. This procedure takes a Keep computing f of last guess, till close enough guess as input, and checks to see if the value of the input Define(close?u v (<fabs(-uv)00001)) Define(fixed-poent t iguess procedure applied to that guess is close to guess, i.e. if it is a Define(try gl fixed point. If it is not, then we"try"again, using the value of lf (close?(1 ol g) f(guess)as our next guess Notice the nice recursive structure to try, which is itself a igher order procedure, since it finds fixed points for any procedure that maps numbers to numbers Using fixed points Slide 6.5.10 (fixed-point (lambda (x)(+1( 1x)))1)->1.6180 Given that I have captured the idea of a fixed point in a x=1+1/ s when x=(+√)/2 procedure, I can now use it as an abstraction. For example, the golden ratio is defined as that value x that is equal to 1 +1/x and thus by using fixed-point with the appropriate input procedure, I can compute that value. The point is that by capturing the idea of a fixed point, I can abstract away the details of the computation and just use the concept itself as a black box abstraction 1001 SICP6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 6.5.8 Here is a good way to find fixed points. Given a guess, evaluate f of that guess, then f of the result, then f of that result, until we get a guess that is good enough. Slide 6.5.9 That has a familiar ring to it, as it sounds somewhat like what we did in the earlier lecture when we talked about square roots. The procedure fixed-point has two parameters, a procedure f and a guess. In the body of fixed-point, we use the auxiliary procedure try. This procedure takes a guess as input, and checks to see if the value of the input procedure applied to that guess is close to guess, i.e. if it is a fixed point. If it is not, then we "try" again, using the value of f(guess) as our next guess. Notice the nice recursive structure to try, which is itself a higher order procedure, since it finds fixed points for any procedure that maps numbers to numbers. Slide 6.5.10 Given that I have captured the idea of a fixed point in a procedure, I can now use it as an abstraction. For example, the golden ratio is defined as that value x that is equal to 1 + 1/x, and thus by using fixed-point with the appropriate input procedure, I can compute that value. The point is that by capturing the idea of a fixed point, I can abstract away the details of the computation and just use the concept itself as a black box abstraction