Peter Gottschling
ABSTRACT
Concepts are a recently proposed extension to C++ for the direct linguistic support of generic programming. As the interface description mechanism for large-scale generic libraries, concepts do not exist in isolation, but rather in semantic frameworks (or concept lattices). Concepts provide powerful type-checking capabilities for generic programming and the semantics associated with them present new and interesting capabilities for library-compiler interactions. This paper presents some of these emergent capabilities in the context of a library of algebraic concepts. Based on this library, which possesses rich, well-structured and mathematically-based semantics, we demonstrate how the concepts therein can enable a sophisticated oncept-aware design for a broad range of scientific generic libraries. In particular, we show that concepts can enable the description and application of property-based, library-defined, optimizations. Whereas compilers without concepts are limited to optimization of built-in types, library-defined optimizations based on concepts not only allow for optimizations of user-defined types unknown to the compiler, they are even applicable to types unknown to the library developer.
- O. Bagge, M. Haveraaen, and E. Visser. CodeBoost: A framework for the transformation of C++ programs. Technical report, Universiteit Utrecht, The Netherlands, October 2000.Google Scholar
- J.-C. Birget, S. Margolis, J. Meakin, and M. Sapir, editors. Algorithmic Problems in Groups and Semigroups. Birkhäuser, Boston, 2000.Google ScholarCross Ref
- N. Bourbaki. Algèbre I: Chapitres 1 à 3. Numérisation BnF de l'édition de Paris, 1970.Google Scholar
- P. Gottschling. Fundamental algebraic concepts in concept-enabled C++. Technical Report 638, Indiana University, 2006.Google Scholar
- P. Gottschling and W. E. Brown. Toward a more complete taxonomy of algebraic properties for numeric libraries in tr2. Technical Report N2650=08-0160, ISO/IEC JTC 1, Information Technology, Subcommittee SC 22, Programming Language C++, June 2008.Google Scholar
- D. Gregor, J. Järvi, J. Siek, B. Stroustrup, G. D. Reis, and A. Lumsdaine. Concepts: Linguistic support for generic programming in C++. In OOPSLA '06, pages 291--310. ACM Press, October 2006. Google ScholarDigital Library
- K. Henckell and J.-E. Pin. Ordered Monoids in J-Trivial, pages 121--137. In Birget et al. {2}, 2000.Google Scholar
- M. R. Hestenes and E. Stiefel. Methods of conjugate gradients for solving linear systems. J. Res. Nat. Bur. Standards, 49(6):409--436, December 1952.Google ScholarCross Ref
- N. J. Higham. Accuracy and Stability of Numerical Algorithms. SIAM, Philadelphia, 1996. Google ScholarDigital Library
- H. Holin. Boost Quaternion Library. Boost, 2003. www.boost.org/libs/math/quaternion.Google Scholar
- D. Kapur, D. R. Musser, and X. Nie. An overview of the Tecton Proof System. Theoretical Computer Science, 133:307--339, Oct. 1994. Google ScholarDigital Library
- S. Mechveliani. DoCon the algebraic domain constructor. http://www.haskell.org/docon/.Google Scholar
- D. R. Musser, S. Schupp, C. Schwarzweller, and R. Loos. The Tecton concept library. Technical report, Fakultät für Informatik, Universität Tübingen, 1999.Google Scholar
- D. Quinlan. ROSE: Compiler support for object-oriented frameworks. Parallel Processing Letters, 10(2,3):215--226, 2000.Google Scholar
- J.-F. Raymond, P. Tesson, and D. Thérien. Multiparty Communication Complexity of Finite Monoids, pages 217--233. In Birget et al. {2}, 2000.Google Scholar
- S. Schupp, D. P. Gregor, and D. R. Musser. Algebraic concepts represented in C++. Technical Report TR-00-8, Rensselaer Polytechnic Institute, 2000. http://www.cs.chalmers.se/~schupp/old_projects/simpl/doc/AlgCpp.pdf.Google Scholar
- S. Schupp, D. P. Gregor, D. R. Musser, and S.-M. Liu. User-extensible simplification - type-based optimizer generators. In R. Wilhelm, editor, International Conference on Compiler Construction, Lecture Notes in Computer Science, 2001. Google ScholarDigital Library
- J. Siek and A. Lumsdaine. Concept checking: Binding parametric polymorphism in C++. In First Workshop on C++ Template Programming, October 2000.Google Scholar
- Silicon Graphics, Inc. SGI Implementation of the Standard Template Library, 2004. http://www.sgi.com/tech/stl/.Google Scholar
- B. Stroustrup and G. Dos Reis. A concept design. C++ Extensions reflector message c++std-ext-7073, April 2005.Google Scholar
- B. L. van der Waerden. Algebra, Volume I and II. Springer, 1990.Google Scholar
- E. Visser. Program transformation with Stratego/XT: Rules, strategies, tools, and systems in StrategoXT-0.9. In C. Lengauer et al., editors, Domain-Specific Program Generation, volume 3016 of Lecture Notes in Computer Science, pages 216--238. Spinger-Verlag, June 2004.Google Scholar
Index Terms
- Integrating semantics and compilation: using c++ concepts to develop robust and efficient reusable libraries
Recommendations
Axioms as generic rewrite rules in C++ with concepts
Compilers are typically hardwired to attempt many optimizations only on expressions that involve particular built-in types. Ideally, however, an optimizing compiler would recognize a rewrite opportunity for user-defined types as well, whenever the ...
Concept-based optimization
LCSD '07: Proceedings of the 2007 Symposium on Library-Centric Software DesignProduction compilers' optimizers typically operate at low abstraction levels, transformation rules enacting on operations on built-in types only. Transformations at higher levels of abstraction, on operations of types defined in libraries or by the user,...
Generic flow-sensitive optimizing transformations in C++ with concepts
SAC '10: Proceedings of the 2010 ACM Symposium on Applied ComputingCompilers are typically hardwired to attempt optimizations only on expressions involving particular built-in types. Ideally, an optimizing compiler can recognize a rewrite opportunity whenever the operands in an expression satisfy the (algebraic) ...
Comments