article

Algorithm specialization in generic programming: challenges of constrained generics in C++

Authors:

Douglas Gregor,

Jeremiah Willcock,

Andrew Lumsdaine,

Jeremy SiekAuthors Info & Claims

ACM SIGPLAN Notices, Volume 41, Issue 6

Pages 272 - 282

https://doi.org/10.1145/1133255.1134014

Published: 11 June 2006 Publication History

Abstract

Generic programming has recently emerged as a paradigm for developing highly reusable software libraries, most notably in C++. We have designed and implemented a constrained generics extension for C++ to support modular type checking of generic algorithms and to address other issues associated with unconstrained generics. To be as broadly applicable as possible, generic algorithms are defined with minimal requirements on their inputs. At the same time, to achieve a high degree of efficiency, generic algorithms may have multiple implementations that exploit features of specific classes of inputs. This process of algorithm specialization relies on non-local type information and conflicts directly with the local nature of modular type checking. In this paper, we review the design and implementation of our extensions for generic programming in C++, describe the issues of algorithm specialization and modular type checking in detail, and discuss the important design tradeoffs in trying to accomplish both.We present the particular design that we chose for our implementation, with the goal of hitting the sweet spot in this interesting design space.

References

[1]

Matthew H. Austern. Generic programming and the STL: Using and extending the C++ Standard Template Library. Professional Computing Series. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1998.]]

Digital Library

[2]

D. G. Bobrow, L. G. DeMichiel, R. P. Gabriel, S. E. Keene, G. Kicsales, and D. A. Moon. Common LISP Object System specification X3J13 document 88-002R. SIGPLAN Not., 23(SI):1--143, 1988.]]

Digital Library

[3]

Daniel G. Bobrow, Kenneth Kahn, Gregor Kiczales, Larry Masinter, Mark Stefik, and Frank Zdybel. CommonLoops: Merging Lisp and object-oriented programming. In OOPSLA '86: Conference proceedings on Object-oriented programming systems, languages and applications, pages 17--29, New York, NY, USA, 1986. ACM Press.]]

Digital Library

[4]

Manuel M. T. Chakravarty, Gabrielle Keller, and Simon Peyton Jones. Associated type synonyms. In ICFP '05: Proceedings of the International Conference on Functional Programming, pages 241--253, New York, NY, USA, September 2005. ACM Press.]]

Digital Library

[5]

Manuel M. T. Chakravarty, Gabrielle Keller, Simon Peyton Jones, and Simon Marlow. Associated types with class. In POPL '05: Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 1--13, New York, NY, USA, 2005. ACM Press.]]

Digital Library

[6]

Craig Chambers. Object-oriented multi-methods in Cecil. In Ole Lehrmann Madsen, editor, Proceedings of the 6th European Conference on Object-Oriented Programming (ECOOP), volume 615 of Lecture Notes in Computer Science, pages 33--56, Berlin, Heidelberg, New York, Tokyo, 1992. Springer-Verlag.]]

Digital Library

[7]

Craig Chambers. Predicate classes. In ECOOP'93 - Object-Oriented Programming, volume 707 of Lecture Notes in Computer Science, pages 268--296, 1993.]]

Digital Library

[8]

Craig Chambers and Gary T. Leavens. Typechecking and modules for multimethods. ACM Trans. Program. Lang. Syst., 17(6):805--843, 1995.]]

Digital Library

[9]

Craig Chambers and the Cecil Group. The Cecil Language: Specification and Rationale, Version 3.1. University of Washington, Computer Science and Engineering, December 2002. http://www.cs.washington.edu/research/projects/cecil/.]]

[10]

Gabriel Dos Reis and Bjarne Stroustrup. Specifying C++ concepts. In POPL '06: Conference record of the 33rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 295--308, New York, NY, USA, 2006. ACM Press.]]

Digital Library

[11]

Michael D. Ernst, Crag Kaplan, and Craig Chambers. Predicate dispatching: A unified theory of dispatch. In ECOOP '98, volume 1445 of Lecture Notes in Computer Science, pages 186--211, New York, NY, 1998. Springer-Verlag.]]

Digital Library

[12]

A. Fabri, G.-J. Giezeman, L. Kettner, S. Schirra, and S. Schönherr. On the design of CGAL, a computational geometry algorithms library. Software-Practice and Experience, 30(11):1167--1202, 2000. Special Issue on Discrete Algorithm Engineering.]]

Digital Library

[13]

Ronald Garcia, Jaakko Järvi, Andrew Lumsdaine, Jeremy Siek, and Jeremiah Willcock. A comparative study of language support for generic programming. In OOPSLA '03: Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, pages 115--134, New York, NY, USA, 2003. ACM Press.]]

Digital Library

[14]

James Gosling, Bill Joy, Guy Steele, and Gilad Bracha. The Java Language Specification, Third Edition. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 2005.]]

Digital Library

[15]

Douglas Gregor. ConceptGCC: Concept extensions for C++. http://www.osl.iu.edu/~dgregor/ConceptGCC, 2005.]]

[16]

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 SC 22, Programming Language C++, August 2005.]]

[17]

International Organization for Standardization. ISO/IEC 14882:1998: Programming languages - C++. Geneva, Switzerland, September 1998.]]

[18]

Jaakko Järvi, Jeremiah Willcock, and Andrew Lumsdaine. Conceptcontrolled polymorphism. In Frank Pfennig and Yannis Smaragdakis, editors, Generative Programming and Component Engineering, volume 2830 of LNCS, pages 228--244. Springer Verlag, September 2003.]]

Digital Library

[19]

Jaakko Järvi, JeremiahWillcock, and Andrew Lumsdaine. Associated types and constraint propagation for mainstream object-oriented generics. In OOPSLA, October 2005.]]

Digital Library

[20]

Mark P. Jones. Dictionary-free overloading by partial evaluation. In Partial Evaluation and Semantics-Based Program Manipulation, Orlando, Florida, June 1994 (Technical Report 94/9, Department of Computer Science, University of Melbourne), pages 107--117, 1994.]]

[21]

Mark P. Jones. Qualified Types: Theory and Practice. Distinguished Dissertations in Computer Science. Cambridge University Press, 1994.]]

Digital Library

[22]

Oleg Kiselyov. Dynamic dispatch on a class of a type. Haskell mailing list, March 2003. http://okmij.org/ftp/Haskell/types.html#class-based-dispatch.]]

[23]

Xavier Leroy. Manifest types, modules, and separate compilation. In Proceedings of the 21st Annual ACM Symposium on Principles of Programming Languages, pages 109--122, 1994.]]

Digital Library

[24]

Mark Lillibridge. Translucent Sums: A Foundation for Higher-Order Module Systems. PhD thesis, Pittsburgh, PA, May 1997.]]

[25]

Brian McNamara and Yannis Smaragdakis. Static interfaces in C++. In First Workshop on C++ Template Programming, October 2000.]]

[26]

Bertrand Meyer. Eiffel: the Language. Prentice Hall, New York, NY, first edition, 1992.]]

Digital Library

[27]

Microsoft Corporation. Generics in C#, September 2002. Part of the Gyro distribution of generics for .NET available at http: //research.microsoft.com/projects/clrgen/.]]

[28]

Microsoft Corporation. C# Version 2.0 Specification, March 2005 Draft, March 2005. http://msdn.microsoft.com/vcsharp/-programming/language.]]

[29]

Todd Millstein and Craig Chambers. Modular statically typed multimethods. In Proceedings of the Thirteenth European Conference on Object-Oriented Programming (ECOOP'99), volume 1628 of Lecture Notes in Computer Science, pages 279--303, Lisbon, Portugal, June 1999. Springer Verlag.]]

Digital Library

[30]

Todd Millstein, Mark Reay, and Craig Chambers. Relaxed MultiJava: balancing extensibility and modular typechecking. In OOPSLA'03: Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, pages 224--240, New York, NY, USA, 2003. ACM Press.]]

Digital Library

[31]

Robin Milner, Mads Tofte, and Robert Harper. The Definition of Standard ML. MIT Press, 1990.]]

Digital Library

[32]

David A. Musser and Alexander A. Stepanov. Generic Programming. In Proceedings of International Symposium on Symbolic and Algebraic Computation, volume 358 of Lecture Notes in Computer Science, pages 13--25, Rome, Italy, 1989.]]

Digital Library

[33]

Martin Odersky and al. An overview of the Scala programming language. Technical Report IC/2004/64, EPFL Lausanne, Switzerland, 2004.]]

[34]

Martin Odersky and Matthias Zenger. Scalable component abstractions. SIGPLAN Not., 40(10):41--57, 2005.]]

Digital Library

[35]

Simon Peyton Jones, Mark Jones, and Erik Meijer. Type classes: an exploration of the design space. In Proceedings of the Second Haskell Workshop, June 1997.]]

[36]

Jeremy Siek. A Language for Generic Programming. PhD thesis, Indiana University, 2005.]]

Digital Library

[37]

Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine. The Boost Graph Library: User Guide and Reference Manual. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 2002.]]

Digital Library

[38]

Jeremy Siek and Andrew Lumsdaine. A modern framework for portable high performance numerical linear algebra. In Modern Software Tools for Scientific Computing. Birkhäuser, 1999.]]

[39]

Jeremy Siek and Andrew Lumsdaine. Concept checking: Binding parametric polymorphism in C++. In First Workshop on C++ Template Programming, October 2000.]]

[40]

Jeremy Siek and Andrew Lumsdaine. Essential language support for generic programming. In PLDI '05: Proceedings of the ACM SIGPLAN 2005 conference on Programming language design and implementation, pages 73--84, New York, NY, USA, June 2005. ACM Press.]]

Digital Library

[41]

Silicon Graphics, Inc. SGI Implementation of the Standard Template Library, 2004. http://www.sgi.com/tech/stl/.]]

[42]

A. Stepanov and M. Lee. The Standard Template Library. Technical Report HPL-94-34(R.1), Hewlett-Packard Laboratories, April 1994. http://www.hpl.hp.com/techreports.]]

[43]

Bjarne Stroustrup. Design and Evolution of C++. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1994.]]

Digital Library

[44]

Bjarne Stroustrup. Concepts - a more abstract complement to type checking. Technical Report N1510=03-0093, ISO/IEC JTC 1, Information Technology, Subcommittee SC 22, Programming Language C++, October 2003. http://www.open-std.org/jtc1/sc22/wg21.]]

[45]

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 SC 22, Programming Language C++, October 2003. http://www.open-std.org/jtc1/sc22/wg21.]]

[46]

Bjarne Stroustrup and Gabriel Dos Reis. A concept design (rev. 1). Technical Report N1782=05-0042, ISO/IEC JTC 1, Information Technology, Subcommittee SC 22, Programming Language C++, May 2005.]]

[47]

The GHC Team. The Glorious Glasgow Haskell Compilation System User's Guide, version 6.4.1 edition. http://www.haskell.org/ghc/docs/latest/html/users guide/index.html.]]

[48]

P. Wadler and S. Blott. How to make ad-hoc polymorphism less adhoc. In ACM Symposium on Principles of Programming Languages, pages 60--76. ACM, January 1989.]]

Digital Library

[49]

Jörg Walter and Mathias Koch. Boost Basic Linear Algebra. Boost, 2002. www.boost.org/libs/numeric.]]

Cited By

Schwaha PHeinzl RStimpfl FSelberherr S(2009)Synergies in scientific computing by combining multi-paradigmatic languages for high-performance applicationsInternational Journal of Parallel, Emergent and Distributed Systems10.1080/1744576090275855224:6(539-549)Online publication date: Dec-2009
https://doi.org/10.1080/17445760902758552
Piatkowski J(2020)The Conditional Multiway Mapped Tree: Modeling and Analysis of Hierarchical Data DependenciesIEEE Access10.1109/ACCESS.2020.29883588(74083-74092)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.2988358
Haveraaen MScholz SShivers O(2018)Proving a core code for FDM correct by 2 + dw testsProceedings of the 5th ACM SIGPLAN International Workshop on Libraries, Languages, and Compilers for Array Programming10.1145/3219753.3219759(42-49)Online publication date: 19-Jun-2018
https://dl.acm.org/doi/10.1145/3219753.3219759
Show More Cited By

Index Terms

Algorithm specialization in generic programming: challenges of constrained generics in C++
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features
        Polymorphism
      2. Language types

Recommendations

Concepts: linguistic support for generic programming in C++
OOPSLA '06: Proceedings of the 21st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications

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, ...
A comparative study of language support for generic programming
OOPSLA '03: Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications

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 ...
Algorithm specialization in generic programming: challenges of constrained generics in C++
PLDI '06: Proceedings of the 27th ACM SIGPLAN Conference on Programming Language Design and Implementation

Generic programming has recently emerged as a paradigm for developing highly reusable software libraries, most notably in C++. We have designed and implemented a constrained generics extension for C++ to support modular type checking of generic ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 41, Issue 6

Proceedings of the 2006 PLDI Conference

June 2006

426 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/1133255

Issue’s Table of Contents

PLDI '06: Proceedings of the 27th ACM SIGPLAN Conference on Programming Language Design and Implementation
June 2006
438 pages
ISBN:1595933204
DOI:10.1145/1133981
General Chair:
Michael Schwartzbach
University of Aarhus, Denmark
,
Program Chair:
Thomas Ball
Microsoft Research

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 June 2006

Published in SIGPLAN Volume 41, Issue 6

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
842
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Schwaha PHeinzl RStimpfl FSelberherr S(2009)Synergies in scientific computing by combining multi-paradigmatic languages for high-performance applicationsInternational Journal of Parallel, Emergent and Distributed Systems10.1080/1744576090275855224:6(539-549)Online publication date: Dec-2009
https://doi.org/10.1080/17445760902758552
Piatkowski J(2020)The Conditional Multiway Mapped Tree: Modeling and Analysis of Hierarchical Data DependenciesIEEE Access10.1109/ACCESS.2020.29883588(74083-74092)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.2988358
Haveraaen MScholz SShivers O(2018)Proving a core code for FDM correct by 2 + dw testsProceedings of the 5th ACM SIGPLAN International Workshop on Libraries, Languages, and Compilers for Array Programming10.1145/3219753.3219759(42-49)Online publication date: 19-Jun-2018
https://dl.acm.org/doi/10.1145/3219753.3219759
Xue J(2016)Genericity in PAR PlatformStructured Object-Oriented Formal Language and Method10.1007/978-3-319-31220-0_1(3-14)Online publication date: 2016
https://doi.org/10.1007/978-3-319-31220-0_1
Chen SErwig MChin WHage J(2014)Early detection of type errors in C++ templatesProceedings of the ACM SIGPLAN 2014 Workshop on Partial Evaluation and Program Manipulation10.1145/2543728.2543731(133-144)Online publication date: 11-Jan-2014
https://dl.acm.org/doi/10.1145/2543728.2543731
Chen SErwig MWalkingshaw E(2014)Extending Type Inference to Variational ProgramsACM Transactions on Programming Languages and Systems10.1145/251819036:1(1-54)Online publication date: 1-Mar-2014
https://dl.acm.org/doi/10.1145/2518190
Bachelet BMahul AYon L(2013)Template metaprogramming techniques for concept-based specializationScientific Programming10.1155/2013/58139721:1-2(43-61)Online publication date: 1-Jan-2013
https://dl.acm.org/doi/10.1155/2013/581397
Pataki NSzgyi ZDévai G(2011)Measuring the Overhead of C++ Standard Template Library Safe VariantsElectronic Notes in Theoretical Computer Science (ENTCS)10.1016/j.entcs.2011.06.005264:5(71-83)Online publication date: 1-Jul-2011
https://dl.acm.org/doi/10.1016/j.entcs.2011.06.005
Pirkelbauer PDechev DStroustrup B(2011)Support for the Evolution of C++ Generic FunctionsSoftware Language Engineering10.1007/978-3-642-19440-5_8(123-142)Online publication date: 2011
https://doi.org/10.1007/978-3-642-19440-5_8
Pirkelbauer PDechev DStroustrup B(2010)Support for the evolution of C++ generic functionsProceedings of the Third international conference on Software language engineering10.5555/1964571.1964583(123-142)Online publication date: 12-Oct-2010
https://dl.acm.org/doi/10.5555/1964571.1964583
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents