TOPICS FOR THE COP 4020 EXAM on Programming Language Concepts and the Declarative Model $Date: 2008/10/01 03:34:06 $ 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] ++ desugar expressions in Oz (Fall07: desugar recursive function containing if expressions) [HW2: expand F into kernel syntax. [HW2: expand Sum1, Sum2 into kernel syntax] [HW2: expand SMerge into kernel syntax] {See also desugaring self-test on WebCT} + Semantic modeling (operational semantics) - Give an EBNF grammar for an example language. ++ 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?) [HW2: free and bound identifiers in Copy] [HW2: free and bound identifiers in F] {See also free and bound self-test on WebCT} ++ Find free and bound identifiers in a C or Java program fragment. (Spring08: free and bound ids in Java method run) [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) [HW2: expand F into kernel syntax.] [HW2: expand Sum1, Sum2 into kernel syntax] [HW2: expand SMerge into kernel syntax] {See also desugaring self-test on WebCT} + 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 strong typing different from static typing? (Fall07: What kind of type checking in Oz, Java?) + 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?) [HW1: difference between variables in Oz vs C++ or Java?] + What are values, partial values? - What is a store entity? + What is a dataflow variable? + What does the unification algorithm do? [HW2: unification] + How can cyclic structures arise? + What is the semantics of assignment, 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) [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) How does it differ from dynamic scoping? Give the value of an Oz expression using 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? Is it used in C, C++, or Java compilers (typically)? + What is garbage collection? What problem does it solve? + Does garbage collection completely eliminate memory leaks? + Syntactic sugars and linguistic abstractions + What is a syntactic sugar? Give examples from Oz. (Spring08: true/false about utility and efficiency of sugars) [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? + What happens if both an exception is thrown in a try and a raise is thrown in a finally clause? + 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?) + 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]