Associated types and constraint propagation for mainstream object-oriented generics

ABSTRACT

Support for object-oriented programming has become an integral part of mainstream languages, and more recently generic programming has gained widespread acceptance as well. A natural question is how these two paradigms, and their underlying language mechanisms, should interact. One particular design option, that of using subtyping to constrain the type parameters of generic functions, has been chosen in the generics of Java and those planned for a future revision of C#.Certain shortcomings have previously been identified in using subtyping for constraining parametric polymorphism in the context of generic programming.To address these, we propose extending object-oriented interfaces and subtyping to include associated types and constraint propagation.Associated types are type members of interfaces and classes. Constraint propagation allows certain constraints on type parameters to be inferred from other constraints on those parameters and their use in base class type expressions.The paper demonstrates these extensions in the context of C# (with generics), describes a translation of the extended features to C#, and presents a formalism proving their safety. The formalism is applicable to other mainstream object-oriented languages supporting F-bounded polymorphism, such as Java.

REFERENCES

• 1: Stepanov, A., Lee, M.: The Standard Template Library. Technical Report HPL-94-34(R.1), Hewlett-Packard Laboratories (1994) http://www.hpl.hp.com/techreports.
• 2: Stepanov, A.: The Standard Template Library --- how do you build an algorithm that is both generic and efficient? Byte Magazine 20 (1995)
• 3: An, P., Jula, A., Rus, S., Saunders, S., Smith, T., Tanase, G., Thomas, N., Amato, N., Rauchwerger, L.: STAPL: An adaptive, generic parallel C++ library. In: Languages and Compilers for Parallel Computing. Volume 2624 of Lecture Notes in Computer Science. Springer (2001) 193--208
• 4: The boost graph library: user guide and reference manual, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2002
• 5: Siek, J., Lumsdaine, A.: A modern framework for portable high performance numerical linear algebra. In: Modern Software Tools for Scientific Computing. Birkhäuser (1999)
• 6: Pitt, W.R., Williams, M.A., Steven, M., Sweeney, B., Bleasby, A.J., Moss, D.S.: The Bioinformatics Template Library--generic components for biocomputing. Bioinformatics 17 (2001) 729--737
• 7: Microsoft Corporation: C# Version 2.0 Specification, March 2005 Draft. (2005) http://msdn.microsoft.com/vcsharp/programming/language.
• 8: Ronald Garcia , Jaakko Jarvi , Andrew Lumsdaine , Jeremy G. Siek , Jeremiah Willcock, A comparative study of language support for generic programming, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 9: O. L. Madsen , B. Moller-Pedersen, Virtual classes: a powerful mechanism in object-oriented programming, Conference proceedings on Object-oriented programming systems, languages and applications, p.397-406, October 02-06, 1989, New Orleans, Louisiana, United States
• 10: Thorup, K.K.: Genericity in Java with virtual types. In: ECOOP '97. Volume 1241 of Lecture Notes in Computer Science. (1997) 444--471
• 11: Peter Canning , William Cook , Walter Hill , Walter Olthoff , John C. Mitchell, F-bounded polymorphism for object-oriented programming, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.273-280, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99392]
• 12: Atsushi Igarashi , Benjamin C. Pierce , Philip Wadler, Featherweight Java: a minimal core calculus for Java and GJ, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.3, p.396-450, May 2001 [doi>10.1145/503502.503505]
• 13: Andrew Kennedy , Don Syme, Transposing F to C^♯: expressivity of parametric polymorphism in an object-oriented language: Research Articles, Concurrency and Computation: Practice & Experience, v.16 n.7, p.707-733, June 2004 [doi>10.1002/cpe.v16:7]
• 14: Selected Papers from the International Seminar on Generic Programming, April 1998
• 15: Kapur, D., Musser, D.: Tecton: a framework for specifying and verifying generic system components. Technical Report RPI--92--20, Department of Computer Science, Rensselaer Polytechnic Institute, Troy, New York 12180 (1992)
• 16: Austern, M.H.: Generic Programming and the STL. Professional computing series. Addison-Wesley (1999)
• 17: Silicon Graphics, Inc.: SGI Implementation of the Standard Template Library. (2004) http://www.sgi.com/tech/stl/.
• 18: International Organization for Standardization: ISO/IEC 14882:1998: Programming languages --- C++, Geneva, Switzerland (1998)
• 19: Bruce, K.B., Fiech, A., Petersen, L.: Subtyping is not a good "match" for object-oriented languages. In: ECOOP '97. Volume 1241 of Lecture Notes in Computer Science., Springer-Verlag (1997) 104--127
• 20: Kresten Krab Thorup , Mads Torgersen, Unifying Genericity - Combining the Benefits of Virtual Types and Parameterized Classes, Proceedings of the 13th European Conference on Object-Oriented Programming, p.186-204, June 14-18, 1999
• 21: Nathaniel Nystrom , Stephen Chong , Andrew C. Myers, Scalable extensibility via nested inheritance, Proceedings of the 19th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 24-28, 2004, Vancouver, BC, Canada
• 22: Torgersen, M.: Virtual types are statically safe. In: FOOL 5: Workshop on Foundations of Object-Oriented Languages. (1998) http://pauillac.inria.fr/~remy/fool/.
• 23: Kim Bruce , Luca Cardelli , Giuseppe Castagna , Gary T. Leavens , Benjamin Pierce, On binary methods, Theory and Practice of Object Systems, v.1 n.3, p.221-242, Fall 1995
• 24: Kim B. Bruce , Martin Odersky , Philip Wadler, A Statically Safe Alternative to Virtual Types, Proceedings of the 12th European Conference on Object-Oriented Programming, p.523-549, July 20-24, 1998
• 25: Bruce, K.B., Vanderwaart, J.C.: Semantics-driven language design: Statically type-safe virtual types in object-oriented languages. In: Mathematical Foundations of Programming Semantics. Volume 20 of Electronic Notes in Theoretical Computer Science. (2000)
• 26: Erik Ernst, Family Polymorphism, Proceedings of the 15th European Conference on Object-Oriented Programming, p.303-326, June 18-22, 2001
• 27: Odersky, M., Cremet, V., Röckl, C., Zenger, M.: A nominal theory of objects with dependent types. In: ECOOP '03. Volume 2743 of Lecture Notes in Computer Science., Springer-Verlag (2003) 201--224
• 28: Odersky, M., Altherr, P., Cremet, V., Emir, B., et al.: The Scala Language Specification. Programming Methods Laboratory, EPFL. Version 1.0 edn. (2005) http://scala.epfl.ch/docu/files/ScalaReference.pdf.
• 29: Odersky, M., Zenger, C.: Nested types. In: FOOL 8: Workshop on Foundations of Object-Oriented Languages. (2001)
• 30: Myers, N.: A new and useful technique: "traits". C++ Report 7 (1995) 32--35
• 31: Robin Milner , Mads Tofte , Robert Harper, The definition of Standard ML, MIT Press, Cambridge, MA, 1990
• 32: Mark P. Jones, Type Classes with Functional Dependencies, Proceedings of the 9th European Symposium on Programming Languages and Systems, p.230-244, April 02, 2000
• 33: Manuel M. T. Chakravarty , Gabriele Keller , Simon Peyton Jones , Simon Marlow, Associated types with class, Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-13, January 12-14, 2005, Long Beach, California, USA
• 34: Manuel M. T. Chakravarty , Gabriele Keller , Simon Peyton Jones, Associated type synonyms, Proceedings of the tenth ACM SIGPLAN international conference on Functional programming, September 26-28, 2005, Tallinn, Estonia
• 35: Chambers, C., the Cecil Group: The Cecil Language: Specification and Rationale, Version 3.1. University of Washington, Computer Science and Engineering. (2002) http://www.cs.washington.edu/research/projects/cecil/.
• 36: 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]
• 37: Torgersen, M., Ernst, E., Hansen, C.P.: Wild FJ. In: FOOL 12: Workshop on Foundations of Object-Oriented Languages. (2005)
• 38: P. Wadler , S. Blott, How to make ad-hoc polymorphism less ad hoc, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.60-76, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75283]
• 39: http://research.cs.tamu.edu/jarvi/csharp (2005)

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Classes and objects

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: C#; Java
      D.3.3 Language Constructs and Features
          Subjects: Polymorphism

General Terms:
Languages

Keywords:
C#, Java, associated, constraint propagation, generic programming, generics, types