Converting java programs to use generic libraries

ABSTRACT

Java 1.5 will include a type system (called JSR-14) that supports <i>parametric polymorphism</i>, or <i>generic</i> classes. This will bring many benefits to Java programmers, not least because current Java practice makes heavy use of logically-generic classes, including container classes.

Translation of Java source code into semantically equivalent JSR-14 source code requires two steps: parameterization (adding type parameters to class definitions) and instantiation (adding the type arguments at each use of a parameterized class). Parameterization need be done only once for a class, whereas instantiation must be performed for each client, of which there are potentially many more. Therefore, this work focuses on the instantiation problem. We present a technique to determine sound and precise JSR-14 types at each use of a class for which a generic type specification is available. Our approach uses a precise and context-sensitive pointer analysis to determine possible types at allocation sites, and a set-constraint-based analysis (that incorporates guarded, or conditional, constraints) to choose consistent types for both allocation and declaration sites. The technique handles all features of the JSR-14 type system, notably the raw types that provide backward compatibility. We have implemented our analysis in a tool that automatically inserts type parameters into Java code, and we report its performance when applied to a number of real-world Java programs.

REFERENCES

• 1: Ole Agesen, The Cartesian Product Algorithm: Simple and Precise Type Inference Of Parametric Polymorphism, Proceedings of the 9th European Conference on Object-Oriented Programming, p.2-26, August 07-11, 1995
• 2: Alexander Aiken , Edward L. Wimmers, Type inclusion constraints and type inference, Proceedings of the conference on Functional programming languages and computer architecture, p.31-41, June 09-11, 1993, Copenhagen, Denmark [doi>10.1145/165180.165188]
• 3: David F. Bacon , Peter F. Sweeney, Fast static analysis of C++ virtual function calls, Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.324-341, October 06-10, 1996, San Jose, California, United States
• 4: G. Bracha, N. Cohen, C. Kemper, S. Mark, M. Odersky, S.-E. Panitz, D. Stoutamire, K. Thorup, and P. Wadler. Adding generics to the Java programming language: Participant draft specification. Technical report, Sun Microsystems, Apr. 27, 2001.
• 5: G. Bracha, M. Odersky, D. Stoutamire, and P. Wadler. GJ specification. http://www.cis.unisa.edu.au/ pizza/gj/Documents/#gj-specification, May 1998.
• 6: Gilad Bracha , Martin Odersky , David Stoutamire , Philip Wadler, Making the future safe for the past: adding genericity to the Java programming language, Proceedings of the 13th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.183-200, October 18-22, 1998, Vancouver, British Columbia, Canada
• 7: Luca Cardelli , Peter Wegner, On understanding types, data abstraction, and polymorphism, ACM Computing Surveys (CSUR), v.17 n.4, p.471-523, Dec. 1985 [doi>10.1145/6041.6042]
• 8: Robert Cartwright , Mike Fagan, Soft typing, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.278-292, June 24-28, 1991, Toronto, Ontario, Canada
• 9: Robert Cartwright , Guy L. Steele, Jr., Compatible genericity with run-time types for the Java programming language, Proceedings of the 13th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.201-215, October 18-22, 1998, Vancouver, British Columbia, Canada
• 10: C. Chambers , D. Ungar, Customization: optimizing compiler technology for SELF, a dynamically-typed object-oriented programming language, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.146-160, June 19-23, 1989, Portland, Oregon, United States
• 11: C. Chambers , D. Ungar , E. Lee, An efficient implementation of SELF a dynamically-typed object-oriented language based on prototypes, Conference proceedings on Object-oriented programming systems, languages and applications, p.49-70, October 02-06, 1989, New Orleans, Louisiana, United States
• 12: OmniCore CodeGuide. http://www.omnicore.com/codeguide.htm.
• 13: B. De Sutter, F. Tip, and J. Dolby. Customization of Java library classes using type constraints and profile information. In ECOOP, June 2004.
• 14: Jeffrey Dean , David Grove , Craig Chambers, Optimization of Object-Oriented Programs Using Static Class Hierarchy Analysis, Proceedings of the 9th European Conference on Object-Oriented Programming, p.77-101, August 07-11, 1995
• 15: A. Donovan. Converting Java programs to use generic libraries. Master's thesis, MIT Dept. of EECS, Sept. 2004.
• 16: A. Donovan and M. D. Ernst. Inference of generic types in Java. Technical Report MIT/ LCS/ TR-889, MIT Lab for Computer Science, Mar. 22, 2003.
• 17: Dominic Duggan, Modular type-based reverse engineering of parameterized types in Java code, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.97-113, November 01-05, 1999, Denver, Colorado, United States
• 18: Eclipse project. http://www.eclipse.org/.
• 19: Jonathan Eifrig , Scott Smith , Valery Trifonov, Sound polymorphic type inference for objects, Proceedings of the tenth annual conference on Object-oriented programming systems, languages, and applications, p.169-184, October 15-19, 1995, Austin, Texas, United States
• 20: Etienne Gagnon , Laurie J. Hendren , Guillaume Marceau, Efficient Inference of Static Types for Java Bytecode, Proceedings of the 7th International Symposium on Static Analysis, p.199-219, June 29-July 01, 2000
• 21: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 22: David Grove , Craig Chambers, A framework for call graph construction algorithms, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.6, p.685-746, November 2001 [doi>10.1145/506315.506316]
• 23: Michael Hind , Anthony Pioli, Evaluating the effectiveness of pointer alias analyses, Science of Computer Programming, v.39 n.1, p.31-55, Jan. 2001 [doi>10.1016/S0167-6423(00)00014-9]
• 24: JetBrains IntelliJ IDEA. http://www.intellij.com/idea/.
• 25: A. Igarashi, B. C. Pierce, and P. Wadler. A recipe for raw types. In FOOL, London, Jan. 2001.
• 26: Atsushi Igarashi , Mirko Viroli, On Variance-Based Subtyping for Parametric Types, Proceedings of the 16th European Conference on Object-Oriented Programming, p.441-469, June 10-14, 2002
• 27: JavaSoft, Sun Microsystems. Prototype for JSR014: Adding generics to the Java programming language v. 1.3. http://jcp.org/jsr/detail/14.html, May 7, 2001.
• 28: Barbara H. Liskov , Jeannette M. Wing, A behavioral notion of subtyping, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.6, p.1811-1841, Nov. 1994 [doi>10.1145/197320.197383]
• 29: Bruce J. McAdam , Andrew Kennedy , Nick Benton, Type inference for MLj, Selected papers from the 2nd Scottish Functional Programming Workshop (SFP00), p.159-172, July 26-28, 2000
• 30: R. Milner. A theory of type polymorphism in programming. Journal of Computer and System Sciences, 17(3):348--375, 1978.
• 31: Joseph A. Bank , Andrew C. Myers , Barbara Liskov, Parameterized types for Java, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.132-145, January 15-17, 1997, Paris, France [doi>10.1145/263699.263714]
• 32: Robert Weeks O'Callahan , Jeannette Wing , Daniel Jackson, Generalized aliasing as a basis for program analysis tools, 2001
• 33: Robert O'Callahan , Daniel Jackson, Lackwit: a program understanding tool based on type inference, Proceedings of the 19th international conference on Software engineering, p.338-348, May 17-23, 1997, Boston, Massachusetts, United States [doi>10.1145/253228.253351]
• 34: A. Ohori , P. Buneman, Static type inference for parametric classes, Conference proceedings on Object-oriented programming systems, languages and applications, p.445-450, October 02-06, 1989, New Orleans, Louisiana, United States
• 35: Jens Palsberg , Michael I. Schwartzbach, Object-oriented type inference, Conference proceedings on Object-oriented programming systems, languages, and applications, p.146-161, October 06-11, 1991, Phoenix, Arizona, United States
• 36: Jens Palsberg , Michael I. Schwartzbach, Object-oriented type systems, John Wiley and Sons Ltd., Chichester, UK, 1994
• 37: P.J. Plauger , Meng Lee , David Musser , Alexander A. Stepanov , Alexander Stepanov, C++ Standard Template Library, Prentice Hall PTR, Upper Saddle River, NJ, 2000
• 38: John Plevyak , Andrew A. Chien, Precise concrete type inference for object-oriented languages, Proceedings of the ninth annual conference on Object-oriented programming systems, language, and applications, p.324-340, October 23-28, 1994, Portland, Oregon, United States
• 39: Michael Siff , Thomas Reps, Program generalization for software reuse: from C to C++, Proceedings of the 4th ACM SIGSOFT symposium on Foundations of software engineering, p.135-146, October 16-18, 1996, San Francisco, California, United States
• 40: Bjarne Stroustrup, The design and evolution of C++, ACM Press/Addison-Wesley Publishing Co., New York, NY, 1995
• 41: Bjarne Stroustrup, The C++ Programming Language, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 42: F. Tip, R. Fuhrer, J. Dolby, and A. Kiežun. Refactoring techniques for migrating applications to generic Java container classes. IBM Research Report RC 23238, IBM T.J. Watson Research Center, Yorktown Heights, NY, USA, June 2, 2004.
• 43: Frank Tip , Adam Kiezun , Dirk Bäumer, Refactoring for generalization using type constraints, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 44: Frank Tip , Jens Palsberg, Scalable propagation-based call graph construction algorithms, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.281-293, October 2000, Minneapolis, Minnesota, United States
• 45: Mads Torgersen , Christian Plesner Hansen , Erik Ernst , Peter von der Ahé , Gilad Bracha , Neal Gafter, Adding wildcards to the Java programming language, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus [doi>10.1145/967900.968162]
• 46: R. Vallée-Rai, L. Hendren, V. Sundaresan, P. Lam, E. Gagnon, and P. Co. Soot - a Java bytecode optimization framework. In CASCON, pages 125--135, Nov. 1999.
• 47: Daniel von Dincklage , Amer Diwan, Converting Java classes to use generics, Proceedings of the 19th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 24-28, 2004, Vancouver, BC, Canada
• 48: Tiejun Wang , Scott F. Smith, Precise Constraint-Based Type Inference for Java, Proceedings of the 15th European Conference on Object-Oriented Programming, p.99-117, June 18-22, 2001
• 49: Dachuan Yu , Andrew Kennedy , Don Syme, Formalization of generics for the .NET common language runtime, Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.39-51, January 14-16, 2004, Venice, Italy

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.5 Object-oriented Programming

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Modules and interfaces
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures

General Terms:
Experimentation, Languages, Theory

Keywords:
JSR-14, Java 1.5, Java 5, generic types, instantiation types, parameterized types, parametric polymorphism, raw types, type inference