TOPICS FOR THE COP 4020 EXAM on Declarative Concurrency, The Message Passing Model and Programming Models vs. Problems $Date: 2011/11/25 14:52:00 $ This exam covers topics from homeworks 4 and 5, including the declarative concurrent model, the demand-driven declarative concurrent model, the message passing model, and related programming techniques in Oz. 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. 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 in the demand-driven declarative concurrent model (as in chapter 4) and the message passing model (chapter 5). The problem may say which model is appropriate. However, you must not use imperative features (such as cells and assignment). (Furthermore, note that these models do not include the primitive IsDet or the library function IsFree; thus you are also prohibited from using either of these functions in your solutions.) But please use all linguistic abstractions and syntactic sugars that are helpful. 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.) In the message passing model you can use NewPortObject and NewPortObject2 as if they were built-in. READINGS Read chapter 4, sections 4.1-4.5, 4.8, and 4.9.2 and chapter 5 (sections 5.1-5.7) of van Roy and Haridi's "Concepts, Techniques, and Models of Computer Programming" (MIT Press, 2004). If you have time, review the first part of chapter 3 for background, read the other parts of chapter 4 for more applications of the ideas, and reread the textbook's introduction and chapter 1. See the course web site and also the course syllabus for other readings. If you have time, study the relevant examples form the Code examples Web page. Also if you have time, and try the old exams (but note that some problems that are relevant to this exam (especially those related to homework 5) were on Exam 4 in other semesters). 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] + Give the output of an Oz expression involving threads (Fall 08: give output of program with and without threads) + Use both the declarative concurrent model and the declarative model 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. [HW4: Order-determining concurrency] (Fall 07: give output of program with threads, Wait, Show; Spring 08: give output of program with threads, Show; Fall 08: give output of program with and without threads) - Explain how to implement dataflow variables in Java (Fall 07: concurrency, dataflow, synchronization in Java; Fall 08: multiple choice about dataflow variables in Java) + synchronization: + Make one thread wait for another. [HW4: The Wait operation] - Write a barrier synchronization procedure. + Explain how dataflow variables affect execution orderings [HW4: Order-determining concurrency] [HW4: Dataflow behavior in a concurrent setting] - How is synchronization done in Java? How could you use that to simulate Oz's dataflow variables? (Fall 07: concurrency, dataflow, synchronization in Java; Fall 08: multiple choice about dataflow variables in Java) + demand-driven declarative concurrent programming: + What is flow control and how is it achieved? [HW4: What is flow control?] (Fall10: Which should be lazy to achieve flow control: the producer or the consumer?) + Give the output of an Oz expression involving threads and ByNeed (or the lazy sugar) (Spring 09: does LMap work on lists, streams, infinite streams?) + Use combinations of the demand-driven declarative concurrent model, the declarative concurrent model, and the declarative model in one program to solve a problem. + Write code that triggers a by-need execution without waiting [HW4: By-need execution (RequestCalc)] + stream-based programming: ++ Write programs using a producer-consumer architecture. [HW4: What is producer-consumer in Oz, and how to implement in Oz. Differentiate] (Spring 08: HeatControl produces heat directives from diffs list) + Explain the different techniques for doing flow control in a stream-based system. (Spring 09: Is a lazy function data driven or demand driven?) (Spring 09: Is LMap incremental?) - 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 + lazy execution: + Write code that uses lazy functions to do stream-based computation [HW4: LSelect, RepeatingListOf, BlockIStream, EncryptIStream] (Spring 11: HoppingBlocks, which outputs some elements, and skips others; StreamFiltering, which includes blocks that pass predicate) ++ Use streams to help modularize computations. [HW4: EncryptIStream, IStreamIterate, ConvergesTo, DiffApproxims, Differentiate] (Fall 07: Map2 which is like Oz's List.zip function, Fall 07: Limit bounds its output, LimitedAverage; Spring 08: TempDiff produces stream of temperature differences, Spring 08: HeatControl produces heat directives from diffs list; Fall 08: FromBy, which produces a lazy stream of integers, Fall 08: TestOverStreams, that produces a stream of test results, Fall 08: AddFailCounts, that produces a list of test results with a running count of the failures encountered; Spring 09: write cumulative/running average of floats, CAvgIter; Spring 09: SizeNSublists of an infinite list; MovingAverage of an infinite list; Spring 10: LMap2 lazy map with 2 stream arguments and 2-arg fun; LRange producing a stream of pairs of largest/smallest; Fall 10: Interest, gives amount of compound interest on amount; IsGreater, which compares two IStreams) + Decide when or explain why functions should be lazy. [HW4: Why is LSelect lazy? EncryptIStream?] (Spring 08: Does TempDiff need to be lazy? explain; Fall 08: Does FromBy need to be lazy? explain; Spring 09: Does CAvgIter need to be lazy?) + Explain how functions are incremental (or not) depending on how they are written. [HW4: How is concurrent Map example incremental? Is LSelect incremental? EncryptIStream?] + Write code that triggers a by need execution without waiting [HW4: By-need execution (RequestCalc)] - 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). + 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, with NewPortObject, typically. [HW5: PCell ADT] (Fall 08: Message passing model and synchronous RMI (multiple choice)) + Simulate asynchronous RMI with Send and ports (or port objects). [HW5: PCell ADT] + Write code to do callbacks using Send and ports (or port objects). + Use message passing and stateless port objects (NewPortObject2) (Fall 08: SynchServer that executes procedure closures) ++ Use message passing and port objects (NewPortObject) to write state-based code for concurrent agents. [HW5: PCell ADT] [HW5: NewCounter port object] [HW5: NewEBay port object] [HW5: NewStack port object] [HW5: NewDropbox ADT] [HW5: NewFutureServer port object] [HW5: NewResourceArbiter] (Fall 07: NewGauge port object, NewAuctioneer port object) (Spring 08: NewThermostat port object) (Fall 08: NewRepeatChecker that checks for repeated words) (Fall 08: NewTaskManager that schedules tasks with requests) (Spring 09: NewGoodBooks that tracks book recommendations.) (Spring 09: NewDataflowVar that simulates a dataflow variable) (Spring 09: NewModel that acts as a model in MVC--observer pattern) (Spring 10: NewCountSatisfying counts samples that satisfy predicate) (Spring 10: NewTurtle that can move/draw on X-Y plane) (Spring 10: NewIterator that can run an iterator) (Spring 10: NewDispatcher that remembers list of waiting dataflow vars) (Fall 10: NewStack that is a stack abstract data type) - 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? 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. + Declarative concurrent model + 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. - How are threads modeled in the operational semantics? - How is garbage collection affected by threads? - What happens when there is an unhandled exception in a thread? + Semantic concepts + What is interleaving? + What is a race condition? [HW4: Why race conditions aren't possible in decl. concurrent model?] + What is the causal order? + What is observable nondeterminism? [HW4: Possible values observable from an expression] (Spring 10: Can you observe nondeterminism in Oz's demand-driven concurrent model?) + What is partial termination? (Spring 08: Does code partially terminate? Fall 08: does code partially or normally terminate?) - What is the formal definition of declarative concurrency? (Spring 09: Why is the declarative concurrent model observably deterministic?) + What is a stream? How would it be implemented? - What are coroutines? Why are they hard to use? [HW4: What problem can occur with coroutines?] - How is a dataflow variable like a communication channel? + What are dataflow variables good for? + Demand-driven declarative concurrent model: + What are the primitives in the demand-driven concurrent model? + What does ByNeed do? (Spring 11: give output of code using ByNeed; Spring 11: Give output of code using lazy functions) + Lazy Execution: + How to do flow control with lazy execution? [HW4: To get flow control, which to make lazy: producer or consumer?] - 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)? [HW4: What operations determine a "need"?, RequestCalc] (Spring 09: Needs from a call to HundredsPlus? Needs from local? Needs from unification? Needs from +?) + How is the lazy modifier on a function translated into ByNeed? + Is ByNeed declarative? (Fall 07: ByNeed and declarativeness, reasoning in Oz) + What is a stream? How would it be implemented? - What is soft real-time programming? What operations are useful for it? + Exceptions: + Is the declarative model with exceptions still declarative? - Explain how exceptions interact with the declarative concurrent model - What happens if the execution of a by-need trigger cannot complete normally? + Message passing model: + What is message passing? What about it is asynchronous? [HW5: how to send twice without waiting for the first to finish?] (Spring 09: Send primitive's semantics; Spring 10: observing nondeterminism and using message passing to do merge Fall10: is message passing synchronous?) + 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? [HW5: How do ports overcome limits of declarative concurrent model] (Spring 09: How does the message passing model overcome the limits 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? + Why is a mutation needed to describe the meaning of Send? - How can one model Erlang's mailboxes in Oz? + What is the relative power of message passing vs. explicit state? [HW5: PCell ADT, PortAsCell, comparison between these models] (Fall 07: power of cells vs. message passing, referential transparency) (Spring 08: In which models can {F X} == {F X} return false?) (Fall 08: Is message passing deterministic? Is nondeterminism useful?) + What is a port object? How is it different from a port? + Can port objects have state? [HW5: When can you use NewPortObject instead of NewPortObject2?] [HW5: PCell ADT] + Are message executed concurrently by a NewPortObject server? [HW5: Are messages executed concurrently by a NewPortObject server?] + What is an agent? + What is a protocol? + What is RMI? (Fall 08: Message passing model and synchronous RMI) + How do you simulate RMI using Send? + How to simulate asynchronous RMI? - How do you specify and verify systems built using message passing? COMPARISONS [Concepts] [MapToLanguages] [EvaluateModels]: + Comparison among styles of programming: + What makes a model or style of programming declarative? + What does declarativeness have to do with determinism (or referential transparency)? (Spring 08: What advantages does referential transparency have in a language with concurrency?; Fall 08: multiple choice about reliability of declarative concurrent model vs. concurrent Java programs) + 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? + Why is declarative concurrency useful? + Why is the declarative concurrent model simple to reason about? (Fall 07: ByNeed and declarativeness, cells and reasoning in Oz; Spring 08: What advantages does referential transparency have in a language with concurrency? Fall 10: Why is IsDet not part of the declarative concurrent model?) + 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? + What is the difference between declarative and imperative programming? + declarative concurrent model: + What are the advantages to using lazy functions to program stream-based computation vs. explicitly programmed triggers? + What is a stream like in Java? How would you implement laziness in Java? [HW4: How are streams like in Java?] (Fall 07: Lazy streams, functions vs. iterators in Java) (Spring 09: Can you consider iterators to be lazy in Java?) - 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? + When is lazy execution useful? + Should an imperative language be lazy by default? [HW4: Should a Java-like language be lazy by default?] + Explain what kinds of problems cannot be (easily) programmed in the demand-driven declarative concurrent model. [HW4: What kind of problem can't be easily programmed in demand-driven concurrent model?] + What is the difference between declarative and imperative programming? [HW4: Why is declarative concurrent model deterministic?] + message passing model: + Explain what can be programmed with message passing that cannot be programmed in the demand-driven declarative concurrent model. [HW4: Limitations of Declarative Concurrency] [HW5: How do ports overcome limits of declarative concurrent model] (Fall 08: can NewPort and Send be programmed in the declarative concurrent model?) + Why is message passing important? + How is a port object (ch. 5) different from a stream object (ch. 4)? + Why can't we write NewPort and Send in the declarative concurrent model? + How and when should message passing and ports be used? [HW4, HW5: programming techniques vs. problems, with examples] + Explain what can be programmed with message passing that cannot be programmed in the declarative concurrent model. [HW4: Limitations of Declarative Concurrency] [HW5: How do ports overcome limits of declarative concurrent model] [HW5: PCell ADT] (Fall 08: can NewPort and Send be programmed in the declarative concurrent model?) + What are the relative advantages and disadvantages of using the message passing vs. the demand driven concurrent model for solving problems? - 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? +general ++ What programming style is best suited for what kinds of problems? [HW5: what style for agent-based auction system?] [HW4, HW5: programming techniques vs. problems, with examples] (Fall 07: what's the best/least expressive model for a problem: book recommendation server, approximation of trig functions, Sudoku puzzle solver, manipulation of ASTs for DB query optimization) (Spring 08: what's the best/least expressive model for a problem: users exchanging cooking recipes, removing images from web pages, finding good schedules for classes, library of combinatorial logic gates) (Spring 08: what's the best/least expressive model for a problem: maintenance of traffic reports from sensors, insertion into XML, seating arrangement for mom's dinner party, filtering and smoothing stream of readings from humidity sensor) (Spring 09: What's the best/least expressive model for a problem: filtering stream of stock prices, tracking reports from bird watchers, generate list of menus for a cafeteria, highlighting terms in HTML) (Spring 10: What's best/least expressive model for a problem: XML configuration file subtree deletion; square root approximations) (Fall 10: What's best/least expressive model for a problem: matching DNA, approximating digits of pi, ticket reservations; Code Dropbox ADT using either declarative concurrency or message passing; Code DoWhile ADT using either declarative concurrency or message passing) (Spring 11: What's best/least expressive model for a problem: seeing if an infinite stream of floats converges, updating list of health records, calculating current word count of a stream) + What are the advantages of each style of programming for making programming easier? + What is the difference between declarative and imperative programming? (Fall 07: ByNeed and declarativeness, cells and reasoning in Oz) (Fall 08: Is message passing deterministic? Is nondeterminism useful?) + 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? (Spring 08: In which models can {F X} == {F X} return false?) + 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?