Stanford University
Computer Science 249B: Winter 2007 - 2008

CS249B 2008 Final Exam

You are not to use any material, including books, course material, etc. 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 form. 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. Audit:
   1. Ossama Barak claims that writing audit code is rather stupid because when the state is corrupted, the first bad pointer will kill the process and otherwise it wont find anything, and there is no way to test the audit code in any case. Describe your position and justify.
   2. Cheriton's claims that it is zombie objects that keep him awake at night because they are hard for audit to catch. Here, a zombie is one that has been deleted by its managing module but has not been destructed because of some extraneous reference elsewhere. Describe why it is hard for audit to detect these and one technique for doing so.
2. Collections: Your junior colleague, Paten Gaelic, cant believe that, here in the 21st century, Cheriton is advocating invasive collection templates as compared to the nice non-invasive collection templates provided by STL. Sketch with diagram/code and written explanation a scenario in which an invasive collection template is far superior.
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.
   Paten 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: Cheriton's approach to concurrency entails partitioning by session and function, providing sequentially executed code, single-writer/multiple reader code and a small amount of multiple writer/multiple reader code. Dr Flumple, an esteemed academic, claims this is all too ad hoc and complicated. Justify the need for all these different techniques with a sketched out example (or argue that Flumple is correct).
5. Templates
   1. Hillary Clinton claims that C++ templates being Turing-complete is unnecessary and part of a vast right-wing conspiracy to make them too complicated for the average person. Describe the features of the template mechanism that make it complete and illustrate how each is useful, or else provide a technical argument that supports her position.
   2. John McCain claims that an object-oriented language without templates/generic support "leaves you between a rock and a hard place". Give an example of what he meant (or at least illustrates this arising) or else argue this is nonsense.
6. 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 a code example that refutes the conservative position and a sketch of a code example that contradicts the liberal position.
   2. The notion of "semi-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 semi-mutable value types, including a specific compelling example.
7. Model and KRS:
   1. Cheriton advocates separately state from processing but a simulation requires active objects that perform processing over (virtual) time. Sketch some simple example code/diagram to illustrate how to maintain this separation between state and processing in simulation.
   2. Cheriton claims that AI knowledge representation systems differ primarily from the object models one implements in C++ using the attribute only interface approach because the KRS's dont support static type checking. Give an example illustrating this point (or argue that Cheriton is missing something).
8. 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.
9. Process: Cheriton proposes to replace a meeting of industry-seasoned software managers to commit to a release with the automatic complication of a document that is likely never printed or read. Is this nonsense or how can you justify this approach?

Thanks, The End