Topics for Exam 2 in Com S 342 $Date: 2006/10/04 06:45:59 $ This exam covers topics from homework 2-4. 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. READINGS - A general aid to the topics on this exam is the course's Code Examples page: http://www.cs.iastate.edu/~cs342/lib342/code-examples.html - Following the grammar handout http://www.cs.iastate.edu/~cs342/docs/follow-grammar.pdf - Essentials Of Programming Languages, Sections 1.1-1.2 - The Little Schemer, Chapters 2-5 (especially chapters 3-4) - Structure And Interpretation Of Computer Programs, Sections 1.1.6, 1.2.1 and 1.3; see http://mitpress.mit.edu/sicp/full-text/book/ - Revised^5 Report On The Algorithmic Language Scheme, Section 4.2 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. * Scheme ** procedures - what lambda does - first-class values + know how to curry a procedure [HW2: average3-c] (Spring 06, curry extend procedure for vectors; Spring 05, curry apologize; Spring 04, curry present-award; Fall 00, average3-c; Spring 99, eval-quadratic-c; Fall 97, dielectric-force-c) - know how to uncurry a procedure (Spring 99, uncurry s-combinator-c) - explain what a curried procedure would be used for (see the gravitational-force example) [HW2: average-9-42] (Spring 04, what is true about currying?) + be able to write a variable arity procedure [HW3: append*, set-union*] (Fall 01, range*; Fall 00, qualifies*; Spring 99, square-each*; Fall 98, downcase-firsts; Fall 97, append-all*) + write a higher-order procedure [HW3: append-map, iterate] (Spring 04, leave-in) ** syntactic abstraction + The advantages and reasons for using syntactic abstraction (sugaring) (Why is it a good thing?) (Spring 05, true statements about syntactic sugars; Spring 04, true statements about syntactic sugars) - For an example, tell which is the sugared form, and which is the desugared form? + Be able to use "and", "or", and "cond" in Scheme programs [HW2: occurs-twice using "and" and "or"] - Be able to use "let", "letrec", and "case" in Scheme programs - Be able to determine the values of expressions using them. - Know how to desugar expressions in Scheme for the sugars: let, and, or, cond, case and how to use the sugars to abbreviate the desugared forms. (You should also know that letrec is a syntactic sugar, but I won't test you on the details or how to desugar a letrec.) - Be able to use letrec to write a tail-recursive procedure + Give an example of a syntactic sugar (and the corresponding desugared forms) in some other language, such as C++, C, Pascal, etc. [HW2: example of syntactic sugar] (Spring 06, name a syntactic sugar in C++ or Java and describe it) * Induction, Recursively Specified Data (1.1) ** Inductive Specifications - Be able to inductively define a set of data items ** Grammars, BNF + Be able to read a BNF grammar + Be able to tell whether a sentence is in a grammar (Spring 06, simplified horn-clause grammar; Spring 05, grammar for module requires forms in MzScheme; Spring 04, sym-exp grammar; Fall 00, ML types grammar; Spring 99, Pascal-like declarations; Fall 97, logical expressions; Spring 96, expressions on array literals with + - *; Fall 95, ML lambda expressions) + write a syntactic derivation from a given grammar (Spring 05, derivation for sentence in grammar of module requires, Fall 01, Scheme types grammar derivation) [HW3: syntactic derivation] + Write recursive grammar rules [HW3: Kleene * and +] ** Induction - Be able to prove a property by induction * Recursively Specified Programs (1.2) ** full recursion following a grammar + Know the steps to take to solve recursive programming problems. *** recursion over flat lists + Be able to tell if a procedure "follows the grammar" for flat lists [HW2: Following the grammar for flat lists, Following ... 2] + Understand recursive procedures over lists and be able to explain what they do. [HW3: change to remove-first, change to remove] ++ Write Scheme programs that do recursions over flat lists [HW3: append-all, append-map, set-ops, merge] (Spring 06, slalom; Spring 05, greet-all; Spring 04, leave-in; 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] (Spring 06, slalom; Spring 05, greet-all; Fall 01, range; Fall 00, qualifies = Haskell's map (> given); Spring 99, square-each; Fall 98, downcase-firsts; Spring 96, graph of a function) - Implement some data abstraction using lists [HW3: set-ops] *** recursion over non-negative integers + Write a recursive program over the non-negative integers [HW3: insert-after, iterate, board] *** recursion over other grammars ++ Write Scheme programs that work on a new grammar, such as the lambda-1-exp grammar used in class. [HW4: largest-width, and shrink-to for window-layouts, beval and bswap for boolean expressions, all-ids, subst-identifier for statements and expressions, mark-selected for XML data] {HW5 is good practice for this: lambda-helpers, free-vars, free?, bound-vars, bound?, free-vars and bound-vars for lambda-if-exp} (Spring 06, stretch-width of a window-layout, replace-constant expressions with variable using the statement and expression grammar, interpret expressions in a simple expression grammar; Spring 05, count number of times symbol appears in a bexp, elim-useless assignments from statements and expressions, subst on a simplified type expression grammar; Spring 04, subst-for-free over lambda-1-exp, total-area over window-layout, eval-fe for "fraction-expressions", replace-unbound for statements and expressions; 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) ** Tail recursion (1.2.3) + be able to write a tail recursive procedure when asked to do so [HW4, vector-index] + know when to use tail recursion to solve problems and write a tail recursive procedure when it's useful, without being told to use tail recursion. (Spring 06, all-zero? elements in a vector; Spring 05, any-equals? for finding a number in a vector; Spring 04, last-slash; Fall 01, vector-increasing?; Fall 00, index-of-second which works on vectors of chars, Spring 99, picture-similar works on vectors of numbers; Fall 98, last-dot-position in a string; Fall 97, vector-same?; Spring 96 vector-positive?; Fall 95, product-nn) [HW2, vector-index; HW3, vector index with letrec] + know when it's better to use full recursion to solve problems (e.g., over lists or other grammars) and write code to do that (without being told to use full recursion) + be able to deal with tail-recursion over vectors and strings * Hints You might look at the suggested practice (or extra credit) problems in the homework, and at the old tests on-line. There are helpers in the library for the ubiquitous sym-exp and s-list examples on old tests, although I don't use this example anymore as it has proved to be somewhat confusing. But if you want to try them, use (require (lib "sym-exp-cooked.scm" "lib342")) and see the code-examples web page for more examples of such problems.