Topics for Exam 2 in Com S 342 $Date: 2004/02/29 01:20:03 $ This test covers topics from homework 2 and problems 1-14 of homework 3. 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 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. * Scheme ** procedures - what lambda does - first-class values + know how to curry a procedure (Fall 00, average3-c; Spring 99, eval-quadratic-c; Fall 97, dialectric-force-c) [HW3, average3-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) [HW3, average-9-42] + be able to write a variable arity procedure [HW2, set-union*] (Fall 01, range*; Fall 00, qualifies*; Spring 99, square-each*; Fall 98, downcase-firsts; Fall 97, append-all*) ** syntactic abstraction + The advantages and reasons for using syntactic abstraction (sugaring) (Why is it a good thing?) + Which is the sugared form, and which is the desugared form? + Be able to use "and", "or", and "cond" in Scheme programs [occurs-twice using "and" and "or"] - Be able to use "let", "letrec", and "case" in Scheme programs [HW3, vector index with letrec] - 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 [HW3, vector index with letrec] + Give an example of a syntactic sugar (and the corresponding desugared forms) in some other language, such as C++, C, Pascal, etc. [HW3, example of syntactic sugar] * 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 (Fall 00, ML types grammar; Spring 99, Pascal-like declarations; Fall 97, logical expressons; Spring 96, expresssions on array literals with + - *; Fall 95, ML lambda expressions) + write a syntactic derivation from a given grammar (Fall 01, Scheme types grammar derivation) [HW2, syntactic derivation] + Write recursive grammar rules [HW2, 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 + Understand recursive procedures over lists and be able to explain what they do. [HW2 change to remove-first, change to remove] ++ 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) ++ Implement some data abstraction using lists [HW2 set-ops] *** 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] ** Tail recursion (1.2.3) ++ be able to write a tail recursive procedure when asked to do so [HW2, 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. (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 * Type checking and Data Abstraction ** Type system for Scheme - be able to explain the difference between static and dynamic type checking [HW3, static vs. dynamic type checking] - Explain the advantages of static or dynamic type checking, and the corresponding disadvantages. ** Data abstraction (2.1) - Why is data abstraction useful? [type checking and abstraction] - What is representation independence? - How does the type checker enforce data abstraction? * Hints You might look at the suggested practice problems in the homework, and at the old tests on-line.