Com S 342 --- Principles of Programming Languages HOMEWORK 1: LANGUAGE DESIGN AND RECURSION (File $Date: 1999/09/13 21:07:17 $) Due: problems 1-11, September 9, 1999. In this homework you will learn some of the basics of Scheme and Java. In particular you will learn about recursive processes, including linear and tail recursion. We will start by reviewing a bit of what we did in classes the first few days, namely a discussion of language design and how the goals of a language influence its design. The section headings below give the readings related to the problems. 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/hw1.tst contains test harnesses for the coding problem. (Recall that $PUB means /home/course/cs342/public, see homework 0.) The way to use the test harnesses is described in the problems below. If you are working from home, see the directions in the following file to use our test harnesses. ftp://ftp.cs.iastate.edu/pub/leavens/scm/README For problems that don't require code, you can write the answer by hand. or you can hand in a printout. CLASS LANGUAGE DESIGN DISCUSSION, SICP pp. 1-16 1. [design goals] The in-class design of our language (`Simp') had 2 goals: simplicity and the ability to manipulate programs as data. Read a discussion of the design goals of Java on the web at the URL: http://java.sun.com/docs/white/langenv/ Then answer the following questions, writing no more than a half page for each. Also we'd prefer that you summarize, rather than just quote from this source, as it shows you're thinking. But be sure to set off in quotation marks anything that you directly quote in your answer. a. (10 points) What are the main design goals of Java? b. (10 points) Both our design of Simp and Java have simplicity as a goal. Why doesn't the syntax of Java look like Scheme then? c. (10 points) How do the design goals of Java differ from those of C++? 2. [means of combination] What does Java use for its means of combination that resemble the following in Scheme: a. (4 points) if-expressions of the form (if b e1 e2) (be careful) b. (3 points) begin c. (3 points) combinations 3. (10 points) [means of abstraction] Briefly describe two means of abstraction in Java. SICP section 1.1 Note: on page 619 of the textbook, there is a `List of exercises' that tells the page number of each exercise. If you can't find an exercise quickly, don't hesitate to look it up there. 4. (5 points) [prefix form] Do exercise 1.2; this can be handwritten. 5. [sum-of-larger-squares] a. (10 points) Do exercise 1.3 in Scheme. Call your procedure sum-of-larger-squares. After doing your own testing on this procedure, you must provide us a transcript of our test cases for your code as follows: First, make sure you cd to a directory you own (not $PUB, for example). If you are using the Com S machines, start a transcript by typing at the Unix shell's prompt script sum-of-larger-squares.out Then, assuming you have the directory $PUB/bin (/home/course/cs342/public/bin) in your PATH, start the interpreter, scheme342, by typing at the shell prompt scheme342 Now load your procedures and insert a comment telling who you are: (load "sum-of-larger-squares.scm") ;; Name: ;; Section: Then execute our test by typing: (test-hw1 "sum-of-larger-squares") (If you get errors that appear to be in our files, they are actually problems in your code... Really.) You can also add your own test cases to the output by running them now if you want. When you are satisfied, you can stop by typing the following lines (exit) exit The first stops the Scheme interpreter, the second stops the Unix script. Print the file `sum-of-larger-squares.out' and hand that in with your printout of the code in `sum-of-larger-squares.scm'. Be sure your name appears in a comment at the top of your code (as in homework 0). See homework 0 for other ways to make transcripts. If you aren't on the Com S machines, see the directions in the course download directory's README file: ftp://ftp.cs.iastate.edu/pub/leavens/scm/README You can also edit and print your code at home but test on ISU's machines if you want. Remember, no credit will be given unless you hand in a transcript that includes our tests. b. Also do the same in Java, with a public static method sumOfLargerSquares in a public class SumOfLargerSquares. In your Java code, use the type `int' for numbers. After doing your own testing on this procedure, you must provide us a transcript of our test cases for your code as follows: First, make sure you are working in a directory you own (not $PUB, for example). Copy our test harness file to your directory as follows: cp $PUB/homework/hw1.tst/SumOfLargerSquaresTest.java . Then compile it with Java, for example as follows: javac -g SumOfLargerSquaresTest.java (You will also need to compile SumOfLargerSquares.java.) If you are using the Com S machines, start a transcript by typing at the Unix shell's prompt script SumOfLargerSquaresTest.out Identify yourself by printing your name and section number; one way to do this is to execute the following command cat ~/.me.java assuming you created this file in homework 0. Then, run the tests by typing at the unix prompt: java SumOfLargerSquaresTest (If you get errors that appear to be in our files, they are actually problems in your code... Really.) Then type exit to stop the Unix script. Print the file `SumOfLargerSquaresTest.out' and hand that in with your printout of your code. Be sure your name appears in a comment in your code (as in homework 0). Remember, no credit will be given unless you hand in a transcript that includes our tests. 6. [applicative vs. normal order] a. (10 points) Do exercise 1.5. b. (5 points) Does Java use applicative-order or normal-order evaluation? How can you tell? 7. (15 points) [special forms] Do exercise 1.6. 8. (15 points) [good enough test in numerical code] Do exercise 1.7 in Java (only), by translating the code from the text into a Java public class Sqrt, with a public static method sqrt, and a public static method isGoodEnough. In your Java code, use the type `double' for numbers, and use `private' for any methods that would be defined using an internal `define' in Scheme. Because of the approximate nature of floating point numbers, you need to do your own testing of the Java code for this problem. Be sure to hand in a script of your testing with your code. SICP sections 1.2.1-1.2.2, 1.2.4-1.2.6 9. [recursion and iteration] a. (25 points) Do exercise 1.11 in Scheme, calling the two procedures `f' and `f-iter' (with the latter being tail-recursive). Test your code using (test-hw1 "f") and (test-hw1 "f-iter") If the test of one of these seems to be taking a long time, either you have an infinite loop, or you aren't using tail recursion for f-iter. b. (10 points) Using a while loop in Java, write a public static method to compute f in a public class F. Use `long' for the type of the numbers To test your Java code, use the file $PUB/homework/hw1.tst/FTest.java as in problem 5(b) above. 10. [fast-expt-iter] a. (15 points) Do exercise 1.16 in Scheme, calling your procedure fast-expt-iter. b. (10 points) Code this in Java, in a public class FastExpt, with a public static method fastExpt. In your Java code, use the type `double' for numbers, and use `private' for any methods that would be defined using an internal `define' in Scheme. Because of the approximate nature of floating point numbers, you need to do your own testing of the code for both parts of this problem. Be sure to hand in a script of your testing with your code. 11. [timing data] (15 points) Do exercise 1.22 in Java (only), in a public class SearchForPrimes, with a public static method timedPrimeTest. Also use the following definitions in your class private static long startTime = System.currentTimeMillis(); public static long runtime() { return System.currentTimeMillis() - startTime; } to do what the Scheme primitive `runtime' described in the exercise is supposed to do. (Actually, in Chez Scheme, this is called `real-time', and it doesn't seem to exist in SCM.) You should do your own testing of this problem. Be sure to hand in a script of your testing with your code. 12. (extra credit) If you have done all of the above, you can do extra credit in SICP sections 1.1 and 1.2 by selecting any of the problems not listed above, except 1.1. Problems in section 1.1 are 10 points extra credit and those in 1.2 are 20 points extra credit. You can do these in either Scheme or Java, or both. Be sure to hand in both your code and test output. Extra credit problems should be handed in separately from the other problems.