TOPICS FOR THE COP 4020 EXAM on Declarative Programming Techniques $Date: 2008/02/29 03:35:04 $ This exam covers topics from homework 3 problems 1-11, including declarative programming techniques. It is related to all the course objectives, but especially to [UseModels]. 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. We suggest that you memorize the Oz syntax you'll need.) 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 cells and assignment in your Oz solutions. (Furthermore, note that the declarative model does not include the primitive IsDet or the library function IsFree; thus you are also prohibited from using either of these functions in your solutions.) But please use all linguistic abstractions and syntactic sugars that are helpful. 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, sections 3.1-3.5 of van Roy and Haridi's "Concepts, Techniques, and Models of Computer Programming" (MIT Press, 2004). Also read the "Following the Grammar" handout. If you have time, study the relevant examples form the Code examples Web page. Also 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] + Oz programming; be able to: ++ Write iterative functions on integers and lists [HW3: iterative factorial, iterative SumList] (Fall07: MinElement, SumSquares) + 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] (Fall07: TeamSpirit, EvenNumbers) ++ Write functions that implement the operations of some declarative ADT. [HW3: SetOps, Possibly Infinite Sets (PISet)] ++ 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] (Fall07: TeamSpirit, EvenNumbers on list grammar, ChangeChannel on WindowLayout grammar, EvalExp on a new expression grammar, ChangeAddress on SalesData grammar, FreeVarIds on the one-argument lambda calculus grammar) 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?