Topics for Makeup for Exam 2 in Com S 342 $Date: 2004/03/12 11:09:41 $ This test covers topics from homework 2 and problems 1-14 of homework 3. SPECIAL INSTRUCTIONS FOR THIS TEST Your code should type check for full credit. You may not use trustme! or has-type-trusted in your code. You are not permitted to use the helping procedures named parse-... in your code. Do not use set!. REMINDERS For this test, you can use one (1) page (8.5 by 11 inches, one (1) side, no less than 9pt font) of notes. Handwriting is okay. No photo-reduction is permitted. Don't use anything with printing on the other side, please. These notes are to be handed in at the end of the test. Have your name in the top right corner. Use of other notes or failure to follow these instructions will be considered cheating. If you need more space, use the back of a page. Note when you do that on the front. This test is timed. We will not grade your test if you try to take more than the time allowed. Therefore, before you begin, please take a moment to look over the entire test so that you can budget your time. For programs, indentation is important to us for ``clarity'' points; if your code is sloppy or hard to read, you will lose points. Correct syntax also matters. Check your code over for syntax errors. You will lose points if your code has syntax errors. You can use helping procedures whenever you like. If you write recursive helping procedures, please give a deftype declaration for them. READINGS See homework 2b in $PUB/homework/hw2b.txt. For homework 2: Essentials Of Programming Languages, Sections 1.1-1.2 The Little Schemer, Chapters 2-4 (especially chapter 3) (Structure And Interpretation Of Computer Programs, Sections 1.2.1 1.3, and 1.1.6) For the first part of homework 3 (problems 1-8): A Type Notation For Scheme (http://www.cs.iastate.edu/~cs342/docs/typedscm_toc.html) See also the code examples page. TOPICS Topics marked + below are more important than topics marked - below. Topics marked ++ are even more important than the others. Names of relevant homework problems are [given in square brackets]. Descriptions of old exam problems are (given in parentheses). In general, things that are more like the homework will be more important. * Induction, Recursively Specified Data (1.1) ** Grammars, BNF + Be able to read a BNF grammar * Recursively Specified Programs (1.2) ** full recursion following a grammar + Know the steps to take to solve recursive programming problems. *** recursion over flat lists (this may be involved in other problems) - Write Scheme programs that do recursions over flat lists [HW2 set-ops, merge] (Fall 01, range, update; Spring 99, list-diff; Fall 98, preceed-each; Fall 97, append-all; Fall 95, duplicate-each) - Use map to write recursions over lists, and when to use it [HW2 subst-with-map using map] (Fall 01, range; Fall 00, qualifies = Haskell's map (> given); Spring 99, square-each; Fall 98, downcase-firsts; Spring 96, graph of a function) *** recursion over sym-exp and s-lists ++ Write Scheme programs that do recusions over sym-exp and slists using the helping procedures from sym-exp.scm to make them type check and be representation independent. [HW2 subst-with-map using map, swapper, swap-sym-exp, occurs?, flatten] (Fall 01, graph-sym-exp; Fall 00, wrap-sym-exp; Spring 99, insert-left-of; Fall 95, slist-map) *** recursion over other grammars ++ Write Scheme programs that work on a new grammar, such as the lambda-1-exp grammar used in class. (Fall 00, total-width of a "window-layout"; Spring 99, sub1-ref over grammar of vector expressions; Fall 98, change-middle-right which works on nested triples; Fall 97, subst-exp over arithmetic expressions with print) [HW3, lambda-helpers, free-vars, free?, bound-vars, bound?, free-vars and bound-vars for lambda+if-exp; Exercise 8, atomic-exp-map] * Hints See homework 2b