TOPICS FOR THE COP 4020 EXAM on Programming Language Concepts and the Declarative Model $Date: 2010/02/22 22:25:38 $ 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] - write simple functions that work on parts of lists or records [HW1: SecondItem in a list] + recognize when an expression is in kernel syntax (Fall09: is {G MyList a Temp} in the declarative kernel language?) [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; Spring09: desugar SumTo 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; Spring09: free and bound identifiers in local with proc call; Spring09: free and bound identifiers in recursive proc Mult Fall09: free and bound identifiers in call to DoIt expression; Fall09: free and bound identifiers in Compose function code) [HW2: free and bound identifiers in Compose function code] [HW2: free and bound identifiers in AvgIter function code] {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 Spring09: free and bound identifiers in Java method "sum". Fall09: Free and bound identifiers in Java mdethod "find".) [HW2: free and bound identifiers in Java code for makeOffset] [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; Fall09: desugar fun definition and call to Product) [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? Spring09: Name a languages that uses: static typing, dynamic typing? Fall09: Are java type errors always reported before running program? Fall09: What kind of type checking does Java have?) [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? Spring09: What happens in SetQ example? Fall09: What happens in SetIt example?) [HW1: difference between variables in Oz vs C++ or Java?] [HW1: What happens in SetIt example? What happens in X=X+1?] [HW1: can variables be assigned more than once in Oz?] + What are values, partial values? [HW2: What is a partial value?] - 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; Spring09: explain what happens in case statement example; Fall09: explain output for case statement example) [HW2: the case statement again] [HW2: SecondItem coding using case; 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?; Spring09: what environment for ToInt in F's closure?; Fall09: What is in environment at point of a call?) + How does it differ from dynamic scoping? + Give the value of an Oz expression using static scoping. (Fall08: Give output of local with Sum definition and call; Fall09: Give output of local with Last function definition/call) [HW2: Purpose of static scoping?] [HW2: contextual environment] + Static scoping in other languages How is xJava's this identifier scoped? [HW2: use of this in Java] + Dynamic scoping? (Fall09: Output of Last function def/call with 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?] + What is nondeterminism? How does it interact with concurrency? [HW1: What problems does nondeterminism cause in concurrent programming?] [HW1: CheckForWinner code, and how concurrency causes trouble] - How does the abstract machine work? + What is last call optimization? Why is it useful? [HW2: Should you write unbounded recursion in C, C++, or Java?] + What is garbage collection? What problem does it solve? [HW2: Does Oz have garbage collection?] + Does garbage collection completely eliminate memory leaks? [HW2: What do you have to do to ensure memory is collected?] + Syntactic sugars and linguistic abstractions + What is a linguistic abstraction? Give examples from Oz, Java... (Fall08: Give example of linguistic abstraction in Java, C, ... Spring09: What is the term for the enhanced "for" loop in Java, C#? Fall09: Give term for shortening in languages? What is one advantage?) [HW2: Give example of linguistic abstraction (aside from for)] [HW2: What is Oz's orelse operator like in Java or C++?] + What is a syntactic sugar? Give examples from Oz. (Spring08: true/false about utility and efficiency of sugars; Spring09: give an advantage of syntactic sugar or ling. abstractions) [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 in Oz 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: Give simple example of how to throw an exception in Oz] + 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