CS 22

Clab 7: Invariants, Divide and Conquer; Functions as first-class objects

At some point, I'll say a few words about invariants, Divide and Conquer, and Functions as first-class objects. When I am not talking work on the following stuff.

Down at the bottom, there is a solution to the exercise subst requested in Clab6.

Review the material in text on pp. 62-65 on lambda and let http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-12.html#%_sec_1.3.2 . From r5rs in on-line help in drscheme, read about lambda and let (the binding construct meaning -- shun the sinful iteration material) Make sure you understand the examples illustrated and how the values were obtained. Ask questions if you have them.

Now enter the search procedure given on page 67.

(define (search f neg-point pos-point) (let ((midpoint (average neg-point pos-point))) (if (close-enough? neg-point pos-point) midpoint (let ((test-value (f midpoint))) (cond ((positive? test-value) (search f neg-point midpoint)) ((negative? test-value) (search f midpoint pos-point)) (else midpoint)))))) (define (close-enough? x y) (< (abs (- x y)) 0.001)) (define average (lambda (x y) (/ (+ x y) 2))) (define cube (lambda (x) (* x x x))) Make sure you understand what it is doing. You will need to define average and close-enough? if you have not done so already. The function cube that we have used before has a root at 0. Test search by evaluating: (search cube -1 2.0). This is an example of a divide and conquer algorithm. Divide and conquer is a general algorithm design technique. Using this technique, one tries to find a way to divide a problem in half (approximately) and then solve just half a problem (or even two halves sometimes, hoping that solving two halves will be easier than solving one whole). Turn trace on search and average and evaluate (search cube -1 2.0) again. Make sure you see how the algorithm is dividing the region where the root may be in half each pass through. The number of thousandths (.001s) between -1 and 2 is 3000 so you can se that the complexity of this algorithm is logarithmic in the size of the interval divided by the accuracy desired.

x^2-4 is a function with root at 2. Without naming this function, we can express it as (lambda (x) (- (square x) 4)). Try search on this function by evaluating: (search (lambda (x) (- (square x) 4)) 0 3.0). Check that you got the root.

1-x is the equation of the straight line that passes through the the points (0, 1) and (3, -2). We can express it as (lambda (x) (- 1 x)). Find the root of 1 -x by evaluating: (search (lambda (x) (- 1 x)) 0 3.0). You should have gotten an answer. BUT--Don't bet your life on the answer you got. What is the right answer? Did you get the right answer? Why not? What do you have to do to get the right answer? Now read page 67 again and then page 68.

Now carefully review the material on pages 73-75. http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-12.html#%_sec_1.3.4

Define deriv as in the text . Note that deriv is a procedure that takes one argument, a function, and returns a function that is an approximation to the derivative of the first argument. deriv expects to be executed in an environment where dx is defined to be a small positive real number (e.g. 0.00001). You should have the functions square and cube defined from before. If not, define them now. Define dx to be 0.001. Now evaluate

(define Dsquare (deriv square)) Dsquare is a function that is an approximation to the derivative of x^2. That is Dsquare is a function that should be very close to the function 2x. Try evaluating Dsquare on some values and check that it does behave like an approximation to the function 2x. Now evaluate (define g (deriv cube)) g should be an approximation to the function 3x^2 which is the derivative of x^3. Check it on a few values.

The composition of 2 functions f and g, sometimes written fg is defined by fg(x) = f(g(x)). That is first apply g to x, then apply f to the result. For example if f(x) = x^3 and g(x) = 1 + x, then fg(x) = (1 + x)^3. We want to define a procedure that takes two functions as arguments and returns the composition of those two argument functions. Here is a start:

;;;given the 2 functions f and g, compose returns the composition fg (define (compose f g) (...you fill in this part) ;;; for convenience we will define the function 1+ which increments ;;; its argument by one. (define 1+ (lambda (x) (+ 1 x))) For example: > (1+ 7) 8 After you have successfully defined compose, you should be able to evaluate: (define h (compose cube 1+)) If you did it right h should be the function h(x) = (1 + x)^3.

Try it and check h for a few values. Try some other compositions.

Ask any questions you may have.

Solution to subst from clab06. There are other correct solutions.

;; subst returns a list with all occurrences of old ;; replaced with new in list l: (define subst (lambda (new old l) (cond ((null? l) '()) ((equal? (car l) old) (cons new (subst new old (cdr l)))) (else (cons (car l) (subst new old (cdr l)))))))