TOPICS FOR THE 541 TEST on Declarative Model, including Functional Programming and Related Language Design Topics $Date: 2006/10/24 07:25:45 $ This exam covers topics from homeworks 1-5, including the declarative model, and declarative programming techniques in Oz. 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 we have seen in chapters 2--3 of our textbook. But unless specifically directed, you should not use imperative features (such as cells). 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 chapters 1-3 of van Roy and Haridi's "Concepts, Techniques, and Models of Computer Programming. 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). (Most of the problems from olders exams were done in Haskell, which has a different type notation than the one used in class for Oz. See section 4.7 of the text, or go to haskell.org for more about Haskell.) SKILLS + Oz programming; be able to: + give the output of a Oz expression, possibly involving: higher-order functions, library functions of general utility, such as Map, FoldR, Filter, or for loops + use built-in functions such as Map, FoldR, and Filter [HW4: DeleteAll, DeleteSecond, Associated, CommaSeparate, OnSeparateLines, IsFunction, define MyAppend using FoldR, DoubleAll, Map using FoldR] (Fall '03: associated, Spring '97: disjoint domains of relations) + use for loops to define functions [HW4: DeleteAll, DeleteSecond, library database, DoubleAll, BrelCompose] (Fall '03: associated, Fall '02: matrixAdd :: Num a => Matrix a -> Matrix a -> Matrix a, Fall '98: setproduct::(Eq a, Eq b) => [a] -> [b] -> [(a,b)], Spring '97: bind for formal parameters or environments ) ++ write recursive functions on lists, numbers, and algebraic data types (grammars) (for grammars, expect to see something like a small interpreter or type checker) [HW1: calculating combinations, HW4: DeleteAll, DeleteSecond, Merge, OnSeparateLines, SumTree, MapTree, TypeOf for Exps] (Fall '04: concatenated list ADT, write toNormalList catlistMap :: (a -> b) -> CatList a -> CatList b, Fall '04: define an instance of the type class FreeVars for a datatype of terms in the Abadi-Cardelli sigma calculus Fall '03: mapN::([a] -> b) -> [[a]] -> [b], and subtyping test, i.e., (<:)::TypeExpr->TypeExpr->Bool, Fall '02: map2 :: (a -> b -> c) -> [a] -> [b] -> [c], and filterTree :: (a -> Bool) -> Tree a -> Maybe (Tree a), eval for little language of numeric expressions with variables, Fall '99: mapTree :: (a -> b) -> Tree a -> Tree b, type checking for Alexander's VHDL spec language, Fall '98: semantic interpreter for part of FP, Fall '97: Prolog term manipulations: varsIn and renameVars, Spring '97: symbols in Prolog terms, simple type checking for Prolog terms) + write functions using tail recursion + Use of dataflow variables in programming to: + allow tail recursion + avoid appends in dealing with lists + use functions as data [HW4: Compose, infinite sets] (Fall '99: infinite geometric regions, Fall '97: fuzzy sets, membershipDegree, union) - infer the types of expressions or functions + generalize functions [HW4: SeparatedBy, FoldTree] (Fall '04: generalize functions on CatLists to write foldCat :: b -> ([a] -> b) -> (b -> b -> b) -> CatList a -> b Spring '97: generalize recursion over lambda calculus terms) + desugar expressions in Oz - explain how a functional language like Oz connects to the real world + Semantic modeling (operational semantics) - Give an EBNF grammar for an example language. + Free and bound identifiers in an expresssion or statement + Be able to read and write operational semantics for a small language + Be able to formally work the semantics of programs using the Oz kernel's operational semantics as described in class. [HW3: show steps in exeuction of 2 programs] ++ Desugar code containing function definitions and function calls [HW2: Expansion into kernel syntax] + Tell if a definition is tail recursive (iterative) + Tell if code will suspend - Give output of code that uses cells or threads [HW1: explicit state] TERMS AND CONCEPTS 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. + General points about programming languages: - What is a programming language? - What is the Turing Tarpit and how does it relate to languages? - What is a paradigm? What kinds of paradigms are there? How do languages fit within the different paradigms? - What is lazy evaluation? Give an example. [HW1: lazy evaluation] - How are threads created? [HW1: explicit state and concurrency] - What is a cell? What's it used for? [HW1: explicit state, explicit state and functions] - What is a class? An object? - How can atomicity be used to prevent race conditions? - How is strong typing different from static typing? - What are the disadvantages and advantages of dynamic typing? + Semantic and semantic modeling concepts in general: - How are languages defined? + Explain how to give meaning to a programming language. - Differences between syntax, semantics, and pragmatics. + Difference between programming models and computational models + Oz and declarative model concepts: + records and how they encode enumerations, lists, and tuples + single-assignment store + (declarative) variables + values, partial values + store entity + dataflow variable + What does the unification algorithm do? [HW2: unification] + How can cyclic structures arise? + semantics of assignment, value creation + semantics of pattern matching [HW2: the case statement again] + = vs. == in Oz + static scoping Why is it useful? How achieved for procedures? + dynamic scoping - What is the lambda calculus? How is it related to the declarative model? + dataflow behavior + how the abstract machine works + last call optimization: why is it useful + garbage collection + Syntactic sugars and linguistic abstractions + What is a syntactic sugar? Give examples from Oz. [HW2: if and case statements] (Fall '04: name a sugar in Oz, give example and desugaring Spring '97: Why are syntactic sugars important?) + What is the difference between a syntactic sugar and a linguistic abstraction? + What sugars does Oz have? [HW2: control abstraction] + What does the "$" nesting marker do? + Exceptions + Why does a language need an explicit exception mechanism? + What values are used in Oz for exceptions? - What happens if both an exception is thrown in a try and a raise is thrown in a finally clause? [HW2: exceptions with a finally clause] + Semantics related to Programming Techniques + recursion versus tail recursion [HW2: tail recursion] - algebraic (free) types and their relation to grammars + abstract data types vs. free types + avoiding capture + higher-order functions + closures (Spring '97: how is a closure like an object in OOP?) + curried functions + using curried functions as toolmakers to abstract from common patterns - combinators + Restrictions to the functional model (how to eliminate unbound variables) + equational reasoning for functional programming + (structural) induction for proving properties, e.g., of list functions [HW1: program correctness] + module systems and Oz's module system + relationship between modules and records + export control: hiding definitions - import conflict resolution + higher-order modules (functors)