TOPICS FOR THE COP 4020 EXAM on Declarative Concurrency $Date: 2008/11/18 03:10:41 $ This exam covers topics from homework 4, including the declarative concurrent model, the demand-driven declarative concurrent model, related programming techniques in Oz, and their relation to Java (and to a limited extent, to C#, C++, and C). This exam is related to all the course objectives, but especially to [UseModels]. 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 declarative concurrent model (as in chapters 2-4 of our textbook), so you must not use cells and assignment in your Oz solutions. (Furthermore, note that the declarative concurrent model does 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.) READINGS Read chapter 4, sections 4.1-4.5, 4.8, and 4.9.2 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 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 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 + 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) + Explain how to implement dataflow variables in Java [HW4: Threads and dataflow in Java] (Fall 07: concurrency, dataflow, synchronization 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? [HW4: Threads and dataflow in Java] (Fall 07: concurrency, dataflow, synchronization in Java) + demand-driven declarative concurrent programming: + Give the output of an Oz expression involving threads and ByNeed (or the lazy sugar) + 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] + stream-based programming: ++ Write programs using a producer-consumer architecture. [HW4: Approximations, SquareRoot, RelativeSquareRoot, Differentiate] (Spring 08: HeatControl produces heat directives from diffs list) + Explain the different techniques for doing flow control in a stream-based system. [HW4: Laziness and incrementally] - 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 ++ Use streams to help modularize computations. [HW4: StreamIterate, Approximations, ConvergesTo, SquareRoot, RelativeSquareRoot, 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) + Decide when or explain why functions should be lazy. [HW4: Why is StreamIterate lazy? Approximations?] (Spring 08: Does TempDiff need to be lazy? explain) + Explain how functions are incremental (or not) depending on how they are written. [HW4: Laziness and incrementality, Laziness and monolithic functions] + Write code that triggers a by need execution without waiting [HW4: 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). 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. [HW4: Thread Semantics, Order determining concurrency] - 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? [HW4: Thread Semantics] + What is a race condition? [HW4: Threads and dataflow in Java] + What is the causal order? + What is observable nondeterminism? + What is partial termination? (Spring08: Does code partially terminate?) - 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? + How is a dataflow variable like a communication channel? + What are dataflow variables good for? [HW4: Threads and dataflow in Java] + Demand-driven declarative concurrent model: + What are the primitives in the demand-driven concurrent model? + What does ByNeed do? + 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? + 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 [HW4: Concurrency and Exceptions] + What happens if the execution of a by-need trigger cannot complete normally? + 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?) + 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?) + 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? (Fall 07: Lazy streams, functions vs. iterators 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? [HW4: programming techniques vs. problems, with examples] - Should an imperative language be lazy by default? + Explain what kinds of problems cannot be (easily) programmed in the demand-driven declarative concurrent model. [HW4: Limitations of Declarative Concurrency] + What is the difference between declarative and imperative programming?