TOPICS FOR THE COP 4020 EXAM on Programming Language Concepts and the Declarative Model $Date: 2009/02/02 21:23:40 $ This exam covers topics from homeworks 1-2, including the declarative model. It is related to all the course objectives but especially to [Concepts], [UseModels], and [MapToLanguages]. 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 we have seen in chapters 1--2 of our textbook. But unless specifically directed, you should not use imperative features (such as cells) or the library functions IsDet and IsFree. Problems relating to the kernel syntax can only use features of the kernel language (given in Tables 2.1 and 2.2 of the textbook). 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-2 of van Roy and Haridi's "Concepts, Techniques, and Models of Computer Programming" (MIT Press, 2004). 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 recursive functions on integers and lists [HW1: calculating combinations] + recognize when an expression is in kernel syntax [HW2: Is {Sum N-1 Acc+N R} in the declarative kernel?] ++ desugar expressions in Oz (Fall07: desugar recursive function containing if expressions; Fall08: desugar Dec function and call) [HW2: expand Sum1, Sum2 into kernel syntax] [HW2: expand SMerge into kernel syntax] {See also desugaring self-test on Webcourses} + Semantic modeling (operational semantics) - Give an EBNF grammar for an example language. + Bound variable identifier occurrence vs. bound store variable [HW2: What's the difference between these concepts?] ++ Find the free and bound identifiers in an expression or statement (Fall07: free and bound ids in recursive proc P; Spring08: free and bound ids in recursive proc M; Spring08: Does closure have bindings for free or bound var ids? Fall08: free and bound identifiers in local A in {F A B} end; Fall08: free and bound identifiers in recursive proc Q) [HW2: free and bound identifiers in Copy] [HW2: free and bound identifiers in P] {See also free and bound self-test on Webcourses} ++ Find free and bound identifiers in a C or Java program fragment. (Spring08: free and bound ids in Java method run; Fall08: free and bound identifiers in bake method) [HW2: free and bound identifiers in C code] [HW2: scoping of "this" in Java code] - Answer questions about the semantics of programs using the Oz kernel's operational semantics ++ Desugar code containing function definitions and function calls (Spring08: Desugar compose function; Fall08: Is {Sum N-1 Acc+N R} in the declarative kernel language? Fall08: Desugar Dec function and call) [HW2: expand Sum1, Sum2 into kernel syntax] [HW2: expand SMerge into kernel syntax] {See also desugaring self-test on Webcourses} + Tell if Oz code will suspend - Give output of code that uses cells or threads TERMS AND CONCEPTS [Concepts] [MapToLanguages] 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 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? - What is a cell? What's it used for? + Why do race conditions make reasoning difficult? [HW1: why is programing with cells and concurrency difficult?] - What is a class? An object? - How can atomicity be used to prevent race conditions? + How is static typing different from dynamic typing? (Fall07: What kind of type checking in Oz, Java?) [HW2: What kind of typing does Java have? Oz?] + What are the disadvantages and advantages of dynamic type checking, as compared to static type checking? (Fall07: When are type errors caught with dynamic typing? Spring08: true/false about static scoping and type checking) + 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: + What are records? + How to access parts of a record in Oz? [HW1: What is pattern matching used for in Oz?] [HW2: case desugaring into if] + How do records encode enumerations, lists, and tuples? + What is a single-assignment store? + What are (declarative) variables? ++ How do variables in Oz differ from variables in C, C++, or Java? (Fall07: What happens in example with reassignment of a variable? Spring08: What happens in example with increment of a variable? Fall08: What happens in Swap example?) [HW1: difference between variables in Oz vs C++ or Java?] [HW2: what if variable used before determined in C++? Java?] + What are values, partial values? - What is a store entity? + What is a dataflow variable? + What does the unification algorithm do? [HW2: Does unification make sense in Java or C++?] [HW2: unification] + How can cyclic structures arise? + What is the semantics of var-var binding, value creation + Semantics of pattern matching (e.g., with constants in patterns) (Fall07: explain what happens in case statement example; Spring08: explain what happens in case statement example; Fall08: explain what happens in case statement example) [HW2: the case statement again] [HW2: expansion into kernel syntax] + What's the difference between = and == in Oz? ++ Static scoping + Why is it useful? How is it achieved for procedures? (Fall07: Why closure stores environment? Spring08: Does closure have bindings for free or bound var ids? Spring08: true/false about static scoping and type checking; Spring08: explain what happens in case statement example Fall08: what environment for Sum in recursive proc Sum's closure?) + How does it differ from dynamic scoping? + Give the value of an Oz expression using static scoping. (Fall08: Give output of local with Sum defintion and call) [HW2: Purpose of static scoping?] [HW2: contextual environment] + Static scoping in other languages How is Java's this identifier scoped? [HW2: use of this in Java] + Dynamic scoping? How does it work? What are its disadvantages? + What is dataflow behavior? [HW1: What happens when a variable is used before it is bound?] - How does the abstract machine work? + What is last call optimization? Why is it useful? [HW2: Is it used in C, C++, or Java compilers (typically)?] + What is garbage collection? What problem does it solve? [HW2: Does Java have garbage collection?] + Does garbage collection completely eliminate memory leaks? [HW2: Can a Java program have memory leaks?] + Syntactic sugars and linguistic abstractions + What is a linguistic abstraction? Give examples from Oz, Java... (Fall08: Give example of linguistic abstraction in Java, C, ...) [HW2: Give example of linguistic abstraction] [HW2: What is Oz's andthen operator like in Java or C++?] + What is a syntactic sugar? Give examples from Oz. (Spring08: true/false about utility and efficiency of sugars) [HW2: Equivalent of Java or C++'s != operator in Oz?] [HW2: if and case statements] + What is the difference between a syntactic sugar and a linguistic abstraction? + What sugars does Oz have? What are their desugaring rules? (Fall07: Could if-then-else be a syntactic sugar or ling. abstr?) [HW2: control abstraction] + What does the "$" nesting marker do? + Exceptions + Why does a language need an explicit exception mechanism? (Fall07: Why does a programming language need exception handling? Spring08: true/false about utility, purpose, and semantics) + What values are used in Oz for exceptions? [HW2: 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? (Fall08: Give output of program with exceptions, try-catch-finally) + Semantics related to the declarative model + Full recursion versus tail recursion (Fall07: What are correct statements about tail recursion?) [HW2: tail recursion] ++ What is a closure? When is it formed in Oz (Fall07: Why closure stores environment?; Spring08: Does closure have bindings for free or bound var ids? Fall08: Closures and free or bound identifier multiple choice) + How is a closure like an object? + What is a curried function? - Restrictions to the functional model (how to eliminate unbound variables) + (structural) induction for proving properties, e.g., of list functions [HW1: program correctness]