A comparative study of language support for generic programming

ABSTRACT

Many modern programming languages support basic generic programming, sufficient to implement type-safe polymorphic containers. Some languages have moved beyond this basic support to a broader, more powerful interpretation of generic programming, and their extensions have proven valuable in practice. This paper reports on a comprehensive comparison of generics in six programming languages: C++, Standard ML, Haskell, Eiffel, Java (with its proposed generics extension), and Generic C. By implementing a substantial example in each of these languages, we identify eight language features that support this broader view of generic programming. We find these features are necessary to avoid awkward designs, poor maintainability, unnecessary run-time checks, and painfully verbose code. As languages increasingly support generics, it is important that language designers understand the features necessary to provide powerful generics and that their absence causes serious difficulties for programmers.

REFERENCES

• 1: M. H. Austern. Generic Programming and the STL. Professional computing series. Addison-Wesley, 1999.
• 2: R. Backhouse, P. Jansson, J. Jeuring, and L. Meertens. Generic programming --- an introduction. In LNCS, volume 1608, pages 28--115. Springer-Verlag, 1999. Revised version of lecture notes for AFP'98.
• 3: G. Baumgartner, M. Jansche, and K. Laufer. Half & Half: Multiple Dispatch and Retroactive Abstraction for Java. Technical Report OSU-CISRC-5/01-TR08, Ohio State University, 2002.
• 4: R. Bellman. On a routing problem. Quarterly of Applied Mathematics, 16(1):87--90, 1958.
• 5: G. Bracha and J. Bloch. JSR 201: Extending the Java Programming Language with Enumerations, Autoboxing, Enhanced for loops and Static Import, December 2002. http://www.jcp.org/en/jsr/detail?id=201.
• 6: G. Bracha, N. Cohen, C. Kemper, S. Marx, et al. JSR 14: Add Generic Types to the Java Programming Language, April 2001. http://www.jcp.org/en/jsr/detail?id=014.
• 7: 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
• 8: K. B. Bruce. Typing in object-oriented languages: Achieving expressibility and safety. Technical report, Williams College, 1996.
• 9: Martin Büchi , Wolfgang Weck, Compound types for Java, Proceedings of the 13th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.362-373, October 18-22, 1998, Vancouver, British Columbia, Canada
• 10: 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
• 11: Chris Cleeland , Douglas C. Schmidt , Tim Harrison, External polymorphism, Pattern languages of program design 3, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 12: W. R. Cook, A proposal for making Eiffel type-safe, The Computer Journal, v.32 n.4, p.305-311, Aug. 1989 [doi>10.1093/comjnl/32.4.305]
• 13: E. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269--271, 1959.
• 14: A. Hejlsberg. The C programming language. Invited talk at Object-Oriented Programming, Systems, Languages and Applications (OOPSLA), 2002.
• 15: R. Hinze and J. Jeuring. Generic Haskell: Practice and theory. In Summer School on Generic Programming, LNCS. Springer-Verlag, 2002/2003.
• 16: M. Howard, E. Bezault, B. Meyer, D. Colnet, E. Stapf, K. Arnout, and M. Keller. Type-safe covariance: competent compilers can catch all catcalls. Apr. 2003.
• 17: International Standardization Organization (ISO). ANSI/ISO Standard 14882, Programming Language C++. 1 rue de Varembe, Case postale 56, CH-1211 Geneve 20, Switzerland, 1998.
• 18: M. Jazayeri, R. Loos, D. Musser, and A. Stepanov. Generic Programming. In Report of the Dagstuhl Seminar on Generic Programming, Schloss Dagstuhl, Germany, Apr. 1998.
• 19: Johan Jeuring , Patrik Jansson, Polytypic Programming, Advanced Functional Programming, Second International School-Tutorial Text, p.68-114, August 26-30, 1996
• 20: 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
• 21: S. P. Jones, J. Hughes, et al. Haskell 98: A Non-strict, Purely Functional Language, February 1999. http://www.haskell.org/onlinereport/.
• 22: S. P. Jones, M. Jones, and E. Meijer. Type classes: an exploration of the design space. In Haskell Workshop, June 1997.
• 23: Nicolai M. Josuttis, The C++ standard library: a tutorial and reference, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 24: Andrew Kennedy , Don Syme, Design and implementation of generics for the .NET Common language runtime, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.1-12, June 2001, Snowbird, Utah, United States
• 25: Gregor Kiczales , Erik Hilsdale , Jim Hugunin , Mik Kersten , Jeffrey Palm , William G. Griswold, An Overview of AspectJ, Proceedings of the 15th European Conference on Object-Oriented Programming, p.327-353, June 18-22, 2001
• 26: G. Kiczales, J. Lamping, A. Mendhekar, C. Maeda, C. V. Lopes, J.-M. Loingtier, and J. Irwin. Aspect-oriented programming. In M. Akcsit and S. Matsuoka, editors, ECOOP'97 -- Object-Oriented Programming, vol. 1241 of Lecture Notes in Computer Science, pages 220--242, 1994.
• 27: K. Laufer, G. Baumgartner, and V. F. Russo. Safe structural conformance for Java. Computer Journal, 43(6):469--481, 2001.
• 28: B. Magnusson. Code reuse considered harmful. Journal of Object-Oriented Programming, 4(3), Nov. 1991.
• 29: B. McNamara and Y. Smaragdakis. Static interfaces in C++. In First Workshop on C++ Template Programming, October 2000.
• 30: Bertrand Meyer, Eiffel: the language, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 31: Bertrand Meyer, Static typing, Addendum to the proceedings of the 10th annual conference on Object-oriented programming systems, languages, and applications (Addendum), p.20-29, October 15-19, 1995, Austin, Texas, United States
• 32: B. Meyer. The start of an Eiffel standard. Journal of Object Technology, 1(2):95--99, July/August 2002. www.jot.fm.
• 33: Microsoft Corporation. Generics in C, September 2002. Part of the Gyro distribution of generics for .NET {34}.
• 34: Microsoft Corporation. Generics for C and .NET CLR, May 2003. http://research.microsoft.com/projects/clrgen/.
• 35: Robin Milner , Mads Tofte , David Macqueen, The Definition of Standard ML, MIT Press, Cambridge, MA, 1997
• 36: 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]
• 37: N. C. Myers. Traits: a new and useful template technique. C++ Report, June 1995.
• 38: M. Odersky. Inferred type instantiation without prototypes for GJ. lampwww.epfl.ch/~odersky/ftp/local-ti.ps, Jan. 2002.
• 39: R. Prim. Shortest connection networks and some generalizations. Bell System Technical Journal, 36:1389--1401, 1957.
• 40: N. Ramsey. Toward a calculus of signatures. http://www.eecs.harvard.edu/~nr/pubs/sigcalc-abstract.html, October 2001.
• 41: The boost graph library: user guide and reference manual, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2002
• 42: J. Siek and A. Lumsdaine. Concept checking: Binding parametric polymorphism in C++. In First Workshop on C++ Template Programming, October 2000.
• 43: Lie-Quan Lee , Jeremy G. Siek , Andrew Lumsdaine, The generic graph component library, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.399-414, November 01-05, 1999, Denver, Colorado, United States
• 44: Jeremy G. Siek , Andrew Lumsdaine, The Matrix Template Library: A Generic Programming Approach to High Performance Numerical Linear Algebra, Proceedings of the Second International Symposium on Computing in Object-Oriented Parallel Environments, p.59-70, December 08-11, 1998
• 45: A. A. Stepanov and M. Lee. The Standard Template Library. Technical Report X3J16/94-0095, WG21/N0482, ISO Programming Language C++ Project, May 1994.
• 46: Bjarne Stroustrup, The design and evolution of C++, ACM Press/Addison-Wesley Publishing Co., New York, NY, 1995
• 47: Todd L. Veldhuizen, Arrays in Blitz++, Proceedings of the Second International Symposium on Computing in Object-Oriented Parallel Environments, p.223-230, December 08-11, 1998

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
        D.2.13 Reusable Software
            Subjects: Reusable libraries

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Multiparadigm languages
      D.3.3 Language Constructs and Features
          Subjects: Constraints; Abstract data types; Polymorphism

General Terms:
Design, Languages, Standardization

Keywords:
C#, C++, Eiffel, Haskell, Java, generic programming, generics, polymorphism, standard ML