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

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, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 2: Daniel G. Bobrow , Linda G. DeMichiel , Richard P. Gabriel , Sonya E. Keene , Gregor Kiczales , David A. Moon, Common Lisp Object System specification, ACM SIGPLAN Notices, v.23 n.SI, p.1-142, September 1988 [doi>10.1145/885631.885632]
• 3: Daniel G. Bobrow , Kenneth Kahn , Gregor Kiczales , Larry Masinter , Mark Stefik , Frank Zdybel, CommonLoops: merging Lisp and object-oriented programming, Conference proceedings on Object-oriented programming systems, languages and applications, p.17-29, September 29-October 02, 1986, Portland, Oregon, United States
• 4: 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
• 5: 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
• 6: Craig Chambers, Object-Oriented Multi-Methods in Cecil, Proceedings of the European Conference on Object-Oriented Programming, p.33-56, June 29-July 03, 1992
• 7: Craig Chambers, Predicate Classes, Proceedings of the 7th European Conference on Object-Oriented Programming, p.268-296, July 26-30, 1993
• 8: Craig Chambers , Gary T. Leavens, Typechecking and modules for multimethods, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.6, p.805-843, Nov. 1995 [doi>10.1145/218570.218571]
• 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 , 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
• 11: Michael Ernst , Craig Kaplan , Craig Chambers, Predicate Dispatching: A Unified Theory of Dispatch, Proceedings of the 12th European Conference on Object-Oriented Programming, p.186-211, July 20-24, 1998
• 12: 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]
• 13: 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
• 14: James Gosling , Bill Joy , Guy Steele , Gilad Bracha, Java(TM) Language Specification, The (3rd Edition) (Java (Addison-Wesley)), Addison-Wesley Professional, 2005
• 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 , Andrew Lumsdaine, Concept-controlled polymorphism, Proceedings of the 2nd international conference on Generative programming and component engineering, p.228-244, September 22-25, 2003, Erfurt, Germany
• 19: 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
• 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, Cambridge University Press, New York, NY, 1995
• 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, 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]
• 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, Inc., Upper Saddle River, NJ, 1992
• 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 D. Millstein , Craig Chambers, Modular Statically Typed Multimethods, Proceedings of the 13th European Conference on Object-Oriented Programming, p.279-303, June 14-18, 1999
• 30: Todd Millstein , Mark Reay , Craig Chambers, Relaxed MultiJava: balancing extensibility and modular typechecking, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 31: Robin Milner , Mads Tofte , Robert Harper, The Definition of Standard ML, MIT Press, Cambridge, MA, 1990
• 32: 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
• 33: Martin Odersky and al. An overview of the Scala programming language. Technical Report IC/2004/64, EPFL Lausanne, Switzerland, 2004.
• 34: Martin Odersky , Matthias Zenger, Scalable component abstractions, ACM SIGPLAN Notices, v.40 n.10, October 2005
• 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 G. Siek , Andrew Lumsdaine, A language for generic programming, Indiana University, Indianapolis, IN, 2005
• 37: The boost graph library: user guide and reference manual, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2002
• 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 G. Siek , Jeremy 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
• 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, The design and evolution of C++, ACM Press/Addison-Wesley Publishing Co., New York, NY, 1995
• 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 , 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]
• 49: Jörg Walter and Mathias Koch. Boost Basic Linear Algebra. Boost, 2002. www.boost.org/libs/numeric.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Polymorphism

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

General Terms:
Languages, Theory

Keywords:
concepts, constrained generics, generic programming, parametric polymorphism, specialization