Essential language support for generic programming

ABSTRACT

Concepts are an essential language feature for generic programming in the large. Concepts allow for succinct expression of constraints on type parameters of generic algorithms, enable systematic organization of problem domain abstractions, and make generic algorithms easier to use. In this paper we present the design of a type system and semantics for concepts that is suitable for non-type-inferencing languages. Our design shares much in common with the type classes of Haskell, though our primary influence is from best practices in the C++ community, where concepts are used to document type requirements for templates in generic libraries. Concepts include a novel combination of associated types and same-type constraints that do not appear in type classes, but that are similar to nested types and type sharing in ML.

REFERENCES

• 1: Ada 95 Reference Manual, 1997.
• 2: Jean-Daniel Boissonnat , Frédéric Cazals , Frank Da , Olivier Devillers , Sylvain Pion , François Rebufat , Monique Teillaud , Mariette Yvinec, Programming with CGAL: the example of triangulations, Proceedings of the fifteenth annual symposium on Computational geometry, p.421-422, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.305001]
• 3: Boost. Boost C++ Libraries. http://www.boost.org/.
• 4: 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.
• 5: Kim B. Bruce , Angela Schuett , Robert van Gent, PolyTOIL: A Type-Safe Polymorphic Object-Oriented Language, Proceedings of the 9th European Conference on Object-Oriented Programming, p.27-51, August 07-11, 1995
• 6: 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]
• 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: 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
• 9: Kung Chen , Paul Hudak , Martin Odersky, Parametric type classes, Proceedings of the 1992 ACM conference on LISP and functional programming, p.170-181, June 22-24, 1992, San Francisco, California, United States
• 10: G. J. Ditchfield. Contextual polymorphism, 1994.
• 11: G. J. Ditchfield. Cforall reference manual and rationale, 1997.
• 12: E. Ernst. gbeta -- a Language with Virtual Attributes, Block Structure, and Propagating, Dynamic Inheritance. PhD thesis, Department of Computer Science, University of Aarhus, AArhus, Denmark, 1999.
• 13: Erik Ernst, Family Polymorphism, Proceedings of the 15th European Conference on Object-Oriented Programming, p.303-326, June 18-22, 2001
• 14: 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
• 15: J.-Y. Girard. Interprétation Fonctionnelle et Élimination des Coupures de l'Arithmetique d'Ordre Superieur. Thèse de doctorat d'état, Université Paris VII, Paris, France, 1972.
• 16: J. A. Goguen, T. Winker, J. Meseguer, K. Futatsugi, and J.-P. Jouannaud. Introducing OBJ. In Applications of Algebraic Specification using OBJ. Cambridge University Press, 1992.
• 17: Cordelia V. Hall , Kevin Hammond , Simon L. Peyton Jones , Philip L. Wadler, Type classes in Haskell, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.2, p.109-138, March 1996 [doi>10.1145/227699.227700]
• 18: International Standardization Organization (ISO). ANSI/ISO Standard 14882, Programming Language C++. 1 rue de Varembé, Case postale 56, CH-1211 Genève 20, Switzerland, 1998.
• 19: J. Järvi, A. Lumsdaine, J. Siek, and J. Willcock. An analysis of constrained polymorphism for generic programming. In K. Davis and J. Striegnitz, editors, Multiparadigm Programming in Object-Oriented Languages Workshop (MPOOL) at OOPSLA, Anaheim, CA, Oct. 2003.
• 20: J. Järvi, J. Willcock, and A. Lumsdaine. Algorithm specialization and concept constrained genericity. In Concepts: a Linguistic Foundation of Generic Programming. Adobe Systems, Apr. 2004.
• 21: 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
• 22: W. Kahl and J. Scheffczyk. Named instances for Haskell type classes. In R. Hinze, editor, Proc. Haskell Workshop 2001, volume 59 of ENTCS, 2001. See also: http://ist.unibw-muenchen.de/Haskell/NamedInstances/.
• 23: D. Kapur and D. Musser. 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, July 1992.
• 24: D. Kapur , D. R. Musser, An overview of the Tecton proof system, Theoretical Computer Science, v.133 n.2, p.307-339, Oct. 24, 1994 [doi>10.1016/0304-3975(94)90192-9]
• 25: D. Kapur , D. R. Musser , A. A. Stepanov, Operators and algebraic structures, Proceedings of the 1981 conference on Functional programming languages and computer architecture, p.59-64, October 18-22, 1981, Portsmouth, New Hampshire, United States [doi>10.1145/800223.806763]
• 26: Dinesh Katiyar , David Luckham , John Mitchell, A type system for prototyping languages, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.138-150, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.177838]
• 27: 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
• 28: A. Kershenbaum, D. Musser, and A. Stepanov. Higher order imperative programming. Technical Report 88-10, Rensselaer Polytechnic Institute, 1988.
• 29: U. Köthe. Handbook on Computer Vision and Applications, volume 3, chapter Reusable Software in Computer Vision. Acadamic Press, 1999.
• 30: Didier Le Botlan , Didier Rémy, ML^F: raising ML to the power of system F, Proceedings of the eighth ACM SIGPLAN international conference on Functional programming, p.27-38, August 25-29, 2003, Uppsala, Sweden
• 31: X. Leroy, D. Doligez, J. Garrigue, D. Remy, and J. Vouillon. The Object Caml Documentation and User's Manual, September 2003.
• 32: B. Liskov , R. R. Atkinson , T. Bloom , E. B. Moss , R. Schaffert , A. Snyder, CLU REFERENCE MANUAL, Massachusetts Institute of Technology, Cambridge, MA, 1979
• 33: Barbara Liskov, Abstraction and specification in program development, MIT Press, Cambridge, MA, 1986
• 34: David MacQueen, An implementation of standard ML modules, Proceedings of the 1988 ACM conference on LISP and functional programming, p.212-223, July 25-27, 1988, Snowbird, Utah, United States [doi>10.1145/62678.62704]
• 35: Bertrand Meyer, Eiffel: the language, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 36: Microsoft Corporation. Generics in C, September 2002. Part of the Gyro distribution of generics for .NET available at http://research.microsoft.com/projects/clrgen/.
• 37: Robin Milner , Mads Tofte , Robert Harper, The Definition of Standard ML, MIT Press, Cambridge, MA, 1990
• 38: John C. Mitchell, Polymorphic type inference and containment, Information and Computation, v.76 n.2-3, p.211-249, February/March 1988 [doi>10.1016/0890-5401(88)90009-0]
• 39: David R. Musser , Alexander A. Stepanov, Generic Programming, Proceedings of the International Symposium ISSAC'88 on Symbolic and Algebraic Computation, p.13-25, July 04-08, 1988
• 40: David R. Musser , Alexander A. Stepanov, A library of generic algorithms in Ada, Proceedings of the 1987 annual ACM SIGAda international conference on Ada, p.216-225, December 1987, Boston, Massachusetts, United States [doi>10.1145/317500.317529]
• 41: Greg Nelson , Derek C. Oppen, Fast Decision Procedures Based on Congruence Closure, Journal of the ACM (JACM), v.27 n.2, p.356-364, April 1980 [doi>10.1145/322186.322198]
• 42: T. Nipkow. Structured Proofs in Isar/HOL. In H. Geuvers and F. Wiedijk, editors, Types for Proofs and Programs (TYPES 2002), volume 2646, pages 259--278, 2003.
• 43: Isabelle/HOL: a proof assistant for higher-order logic, Springer-Verlag, London, 2002
• 44: M. Odersky and al. An overview of the scala programming language. Technical Report IC/2004/64, EPFL Lausanne, Switzerland, 2004.
• 45: M. Odersky, V. Cremet, C. Röckl, and M. Zenger. A nominal theory of objects with dependent types. In Proc. ECOOP'03, Springer LNCS, 2003.
• 46: Martin Odersky , Konstantin Läufer, Putting type annotations to work, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.54-67, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237729]
• 47: Benjamin C. Pierce, Intersection types and bounded polymorphism, Mathematical Structures in Computer Science, v.7 n.2, p.129-193, April 1997 [doi>10.1017/S096012959600223X]
• 48: Benjamin C. Pierce, Types and programming languages, MIT Press, Cambridge, MA, 2002
• 49: W. R. Pitt, M. A. Williams, M. Steven, B. Sweeney, A. J. Bleasby, and D. S. Moss. The bioinformatics template library: generic components for biocomputing. Bioinformatics, 17(8):729--737, 2001.
• 50: E. Poll and S. Thompson. The Type System of Aldor. Technical Report 11-99, Computing Laboratory, University of Kent at Canterbury, Kent CT2 7NF, UK, July 1999.
• 51: Didier Rémy , Jérôme Vouillon, Objective ML: an effective object-oriented extension to ML, Theory and Practice of Object Systems, v.4 n.1, p.27-50, 1998 [doi>10.1002/(SICI)1096-9942(1998)4:1<27::AID-TAPO3>3.0.CO;2-4]
• 52: John C. Reynolds, Towards a theory of type structure, Programming Symposium, Proceedings Colloque sur la Programmation, p.408-423, April 09-11, 1974
• 53: 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
• 54: The boost graph library: user guide and reference manual, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2002
• 55: J. Siek and A. Lumsdaine. Essential language support for generic programming: Formalization part 1. Technical Report 605, Indiana University, December 2004.
• 56: J. G. Siek and A. Lumsdaine. Advances in Software Tools for Scientific Computing, chapter A Modern Framework for Portable High Performance Numerical Linear Algebra. Springer, 2000.
• 57: Silicon Graphics, Inc. SGI Implementation of the Standard Template Library, 2004. http://www.sgi.com/tech/stl/.
• 58: A. Stepanov. gclib. http://www.stepanovpapers.com, 1987.
• 59: A. A. Stepanov and M. Lee. The Standard Template Library. Technical Report X3J16/94-0095, WG21/N0482, ISO Programming Language C++ Project, May 1994.
• 60: B. Stroustrup. Parameterized types for C++. In USENIX C++ Conference, October 1988.
• 61: Jerzy Tiuryn , Pawel Urzyczyn, The subtyping problem for second-order types is undecidable, Information and Computation, v.179 n.1, p.1-18, November 25, 2002 [doi>10.1006/inco.2001.2950]
• 62: M. Troyer, S. Todo, S. Trebst, and A. F. and. ALPS: Algorithms and Libraries for Physics Simulations. http://alps.comp-phys.org/.
• 63: 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]
• 64: J. Walter and M. Koch. uBLAS. Boost. http://www.boost.org/libs/numeric/ublas/doc/index.htm.
• 65: J. Willcock, J. Järvi, A. Lumsdaine, and D. Musser. A formalization of concepts for generic programming. In Concepts: a Linguistic Foundation of Generic Programming at Adobe Tech Summit. Adobe Systems, Apr. 2004.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Abstract data types

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
        D.2.13 Reusable Software
            Subjects: Reusable libraries
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Multiparadigm languages
      D.3.3 Language Constructs and Features
          Subjects: Constraints; Polymorphism

General Terms:
Design, Languages

Keywords:
C++, Haskell, generic programming, polymorphism, standard ML