Com S 227 --- Introduction to Computer Programming HOMEWORK 2: PROCEDURES AND RECURSION (File $Date: 1993/09/15 18:59:17 $) Due: problems 1-5, Sept. 10; 6-8 Sept. 13; 9-15, Sept. 15; 16-18, Sept. 17; 21-25, Sept. 20. GENERAL DIRECTIONS Your solutions to these and all other problems should only use the features of Scheme introduced up to point in the text where the problem occurs. (In particular, you may not use DEFINE except at the top level.) For a problem that asks you to write a procedure ``foo'', type the Scheme code for foo into a file named ``foo.ss'', and hand in a printout of your code and a Scheme transcript showing how you loaded and tested the procedure. (As a study aid for the tests, we would also suggest that you write out the code for a procedure by hand, check it in your head, and then start working with the computer. During a test you won't have a computer.) For other problems, we prefer typed answers (edit on the computer and print if you can), but we will accept handwritten solutions. Your TA may insist on typing if your handwriting is too hard to read. You are always welcome to draw pictures by hand. Each Scheme procedure must be labeled with a comment of the following form. ;; NAME: TA: SECTION: This comment should be on the first line (closest to the top). (You can make up a file with this information in it, and then insert that file into each procedure's file when you begin to type it.) Arrange your printouts so that each procedure is followed by the transcript. If your transcript is not attached to your procedure, put the same information on it, and indicate what problem it is for. If you make a transcript, be sure that you test all relevant cases. There is no standard required for comments; you are responsible for making your procedures clear as you think best. You may imitate the comments used in class if you wish. You may also leave off comments if you believe a procedure speaks for itself. Watch out for ``over-commenting'' such as (+ 3 count) ; add 3 to count which does not make the code clearer, but only adds extra work for the reader, without any significant explanation. We urge you to experiment and be creative in your use of comments, keeping in mind that the main purpose is to make your code clear. These directions apply not only to this homework, but to all subsequent homeworks. SECTION 2.2, PROCEDURES 1. (0 points; suggested practice) Do exercises 2.2 and 2.3. Test your answer to 2.2 on the computer, and check your answer to 2.3 on the computer. 2. (5 points; basic) Let us consider a sentence to be a list of symbols. For example, (scheme is fun) This simple sentence is an example of normal English word order: subject-verb-object. Yoda, in the movie "The Empire Strikes Back", speaks in sentences which are inverted into object-subject-verb. Steven Spielberg wants you to automate the translation of normal subject-verb-object sentences into object-subject-verb sentences. You should write for him a procedure ``yodaize'' that does this for three word sentences. For example: (yodaize '(scheme is fun)) ==> (fun scheme is) (yodaize '(you must come)) ==> (come you must) (yodaize '(you learn patience)) ==> (patience you learn) Note that your procedure should work on any list of three items. This allows Yoda to speak slightly more complex sentences. (yodaize '((the force) is strong)) ==> (strong (the force) is) (yodaize '((the force) flows (from the rock))) ==> ((from the rock) (the force) flows) 3. (5 points; extra credit only) Write a procedure that turns three word subject-verb-object sentences into questions. (make-question '(scheme is fun)) ==> (is scheme fun) (make-question '(you must come)) ==> (must you come) Explain why this doesn't work well with the sentence: (you learn patience). 4. (5 points) Often in a program one wants to represent a table or association of information. Two ways of doing this are association lists and pairs of list. Association lists are lists of two-element lists, for example ((one uno) (two dos) (three tres)) represents a way to translate the English numbers 1-3 into Spanish. That is, ``one'' is associated with ``uno'', etc. The pairs of lists representation of the same information is as follows. ((one two three) (uno dos tres)) For the moment, we will focus on lists, like the above, that have only three (3) associations. Write a procedure, to-alist, that takes a pair of 3 item lists and turns it into an association list with 3 associations. For example, (to-alist '((one two three) (uno dos tres))) ==> ((one uno) (two dos) (three tres)) (to-alist '((iowa michigan new-york) (des-moines lansing albany))) ==> ((iowa des-moines) (michigan lansing) (new-york albany)) 5. (0 points; suggested practice) Write a procedure, to-pair-of-lists, that does the opposite of the previous problem. For example, (to-pair-of-lists '((one uno) (two dos) (three tres))) ==> ((one two three) (uno dos tres)) (to-pair-of-lists '((iowa des-moines) (michigan lansing) (new-york albany))) ==> ((iowa michigan new-york) (des-moines lansing albany)) SECTION 2.3, CONDITIONAL EXPRESSIONS 6. (0 points; suggested practice) Do as many parts of exercises 2.6, 2.7, 2.8, and 2.9 as you need to feel confident about the special forms and and or. Check your answers on the computer 7. (6 points; basic) A syntax error is a mistake in the form of an expression, such as a missing or incorrectly placed parentheses. A type error in Scheme occurs when you call a procedure and pass it an argument for which it is not prepared, or when you try to call something that is not a procedure. For example, in the ``expression'' )(3 + 4) There is a syntax error, an extra left parentheses at the beginning. There is another error, in that 3 and + are in the wrong places; the expression should read (+ 3 4). This could be classed as a type error (3 is not a procedure) or as a syntax error (+ is in the wrong spot). Find all the syntax errors and type errors in the following expressions, circle the mistakes, and write out a corrected version. Assume that the code is indented reasonably. You should handwrite your answer to this, and try to find the errors without using the computer. (You can check your answers on the computer if you wish.) Be careful, these expressions may have more than one mistake each. a. car(cons 4 '()) b. (car (cons (3 '()))) c. (cond ((null? ls) '() (zero? n) (cons n '()) (else (cons n cons(- n 1) ls)) d. (if null? lst '() (else (cons (car lst) (cdr lst)))) 8. (10 points) In this problem, and several others below, we will represent words by lists of symbols. For example, the list (w o r d) represents the word ``word''. That is, each one-letter symbol in the list stands for a character in the word. Gary Leavens spent some time learning French last summer, and knowing the computer's capacity for encoding knowledge, he decided to encode some of the rules of French in Scheme. One of the first things he learned about was French pronunciation. It seems that the French people usually do not pronounce the final consonant of a word. However, in some cases the final consonant is pronounced. An oversimplified explanation of which consonants are pronounced is that the letters ``c'', ``f'', ``l'', ``n'', ``m'', and ``r'' are pronounced (``m'' and ``n'' by making a preceding vowel nasal), but nothing else. He wants you to write a procedure ``pronounced?'' that takes a one-letter symbol and returns #t if it is pronounced, and #f otherwise. For example, (pronounced? 'c) ==> #t (pronounced? 'd) ==> #f (pronounced? 'f) ==> #t (pronounced? 'n) ==> #t SECTION 2.4, RECURSION If you are having trouble with the problems in this section, you might want to read chapters 2 and 3 of the ``Little LISPer''. Some aids to finding errors in your procedures may be found in section 2.5 of ``Scheme and the Art of Programming'' and in the file /home/cs227/doc/debugging-chez-scheme.txt on project Vincent. 9. (6 points) Do exercises 2.10 (translate cond to if). 10. (0 points; suggested practice) Do exercise 2.11. Check your answers on the computer. 11. (0 points; suggested practice) Do exercise 2.12. 12. (16 points; basic) In this problem, you will write 2 procedures. The first deals with symbols, the second with lists. a. The first procedure, ``symbol-pronounize'', takes a list of symbols, ``sentence'', and two symbols: ``name'' and ``pronoun''. It returns a list that is just like sentence, but with the first occurrence of name replaced by pronoun. Determine the first occurrence by using the Scheme procedure eq?. For example, (symbol-pronounize '() 'beatrice 'she) ==> () (symbol-pronounize '(mary beats the bush and fred catches the bird) 'mary 'she) ==> (she beats the bush and fred catches the bird) (symbol-pronounize '(mary beats the bush and fred catches the bird) 'fred 'he) ==> (mary beats the bush and he catches the bird) (symbol-pronounize '(mary beats the bush and fred catches the bird) 'susan 'she) ==> (mary beats the bush and fred catches the bird) (symbol-pronounize '(jack tom said hello to tom jack) 'tom 'he) ==> (jack he said hello to tom jack) 'tom 'he) b. The second procedure, ``word-pronounize'', takes a list of words, ``sentence'', and two words: ``name'' and ``pronoun''. Words are represented by lists of symbols. Otherwise it acts the same as symbol-pronounize. Use equal? to determine the first occurrence of a word in the sentence. For example, consider the following (in French, the lines starting with the semicolons (;) are comments for your understanding. (word-pronounize '() '(j a c q u e s) '(i l)) ; jack he ==> () (word-pronounize '((j e a n) (e s t) (b i e n)) '(j e a n) '(i l)) ; john is good john he ==> ((i l) (e s t) (b i e n)) (word-pronounize '((j e a n) (e s t) (j e a n)) '(j e a n) '(i l)) ==> ((i l) (e s t) (j e a n)) (word-pronounize '((j e) (r e g a r d e) (j e a n)) ; I see john '(j e a n n e) '(e l l e)) ; jean she ==> ((j e) (r e g a r d e) (j e a n)) 13. (5 points; extra credit only) Do the procedures symbol-pronounize and word-pronounize of the previous problem only work on sentences? If not, explain what they do in general. 14. (12 points; basic) Gary found out that, in French, long adjectives follow the noun they modify. Define a procedure, ``insert-long-adjective'' that is like remove-1st except that instead of removing the item it is searching for, it puts the adjective to the right of that item. That is, ``insert-long-adjective'' takes 3 arguments: an adjective, a word, an a sentence, it returns a list that is the same as the original sentence, except that the adjective is placed to the right of the first occurrence of the word. This should work for sentences that are composed of either symbols or lists of symbols (words). For example, (insert-long-adjective 'flexible 'screw '()) ==> () (insert-long-adjective 'flexible 'screw '(ada found the screw today)) ==> (ada found the screw flexible today)) (insert-long-adjective 'flexible 'pen '(ada found the screw today)) ==> (ada found the screw today)) (insert-long-adjective 'important 'meeting '(vous avez manque un meeting madame)) ; you have missed a meeting madam ==> (vous avez manque un meeting important madame) (insert-long-adjective '(m o u i l l acute-e) ; wet '(c h i e n) ; dog '((i l) (t r o u v e) (u n) (c h i e n))) ; he finds a dog ==> ((i l) (t r o u v e) (u n) (c h i e n) (m o u i l l acute-e)) (insert-long-adjective 'graisseuse ; greasy (fem.) 'poele ; frying pan (when fem., oven when m.) '(il laisse la poele dans le poele)) ; he leaves the frying pan in the oven ==> (il laisse la poele graisseuse dans le poele) 15. (8 points) Define a procedure, ``acronym'', that takes a list of words and returns a word that is composed of the first letters of the word, in the same order -- an acronym. For example, (acronym '()) ==> () (acronym '((c o n t e n t s) (a d d r e s s) (r e g i s t e r))) ==> (c a r) (acronym '((c o n t e n t s) (d e c r e m e n t) (r e g i s t e r))) ==> (c d r) (acronym '((l o t s) (i r r i t a t i n g) (s i g n i f i c a n t) (p a r e n t h e s e s))) ==> (l i s p) 16. (8 points; basic) Do exercise 2.17 (remove-2nd). 17. (15 points) Define a procedure ``last-adj-out'' that takes an adjective and a sentence and returns a list that is the same as the original sentence, except that the last occurrence of the adjective is deleted. (last-adj-out 'flexible '()) ==> () (last-adj-out 'flexible '(she found the screw flexible today)) ==> (she found the screw today) (last-adj-out 'nice '(the nice dog looked at the nice nice puppy)) ==> (the nice dog looked at the nice puppy) (Hint: you'll probably need a helping procedure.) 18. (0 points; suggested practice) Do exercise 2.20. How does this relate to type checking? 19. (15 points; extra credit only) There are intentionally no examples for this problem. The problem is not very well specified. (This is just as in real life.) If you need to make additional assumptions, write them down. Part of your grade will depend on how well you design the input and the output. Suppose you have a list representing your private collection of record albums (see problem 12 in homework 1). Write a procedure titles that takes the list representing your collection as an argument, and returns the titles of all the albums in your collection as a list. 20. (10 points; extra credit) Do exercise 2.21. SECTION 2.5, TRACING AND DEBUGGING You might also want to read /home/cs227/doc/debugging-chez-scheme.txt as a supplement to this section. To use the code for the procedures entering and leaving, you will need to type, at the Scheme prompt, the command (load "/home/cs227/lib/ch2.ss"). 21. (0 points; suggested practice) Do problem 2.22 on page 64. Check your answer on the computer. 22. (0 points; suggested practice) Do problem 2.23. Check your answers on the computer. 23. (8 points; basic) Consider the following procedure definition. (DEFINE good? (LAMBDA (sym) (BEGIN (writeln "sym is" sym) (COND ((not (symbol? sym)) (BEGIN (writeln sym " is not a symbol") #f)) ((eq? sym 'raindrops-on-roses) (BEGIN (writeln "hello mary poppins") #t)) ((eq? sym 'money) (BEGIN (writeln "it's money") #t)) (ELSE (BEGIN (writeln "nothing I know about") #f)))))) Identify what is printed on the screen and what is returned by each of the following expressions, which call the procedure defined above. a. (good? 'raindrops-on-roses) b. (good? (good? 'money)) 24. (8 points; basic) Do exercise 2.25, and hand in a printout and a transcript. 25. (0 points; suggested practice) Using the trace primitive of Chez Scheme (or any other Scheme that has it), try the following. See /home/cs227/doc/debugging-chez-scheme.txt for details on using ``trace''. (DEFINE down-up (LAMBDA (n) (IF (zero? n) (list 0) (list n (down-up (sub1 n)) n)))) (trace down-up) (down-up 4) Explain the results. 26. (3 points; extra credit) Do problem 2.26, except instead of building the tables for the applications given in the problem, do them for (last-item '(force is strong)) and (member? 'bingo '(grocho harpo zepho)). EXTRA CREDIT EXPLORATIONS 27. (10 points; extra credit) Consider classifying the procedures that you have seen in this chapter by their types (e.g., (-> (list T) T), etc.). Is there any general form that procedures of a given type take? If so, describe the general form of the procedures of that type, and give the names of the examples. If not, is there any reason for the lack of a general form? 28. (15 points; extra credit) Categorize the kinds of mistakes that you have made in solving the problems in this chapter. For each kind of mistake, describe it and give an example along with a fix. Post your findings to the newsgroup isu.coms.227, and be sure to include your name so you can get credit for this. (See the file /home/cs227/doc/reading-news.txt for details on how.) Can you suggest ways to help avoid these mistakes? 29. (10 points; extra credit) This problem is about conjugations of verbs in French, specifically the conjugation of regular verbs in the present tense. Gary started to work on a program for this, but unfortunately he had to leave on vacation (to France) before he could complete the program, so perhaps you can help. The procedure you are to write is to be called ``french-present-er''. It takes a verb in the infinitive form as a list of symbols, such as: (m a r c h e r) or (p r o g r a m m e r) and also a pronoun, such as (j e), (t u), etc. (a complete list is below). It returns the verb conjugated for the pronoun. Here are examples for the verb (p r o g r a m m e r), which means ``to program'', one example for each pronoun. (The comments at the right give the English translation of the pronouns.) (french-present-er '(p r o g r a m m e r) '(j e)) ; I ==> (p r o g r a m m e) (french-present-er '(p r o g r a m m e r) '(t u)) ; you(familiar) ==> (p r o g r a m m e) (french-present-er '(p r o g r a m m e r) '(i l)) ; he ==> (p r o g r a m m e) (french-present-er '(p r o g r a m m e r) '(e l l e)) ; she ==> (p r o g r a m m e) (french-present-er '(p r o g r a m m e r) '(n o u s)) ; we ==> (p r o g r a m m o n s) (french-present-er '(p r o g r a m m e r) '(v o u z)) ; you(plural) ==> (p r o g r a m m e z) (french-present-er '(p r o g r a m m e r) '(i l s)) ; they(masc.) ==> (p r o g r a m m e n t) (french-present-er '(p r o g r a m m e r) '(e l l e s)) ; they(fem.) ==> (p r o g r a m m e n t) This program should work for all other verbs with the same pronouns. (french-present-er '(m a r c h e r) '(e l l e)) ==> (m a r c h e) (french-present-er '(p r acute-e s e n t e r) '(n o u s)) ==> (p r acute-e s e n t o n s) In the last example above, we have used the symbol acute-e for an ``e'' with an acute accent (`) over it. Don't let that bother you, it's still doing the same thing with the ending. 30. (15 points; extra credit) What makes a program good? Take one of your longer procedures and make 3 versions of it. One that is as good as you can make it, one that is as bad as you can make it, and another that is middle of the road. (That is, A, F, and C grades.) Describe what makes the different versions good, bad, or indifferent.