TOPICS FOR THE COP 4020 EXAM on Declarative Programming Techniques $Date: 2007/10/17 03:28:06 $ This exam covers topics from homework 3, including declarative programming techniques. It is related to all the course objectives, but especially to [UseModels]. (This test also covers the material from topics that didn't test well in exam 1 the concepts of free and bound variable identifiers and the concept of desugaring to kernel syntax.) REMINDERS The exam will be open book, open notes. (Warning: don't expect to learn the material during the exam, you won't have time! A good idea for studying is to condense your notes to a few pages of ready reference materials.) If you need more space, use the back of a page. Note when you do that on the front. Before you begin, please take a moment to look over the entire test so that you can budget your time. Clarity is important; if your programs are sloppy and hard to read, you may lose some points. Correct syntax also makes a difference for programming questions. When you write Oz code on this test, you may use anything in the declarative model (as in chapters 2-3 of our textbook). So you must not use imperative features (such as cells and assignment). You are encouraged to define functions or procedures not specifically asked for if they are useful to your programming; however, if they are not in the Oz base environment, then you must write them into your test. READINGS Read chapter 3 of van Roy and Haridi's "Concepts, Techniques, and Models of Computer Programming" (MIT Press, 2004). (For the parts being made up from exam 1, read section 2.4.3 about "Free and bound identifier occurrences" and read section 2.3.1 and 2.6 about desugaring from the Oz language to the kernel syntax. We'll also have some supplementary problems about these concepts.) If you have time, see the course web site and also the course syllabus for other readings. TOPICS In the following, I use + to denote relatively more important topics, and - to denote relatively less important topics. Topics marked with ++ are almost certain to be on the exam. All of these are fair game, but if you have limited time, concentrate on the ones that are more important first (and in those, the ones you are most uncertain about). SKILLS [UseModels] [Concepts] [MapToLanguages] + Semantic modeling (operational semantics) ++ Find the free and bound identifiers in an expression or statement [HW2: free and bound identifiers] ++ Find free and bound identifiers in a C or Java program fragment. [HW2: free and bound identifiers in C code] [HW2: scoping of this in Java code] ++ Desugar code containing function definitions and function calls [HW2: Expansion into kernel syntax] + Oz programming; be able to: ++ Desugar expressions in Oz [HW2: Expansion into kernel syntax] ++ Write iterative functions on integers and lists [HW3: iterative factorial, iterative SumList] + Know when to use (or not use) tail recursion to write iterative functions. - Convert a fully recursive function into one that uses tail recursion. ++ Write functions that work on (finite) lists (following the grammar) [HW3: DeleteAll, DeleteSecond, SetOps, Associated, Borrowers, Borrowed, NumBorrowed, CommaSeparate, OnSeparateLines] ++ Write functions that implement the operations of some declarative ADT. [HW3: SetOps, Infinite Sets (Set)] ++ Write functions that work on a given grammar, following the grammar, even if the grammar is previously unknown to you and for which you have never seen examples. [HW3: ShrinkTo on the WindowLayout grammar] [HW3: BEval on the BExp grammar] [HW3: AllIds and SubstIdentifier on the Statement and Expression grammar] [HW3: SumTree and MapTree on a tree grammar] [HW3: TypeOf on an expression grammar] ++ Write functions using for loops (with collect:). [HW3: Associated, Borrowers, Borrowed, NumBorrowed] ++ Write functions using Oz library functions such as Map, Filter, FoldR, All. [HW3: Associated, Borrowers, Borrowed, NumBorrowed, IsFunction] [HW3: MyAppend, DoubleAll, and MyMap using FoldR] + Know when to use Oz library functions (especially Map, Filter, and FoldR) and for loops. [HW3: Associated, Borrowers, Borrowed, NumBorrowed, BRelCompose] + Curry a given function (make a curried version of it). + Be able to use a curried function to accomplish some task. - Uncurry a given function. ++ Write curried, higher-order functions that satisfy some specification. [HW3: Compose a list of functions] [HW3: Infinite sets (Set)] ++ Write higher-order abstractions of other functions, and use the abstraction to define the original other functions [HW3: SeparatedBy as abstraction of CommaSeparate and OnSeparateLines] [HW3: FoldTree as abstraction of SumTree and MapTree] + Use functions embedded in data to implement a specification. [HW3: Infinite sets (Set)] TERMS AND CONCEPTS [Concepts] [MapToLanguages] [EvaluateModels] You should be able to explain and use (in problems or essays) the following concepts (with appropriate comparisons to related concepts). You should be able to give examples of these concepts. + Read a BNF grammar for a data structure. + Decide whether code (in Oz) follows a given grammar. [HW3: following grammar for lists] + When is declarative programming useful? + How is declarative programming defined? + What is a difference list? + What are difference lists useful for? What are their limitations? + What is a curried function? + How is an ADT different from a data type specification? + What is an invariant property of data? + What problems related to the security of ADTs do we need to prevent? + Why prevent them? How could we prevent them? - Why are read-only views needed in the declarative model? + What is a module? What is it like in C, C++, and Java? + What is a functor? What is it like in C, C++, and Java? [HW3: SetOps] - How are modules linked?