Concepts: linguistic support for generic programming in C++

ABSTRACT

Generic programming has emerged as an important technique for the development of highly reusable and efficient software libraries. In C++, generic programming is enabled by the flexibility of templates, the C++ type parametrization mechanism. However, the power of templates comes with a price: generic (template) libraries can be more difficult to use and develop than non-template libraries and their misuse results in notoriously confusing error messages. As currently defined in C++98, templates are unconstrained, and type-checking of templates is performed late in the compilation process, i.e., after the use of a template has been combined with its definition. To improve the support for generic programming in C++, we introduce concepts to express the syntactic and semantic behavior of types and to constrain the type parameters in a C++ template. Using concepts, type-checking of template definitions is separated from their uses, thereby making templates easier to use and easier to compile. These improvements are achieved without limiting the flexibility of templates or decreasing their performance - in fact their expressive power is increased. This paper describes the language extensions supporting concepts, their use in the expression of the C++ Standard Template Library, and their implementation in the ConceptGCC compiler. Concepts are candidates for inclusion in the upcoming revision of the ISO C++ standard, C++0x.

REFERENCES

• 1: David Abrahams , Aleksey Gurtovoy, C++ Template Metaprogramming: Concepts, Tools, and Techniques from Boost and Beyond (C++ in Depth Series), Addison-Wesley Professional, 2004
• 2: P. An, A. Jula, S. Rus, S. Saunders, T. Smith, G. Tanase, N. Thomas, N. Amato, and L. Rauchwerger. STAPL: A standard template adaptive parallel C++ library. In Int. Wkshp on Adv. Compiler Technology for High Perf. and Embedded Processors, page 10, July 2001.
• 3: Matthew H. Austern, Generic programming and the STL: using and extending the C++ Standard Template Library, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 4: G. Baumgartner, M. Jansche, and K. Läufer. Half & Half: Multiple Dispatch and Retroactive Abstraction for Java. Technical Report OSU-CISRC-5/01-TR08, Ohio State University, 2002.
• 5: Gerald Baumgartner , Vincent F. Russo, Signatures: a language extension for improving type abstraction and subtype polymorphism in C++, Software—Practice & Experience, v.25 n.8, p.863-889, Aug. 1995 [doi>10.1002/spe.4380250803]
• 6: Boost. Boost C++ L ibraries. http://www.boost.org/.
• 7: Alex Breuer, Peter Gottschling, Douglas Gregor, and Andrew Lumsdaine. Effecting parallel graph eigensolvers through library composition. In Performance Optimization for High-Level Languages and Libraries (POHLL), April 2006.
• 8: 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]
• 9: 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
• 10: 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
• 11: Krzysztof Czarnecki , Ulrich W. Eisenecker, Generative programming: methods, tools, and applications, ACM Press/Addison-Wesley Publishing Co., New York, NY, 2000
• 12: Gabriel Dos Reis , Bjarne Stroustrup, Specifying C++ concepts, Conference record of the 33rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.295-308, January 11-13, 2006, Charleston, South Carolina, USA
• 13: Peter J. Downey , Ravi Sethi , Robert Endre Tarjan, Variations on the Common Subexpression Problem, Journal of the ACM (JACM), v.27 n.4, p.758-771, Oct. 1980 [doi>10.1145/322217.322228]
• 14: Andreas Fabri , Geert-Jan Giezeman , Lutz Kettner , Stefan Schirra , Sven Schönherr, On the design of CGAL a computational geometry algorithms library, Software—Practice & Experience, v.30 n.11, p.1167-1202, Sept. 2000 [doi>10.1002/1097-024X(200009)30:11<1167::AID-SPE337>3.0.CO;2-B ]
• 15: 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
• 16: Ronald Garcia, Jaakko Järvi, Andrew Lumsdaine, Jeremy Siek, and Jeremiah Willcock. An extended comparative study of language support for generic programming. Journal of Functional Programming, 2005. Accepted.
• 17: GNU compiler collection. http://www.gnu.org/software/gcc/, 2005.
• 18: James Gosling , Bill Joy , Guy Steele , Gilad Bracha, Java(TM) Language Specification, The (3rd Edition) (Java (Addison-Wesley)), Addison-Wesley Professional, 2005
• 19: Douglas Gregor. ConceptGCC: Concept extensions for C++. http://www.generic-programming.org/software/ConceptGCC, 2005.
• 20: Douglas Gregor , Andrew Lumsdaine, Lifting sequential graph algorithms for distributed-memory parallel computation, Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA
• 21: Douglas Gregor and Jeremy Siek. Implementing concepts. Technical Report N1848=05-0108, ISO/IEC JTC 1, Information Technology, Subcommittee 22, Programming Language C++, August 2005.
• 22: Douglas Gregor, Jeremy Siek, Jeremiah Willcock, Jaakko Järvi, Ronald Garcia, and Andrew Lumsdaine. Concepts for C++0x (revision 1). Technical Report N1849=05-0109, ISO/IEC JTC 1, Information Technology, Subcommittee 22, Programming Language C++, August 2005.
• 23: Douglas Gregor and Bjarne Stroustrup. Concepts. Technical Report N2042=06-0112, ISO/IEC JTC 1, Information Technology, Subcommittee 22, Programming Language C++, June 2006.
• 24: Michi Henning, The rise and fall of CORBA, Queue, v.4 n.5, June 2006 [doi>10.1145/1142031.1142044]
• 25: International Organization for Standardization. ISO/IEC 14882:1998: Programming languages - C++. Geneva, Switzerland, September 1998.
• 26: J. Järvi, B. Stroustrup, and G. Dos Reis. Decltype and auto (revision 4). Technical Report N1705=04-0145, ISO/IEC JTC 1, Information Technology, Subcommittee 22, Programming Language C++, September 2004. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1705.pdf.
• 27: Jaakko Järvi , Douglas Gregor , Jeremiah Willcock , Andrew Lumsdaine , Jeremy Siek, Algorithm specialization in generic programming: challenges of constrained generics in C++, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 28: Jaakko Järvi, Jeremiah Willcock, Howard Hinnant, and Andrew Lumsdaine. Function overloading based on arbitrary properties of types. C/C++ Users Journal, 21(6):25--32, June 2003.
• 29: Jaakko Järvi , Jeremiah Willcock , Andrew Lumsdaine, Associated types and constraint propagation for mainstream object-oriented generics, Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA
• 30: Selected Papers from the International Seminar on Generic Programming, April 1998
• 31: 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.
• 32: Steve Karmesin , James Crotinger , Julian Cummings , Scott Haney , William J. Humphrey , John Reynders , Stephen Smith , Timothy Williams, Array Design and Expression Evaluation in POOMA II, Proceedings of the Second International Symposium on Computing in Object-Oriented Parallel Environments, p.231-238, December 08-11, 1998
• 33: K. Läufer, G. Baumgartner, and V. F. Russo. Safe structural conformance for Java. The Computer Journal, 43(6):469--481, 2000.
• 34: Lie-Quan Lee , Jeremy G. Siek , Andrew Lumsdaine, Generic Graph Algorithms for Sparse Matrix Ordering, Proceedings of the Third International Symposium on Computing in Object-Oriented Parallel Environments, p.120-129, December 08-10, 1999
• 35: Xavier Leroy, Manifest types, modules, and separate compilation, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.109-122, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.176926]
• 36: Mark Lillibridge. Translucent Sums: A Foundation for Higher-Order Module Systems. PhD thesis, Pittsburgh, PA, May 1997.
• 37: Vassily Litvinov, Contraint-based polymorphism in Cecil: towards a practical and static type system, Proceedings of the 13th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.388-411, October 18-22, 1998, Vancouver, British Columbia, Canada
• 38: 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
• 39: Bertrand Meyer, Eiffel: the language, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 40: Microsoft Corporation. Generics in C#, September 2002. Part of the Gyro distribution of generics for .NET available at http://research.microsoft.com/projects/clrgen/.
• 41: Robin Milner , Mads Tofte , Robert Harper, The Definition of Standard ML, MIT Press, Cambridge, MA, 1990
• 42: David R. Musser , Gilmer J. Derge , Atul Saini, STL tutorial and reference guide, second edition: C++ programming with the standard template library, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2001
• 43: 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]
• 44: 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
• 45: David R. Musser , Alexander A. Stepanov, Algorithm-oriented generic libraries, Software—Practice & Experience, v.24 n.7, p.623-642, July 1994 [doi>10.1002/spe.4380240703]
• 46: Nathan Myers. A new and useful technique: "traits". C ++ Report, 7(5):32--35, June 1995.
• 47: Nathan C. Myers. Traits: a new and useful template technique. C ++ Report, June 1995.
• 48: 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]
• 49: Martin Odersky. The Scala language specification: Version 2.0, draft March 17, 2006. http://scala.epfl.ch/docu/files/ScalaReference.pdf, 2006.
• 50: Martin Odersky and al. An overview of the Scala programming language. Technical Report IC/2004/64, EPFL Lausanne, Switzerland, 2004.
• 51: Martin Odersky , Matthias Zenger, Scalable component abstractions, ACM SIGPLAN Notices, v.40 n.10, October 2005
• 52: Sibylle Schupp , Douglas Gregor , David R. Musser , Shin-Ming Liu, User-Extensible Simplification–Type-Based Optimizer Generators, Proceedings of the 10th International Conference on Compiler Construction, p.86-101, April 02-06, 2001
• 53: Jeremy Siek, Douglas Gregor, Ronald Garcia, Jeremiah Willcock, Jaakko Järvi, and Andrew Lumsdaine. Concepts for C++0x. Technical Report N1758=05-0018, ISO/IEC JTC 1, Information Technology, Subcommittee 22, Programming Language C++, January 2005.
• 54: The boost graph library: user guide and reference manual, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2002
• 55: Jeremy G. Siek , Andrew Lumsdaine, The Matrix Template Library: Generic Components for High-Performance Scientific Computing, Computing in Science and Engineering, v.1 n.6, p.70-78, November 1999 [doi>10.1109/5992.805137 ]
• 56: Jeremy Siek and Andrew Lumsdaine. Concept checking: Binding parametric polymorphism in C++. In First Workshop on C++ Template Programming, October 2000.
• 57: Jeremy Siek , Jeremy G. Siek , Andrew Lumsdaine, Essential language support for generic programming, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 58: Jeremy Siek and Andrew Lumsdaine. Language requirements for large-scale generic libraries. In GPCE '05: Proceedings of the fourth international conference on Generative Programming and Component Engineering, September 2005. To appear.
• 59: Jeremy G. Siek , Andrew Lumsdaine, A language for generic programming, Indiana University, Indianapolis, IN, 2005
• 60: Alexander A. Stepanov and Meng Lee. The Standard Template Library. Technical Report X3J16/94-0095, WG21/N0482, ISO Programming Language C++ Project, May 1994.
• 61: Bjarne Stroustrup, The design and evolution of C++, ACM Press/Addison-Wesley Publishing Co., New York, NY, 1995
• 62: Bjarne Stroustrup, The C++ Programming Language, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 63: Bjarne Stroustrup and Gabriel Dos Reis. Concepts - design choices for template argument checking. Technical Report N1522=03-0105, ISO/IEC JTC 1, Information Technology, Subcommittee 22, Programming Language C++, October 2003. http://www.open-std.org/jtc1/sc22/wg21.
• 64: Bjarne Stroustrup and Gabriel Dos Reis. A concept design (rev. 1). Technical Report N1782=05-0042, ISO/IEC JTC 1, Information Technology, Subcommittee 22, Programming Language C++, May 2005.
• 65: Mathias Troyer and Prakash Dayal. The Iterative Eigensolver Template Library. http://www.comp-phys.org:16080/software/ietl/.
• 66: Todd Veldhuizen. Using C ++ template metaprograms. C++ Report, May 1995.
• 67: Todd Veldhuizen, Expression templates, C++ gems, SIGS Publications, Inc., New York, NY, 1996
• 68: 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
• 69: Todd L. Veldhuizen. Five compilation models for C++ templates. In First Workshop on C++ Template Programming, October 10 2000.
• 70: 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]

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.3 Language Constructs and Features
          Subjects: Polymorphism

General Terms:
Design, Languages

Keywords:
C++ templates, C++0x, concepts, constrained generics, generic programming, parametric polymorphism