CS 37

Clab 5: Invariants, exponentiation, functions as first-class objects

Here are some solutions to last clabs work. Make sure you understand them thoroughly. If not, ask me about them.

;;;some test lists (define a '(cat dog amt)) (define b '(horse dog)) (define d '(horse dog cat ant dog x y x z)) ;;; memb? returns #t if el is an element of list lst ;;; returns #f otherwise. Assume lst is a list. (define (memb? el lst) (cond ((null? lst) #f) ((equal? el (car lst)) #t) (else (memb? el (cdr lst))))) ;; remove-first returns a list with the first occurrence of ;; sym removed from list l: (define remove-first (lambda (sym l) (cond ((null? l) '()) ((equal? (car l) sym) (cdr l)) (else (cons (car l) (remove-first sym (cdr l))))))) Notice how we cons up a solution after cdring down one of the parameters. This kind of structure is common to many list processing solutions.

Here are some more solutions

;; remove-all returns a list with all occurrences of sym ;; removed from the list l (define remove-all (lambda (sym l) (cond ((null? l) '()) ((equal? (car l) sym) (remove-all sym (cdr l))) (else (cons (car l) (remove-all sym (cdr l))))))) The above generates a recursive process to solve the substition remove-all problem. You can prove it is correct by doing mathematical induction on the length of the list. Here next is an iterative solution to the remove-all problem. The comment before remove-all-iter is called an invariant. We design remove-all-iter to maintain the truth of the invariant in terms of the current values of the parameters mentioned at any invocation of remove-all-iter. We can use this to prove the correctness of remove-all-iter. ;; remove-all-i returns a list with all occurrences of sym ;; removed from the list l (define remove-all-i (lambda (sym l) (remove-all-iter sym '() l))) ;; remove-all-iter returns a list that consists appending ;; the list partdonelis to the list that results from ;; removing all occurences of sym from the list todolis. ;; inv: if called by remove-all-i as above, appending ;; partdonelis to the list that results from removing all ;; occurences of sym from todolis yields a new list that ;; is the same as l with all occurences of sym removed (define remove-all-iter (lambda (sym partdonelis todolis) (cond ((null? todolis) partdonelis) ((equal? sym (car todolis)) (remove-all-iter sym partdonelis (cdr todolis))) (else (remove-all-iter sym (append partdonelis (list (car todolis))) (cdr todolis))))))
Now work through the 3 different exponential procedures given on pages 44-46. Use trace on them (you may want to trace * also) to help you understand what they are doing. Make sure you understand how each of them works and that (1) the first one requires O(n) time and space, (2) the second one requires O(n) time and O(1) space, and (3) the third one, fast-exp, requires O(log n) time and space. Ask questions if you have them.

What is a good invariant for expt-iter?

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

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

Define deriv as in the text on p. 74.

(define (deriv g) (lambda (x) (/ (- (g (+ x dx)) (g x)) dx))) (define dx .00001) (define square (lambda (x) (* x x))) (define cube (lambda (x) (* x x x))) 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.00001. 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.