6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 6.5.14 So damp out the oscillation So here is the type of this procedure, demonstrating that it is a new kind of higher order procedure 1 ambda《x (average x (f x )))) → number)÷( number> number) that is, this takes a procedure as input, and returns a new procedure as outpul Slide 6.5.15 so damp out the oscillation Does this really work? Well, let's just try it using our (define (average-damp f) substitution model. I am going to evaluate an average damp of (lambda (*) square on the value 5. Notice that the first subexpression of this expression is itself a compound expression, something we Check out the type: haven't seen before. By but our type discussion, this should be ( Dumber→ number)→( number number) right, since we expect that value of the subexpression to be a that is, this takes a procedure as input, and returns a nEw procedure as output! procedure. Indeed, if I substitute the value of square(which we .((average-damp square)10) know is a procedure but for convenience we will just use the .((lambda(x)(average x(square x)))10) rimitive name here)into the body of average-damp in place of .(average 10(square 10)) the formal parameter x, we just get the second expression Notice how this body is a lambda expression, but this is just what we need, as evaluating that lambda expression will give us a procedure In fact, we know by the substitution model that this second expression reduces to the body of the lambda, with the value 5 substituted for the formal parameter, leading to the third expression, and that now is simply a procedure applied to two numbers(since we know that square maps numbers to numbers), giving us what we expect Thus, by our substitution model, this works quite nicely, as average damp takes a procedure as input and produces an appropriate procedure as output which gives us a clean version of sqrt Slide 6.5.16 And this just brings us back to square roots. We can fix our (fixed-point problem by finding the fixed point of the average damp of our (lambda (y)(/x y)) original procedure The key things to notice are how average-damp cleanly e this to Herons algorithm in textbook-same process, but ideas intertwined with code isolates the problem of damping from the problem of fixed points, and how average-damp nicely satisfies the type contract for fixed point, that is, it takes a procedure as input and produces a procedure as output, exactly forming the type of input needed by fixed- point Why is this useful? Well compare this code to the algorithm in the textbook(or the one we talked about earlier). This is exactly the same process, but now the ideas underlying the process have been cleanly separated into appropriate computational pieces, a fixed point process and a damping process6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 6.5.14 So here is the type of this procedure, demonstrating that it is a new kind of higher order procedure. Slide 6.5.15 Does this really work? Well, let's just try it using our substitution model. I am going to evaluate an average damp of square on the value 5. Notice that the first subexpression of this expression is itself a compound expression, something we haven't seen before. By but our type discussion, this should be right, since we expect that value of the subexpression to be a procedure. Indeed, if I substitute the value of square (which we know is a procedure but for convenience we will just use the primitive name here) into the body of average-damp in place of the formal parameter x, we just get the second expression. Notice how this body is a lambda expression, but this is just what we need, as evaluating that lambda expression will give us a procedure. In fact, we know by the substitution model that this second expression reduces to the body of the lambda, with the value 5 substituted for the formal parameter, leading to the third expression, and that now is simply a procedure applied to two numbers (since we know that square maps numbers to numbers), giving us what we expect. Thus, by our substitution model, this works quite nicely, as average damp takes a procedure as input and produces an appropriate procedure as output. Slide 6.5.16 And this just brings us back to square roots. We can fix our problem by finding the fixed point of the average damp of our original procedure. The key things to notice are how average-damp cleanly isolates the problem of damping from the problem of fixed points, and how average-damp nicely satisfies the type contract for fixed point, that is, it takes a procedure as input, and produces a procedure as output, exactly forming the type of input needed by fixed-point. Why is this useful? Well compare this code to the algorithm in the textbook (or the one we talked about earlier). This is exactly the same process, but now the ideas underlying the process have been cleanly separated into appropriate computational pieces, a fixed point process and a damping process