Topics for Exam 3 in Com S 342 $Date: 2004/04/07 20:22:21 $ This exam covers topics from homeworks 3-5 (primarily problems 10-19 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 Essentials Of Programming Languages, Sections 1.3, 2.1-2.2, 2.3.1-2.3.2 Code Examples Web Page for the above EOPL2e sections (see http://www.cs.iastate.edu/~cs342/docs/code-examples.html) You may also want to look at the following readings: Structure And Interpretation Of Programming Languages, Sections 1.1.6, 1.3, 2.1 (on-line at http://mitpress.mit.edu/sicp/full-text/book) A Type Notation For Scheme (http://www.cs.iastate.edu/~cs342/docs/typedscm_toc.html) Revised^5 Report On The Algorithmic Language Scheme 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. * Scoping and Binding of Variables (Section 1.3) + static vs. dynamic properties [static vs. dynamic type checking] ++ free and bound variable uses in an expression, free and bound variable names in an expression (Fall 95, Spring 96, Fall 97, Fall 98, Spring 99, Fall 00: free and bound variables, also in let and letrec; Fall 01: free and bound variables with nested lambdas) - combinators ++ you should be able to write procedures like free?, bound?, free-vars, bound-vars over various grammars, including new ones (the grammars will be provided.) [free-vars, free?, bound-vars, bound?, free-vars and bound-vars for lambda+if-exp, bound-vars in hw4] (Fall 95: count-free-occurrences, Fall 00: write free-vars over lambda with assignment expressions) + What are the free or bound variables (variable uses) in a let? + What are the free and bound variables are in a letrec? + region and scope of a declaration, hole in a scope, shadowing + you should be able to draw arrows from a variable reference to the declaration it refers to (Fall 97, Spring 99, Fall 00, Fall 01: draw arrows) + you should be able to draw contours showing the regions of variable declarations (Fall 00, Fall 01: draw contours) ++ lexical address of a variable reference ++ you should be able to give the lexical address form of an expression [lexical address idea] (Fall 95, Fall 97, Spring 99, Fall 00, Fall 01: give lexical address form) + you should be able to write parts of lexical-address [lexical-address] * Data Abstraction (Chapter 2) ** Specifying Data via Interfaces (2.1) - What is an interface? - What is a specification? + What is the importance of data abstraction? Can you give examples? (Both positive and negative ones) [lambda-helpers] + What is the importance of representation independence? Can you give examples? (Both positive and negative ones) [type checking and abstraction] (Spring 96: what is the importance of rep indep, give example) + How does the type of an ADT's operations relate to the types of the implementation's operations? [set-ops, inf-set-as-proc] (Fall 01: give implementation of colors with defrep and abstract colors) ** An abstraction for inductive data types (define-datatype and cases) (2.2) - What is a variant record? Give examples. What would this look like in other languages? + what does define-datatype do? How are the procedures it produces used? [bintree-to-list] - What does parse do? What does unparse do? + What is the abstract syntax for some concrete syntax? e.g., given a concrete syntax in the form of a BNF, give the corresponding define-datatype declarations. [abstract syntax for a grammar] (Spring 96: give abstract syntax for command grammar) ++ You should be able to write recursions over abstract syntax, using cases [eval-arith-expr, strength-reduce, bound-vars] (Fall 95: in-order traversal of tree, syntax expand "let", Spring 96: nary-sub1 over nary trees, Fall 97, desugar "and" expressions, Fall 98, strength-reduce, Spring 99, desugar when expressions, Fall 00: desugar do-unless expression, Fall 01: desugar multiple argument lambdas with "bind") * Representation Strategies for Data Types (2.3.1-2.3.2) + Be able to implement an ADT using a procedural representation [inf-set-as-proc] ++ Be prepared to transform a procedural representation of some data to an abstract syntax tree representation, or vice versa [inf-set-as-ast] (Spring 96: transform 2D boards, Fall 97, transform geometric regions code, Fall 98, transform image-generator, etc., Fall 00: transform music-generator, transpose, note-at, etc., Fall 01: transform schedule operations (add-meeting, etc.)) - Be able to answer questions about the behavior of the environment ADT. (E.g., given an example, what is the output?) * Hints You might look at the suggested practice problems in the homework, and at the old tests on-line.