TOPICS FOR THE 541 TEST on Declarative Concurrency and Message Passing Models, including Streams, Lazy Execution, Port Objects and Related Language Design Topics $Date: 2006/12/11 08:07:51 $ This exam covers topics from homeworks 6-7, including the declarative concurrent model, the message passing model, and related programming techniques in Oz. 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 we have seen in chapters 2--5 of our textbook. But unless specifically directed, you should not use cells (explicit state). 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 4-5 of van Roy and Haridi's "Concepts, Techniques, and Models of Computer Programming. 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). (Some of the relevant problems from older exams were done in Haskell, which has a different type notation than the one used in class for Oz. See section 4.7 of the text, or go to haskell.org for more about Haskell.) SKILLS + Oz programming; be able to: + Give the output of a Oz expression, possibly involving: threads, message passing primitives (NewPort, Send) + Use several computational models in one program to solve a problem. + dataflow variables: + Use dataflow variables to help with programming with threads; e.g., to automatically determine order of calculations, or to return results or synchronize. [HW7: Fault tolerance for the lift control system] + stream-based programming: + Program with a producer-consumer architecture? + Explain the techniques for doing flow control in a stream-based system? Program them. + Use a bounded buffer to help with flow control. + Implement a bounded buffer - Use streams to implement circuit simulations. - Fix deadlocks from feedback in a stream-based system + synchronization: + Make one thread wait for another. [HW6: The Wait operation] [HW7: Fault tolerance for the lift control system] - Write a barrier synchronization procedure. + Explain how dataflow variables affect execution orderings [HW6: Dataflow behavior in a concurrent setting] + Write code that triggers a by-need execution without waiting [HW6: By-need execution] + lazy execution: + Write code that uses lazy functions to do stream-based computation ++ Use streams to help modularize computations. [HW6: StreamIterate, Approximations, ConvergesTo, SquareRoot, RelativeSquareRoot, DiffApproxims, Differentiate] ++ Decide when or explain why functions should be lazy. [HW6: Why is StreamIterate lazy? Approximations?] + Explain how functions are incremental (or not) depending on how they are written. [HW6: Laziness and incrementality, Laziness and monolithic functions] + Write code that triggers a by need execution without waiting [HW6: By-need execution] + soft real-time programming: - Write NewTicker such that {NewTicker} returns a stream that grows by 1 element per second. + Write soft real-time code using (Delay or Alarm). [HW7: Fault tolerance for the lift control system] + message passing and ports: + Simulate RMI using Send and ports. + Simulate asynchronous RMI with Send and ports. + Write code to do callbacks using Send and ports. - Show how to pass exceptions back to clients in client/server code. - Design a new multiagent system from scratch ++ Use message passing and port objects to write state-based code for concurrent agents. [HW7: Fault tolerance for the lift control system] + Use list operations (such as Map) do write patterns of concurrent code (such as broadcast). - Use coroutining to avoid multiple threads + Program a concurrent data structure, such as a queue. + Show to detect termination of threads or track resource usage in a modular way. + Semantic modeling (operational semantics): + Threads: + What new features are added to the declarative model to support concurrency? + Given a sample program, say what possible orders of execution follow the causal order. [HW6: Thread Semantics, Order determining concurrency] + How are threads modeled in the operational semantics? - How is garbage collection affected by threads [HW6: Threads and garbage collection] - What happens when there is an unhandled exception in a thread? + Lazy Execution: + What was needed in the formal model to have lazy execution? + What is ByNeed's semantics like, if you ignore scheduling of when it runs? + What is a need (what activates triggers)? + How is the lazy modifier on a function translated into ByNeed? + Exceptions: + Is the declarative model with exceptions still declarative? + Explain how exceptions interact with the declarative concurrent model [HW6: Concurrency and Exceptions] + What happens if the execution of a by-need trigger cannot complete normally? + Message passing and ports: + Why is a mutable store needed to describe the semantics of NewPort and Send? + How can one model Erlang's mailboxes in Oz? - Explicit state (cells): - How are cells modeled? - How do you get assignment from the Exchange primitive? Access? + comparison among styles of programming: + Why is declarative concurrency useful? + Why is the declarative concurrent model simple to reason about? + What are the advantages to using lazy functions to program stream-based computation vs. explicitly programmed triggers? + What are the interesting features of Haskell? How does it differ from Oz? - What kinds of types does Haskell support? What is the notation for each type? - How do Haskell type classes relate to object-oriented programming? How are they different? + What are the advantages of declarative programming? + Can we do everything efficiently with the declarative model? What can't be done efficiently? + What problems are hard to modularize in the declarative model? + Is the real world declarative? + When is lazy execution useful? + Should an imperative language be lazy by default? + 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. [HW6: Limitations of Declarative Concurrency] + 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? [HW7: Erlang’s receive as a control abstraction] - What is the nondeterministic concurrent model? How does it differ from the declarative concurrent model? From the message passing model? What are its problems? + What is the difference between declarative and imperative programming? + What are the advantages of explicit state? + How does explicit state help abstraction? Encapsulation? TERMS AND CONCEPTS 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. - What is interleaving? - What is the causal order? + What is observable nondeterminism? - What is partial termination? + What is the formal definition of declarative concurrency? + What is a stream? How would it be implemented? - What are coroutines? Why are they hard to use? - What is soft real-time programming? What operations are useful for it? + What is a monomorphic type? What is a polymorphic type? Give an example of each - What is the difference between parametric and ad hoc polymorphism? - How does type inference work? + What is normal order? How does it differ from applicative order reduction? + How is a dataflow variable like a communication channel? + What are dataflow variables good for? + What is message passing? What about it is asynchronous? + What is a port? How does it overcome the limitations of the declarative concurrent model? + What is a port object? How is it different from a port? + Can port objects have state? + What is an agent? + What is RMI? + 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?