Hostname: page-component-745bb68f8f-cphqk Total loading time: 0 Render date: 2025-01-21T16:49:10.527Z Has data issue: false hasContentIssue false
  • English
  • Français

An extended comparative study of language support for generic programming

Published online by Cambridge University Press:  01 March 2007

RONALD GARCIA ,
JAAKKO JARVI ,
ANDREW LUMSDAINE ,
JEREMY SIEK  and
JEREMIAH WILLCOCK
RONALD GARCIA
Affiliation:
Open Systems Lab, Indiana University, Bloomington, IN, USA (e-mail: garcia@osl.iu.edu, lums@osl.iu.edu, jewillco@osl.iu.edu)
JAAKKO JARVI
Affiliation:
Texas A&M University, Computer Science, College Station, TX, USA (e-mail: jarvi@cs.tamu.edu)
ANDREW LUMSDAINE
Affiliation:
Open Systems Lab, Indiana University, Bloomington, IN, USA (e-mail: garcia@osl.iu.edu, lums@osl.iu.edu, jewillco@osl.iu.edu)
JEREMY SIEK
Affiliation:
Rice University, Computer Science, Houston, TX, USA (e-mail: jeremy.g.siek@rice.edu)
JEREMIAH WILLCOCK
Affiliation:
Open Systems Lab, Indiana University, Bloomington, IN, USA (e-mail: garcia@osl.iu.edu, lums@osl.iu.edu, jewillco@osl.iu.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Many modern programming languages support basic generics, sufficient to implement type-safe polymorphic containers. Some languages have moved beyond this basic support, and in doing so have enabled a broader, more powerful form of generic programming. This paper reports on a comprehensive comparison of facilities for generic programming in eight programming languages: C++, Standard ML, Objective Caml, Haskell, Eiffel, Java, C# (with its proposed generics extension), and Cecil. By implementing a substantial example in each of these languages, we illustrate how the basic roles of generic programming can be represented in each language. We also identify eight language properties that support this broader view of generic programming: support for multi-type concepts, multiple constraints on type parameters, convenient associated type access, constraints on associated types, retroactive modeling, type aliases, separate compilation of algorithms and data structures, and implicit argument type deduction for generic algorithms. We find that these features are necessary to avoid awkward designs, poor maintainability, and painfully verbose code. As languages increasingly support generics, it is important that language designers understand the features necessary to enable the effective use of generics and that their absence can cause difficulties for programmers.

Type
Article
Information
Journal of Functional Programming , Volume 17 , Issue 2 , March 2007 , pp. 145 - 205
Copyright
Copyright © Cambridge University Press 2006

References

Austern, M. H. (1998) Generic programming and the STL: Using and extending the C++ Standard Template Library. Professional Computing Series. Boston, MA, USA: Addison-Wesley.Google Scholar
Backhouse, R., Jansson, P., Jeuring, J. & Meertens, L. (1999). In: Pages 28–115 of: Swierstra, S. D., Doaitse, H., Rangel, P. and Oliveira, J. M. (eds.), Advanced Functional Programming, Third International School, Braga, Portugal, revised lectures. Lecture Notes in Computer Science, vol. 1608. Springer-Verlag.Google Scholar
Baumgartner, G., Jansche, M. & Läufer, K. (2002) Half & Half: Multiple Dispatch and Retroactive Abstraction for Java. Tech. rept. OSU-CISRC-5/01-TR08. Ohio State University.Google Scholar
Bellman, R. (1958) On a routing problem. Quart. J. Appl. Math. 16 (1), 87–90.CrossRefGoogle Scholar
Bracha, G., Odersky, M., Stoutamire, D. & Wadler, P. (1998) Making the future safe for the past: adding genericity to the Java programming language. Pages 183–200 of: OOPSLA '98: Proceedings of the 13th ACM SIGPLAN Conference on Object-oriented Programming, Systems, Languages, and Applications. ACM Press.CrossRefGoogle Scholar
Bruce, K. B. (1996) Typing in object-oriented languages: Achieving expressibility and safety. Tech. rept. Williams College.Google Scholar
Chakravarty, M. M. T., Keller, G. & PeytonJones, S. Jones, S. (2005a) Associated type synonyms. ICFP '05: Proceedings of the International Conference on Functional Programming. ACM Press.CrossRefGoogle Scholar
Chakravarty, M. M. T., Keller, G., Peyton Jones, S. & Marlow, S. (2005b) Associated types with class. Pages 1–13 of: POPL '05: Proceedings of the 32nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM Press.CrossRefGoogle Scholar
Chambers, C. & the Cecil Group. (2002) The Cecil language: Specification and rationale, version 3.1. University of Washington, Computer Science and Engineering. http://www.cs.washington.edu/research/projects/cecil/.Google Scholar
Cleeland, C., Schmidt, D. C. & Harrison, T. H. (1997) External polymorphism – an object structural pattern for transparently extending C++ concrete data types. In: Martin, R. C., Riehle, D. & Buschmann, F. (eds.), Pattern Languages of Program Design. Software Pattern Series, vol. 3. Addison-Wesley.Google Scholar
Cook, W. R. (1989) A proposal for making Eiffel type-safe. The Comput. J. 32 (4), 304–311.CrossRefGoogle Scholar
Dijkstra, E. W. (1959) A note on two problems in connexion with graphs. Numerische Mathematik, 1, 269–271.CrossRefGoogle Scholar
ECMA (2005) Standard: Eiffel analysis, design and programming language. ECMA International. Draft 5.00.00-1.Google Scholar
Gamma, E., Helm, R., Johnson, R. & Vlissides, J. (1995) Design Patterns: Elements of reusable object-oriented software. Professional Computing Series. Addison-Wesley Longman.Google Scholar
Garcia, R., Järvi, J., Lumsdaine, A., Siek, J. & Willcock, J. (2003) A comparative study of language support for generic programming. Pages 115–134 of: OOPSLA '03: Proceedings of the 18th Annual ACM SIGPLAN Conference on Object-oriented Programing, Systems, Languages, and Applications. ACM Press.CrossRefGoogle Scholar
Gosling, J., Joy, B., Steele, G. & Bracha, G. (2005) The Java language specification, third edition. Addison-Wesley Longman.Google Scholar
Graph Library URL (2005) Available at http://www.osl.iu.edu/research/comparing/.Google Scholar
Haack, C. & Wells, J. B. (2003) Type error slicing in implicitly typed higher-order languages. In: Pages 284–301 of: Degano, P. (ed.), Programming languages and systems: 12th European Symposium on Programming, ESOP 2003, Warsaw, Poland. Lecture Notes in Computer Science, vol. 2618. New York, NY: Springer-Verlag.CrossRefGoogle Scholar
Hinze, R. & Jeuring, J. (2003) Generic Haskell: Practice and theory. In: Pages 1–56 of: Backhouse, R. & Gibbons, J. (eds.), Generic programming: Advanced lectures. Lecture Notes in Computer Science, vol. 2793. Springer-Verlag.CrossRefGoogle Scholar
Howard, M., Bezault, Eric, Meyer, Bertrand, Colnet, Dominique, Emmanuel, Stapf, Arnout, K. & Keller, M. (2003) Type-safe covariance: competent compilers can catch all catcalls. http://www.inf.ethz.ch/meyer/.Google Scholar
Järvi, J., Willcock, J. & Lumsdaine, A. (2005) Associated types and constraint propagation for mainstream object-oriented generics. OOPSLA '05: Proceedings of the 20th Annual ACM SIGPLAN Conference on Object-oriented Programing, Systems, Languages, and Applications. To appear.CrossRefGoogle Scholar
Jazayeri, M., Loos, R., Musser, D. & Stepanov, A. 1998 (Apr.) Generic Programming. Report of the Dagstuhl seminar on generic programming.Google Scholar
Jeuring, J. & Jansson, P. (1996) Polytypic programming. In: Pages 68–114 of: Launchbury, J., Meijer, E. & Sheard, T. (eds.), Advanced functional programming, second international school-tutorial text. Lecture Notes in Computer Science, vol. 1129. Springer-Verlag.CrossRefGoogle Scholar
Jones, M. P. (2000) Type classes with functional dependencies. Pages 230–244 of: ESOP '00: Proceedings of the 9th European Symposium on Programming Languages and Systems. Lecture Notes in Computer Science, vol. 1782. Springer-Verlag.CrossRefGoogle Scholar
Kennedy, A. & Syme, D. (2001) Design and implementation of generics for the. NET Common Language Runtime. Pages 1–12 of: PLDI '01: Proceedings of the ACM SIGPLAN 2001 Conference on Programming Language Design and Implementation. ACM Press.CrossRefGoogle Scholar
Kiczales, G., Lamping, J., Mendhekar, A., Maeda, C., Lopes, C., Loingtier, J.-M. & Irwin, J. (1997) Aspect-oriented programming. In: Pages 220–242 of: Akşit, M. & Matsuoka, S. (eds.), ECOOP '97 – Object-oriented Programming 11th European Conference, Jyväskylä, Finland. Lecture Notes in Computer Science, vol. 1241. Springer-Verlag.CrossRefGoogle Scholar
Kiczales, G., Hilsdale, E., Hugunin, J., Kersten, M., Palm, J. & Griswold, W. G. (2001) An overview of AspectJ. In: Pages 327–353 of: Knudsen, J. L. (ed.), ECOOP 2001 – Object-oriented Programming 15th European Conference. Lecture Notes in Computer Science, vol. 2072. Springer-Verlag.CrossRefGoogle Scholar
Läufer, K., Baumgartner, G. & Russo, V. F. (2000) Safe structural conformance for Java. The Comput. J. 43 (6), 469–481.CrossRefGoogle Scholar
Lee, L.-Q., Siek, J. G. & Lumsdaine, A. (1999) The Generic Graph Component Library. Pages 399–414 of: OOPSLA '99: Proceedings of the 14th ACM SIGPLAN Conference on Object-oriented Programming, Systems, Languages, and Applications. ACM Press.CrossRefGoogle Scholar
Leroy, X. (2000) The Objective Caml system: Documentation and user's manual. With Damien Doligez, Jacques Garrigue, Didier Rémy, and Jérôme Vouillon.Google Scholar
Leroy, X., Doligez, D., Garrigue, J., Rémy, D. & Vouillon, J. (2003) The Objective Caml documentation and user's manual.Google Scholar
Litvinov, V. (1998) Contraint-based polymorphism in Cecil: towards a practical and static type system. Pages 388–411 of: OOPSLA '98: Proceedings of the 13th ACM SIGPLAN Conference on Object-oriented Programming, Systems, Languages, and Applications. ACM Press.CrossRefGoogle Scholar
Magnusson, B. (1991) Code reuse considered harmful. J. Object-oriented Program. 4 (3).Google Scholar
McNamara, B. & Smaragdakis, Y. (2000) Static interfaces in C++. First Workshop on C++ Template Programming.Google Scholar
Meyer, B. (1992) Eiffel: The language. First edn. Prentice Hall.Google Scholar
Meyer, B. (1995) Static typing. Pages 20–29 of: OOPSLA '95: Addendum to the Proceedings of the 10th Annual Conference on Object-oriented Programming Systems, Languages, and Applications. ACM Press.CrossRefGoogle Scholar
Meyer, B. (2002) The start of an Eiffel standard. J. Object Technology, 1 (2), 95–99. http://www.jot.fm/.CrossRefGoogle Scholar
Microsoft Corporation (2002) Generics in C#. Part of the Gyro distribution of generics for .NET available at http://research.microsoft.com/projects/clrgen/.Google Scholar
Microsoft Corporation (2005) C# version 2.0 specification, march 2005 draft. http://-msdn.-microsoft.-com/vcsharp/-programming/-language.Google Scholar
Milner, R., Tofte, M., Harper, R. & MacQueen, D. (1997) The definition of Standard ML (revised). MIT Press.CrossRefGoogle Scholar
Myers, N. C. (1995) Traits: a new and useful template technique. C++ report.Google Scholar
PeytonJones, S. Jones, S., Jones, M. & Meijer, E. (1997) Type classes: an exploration of the design space. Proceedings of the Second Haskell Workshop.Google Scholar
Peyton Jones, S., Hughes, J. et al. (1999) Haskell 98: A non-strict, purely functional language. http://www.haskell.org/onlinereport/.Google Scholar
Prim, R. C. (1957) Shortest connection networks and some generalizations. Bell system technical journal, 36, 1389–1401.CrossRefGoogle Scholar
Ramsey, N., Fisher, K. & Govereau, P. (2005) An expressive language of signatures. ICFP '05: Proceedings of the Tenth ACM SIGPLAN International Conference on Functional Programming. To appear.CrossRefGoogle Scholar
Rémy, D. & Vouillon, J. (1997) Objective ML: a simple object-oriented extension of ML. Pages 40–53 of: POPL '97: Proceedings of the 24th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM Press.CrossRefGoogle Scholar
Rémy, D. & Vouillon, J. (1998) The reality of virtual types for free! Unpublished note available electronically.Google Scholar
Siek, J. (2005) A language for generic programming. Ph.D. thesis, Indiana University.CrossRefGoogle Scholar
Siek, J. & Lumsdaine, A. (2000) Concept checking: Binding parametric polymorphism in C++. First Workshop on C++ Template Programming.Google Scholar
Siek, J. & Lumsdaine, A. (2005a) Essential language support for generic programming. Pages 73–84 of: PLDI '05: Proceedings of the ACM SIGPLAN 2005 Conference on Programming Language Design and Implementation. ACM Press.CrossRefGoogle Scholar
Siek, J. & Lumsdaine, A. (2005b) Language requirements for large-scale generic libraries. GPCE '05: Proceedings of the Fourth International Conference on Generative Programming and Component Engineering. To appear.CrossRefGoogle Scholar
Siek, J., Lee, L.-Q. & Lumsdaine, A. (2002) The Boost Graph Library: User guide and reference manual. Addison-Wesley Longman.Google Scholar
Siek, J., Gregor, D., Garcia, R., Willcock, J., Järvi, J. & Lumsdaine, A. (2005) Concepts for C++0x. Tech. rept. N1758=05-0018. ISO/IEC JTC 1, Information Technology, Subcommittee SC 22, Programming Language C++.Google Scholar
Stroustrup, B. (1994) Design and evolution of C++. Addison-Wesley Longman.Google Scholar
Stroustrup, B. & DosReis, G. Reis, G. (2005) A concept design (rev. 1). Tech. rept. N1782=05-0042. ISO/IEC JTC 1, Information Technology, Subcommittee SC 22, Programming Language C++.Google Scholar
Torgersen, M., Hansen, C. P., Ernst, E., vonder Ahé, P. der Ahé, P., Bracha, G. & Gafter, N. (2004) Adding wildcards to the Java programming language. Pages 1289–1296 of: SAC '04: Proceedings of the 2004 ACM Symposium on Applied Computing. ACM Press.CrossRefGoogle Scholar
Submit a response

Discussions

No Discussions have been published for this article.