Object behavior

[Bill Frantz]

At 09:35 AM 7/27/00 -0700, Karp, Alan wrote:
>Actually, you can get into trouble without using threads in your example.
>The behavior is undefined if you redefine the object being enumerated.  For
>example, you need to use two vectors to produce a new vector that skips some
>elements of the original; you can't do it in place.

The example does not redefine the object being enumerated.  It is always
the same object, just its state has changed.


>In your Java example, Vector isn't broken; the multithreaded program is.  I
>need to do one of two things.  I can lock the vector while I'm stepping
>through the enumerations.  (Locking the enumeration won't do the trick for
>the reason given in the previous paragraph.)  Alternatively, I can catch the
>exception and proceed, which is one way to implement a "hungry puppies"
>algorithm.

Well, it is clear that the multithreaded program is broken.  As far as I
can see, there are two choices as to why: (1) the Vector documentation is
broken, or (2) the Vector specification is broken.

Case 1, the Vector documentation is broken:

The example does not mention that it is only valid in an environment where
only one thread has access to the Vector object.  (It is not clear to me
that the Java team even knew that their example was broken.)  A non-broken
(I hope) version of the example:

 For example, to print all elements of a vector v: 
 
   try {
      for (Enumeration e = v.elements() ; ;) {
          System.out.println(e.nextElement());
      }
   } catch(NoSuchElementException e) {
   }

[Ironically, in some cases this method may be more efficient than the
example given.]

or:
      for (Enumeration e = v.elements() ; ;) {
          Object obj;
          synchronized(v) {
              if (!v.hasMoreElements()) break;
              obj = e.nextElement();
          }
          System.out.println(obj);
      }

[Which will be less efficient in all cases because of the extra locking.]


Case 2, the Vector specification is broken:

The vector specification could say:
 The public final synchronized Enumeration elements() method returns an
 enumeration of the components of a constant snapshot of this vector.

The obvious way to implement this specification is by using the clone
operation:

   return new VectorEnumerator(this.clone());

An exercise for the student is designing an efficient clone implementation
for this (and other) application.  It should not copy the Vector unless a
state-mutating operation is performed.

>
>_________________________
>Alan Karp
>Decision Technology Department
>Hewlett-Packard Laboratories MS 1U-2
>1501 Page Mill Road
>Palo Alto, CA 94304
>(650) 857-3967, fax (650) 857-6278
>
>
>> -----Original Message-----
>> From: Bill Frantz [mailto:frantz@communities.com]
>> Sent: Wednesday, July 26, 2000 5:55 PM
>> To: e-lang@eros-os.org
>> Subject: Object behavior, was RE: Split Capabilities: Making
>> Capabilities Scale
>> 
>> 
>> Rather than try to reply, I'm going to change the subject. :-)
>> 
>> <JAVA GEEKS START SKIPPING>
>> For a bald statement, there are no interesting objects without side
>> effects.  The square root function is hereby declared as 
>> uninteresting,
>> although useful.  Let me give a quick example.
>> 
>> Consider the behavior of the java.util.Vector object.  The 
>> basic contract
>> of Vector is, "The Vector class implements a growable array 
>> of objects.
>> Like an array, it contains components that can be accessed 
>> using an integer
>> index. However, the size of a Vector can grow or shrink as needed to
>> accommodate adding and removing items after the Vector has 
>> been created."
>> I won't go into all the details, but there is one method which is
>> interesting from this discussion.
>> 
>> The public final synchronized Enumeration elements() method returns an
>> enumeration of the components of this vector.  An Enumeration 
>> is defined as:
>> 
>> An object that implements the Enumeration interface generates 
>> a series of
>> elements, one at a time. Successive calls to the nextElement 
>> method return
>> successive elements of the series.
>>  
>> For example, to print all elements of a vector v: 
>> 
>>      for (Enumeration e = v.elements() ; e.hasMoreElements() ;) {
>>          System.out.println(e.nextElement());
>>      }
>> 
>> The two methods on an Enumeration are defines as:
>> 
>> public abstract boolean hasMoreElements()
>> 
>> Tests if this enumeration contains more elements. 
>> 
>> Returns: 
>> true if this enumeration contains more elements; false otherwise. 
>> 
>>  public abstract Object nextElement()
>> 
>> Returns the next element of this enumeration. 
>> 
>> Returns: 
>> the next element of this enumeration. 
>> Throws: NoSuchElementException 
>> if no more elements exist. 
>> </JAVA GEEKS START SKIPPING>
>> 
>>  
>> The code fragment above is all very fine, and simple to understand,
>> unfortunately it is broken.  It is broken because of the side 
>> effects of
>> having another thread remove elements from the Vector.  If 
>> another thread
>> removes the last element of a Vector between the call to 
>> hasMoreElements()
>> and nextElement(), then the code fragment will be terminated by the
>> NoSuchElementException.
>> 
>> The problems of side effects are not confined to object 
>> systems with facets.
>> 
>> Cheers - Bill
>> 
>> 
>
>