TOPICS FOR THE COP 4020 EXAM
				  on
    The Message Passing Model and Programming Models vs. Problems
		     $Date: 2009/11/30 03:35:52 $

This exam covers topics from homework 5, including the message passing
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
demand-driven declarative concurrent model (as in chapter 4), 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, Max, etc.)
In the message passing model you can use NewPortObject and
NewPortObject2 as if they were built-in.

READINGS

Read chapter 5 (sections 5.1-5.7)
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
and discussions at the beginnings and ends of chapters 4 and 5.

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?
         [HW5: Describe components used in the message passing model]
	 [HW5: How does Controller use the Timer in the Lift program?]
      + How can you get information out of a port object?
      + Simulate RMI using Send and ports, with NewPortObject, typically.
        [HW5: Box ADT] [HW5: NewGauge port object]
        (Fall 08: Message passing model and synchronous RMI (multiple choice))
     + Simulate asynchronous RMI with Send and ports (or port objects).
        [HW5: Box ADT] [HW5: NewGauge port object]
    + Write code to do callbacks using Send and ports (or port objects).
        [HW5: Describe technique for programming callbacks]
        [HW5: Erlang mailbox, which has a timer object that does callbacks]
     + 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: Box ADT]  [HW5: NewGauge port object]
        [HW5: NewAuctioneer port object] [HW5: NewCatalog port object]
	[HW5: NewThermostat port object]
        [HW5: Erlang's receive as a control abstraction]
        (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)
      - 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.

 + Message passing model:

   + What is message passing? What about it is asynchronous?
     (Spring09: Send primitive's semantics)
   + 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]
     (Spring09: 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?
     [HW5: Describe how patterns in Erlang's receive are like Oz's case patterns]
     [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]
     (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 NewPortObject2?]
     [HW5: Box 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]:

 + 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: Box 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?
     [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]

 +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)

   + 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?