Stanford University
Computer Science 349: Winter 2005 - 2006

CS349 2006 Final Exam: Take Home Exam

You are free to use any material, including books, course material, etc. However, you should complete the exam yourself without assistance from others. It is a violation of the house code to receive assistance from others or to copy material without proper attribution.

Feel free to use point from. Each question can be answered satisfactorily in a page of writing or less. I am primarily interested in the most key points responsive to each question.

1. Value Types
   1. The conservative view is that you should just use built-in types because application-specific value types are difficult to define correctly, increase development time and execution overhead. The liberal view is that you can easily accommodate a diversity of measure systems with template-generated application-specific value types providing automatic protection against unit and type errors, with inheritance and conversion operators providing automatic conversions when appropriate. Provide an example that refutes the conservative position and an example that contradicts the liberal position.
   2. The notion of "quasi-mutable" type disgusts your colleaque Patel Gaelic. "Why?", he asks, "does Cheriton invent this nonsense when C++ has already has const and non-const and mutable." Describe the rationale for quasi-mutable value types, including a specific compelling example.
2. Type Structure of Programs:
   1. Professor Knowitall announces with great confidence that any use of run-time type identification (RTTI) (e.g. dynamic cast) is a failure of programming structure. Describe a key use of RTTI that you would use to challenge this statement, or argue in support of this statement if you prefer.
   2. Condeleeza Rice states: "C++ dynamic cast is just an optimization over the double-dispatch trick as arises in the visitor pattern." Describe whether this is true or false and support your conclusion.
3. Descriptions: The description data structures explored in the course can be characterized as:
   1. reference by smart pointer from the value type
   2. store as a hierarchial collection of fixed-sized blocks
   3. use a per-address space managment module that ensures there is at most one copy of a block storing a given value.
   Patel Gaelic claims these are quasi-arbitrary choices and there are many other reasonable designs whereas Bill Graham is convinced that these choices are ordained by the Almighty as the only true way. For each of these design choices, describe the impact of changing it and comment on whether there is in fact any other reasonable alternative.
4. Concurrency: Jeffrey Skilling of Enron fame now claims in his trial that the real scam is not his "management" at Enron but Cheriton's approach to concurrency, namely the single-writer assumption on interfaces when there can be arbitrary many concurrent clients, the reliance of non-blocking synchronization (which is known to be complex for non-trivial data structures), and the view that one can sequentialize the internal implementation of a module (which is known in conventional programming to create performance problems). Describe for the judge the key extra restrictions/structures that the concurrency chapter relies on to avoid these known problems.
5. Memory Management : You casually mention the MemPool approach to Paten Gaelic, who responds with distain that this is typical of academics, trying to push a one-size-fits all approach which works for their toy programs but is not sufficient for the real world. He continues on to mention that Stroustrup provides per-class overriding of new and delete because he realized that some classes needed specialized allocation and further, STL provides a different scheme than Cheriton's and so does ODMG-93, so surely there is a need for many different memory management approaches. Describe why the MemPool approach is in fact adequate for implementing all possible approaches (i.e. there is nothing you cannot do), and is only limited by extreme performance requirements, characterizing what those are.

Thanks, The End