Com S 342 --- Principles of Programming Languages EXERCISE 01: SCHEME BASICS AND PROCEDURES (File $Date: 2004/01/19 22:14:05 $) The purpose of this exercise is for you to learn how to work with simple lists in Scheme. 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. [Basics of Lists] Read chapter 1 of the "Little Schemer" (4th ed., 1996) by Friedman and Felleisen. Make a transcript for the following, and hand in a printout of your transcript. On the transcript identify the following. a. Give a Scheme expression that returns the list (()). b. Give a Scheme expression that returns the list (part-b ()). c. Give a Scheme expression that returns the list ((part-c ()) part-b ()). Suppose now that the-list is defined to be (part-d (part-e) ((x part-f))) as in (define the-list '(part-d (part-e) ((x part-f)))) d. Write an expression using only the-list, car, cdr, and calls that returns the symbol part-d. e. Write an expression using only the-list, car, cdr, and calls that returns the symbol part-e. f. Write an expression using only the-list, car, cdr, and calls that returns the symbol part-f. 2. [Flat Recursion over Lists] Read chapter 2 of the "Little Schemer" (4th ed., 1996) by Friedman and Felleisen. Without using the function member?, define a function non-member? : (-> (symbol (list-of symbol)) boolean) that, when given a symbol, a, and a list of symbols lat, returns #t if a is not a top-level element in the list lat, and #f otherwise. For example, (non-member? 'mysym '()) ==> #t (non-member? 'mysym '(mysym x mysym)) ==> #f (non-member? 'mysym '(a b c d e f g)) ==> #t Do this in Scheme and hand in a printout of your code and a transcript of your testsing, 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 pages 1-31 (up to the start of section 1.2) of the recommended textbook "Structure and Interpretation of Computer Programs", by Abelson and Sussman, which is on reserve and also on-line at the following URL. http://mitpress.mit.edu/sicp/