Com S 342 --- Principles of Programming Languages EXERCISE 04: RECURSION OVER THE NATURAL NUMBERS (File $Date: 2004/02/04 03:48:11 $) The purpose of this exercise is for you to learn some basic ideas about recursion over the natural numbers. As with all exercises, this is to be done individually. And it is due the day this topic is planned to be discussed in class, unless specified otherwise (see the syllabus at: http://www.cs.iastate.edu/~cs342/syllabus.shtml). As with all exercises, you have two choices for doing the work. You can either: - complete it as specified or - write down questions or problems that you had in trying to complete it. If you write down questions or problems you have, these should be detailed enough so that we can tell that you have read the materials and thought about them. (Don't just write: "I didn't understand how to do it". Instead, say what you tried and what you didn't understand.) During the class where this exercise is discussed, you should ask about these difficulties, and clear them up. Don't be shy; there will be other people with the same problem, and everyone can learn by discussing these issues. And you'll most likely see similar things on the homework, so it's best to understand them now. 1. [nat-leq] Read chapter 4 of the "Little Schemer" (4th ed., 1996) by Friedman and Felleisen. Write a procedure, nat-leq : (-> (number number) boolean) that takes two numbers, x and y, and returns true just when x is less than or equal to y. As in Chapter 4 of the Little Schemer, the numbers should be assumed to be natural numbers, that is, integers that are greater than or equal to 0. You should only use the procedures zero?, and sub1 in your solution, but no other Scheme procedures. (You can, however, use special forms, such as lambda, define, and, and or). For example: (nat-leq 2 2) ==> #t (nat-leq 1 1) ==> #t (nat-leq 0 0) ==> #t (nat-leq 1 0) ==> #f (nat-leq 2 1) ==> #f (nat-leq 742 15) ==> #f (nat-leq 15 742) ==> #t Do this in Scheme and hand in a printout of your code and a transcript of your testing, showing the results on the tests above. (In the notation used above ==> separates the test from the expected result; to perform a test you run the code on the left of the ==>). 2. [unary-notation] Read chapter 4 of the "Little Schemer" (4th ed., 1996) by Friedman and Felleisen. Write a procedure unary-notation : (-> (number) (list-of number)) that takes a natural number, n, and returns a list of length n, all of whose elements are the number 1. For example, (unary-notation 0) ==> () (unary-notation 3) ==> (1 1 1) (unary-notation 6) ==> (1 1 1 1 1 1) Do this in Scheme and hand in a printout of your code and a transcript of your testing, showing the results on the tests above. (In the notation used above ==> separates the test from the expected result; to perform a test you run the code on the left of the ==>). WHAT TO HAND IN You should have at the beginning of class, written answers to the above questions (or written out questions and problems you encountered for each part). Make sure your name is on these. Attach the printouts, if any, requested above. ADDITIONAL READINGS If you have time, read chapter 4 of the "Little Schemer" (4th ed., 1996) by Friedman and Felleisen.