Com S 227 --- Introduction to Computer Programming HOMEWORK 5: Locally Defined Procedures (File $Date: 1993/10/20 18:42:35 $) Due: (((1-7 8-14) (Oct. 20)) ((17-20) (Oct. 22)) ((21-22 29) (Oct 27))) In this homework you will learn how to use let and letrec, and see another example of abstract data types: polynomials. Let and letrec help one write programs that are more concise, by allowing one to make local definitions and abbreviations without flooding the global namespace with new names. Polynomials are used to explain binary arithmetic, and conversions from one number system to another. All the directions from homework 2 apply to this homework. In particular, remember to hand in labeled printouts for procedures, and transcripts showing your testing. We highly recommend that you put each Scheme program in a separate file, and when making a transcript use the Scheme procedure ``load'' to read that file in to the Scheme interpreter. SECTION 5.2, LET AND LETREC 1. (4 points) When should one use ``let'' in a program? For problems 2, 3, and 4 below you are to do the following: (i) write the local environments for each let expression, (ii) draw a smooth arrow (--->) from each variable use to where it is bound (i.e., the parameter) in a surrounding lambda or let expression, (iii) draw a squiggly arrow (~~~>) from each such parameter to the value to which it is bound, and For example, consider the expression (let ((a 7)) (let ((doit (lambda (b) (list a b)))) (let ((a 102) (b 29)) (doit (+ a b))))) For this example, the answer would look something like the following. (Please make an allowance for the crude drawings, you should do parts (i), (ii), and (iii) by hand.) (i) Environment 1 (parent Environment 0): a ~~~> [7] Environment 2 (parent Environment 1): doit ~~~> [Procedure | (b) | (list a b) | Environment 1] Environment 3 (parent Environment 2): a ~~~> [102] b ~~~> [29] (ii) and (iii) |------------------------------ v | (let ((a ~~~> 7)) | ~~~~~~~~~|~~~~~~~~~~ ~ | ~ (let ((doit ~~~> (lambda (b) (list a b)))) ~ ^ | ~ |----------- ~ (let ((a ~~~> 102) ~ -----^ ~ | ~ | (b ~~~> 29)) ~ | ^------ ~ |-------- | ~ \ | ~ (doit (+ a b))))) ~ ^^^^^ ~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 2. (0 points; suggested practice) Do this for the examples in exercise 5.1. 3. (7 points; basic) The directions for this problem are above. (Incidentally, the following expression calculates the sum of the squares of the numbers from 1 to 10.) (let ((n 10)) (let ((n-squared (* n n))) (let ((n-cubed (* n n-squared))) (+ (/ n-cubed 3) (/ n-squared 2) (/ n 6))))) 4. (15 points; basic) The directions for this problem are above. (let ((kmize (lambda (y) (let ((num (car y)) (unit (cadr y))) (let ((conversion-factor (cond ((eq? unit 'miles) 1.609344) ((eq? unit 'feet) 3.048e4) ((eq? unit 'inches) 2.54e5)))) (list (* conversion-factor num) 'kilometers)))))) (let ((unit (list 5 'miles))) (list unit 'is (kmize unit)))) 5. (5 points) For this problem, you are to translate from lambda to let. First we present an example. Our example expression: ((lambda (x) ;; example ((lambda (g) ((lambda (x) (list x (g (+ x 1)))) 3)) (lambda (y) (list y x)))) 100) would be translated into (let ((x 100)) ;; example answer (let ((g (lambda (y) (list y x)))) (let ((x 3)) (list x (g (+ x 1)))))) Note that both expressions have the same result. You are to translate the following expression and replace each lambda by a let so that the value computed is the same. ((lambda (num) ;; this one's for you to do ((lambda (a b) (list a b num)) 1 33.0)) 6.2) 6. (5 points) In this problem you will do the opposite of the previous problem. That is, you are to replace each use of let by lambda in the following expression. Your answer should be an expression that computes the same value as the one below. (let ((n 10)) (let ((n-squared (* n n))) (let ((n-cubed (* n n-squared))) (+ (/ n-cubed 3) (/ n-squared 2) (/ n 6))))) 7. (0 points; suggested practice) Do exercise 5.3. Check on the computer that your answer evaluates to the same value as the original expressions. 8. (4 points) What's the use of letrec in a program? When does letrec need to be used instead of let? 9. (0 points; suggested practice) Do exercise 5.2. Check your answer on the computer. 10. (0 points; suggested practice) Do exercise 5.4. Check your answer on the computer. 11. (0 points; suggested practice) Do exercise 5.5. You can handwrite your answer to this. 12. (5 points; basic) Do exercise 5.6 (insert-left-all). 13. (0 points; suggested practice) Do exercise 5.7. 14. (5 points) Do exercise 5.8 (list-ref). 15. (15 points; extra credit) Improve the clarity and efficiency of the Scheme code in the file /home/cs227/lib/chaos.ss by using iteration, let, and letrec, whenever possible. (Don't be mislead by the words ``iterates'' and ``iterations'' used in the code, that has nothing to do with whether the code is iterative or not.) Your answer will be judged by how well you make use of these ideas in the code. Make a copy (using the unix command cp), change the copy to make improvements, and hand in a print out of your copy. In what you hand in, highlight all the places you changed the code. 16. (20 points; extra credit) Write a program to-c-type that takes a Scheme style type, represented as a list, and returns the equivalent C style type. A C style type has the return type first, and so instead of using the arrow, ->, we use the reverse arrow, <-. Your program should be able to deal with arrow types within other types, as this is one of the most difficult aspects of the C type system. Furthermore, the Scheme type constructor vector should be translated to array, but backwards, so that (vector int) becomes (int array). For example, (to-c-type '(-> (int) void)) ==> (<- void (int)) (to-c-type '(-> ((vector int) int) boolean)) ==> (<- boolean ((int array) int)) (to-c-type '(-> ((vector int)) (vector int))) ==> (<- (int array) ((int array))) (to-c-type '(-> ((-> (int) int)) int)) ==> (<- int ((<- int (int)))) (to-c-type '(-> ((-> (int) bool) (-> (char) int)) (-> (char) bool))) ==> (<- (<- bool (char)) ((<- bool (int)) (<- int (char)))) SECTION 5.3 SYMBOLIC MANIPULATION OF POLYNOMIALS Procedures for this section must be written at the appropriate level of detail. That is, unless you are implementing one of the basic procedures for polys, your code should work for any representation of polys. (This property is called representation independence.) If your code is too low-level, you will lose points (and you'll have a harder time writing it too). You can load the code for polynomials by executing (load "/home/cs227/lib/ch5.ss") To test whether your procedures are written at the right level, you can load one of the following files /home/cs227/lib/polynomials1.ss /home/cs227/lib/polynomials2.ss /home/cs227/lib/polynomials3.ss after you load ch5.ss. If you load them before you load ch5.ss they will have no effect. 17. (12 points; basic) Look at the code in /home/cs227/lib/polynomials2.ss and in /home/cs227/lib/polynomials3.ss Describe their representations of polys and how the differ from the representation given in Program 5.14 of the text. It would be helpful to describe how 5.4x + 3.2 is represented in each case. 18. (5 points; basic) We can define the polynomial 5.2x^3 -3.14x^2 + x-17.3 (where 5.2x^3 means 5.2 times x cubed) by writing (poly-cons 3 5.2 (poly-cons 2 -3.14 (poly-cons 1 1.0 (poly-cons 0 -17.3 the-zero-poly))))) Do the same for the following polynomials, and use print-poly to show that you have the right answer. (That is, type them in to Scheme, and give us a transcript.) a. 7.2x b. 9.7x^2 - 7.2x + 11.0 c. x + 103.4 d. 8.1x^3 - 3.14159 e. 0.66x^6 + 22.1x^5 - 4.3x^4 + 2.1x - 232.8 19. (0 points; suggested practice) Using the procedures p+, p-, etc. from ch5.ss, compute the sum of 4.3x and 8.7x^2 -3.1x + 5.4 on the computer. Try additional examples of arithmetic operations of the polynomials in the previous problem if you are unfamiliar with polynomial arithmetic. 20. (0 points; suggested practice) Do exercise 5.10. 21. (10 points) Write a procedure ``differentiate'' that takes a polynominal and returns its derivative. The derivative is formed by multiplying each terms coefficient by its degree, and reducing its degree by one. Any zero-degree term is discarded. For example, passing the polynomial 2.0x^3 + 9.0x + 7.2 to differentiate should result in the polynomial 6x^2 + 9.0. Passing the zero polynomial to differentiate results in the zero polynomial. 22. (15 points) For this problem you will write two procedures: poly-quotient and poly-remainder. The procedure poly-quotient finds the quotient polynomial when poly1 is divided by poly2. The procedure poly-remainder finds the remainder polynomial when poly1 is divided by poly2. (Hint: remember how to do long division? Note that because one can use real numbers for coefficients of terms, one can always cancel the leading term exactly when dividing.) For examples, consider the following transcript. > (load "/home/cs227/lib/ch5.ss") > (load "/home/cs227/lib/print-poly.ss") > (load "poly-division.ss") > (define p1 (poly-cons 3 5.2 (poly-cons 2 -3.14 (poly-cons 1 1.0 (poly-cons 0 -17.3 the-zero-poly))))) > (define p2 (poly-cons 2 14.32 the-zero-poly)) > (print-poly p1) 5.2 x^3 + -3.14 x^2 + 1.0 x + -17.3 > (print-poly p2) 14.32 x^2 > (print-poly (poly-quotient p1 p2)) 0.36312849162011174 x + -0.21927374301675978 > (print-poly (poly-remainder p1 p2)) 1.0 x + -17.3 > (print-poly (poly-quotient p2 p1)) 0 > (print-poly (poly-remainder p2 p1)) 14.32 x^2 23. (0 points; suggested practice) Do problem 5.13. Write out the five basic definitions for polynomials using this representation and test your code on the computer. 24. (5 points; extra credit) Do exercise 5.14. 25. (5 points; extra credit) Write a procedure big-O that takes a polynomial representing the resources used by a computation and returns the polynomial that is the order of the polynomial. (See page 126 of the text.) 26. (8 points; extra credit) Given two polynomials p1 and p2, we say that p1 >= p2 if and only if there is some number N such that for all n > N, (>= (poly-value p1 n) (poly-value p2 n)) Implement this in an efficient manner! (That is, define a procedure p>= that terminates with a boolean result for all polynomial arguments.) 27. (20 points; Extra credit only) Generalize polynomials to an arbitrary number of variables. For example, your program should be able to work with 4.3x^2 +3.4z^3 + 2.1y^2. You will have to pass the names of the variables as parameters. The design of the ``basic definitions'' and the generalizations of the other procedures is up to you, but you should describe it to us, so we can understand your solution. As a simplier version of this problem, you can get up to 15 points for generalizing polynominals to work with 2 variables. BINARY NUMBERS 28. (0 points; suggested practice) Do exercises 5.16 and 5.17. Check your answers using the binary->decimal and decimal->binary procedures from ch5.ss. 29. (16 points) Do exercise 5.18. 30. (10 points; extra credit) Do exercise 5.20.