22C:54 -- Programming Langauge Concepts PRESCRIPTION FOR MAKEUPS FOR TEST 1. (File $Date: 2000/10/09 17:50:49 $) For test 1 there will be a makeup test; we will record the maximum of your original test 1 grade and the grade on the makeup. The makeup test is optional, you don't have to take it if you are happy with your test 1 grade. The makeup test will happen in class on Monday, October 9. However, this will not be a simple retaking of the test. The main objective is for you to learn the material (and for me to make sure that I have communicated it to you). The material on this test is quite important for the rest of the semester, and it is important that you master it. To that end, I expect you to do some work before taking the new test. You can either do this completely on your own, or see me or the TA for help on it. I suggest that you come see one of us if your score was especially low on the test, or if you are confused about anything at all that was on the test. What we ask before the test is that you do whatever of the following you find is helpful for your learning of the material. You can simply bring it to the test as evidence that you have done something, or you can show to one of us earlier if you want some feedback. However, you must do something if you wish to take the makeup test, any must bring whenever you have done with you to the makeup test as evidence. You will not, under any circumstances be allowed to take the makeup test without having some evidence of work that you have done. Finally note that the makeup test will be a new test over the same material. In particular, all the problems will be different, and you will see a new grammar for the last problem. 1. For trouble with the syntax of Scheme (grammar errors): We will show you how to translate from C++ notation into Scheme notation. Have you seen the file $PUB/docs/c++-translation.txt? (a) Write out a list of the kind of mistakes you make in syntax. (b) Copy, by hand, up to 5 procedures from chapters 1-2 of the textbook. Check these over for your mistakes. (c) Type in all the code you wrote on the test, and get it to run. (d) Write down up to 5 different examples of the syntax you made the most mistakes with. Don't just make a difference in names. The rest of the problems are keyed to the problem numbers of the test. That is, problem 2, refers to test problem 2, problem 3 to test problem 3, etc. 2. If you had trouble with the extraction (returning) of a symbol problem: (a) If you had an expression in your answer, what does it produce when you use Scheme on-line? (b) Draw a box and pointer diagram for the problem you had on the test. (c) What Scheme expression will return the symbol womens-diving from the-sports? (d) What Scheme expression will return the symbol "not" from the-sports? 3. If you had trouble drawing box and pointer diagrams. (a) Is the empty list a symbol? Check your answer on the computer using Scheme. (b) Make up 2 similar lists, and draw box and pointer diagrams for them. (c) Use the $PUB/lib/dot-notation.scm procedure to print out the dot-notation version for the lists you diagramed in part (b). If you can't tell whether your answer was right from that, see a staff member for help. 4. If you had trouble building lists with cons. (a) What does Scheme return for the expression you wrote (assuming you fix the syntax errors)? (b) Using only cons, quoted symbols, and the empty list, write a Scheme expression that returns the lists you made up in problem 3(b). (Make up 2 other similar problems if you didn't have trouble with problem 3.) 5. If you had trouble with the grammar problem. (a) make up 4 examples of sentences in the grammar on the test, and 4 that are not in that grammar. (b) Write out a parse tree for the examples that you made up that are in the grammar. (c) Consider the sym-exp grammar ::= | ::= ( {}* ) The depth of a sym-exp is the largest number of paretheses that surround any place in the sym-exp. For example, a has depth 0 () has depth 1 (a () (b)) has depth 2 Give 5 more examples of sym-exp, one at depth 0, one at depth 1, one at depth 2, one at depth 3, and another at depth 4. (d) Is the symbol x in the grammar for ? If so, give a derivation. If not, say why not. 6. If you had trouble with the currying problem. (a) Write a curried version of the first version of remove on page 46 of EOPL. (b) Also give a deftype for the original and the curried version of this procedure. 6.5 For trouble understanding questions on the test, such as problem 7-10, come see Gary. (a) If you had trouble with the vocabulary used in stating the problems, make a list of the phrases or words that you had difficulty understanding. Write out definitions of these (perhaps in another language if necessary). (b) Write down a description of the problem that you actually solved on the test, in the same style as the test. (c) Write down 4 problem descriptions for problems you think might be on the test, in the same style as the test problem. Two problems should be about lists, and one about s-lists or symbol-expressions, and one about a new grammar. 7. For problem 7. Choose whatever from the following will help you learn how do such problems. (a) Did you read The Little Schemer? If not, read chapters 3-5; it's on reserve at the library. (b) Trace, on paper, the execution most of your original solution to the problem, and of a corrected version for an example with at least three elements in the list of numbers that's the argument. (c) Solve the problem on the test using the Scheme map procedure. (d) Design a recursion over flat lists problem by giving an English explanation, the deftype, and some examples. Solve your problem. (e) What is the outline of a recursive procedure over flat lists? Explain how it relates to the grammar for lists. (f) Practice doing flat recursion over lists problems until you can do them very quickly on paper. Try some of the suggested practice problems in homework 2. 8. For problem 8. Choose whatever from the following will help you learn how do such problems. (a) What does the "..." notation in types mean? (b) What happens when you execute the following? (deftype show-args (-> (T ...) (list T))) (define show-args (lambda args (begin (displayln args) args))) (show-args ) (show-args 1 2 3) (c) causing the above definition what happens when you do: (apply show-args '(1 2 3)) (d) Explain the type of show-args above. 9. For problem 9. Choose whatever from the following will help you learn how do such problems. (a) Is the empty list a symbol? Check your answer on the computer using Scheme. (b) Do problem 5(c) above. (b) Trace, on paper, the execution most of your original solution to the problem, and of a corrected version for an example. Use an input that has a depth of at least 2. (c) What does the type checker say about your original solution? How does that relate to the corrections? (d) Design a sym-exp problem by giving an English explanation, the deftype, and some examples. Solve your problem. (e) What is the outline of a procedure that works on sym-exps? Explain how it relates to the grammar for sym-exp. What is the outline of a procedure that works on s-lists.? Explain how it relates to the grammar for s-lists. (g) Practice doing sym-exp and s-list problems until you can do them very quickly on paper. Always use 2 procedures. Try some of the suggested practice problems in homework 2, or the problems on old tests. 10. For problem 10. Choose whatever from the following will help you learn how do such problems. The code for the helpers for window-layouts is found in $PUB/exams/window-layout.scm. (a) Trace, on paper, the execution most of your original solution to the problem, and of a corrected version for an example. (b) What does the type checker say about your original solution? How does that relate to the corrections? (c) If you had the version of the test that asked you to do total-width, program total-height, or vice versa. (d) Design a problem over window-layouts, give an English explanation, the deftype, and some examples. Solve your problem, first on paper, then on the computer. For example, you might do something like computing the total area of the window layout, or a list of all the names of the windows... (e) Consider the following grammar ::= | (and ) | (or ) | (not ) ::= P | Q Helping procedures for this grammar are available in $PUB/exams/bexp.scm. Write a procedure (deftype beval (-> (bexp boolean boolean) boolean)) that takes 3 araguments: bexp, which is a , p-val, which is the value for P, and q-val, which is the value for Q. It evaluates the expression for those values. (Do this without using Scheme's eval function.) For example, (beval (parse-bexp 'P) #t #f) ==> #t (beval (parse-bexp 'Q) #t #f) ==> #f (beval (parse-bexp '(not P)) #t #f) ==> #f (beval (parse-bexp '(or (not P) Q)) #t #f) ==> #f (beval (parse-bexp '(and P (or Q (not Q)))) #t #f) ==> #t Do this by hand first, then on the computer. (f) For the grammar in part e, write a procedure (deftype bswap (-> (bexp) bexp)) that takes a and returns a with the same shape, but with every P changed to Q and every Q changed to P. For example, (bswap (parse-bexp 'P)) ==> Q (bswap (parse-bexp 'Q)) ==> P (bswap (parse-bexp '(not P))) ==> (not Q) (bswap (parse-bexp '(or (not P) Q))) ==> (or (not Q) P) (bswap (parse-bexp '(and P (or Q (not Q))))) ==> (and Q (or P (not P))) Do this by hand first, then on the computer.