This is last year's Exam 2. You should be able to answer all of these questions. Some material covered in this year's class, including Java byte codes and type safety, is not covered on this exam, but you should expect it to be covered on your exam. You can find comments on this exam at: http://www.cs.virginia.edu/cs201j/exams/fall2002/exam2-comments.html but we strongly recommend trying to answer the questions yourself before looking at them.

Subtyping

1. (10) Assume the following code is valid Java code:

   MysteryType1 mt1;
   MysteryType2 mt2;
   ... (anything could be here)
   mt1 = mt2.ossifrage (mt1);

Could MysteryType2 be a subtype of Wombat (as specified below) that satisfies the substitution principle? Explain why or why not clearly.

    public class Wombat extends Object {
       // OVERVIEW: A Wombat represents a confused bat.

       public Wombat () 
          // EFFECTS: Initialize this to a new Wombat.

       public Wombat ossifrage (Object o)
          // EFFECTS: Returns the ossifrage of this and o.
    }

2. (10) What can you determine about the specification of the MysteryType2 class? Be as specific as possible, but do not make any assumptions about the class that are not necessary for the code above to be correct. (Note: you should not assume MysteryType2 is a subtype of the Wombat type mentioned in the previous question.)

3. (10) Recall the SimObject class from Problem Set 5, excerpted and slightly modified below:

abstract public class SimObject implements Runnable {
    // OVERVIEW: A SimObject is an object that represents a simulator object.
    //    It has a grid (a circular reference to the grid containing this object),
    //    location (integer row and column), initialization state (boolean
    //    that is true if it has been initialized).
    //
    //    A typical SimObject is < grid, row, col, initialized >.
    //
    //  Note: SimObject is an abstract class.  The executeTurn method must 
    //  be implemented by subclasses.
    
    //@ghost public boolean isInitialized;

    public SimObject ()
	// EFFECTS: Creates a new, uninitalized SimObject.
	//@ensures !isInitialized
    { }

    public void init (int row, int col, /*@non_null@*/ Grid grid)
       //@requires !isInitialized
       //@ensures isInitialized
       // EFFECTS: Initializes this snake object with grid at row and col.
    { }

    abstract public void executeTurn() 
	//@requires isInitialized
	// EFFECTS: Executes one turn for this object.
	;
  
    public /*@non_null@*/ Color getColor () 
       // EFFECTS: Returns the color that represents this SimObject, for
       //  painting the grid.
    { }
}

Would the SnakeSimObject class specified on the next page satisfy the substitution principle rules to be a subtype of SimObject? For full credit, you answer must clearly explain why or why not.

public class SnakeSimObject extends SimObject {
    // OVERVIEW: A SnakeSimObject is an object that represents a slimey snake.
    //    It has a grid (a circular reference to the grid containing this object),
    //    location (integer row and column), initialization state (boolean
    //    that is true if it has been initialized), length (integer
    //    that gives the length on the snake), and direction (compass direction
    //    that gives the direction the snake is facing).
    //
    //    A typical SnakeSimObject is < grid, row, col, initialized,
    //         length, direction >, e.g., < grid, 5, 12, true, 4, S >.
    //

    public SnakeSimObject ()
	// EFFECTS: Creates a new, uninitalized SnakeSimObject with
	//	length 3 and facing direction N.
	//@ensures !isInitialized
    { }

    public void init (int row, int col, /*@non_null@*/ Grid grid)
       //@requires !isInitialized
       //@ensures isInitialized 
       // EFFECTS: Initializes this snake object with grid at row and
       //       col.  If the length of the snake is not positive or
       //       greated than the number of rows in grid, sets the
       //       length of this to 1. 
       //    
    { }

    public void executeTurn() 
        // REQUIRES: true
	// EFFECTS: Executes one turn for this object.  If this is not
	//    initialized (!isInitialized), does nothing.  Otherwise,
	//    the snake will move one square in the direction it is 
	//    facing.
    { }

    public /*@non_null@*/ Color getColor ()
        // EFFECTS: Returns greenish-brown snake color.
    { }
}

4. (10) Suppose we changed the specification of the constructor to:

    public SnakeSimObject ()
	// EFFECTS: Creates a new initialized SnakeSimObject at (0,0)
	//	with length 3 and facing direction N.
	//@ensures isInitialized
    { }

Illustrate why this specification would not satisfy the substitution principle by showing a short code fragment where a SnakeSimObject could not be safely used in place of a SimObject and explain what could go wrong.

Concurrency

5. (10) Explain how the implementation below could exhibit a race condition if this code were used as part of a distributed voting machine (where the same Candidate object may be referenced by multiple threads).

 1 public class Candidate {
 2    private String name;
 3    private int votes;
 4
 5   public Candidate (String n) { 
 6      // EFFECTS: Initializes this to the candidate named n with 0
 7      //             votes.
 8      name = n;
 9   }
10   
11   public void tallyVote () {
12      // EFFECTS: Increases this candidate's vote total by 1.
13      System.err.println ("Recorded vote for: " + name);
14      votes = getVotes () + 1;
15   }
16
17   public int getVotes () {
18      return votes;
19   }
20 }

6. (5) Explain what small change you would make to the code to fix the problem you identified in question 5?

7. (15) In Problem Set 5, Question 7, we suggested solving the deadlock where three philosophers interact by adding a rep invariant the requires colleage relationships to be reflexive (that is, if A is B's colleague, B must be A's colleague). Suppose we did not want to place this restriction on colleagues. Instead, we should be able to have three philosophers where A is B's colleague, B is C's colleague and C is A's colleague. Describe a locking strategy that would allow this without ever deadlocking. A good strategy description is worth 10 points, but for full credit, you must show (pseudocode is fine) how you would modify code for the philosophize method below to implement your strategy:

    public void philosophize () {
	Object lock1, lock2;

	if (colleague != null) { // Need a colleague to start and argument.
	    // Always grab the lock for whichever name is alphabetically first
	    if (name.compareTo (colleague.name) < 0) {
		lock1 = this;
		lock2 = colleague;
	    } else {
		lock1 = colleague;
		lock2 = this;
	    }
	        
	    synchronized (lock1) {
		synchronized (lock2) {
		    System.err.println (name + "[Thread " + Thread.currentThread().getName () + "] says " + quote);
		    colleague.argue ();
		} 
	    }
	}
    }

Memory Management

8. (10) Consider the following classes (similar to Problem Set 4 and Lecture 17):

public class Species {
    // OVERVIEW: Immutable record type for representing a species with a name and genome.
    /*@non_null@*/ private String name;
    /*@non_null@*/ private Genome genome;

    public Species (/*@non_null@*/ String n, /*@non_null@*/ Genome g) {
	name = n;
	genome = g;
    }

    public /*@non_null@*/ String getName () {
	return name;
    }
}

public class SpeciesSet { 
    // OVERVIEW: SpeciesSets are unbounded, mutable sets of Species.
    //    A typical SpeciesSet is { x1, ..., xn }
   private Vector els; 

    //@invariant els != null
    //@invariant els.elementType == \type(Species)
    //@invariant els.containsNull == false
    // invariant els does not contain two species with the same name.

   public SpeciesSet () { 
	// EFFECTS: Initializes this to be empty: { }
      els = new Vector (); 
   }

   public void insert (/*@non_null@*/ Species s) {
	// MODIFIES: this
	// EFFECTS: If s already contains a Species whose name matches
	//	the name of s, does nothing.  Otherwise, adds s to the
	//      elements of this: this_post = this_pre U { s }
        if (getIndex (s) < 0) els.add (s); 
   }

    private int getIndex (/*@non_null@*/ Species s) 
	// EFFECTS: If a species with the same name as s is in this
	//    returns index where it appears, else returns -1. 
	//@ensures \result >= -1
	//@ensures \result < els.elementCount
    {
	for (int i = 0; i < els.size (); i++) {
	    if (s.getName ().equals (((Species) els.elementAt (i)).getName ())) {
		return i;
	    }
	}
	return -1;
    }
} 

Fill in the missing parts in the small code fragment below so that a mark and sweep garbage collector that runs at the marked location would collect exactly 2 garbage Species objects.

   SpeciesSet ss = new SpeciesSet ();
   Species s1 = new Species ("snake", "ACATGA");
   Species s2 = [[[ fill in space 1 ]]]; 
   Species s3 = [[[ fill in space 2 ]]];

   ss.insert (s1);
   s1 = null;
   ss.insert (s2);
   s2 = null;
   ss.insert (s3);
   s3 = null;

   ← mark and sweep collector runs here
   ...

9. (10) In a language with explicit memory management like C, explain why it would be useful to change the specification of insert to:

   public boolean insert (/*@non_null@*/ Species s) 
	// MODIFIES: this
	// EFFECTS: If s already contains a Species whose name matches
	//	the name of s, returns false and does nothing.
	//	Otherwise, returns true and adds s to the elements of
	//	this: this_post = this_pre U { s } 

10. (10, a good answer is worth bonus points; a complete language design and implementation is worth an automatic A+ in CS201J) After being barred from using Sun's Java trademarks, a large software company in Mondred, Washington has decided to attempt to implement a new language that will offer the performance advantages of C with the saftey and ease of development advantages of Java. They call their new language Db (pronounced "D flat"), not to be confused with its tonal near-equivalent C# ("C sharp"). In particular, they would like it to be possible to build a reference counting garbage collector that will work for Db but still be able to manipulate memory addresses directly in at least some of the ways allowed by C. Assume they will start their design with C, and add or remove features to produce Db. Either argue why their goal is impossible to achive, or explain what changes they should make to C to achieve their goal.

11. (Optional, no credit, but I might give bonus points for good answers) Describe what CS201J is about using one word or a short phrase.

12. (Optional, no credit) Do you feel your performance on this exam will fairly reflect your understanding of the course material so far? If not, explain why.

University of Virginia Department of Computer Science CS 201J: Engineering Software

Sponsored by the National Science Foundation

cs201j-staff@cs.virginia.edu