TOPICS FOR THE COP 4020 EXAM on Programming Language Concepts and the Declarative Model $Date: 2012/02/15 21:24:52 $ 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, but no electronics. (Warning: don't expect to learn the material during the exam. 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 simple functions that work on parts of lists or records [HW1: Subject, Verb, Object functions on 3 element lists; HW1: MakeSentence] + recognize when an expression is in kernel syntax (Fall09: is {G MyList a Temp} in the declarative kernel language?) ++ desugar expressions in Oz (Fall07: desugar recursive function containing if expressions; Fall08: desugar Dec function and call; Spring09: desugar SumTo function and call; Spring10: desugar Reverse function statement and call) [HW2: desugar into kernel; desugaring of if and case] {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; Spring10: free and bound identifiers in MyFun and MyMap code; Fall10: is X a free variable identifier in given code?; Fall10: find free and bound variable identifiers in call to Append code; Fall10: find free and bound variable identifiers in FilterIter code) [HW2: free and bound variable identifiers vs. bound store variables] [HW2: free and bound identifiers in CurriedChicken function code] [HW2: free and bound identifiers in AvgHelper 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". Spring10: Free and bound identifiers in Java for loop. Fall10: Free and bound identifiers in Java if with array assignments.) [HW2: free and bound identifiers in Java code for makeOffset] - 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; Fall10: desugar Swap code) [HW2: free and bound variable identifiers vs. bound store variables] [HW2: Desugaring of if and case] {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 programming model (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? Spring10: Ruby checks for type errors at runtime, so what kind of type checking does Ruby have?; Fall10: Can code given by type checked statically or must it be dynamically?) [HW2 (quiz): What kind of typing does Java have?] + 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? [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? Spring10: What happens in Sum example? Fall10: What happens in Square example?) + What are values, partial values? [HW2 (quiz): What is a partial value?] - What is a store entity? + What is a dataflow variable? + What does the unification algorithm do? - 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; Spring10: give output of case statement examples; Fall10: give output of case statement example; Fall10: give output of Swap call) [HW2 (quiz): case statements] + 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; Spring10: Give output of statement in kernel language of Oz; Fall10: Why is static scoping useful?) - Static scoping in other languages How is Java's this identifier scoped? + Dynamic scoping How does it work? What are its disadvantages? (Fall09: Output of Last function def/call with dynamic scoping; Spring10: Give output of statement in Oz with dynamic scoping; Fall10: Can language with with dynamic scoping have static type checking?) + What is dataflow behavior? (Fall10: How do dataflow variables work in Oz?; Fall10: Can you write a random number funciton with no arguments in Oz?) [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: ReserveSeat code, and how concurrency causes trouble] (Spring10: What's an advantage of determinism for concurrency?) - How does the abstract machine work? + What is last call optimization? Why is it useful? + What is garbage collection? What problem does it solve? + Does garbage collection completely eliminate 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, ... 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", "interface", and switch)] [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: 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? + Semantics related to the declarative model + Determinism of the declarative model (Spring10: are programs in the declarative model necessarily deterministic?) + 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; Fall10: What is a closure?) + 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 - Exceptions and exception handling + Why are exceptions better than error return codes? - What is the syntax for raising exceptions in Oz? + How does one handle exceptions? [HW2: ExpectException] + What is the semantics of exception handling code (try-catch)?