Search for KJL ContainerTraversalSupport project Team Members: Art Huston COM3360, Fall 1996 ============================================================================== OVERVIEW ======== The ContainerTraversalSupport Project (CTS Project) will extend Demeter/Java so that traversals and other methods work with Vectors and other container- type classes. This will provide the Demeter programmer with the flexibility to use repetition classes other than the default DemJava repetition class. CHANGES TO DEMJAVA SYNTAX ========================= The DemJava syntax will be extended by modifing demjava.cd. Specifically, the RepetionClass will be extended by adding an optional *using* keyword, followed by an existing class name that will be used to implement the repetition class: RepetitionClass = "~" Sandwich(RepeatedPart) [ *using* ParamClassName ]. REPETITION CLASS ACCESSORS ========================== When it is specified, the class must implement the following APIs to allow insertions and traversal: void addElement(RepeatedPartType) synchronized Enumeration elements() The addElement method will insert the RepeatedPartType object into the object. The position of the inserted object after insertion will be determined by the object; for a Vector, it will be at the end of the list, but for other classes it may be inserted in some lexical order. RepeatedPartType must be the type of RepeatedPart for the RepititionClass, or a super-class of RepeatedPart. KJL? Why the previous line? The elements() method returns an Enumeration class which can be used to iterate through the list of objects. The Enumeration class is standard in Java. KJL: Enumeration is an interface, not a class USING THE VECTOR CLASS IN DEMJAVA ================================= The addElement(RepeatedPartType) and elements() methods have been chosen for two reasons: 1) they provide the necessary functionality of inserting elements and traversing the list; 2) they are provided automatically by the Vector Class. The Vector class is provided in the java.util package. It provides a resize- able array of Object. Implementing a DemJava RepetitionClass using Vector instead of the default implementation makes it possible to use any of the Vector methods to insert objects, remove objects, or search for objects. It must be pointed out that Vectors can store any Java object, since all of the methods work with objects of type Object. This is not exactly what we want for DemJava, since the RepetitionClass specifies the type of the objects it contains, and is restricted to objects of that type and its sub-types. In the CTS project, we are willing to live with this restriction and trust that programs insert only objects of the correct type. If programs misbehave, we will capture the exception when it is thrown. Appendix A presents an alternative approach to creating type-safe containers. Note that there is no super-class or Interface above Vector that declares the addElement(Object) or elements() methods. This means that container classes in Java can be created without either or both of these member functions. The Dictionary interface and HashTable class in java.util are good examples; they both have the elements() method, but not addElement(Object). To use them with DemJava RepetitionClasses, it will be necessary to inherit the class and provide elements with the right signature. In particular, using a HashTable in DemJava will require writing a wrapper which takes a single argument to addElement and breaks it into two parts, a key and an element. A POSSIBLE FUTURE FOR JAVA: PARAMETERIZED CLASSES ================================================= The use of Java containers from libraries outside of Demeter will be somewhat restricted. This is true because the Java containers available to date store Objects of any type, at the cost of some type-safety and loss of readability (objects returned from the container must be casted to the correct type). This may be remedied in future implementations of Java that implement parameterized classes. CONTAINER TRAVERSAL IMPLEMENTATION USING EXISTING CONTAINER CLASSES =================================================================== The CTS project will implement traversals using existing container classes by writing its traversals using the underling addElement(Object) and elements() member functions. This will be done in four steps: 1) For each RepetionClass, check if has been specified. 2) If has not been specified, use the default DemJava implementation for RepetitionClass. 3) If has been specified, create a corresponding T_, where T is the type of the object being stored in the RepetitionClass. 4) For each traversal of the RepetitionClass, write a traversal method in T_. The T_ class will look like this: class T_ { // no-args constructor public T_() { container = new (); } // add element public void addElement(T t) { container.addElement(t); } //// private member functions //// // get enumeration. private void elements() { e = container.elements(); } // has more elements? private boolean hasMoreElements() { return e.hasMoreElements(); } // next element private T nextElement() { return (T) e.nextElement(); } //// private data members //// // container data member private container; // enumeration data member private Enumeration e; }; Each traversal of the container will call private member functions and use run-time type identification to get objects of the correct type. The traversal may be for objects of type T or sub-classes of T, and will have a visitor as an argument. The visitor will provide a visit member function taking an object of type T or a sub-class of T as its argument. A traversal member function will take the following form: // traversal to HOST type using VISITOR type. void toHOST_traverse(VISITOR v) { elements(); while (hasMoreElements()) { T t = nextElement(); if (t instanceof HOST) { v.visit((HOST) t); } } } Note that this simple implementation of a container is functionally very similar to the standard DemJava implementation because it allows insertions and traversal. It does not, for example, provide access to any of the special features of the underlying container, with the possible exception of the ordering of items inserted into the container. The programmer may access special features of the container by adding methods to the DemJava-generated container. SUMMARY ======= The ContainerTraversalSupport project will extend the DemJava syntax by adding an optional *using* class to the RepetitionClass. When this class is specified, the DemJava package will create a corresponding container class which contains a object. The class must support two methods, with the signatures "addElement(TYPE t)" and "elements()". The addElement method must add objects of the correct type to the container. The elements method must return an Enumeration which can be used to traverse the object. These methods are implemented in the Vector class in the java.util package. They must be added manually to use most other classes. The ContainerTraversalSupport project exposes only enough of the underlying container class to allow insertions and traversals. To use the special features of the underlying container, the programmer must add methods to the DemJava-generated class. APPENDIX A: CREATING TYPE-SAFE CONTAINERS ========================================= USING INHERITANCE FOR TYPE-SAFETY; A FAILED APPROACH ==================================================== At first glance it should be simple to create a type-safe container by inheriting a class and restricting access to its methods. For example, if we wish to store objects of type Fruit in a Vector in a type-safe way, we would like to do something like this: KJL: the problem is: many of the methods of Vector are final and cannot be subclassed. class Fruit_Vector extends Vector { // no-args constructor. public Fruit_Vector() : super() {} // hide addElement(Obj) by declaring it as private private synchronized void addElement(Object obj) { super.addElement(obj); } // insert Fruit object. public synchronized void addElement(Fruit f) { addElement((Object) f); } }; There are two reasons why this will not work, either of which is sufficient to invalidate the approach: 1) Vector declares its methods as final, so they cannot be overloaded. 2) Vector declares its methods as public, so they cannot be declared as protected or private. The latter restriction is somewhat obvious when we consider that the member function that we have restricted access to becomes available simply by casting the Vector-derived object to its super-class (see The Java Programming Language, Arnold and Gosling, page 59). USING CONTAINMENT TO IMPLEMENT TYPE-SAFETY ========================================== The implementation of a type-safe container is relatively straight-forward; the type-safe container contains a copy of a non-type safe container as a data member. In addition, the type-safe container provides type-safe methods to access the methods in the data member. Here is an example of a type-safe enumeration and container using the Vector class: class Fruit_Enumeration { // constructor protected Fruit_Enumeration(Enumeration anEumeration) { e = aEumeration; } // return TRUE if the enumeration contains more elements. public boolean hasMoreElements() { return e.hasMoreElements(); } // return next element. public Fruit nextElement() { return (Fruit) e.nextElement(); } // Enumeration data member. Enumeration e; }; class Fruit_Vector { // no-args constructor public Fruit_Vector() { v = new Vector(); } // insert Fruit object. public synchronized void addElement(Fruit f) { v.addElement(f); } // return an Enumeration for the current list of elements. public synchronized Fruit_Enumeration elements() { return new Fruit_Enumeration(v.elements()); } // Vector data member. Vector v; }; Note first of all that this implementation will compile; the fact that the Vector class is final does not prevent us from using it as a data member, and the fact that its member functions are public does not prevent us from restricting access to them. Note also that we have made Vector_Fruit completely type-safe; it is impossible to add anything to it that is not a Fruit. A significant limitation of this approach, however, is that the Fruit_Vector class has prevented access to *all* of the Vector member functions. In order to provide access, it must provide member functions of its own. In the example we have implemented just two of them, not counting the constructor; in fact, Vector contains 28 member functions. This implementation of Fruit_Vector makes use of the Fruit_Enumeration class, which is itself a type-safe implementation of Enumeration for Fruit objects. The Fruit_Enumeration constructor is protected so that it can be accessed by classes in the same package, in this case Fruit_Vector. The only way to construct a Fruit_Enumeration is through the Fruit_Vector elements() method. The Fruit_Vector elements() method does most of the work by getting the Enumeration object from its Vector data member and passing it into the Fruit_Enumeration constructor. It is important to note that we have made Fruit_Vector significantly more type-safe than Vector, but at the cost of some re-usability. This is so because existing class libraries that work with Vectors will not work with Fruit_Vector because the Vector class is contained instead of inherited. A reasonable compromise is to provide a member function on Fruit_Vector to directly access the Vector object, with a resulting relaxation of type-safety but a significant increase in re-use. GENERAL ALGORITHM FOR TYPE-SAFE CONTAINERS ========================================== If we have a complete specification for a container class C containing objects of type O, it should be possible to write a transformation function F which restricts C to containing objects of type D, a derived class of O ("derived" is chosen instead of "sub-class" because S can indicate either super or sub-class): F = 1.) Call the new class D_C (name mangling). 2.) Insert a private data member into D_C of type C. Call it . 3.) For each member function in C, write a corresponding member function in D_C with the same name. 4.) For each member function in D_C, write an implementation that passes the arguments to and returns the result. 5.) If the arguments to a member function in C are of type O, the corresponding arguments to a member function in D_C should be changed to type D. 6.) If the return type of a member function in C is if type O, the return type of the member function in D_C should be casted and returned as type D. 7.) If a member function is a constructor, the object should be constructed by calling new and passing the arguments to the object. This is sufficient to restrict the type of arguments in any class, but it lacks one thing for container classes; the ability to return a type-safe Enumeration. The following steps take care of this: 8.) If C contains an "elements()" function with a return type of E, create a D_E class with a protected constructor taking an E object and containing a private E data member. Write the hasMoreElements() and nextElement() methods by calling the E data member. The nextElement() method must cast the result to D and return it. 9.) If the member function signature in C is "elements()", change the return type of elements() in D_C from E to D_E. Call the corresponding member function on and construct a D_E object using the result. Return the D_E object. SUMMARY ======= Because inheritance can only add functionality and not restrict it, it is not possible to create type-safe containers using inheritance. It is, however, possible to create type-safe containers by storing the non- safe container as a data member. This requires knowing the signatures of all the member functions in the container, and writing a pass-through method for each. There is some loss of reusability, which can be partially solved by providing direct access to the underlying container class, at the cost of some type safety.