TOPICS FOR THE COP 4020 EXAM on Message Passing and the Relational Model $Date: 2007/12/01 23:04:47 $ This exam covers topics from homeworks 5 and 6, including the message passing model, the relational model, and related programming techniques in Oz. This exam will also include a portion related to comparing models and programming paradigms, including their advantages and disadvantages and how well they might solve various programming problems. This exam is related to all the course objectives. 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 in the message passing or relational model (as in chapters 5 and 9 of our textbook). The problem will say which model is appropriate. However, you must not use imperative features (such as cells and assignment). 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. (This means you can use functions in the Oz base environment such as Map, FoldR, Filter, Append, etc.) READINGS Read chapters 5 (sections 5.1-5.7) and 9 (sections 9.1-9.3) of van Roy and Haridi's "Concepts, Techniques, and Models of Computer Programming" (MIT Press, 2004). For the material comparing models and programming styles, it will be helpful to re-read chapter 1. If you have time, you may want to read the introduction and skim over parts of chapter 6 in the textbook. 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] [EvaluateModels] + Oz programming; be able to: + message passing and ports: + How do you create and use a port object? + How can you get information out of a port object? + Simulate RMI using Send and ports. + Simulate asynchronous RMI with Send and ports. + Write code to do callbacks using Send and ports. + Are message executed concurrently by a NewPortObject server? ++ Use message passing and port objects to write state-based code for concurrent agents. [HW5: Box ADT] [HW5: Fault tolerance for the lift control system] - Show how to pass exceptions back to clients in client/server code. - Design a new multiagent system from scratch - In what way do list operations correspond to concurrency patterns? - How would you program a concurrent queue using ports? - How can you detect termination or other resource use in a modular way? + relational model (logic programming): + Write relations over lists and other data structures. [HW6: Concecutive elements in a list] - What features of the relational model are used in generate and test? - Solve a problem, such as the VCR problem in the notes, using generate and test. + When is it appropriate to use generate and test? - How would you program sorting, using generate and test? - How efficient would that be? TERMS AND CONCEPTS [Concepts] [MapToLanguages] [EvaluateModels] 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. + message passing model: + What is message passing? What about it is asynchronous? + What does NewPort do? What does Send do? [HW5: PortAsCell] + What is a port? How does it overcome the limitations of the declarative concurrent model? - How would you implement NewPort and Send in Java? + Why is a mutable store needed to describe the semantics of NewPort and Send? + How can one model Erlang's mailboxes in Oz? [HW5: Erlang's receive as a control abstraction] + What is the relative power of message passing vs. explicit state? [HW5: Box ADT, PortAsCell, comparison between these models] + Why is a mutation needed to describe the meaning of Send? + What is a port object? How is it different from a port? + Can port objects have state? [HW5: Box ADT] + What is an agent? + What is a protocol? + What is RMI? + How do you simulate RMI using Send? + How to simulate asynchronous RMI? - How do you specify and verify systems built using message passing? + Relational model: + What features are added to the declarative model in the relational model? + What does choice do? How does it execute? + What does fail do? How does it execute? + What does Solve do? How does it execute? + In what order are choices used? + Does a fail statement have to occur textually nested within the execution of a choice statement? + What happens when there are no more choices and a fail occurs? + Is there a difference between unification failure and fail? + What happens to variable bindings after a failure? + Be able to draw a search tree for a query. + In what sense does Solve give encapsulated search? + How does encapsulating search help reasoning? COMPARISONS [Concepts] [MapToLanguages] [EvaluateModels]: + message passing model: + Why is message passing important? + How is a port object different from a stream object? + Why can't we write NewPort and Send in the declarative concurrent model? + How and when should message passing and ports be used? + Explain what can be programmed with message passing that cannot be programmed in the declarative concurrent model. [HW4: Limitations of Declarative Concurrency] + What are the relative advantages and disadvantages of using the message passing vs. the demand driven concurrent model for solving problems? [HW5: using message passing vs. streams for square root approximation] + What are the features of Erlang that make it interesting? + What is useful about Erlang's combination of features? + How does the Erlang model differ from that of Oz? + What does Erlang's receive do? How would it be simulated in Oz? [HW5: Erlang's receive as a control abstraction] + relational model: + When is logic programming useful? + What are the key ideas of logic programming? + When is the relational model most useful? + Can the relational model be used to implement explicit state (cells)? [HW6: can relational model implement cells?] + Does encapsulated search aid putting logic programming into other languages? [HW6: Is encapsulated search appropriate for embedding in Java?] + What kind of modularity properties does the relational model have? + Is the relational model declarative? Referentially transparent? + Can we mix the relational model with state? - Can we do logic programming in the declarative model? - What happens if we add concurrency to the relational model? - Can we use logic programming ideas in the stateful models? - What is a constructive proof? - Does constructive logic allow "proof by contradiction"? - What does sequencing mean, in the logical translation of Oz? - What does a choice statement mean, in logic? - How do you state an existential property in Oz? - How do you state a universal property (rule) in Oz? - What does a choice mean in a rule? - How do you write a query for a fact? - What is the closed world assumption? - Can the closed world assumption ever be wrong? - How do you write a query to join two pieces of information? - What syntax is used to represent conjunction in queries? +general ++ What programming style is best suited for what kinds of problems? [HW5: what style for agent-based auction system?] + What are the advantages of each style of programming for making programming easier? + What is the difference between declarative and imperative programming? + What are the advantages of explicit state? + How does explicit state help abstraction? Encapsulation? + What are the goals of declarative programming? + What are the goals of logic programming? + What makes a model or style of programming declarative? + What does declarativeness have to do with referential transparency? + Is programming with state declarative? Why or why not? + Can a program that uses state be declarative? - What are two ways to read a declarative program? - What is an alias? What problems can it cause? - What is the difference between structural and token equality? Which is used for cells? - What is a data abstraction? How does it differ from an ADT? Object?