CSAIL Research Abstracts - 2005 link to http://publications.csail.mit.edu/abstracts/abstracts05/index.html link to http://www.csail.mit.edu
bullet Introduction bullet Architecture, Systems
& Networks		 bullet Language, Learning,
Vision & Graphics		 bullet Physical, Biological
& Social Systems		 bullet Theory bullet

horizontal line

Inference of Generic Types in Java Libraries

Adam Kiezun, Michael D. Ernst & Frank Tip

Introduction

Generic types in Java 1.5 offer multiple benefits to the programmers. However, safely converting existing libraries into generic libraries (i.e., without breaking clients) is a complex task, even for experienced software developers. Our research aims at creating analyses and tools to assist library builders in converting their software to use generic types, in a controlled way and with the safety needed to retain compatibility of existing client applications. As an example of a conversion consider the following library class on the left and its generic version on the right.

Non-generic class Generic version of the class
(note the introduced type parameters K and V
and the wildcard types in the last method)
class Hashtable{
  Object put(Object key, Object val){...}

  Object get(Object key){...}

  Set entries(){...}

  Iterator keys(){...}

  void putAll(Hashtable ht){…}
}
 		class Hashtable<K, V>{
  V put(K key, V val){...}

  V get(Object key){...}

  Set<Entry<K, V>> entries(){...}

  Iterator<K> keys(){...}

  void putAll(Hashtable<? extends K, ? extends V> ht){...}
}
Approach

For a given library, only a selected subset of classes will benefit from being type-parameterized. While previous work in the area (e.g. [1]) focused on either discovering that subset or treated all classes the same (e.g. [2, 3]), it is our view that the designer of the library typically knows which subset that is. They also have an idea which type references should become references to type parameters. What he or she needs assistance with is the exact typing of the rest of the program that would reflect these choices. For example, when this type reference becomes a type parameter, then what other references must also become type parameters? Which may but need not become type parameters? What should their bounds be? Which type parameters should be wildcards? What kind of wildcards - upper or lower bounded? Which references should remain untouched? What about compatibility for the clients of the library?

We intend to create sound analyses and an easy-to-use and robust tool that would assist library developers in the process of parameterizing their classes.

Our approach is based on type-constraint analysis in which type constraints are enhanced with type substitutions in order to express the semantics of parametric types. The constraint system is created for the selected part of the program and solved using the input provided initially by the programmer (or another tool - for example, a heuristic). The result is a type-correct program in which the selected type references are changed into type parameters and all other necessary modifications (e.g., parameterization of other type references or classes) have been introduced. The programmer can then further refine the parameterization by adding/removing/splitting/merging type parameters, changing wildcards into named type parameters etc. There refinements are also implemented as manipulations on the type constraint system that is later solved and the entailed source-code modifications are introduced.

Progress

We are in the process of designing the analyses. For the implementation, we plan to extend the type-constraint infrastructure that we have successfully used for research on migration of Java applications to use already generic libraries.

Future

We plan to implement the analysis in a tool integrated with a programming environment. This will enable its better practicality and availability.  We plan to evaluate the tool by using it to parameterize a number of selected libraries.

Research Support

This research is supported by IBM and by NSF grants CCR-0133580 and CCR-0234651.

References

[1] Daniel von Dincklage and Amer Diwan. Converting Java Classes to use Generics. In the Proceedings of OOPSLA, pp. 1-15, Vancouver, BC, Canada, October 2004.

[2] Dominic Duggan. Modular type-based reverse engineering of parameterized types in Java code. In the Proceedings of OOPSLA, 1999.

[3] Alan Donovan and Michael D. Ernst. Inference of generic types in Java. MIT Laboratory for Computer Science technical report MIT/LCS/TR-889, Cambridge, MA, USA, March 2003

horizontal line

MIT logo Computer Science and Artificial Intelligence Laboratory (CSAIL)
The Stata Center, Building 32 - 32 Vassar Street - Cambridge, MA 02139 - USA
tel:+1-617-253-0073 - publications@csail.mit.edu
(Note: On July 1, 2003, the AI Lab and LCS merged to form CSAIL.)