Com S 342 --- Principles of Programming Languages HOMEWORK 5: DATA ABSTRACTION (File $Date: 1999/11/14 20:41:22 $) Due: problems 1-7, at beginning of class November 4, 1999. In this homework you will learn about data as a means of combination and abstraction. You will also learn about how the mechanisms in Scheme and Java support information hiding and data abstraction; and gain more practice with various kinds of recursion. The section headings below give the readings related to the problems. You may also want to look at the file $PUB/docs/type-notation.txt, which describes the notation used for types below. WHAT TO HAND IN For code hand in *both* your printout of the code and a transcript of testing. Be sure the code has your name and section information in a comment at the top as described in homework 0 at the top. Although you may want to write your code out by hand as practice for taking the tests, and then type it in, please don't turn in handwritten code, unless the problem specifically states otherwise. *No* credit will be given for programming problems unless you also hand in a transcript that includes test output. For many problems, we will provide test harnesses; for such problems you must run our tests. For some problems, you will have to provide your own tests. For this homework, the directory $PUB/homework/hw5.tst contains test harnesses for the coding problem. For problems that don't require code, you can write the answer by hand. or you can hand in a printout. SICP section 2.2.2, also The Little Schemer chapter 5 1. [understanding trees] (5 points) Do exercise 2.24 in the text. This can be done with pencil and paper; you don't need any code. 2. [car and cdr on trees] (5 points) Do exercise 2.25 in the text. This can be done with pencil and paper; you don't need any code. If you wish, you can check your answers using the Scheme interpreter. 3. [deep-reverse] (10 points) Using Scheme, do exercise 2.27 in the text, which is to implement the procedure deep-reverse : (-> ((tree T)) (tree T)). You can test your code using (test-hw5 "deep-reverse") 4. [fringe] (15 points) Using Scheme, do exercise 2.28 in the text, which is to implement the procedure fringe : (-> ((tree T)) (list T)). You can test your code using (test-hw5 "fringe") 5. [binary mobiles] (40 points) Do exercise 2.29 in the text in Scheme. Call the procedure for part (c) ``balanced?''. You can test your code for parts (a) through (c) using (test-hw5 "binary-mobile") Put the code for part (d) in a separate file, and run the test again. Make sure your code is written so that the answer to the question in part (d) at the end helps show how good your code for parts (b) and (c) is. 6. [scale-tree] a. (5 points) What happens if you execute (scale-tree (list 2 (list) 3) 4) using the two implementations of scale-tree on page 112? Briefly explain. b. (10 points) If one of the two implementations of scale-tree on page 112 needs to be fixed, fix it, and test it on the example given above and a few others. Hand in your code for the corrected version, and your testing, along with part (a). Hint: you can load the procedure atom? defined in the file $PUB/lib/atom.scm by writing the following in your Scheme file (load-from-lib "atom.scm") Note that the atom? is not standard Scheme, and the version of atom? you get by default in Chez Scheme is different than this one. The one in $PUB/lib/atom.scm corresponds to the definition given in "The Little Schemer" (p. 10). 7. [tree-map] (20 points) Do exercise 2.31 in the text in Scheme. You can test your code using (test-hw5 "tree-map") 8. (extra credit) If you have done all of the above, you can do extra credit in SICP sections 2.2.2 by selecting any of the exercises not listed above that are found in those sections, except for 2.26. These problems will be worth 10 points extra credit if done in Scheme, and 20 if done in Java. Be sure to hand in both your code and test output. Extra credit problems should be handed in separately from the other problems.