Algorithm Specialization in Generic ProgrammingChallenges of Constrained Generics in C++Jaakko J¨arviTexas A&M [email protected] GregorJeremiah WillcockAndrew LumsdaineIndiana University{dgregor, jewillco, lums}@osl.iu.eduJeremy SiekRice [email protected] programming has recently emerged as a paradigm for de-veloping highly reusable software libraries, most notably in C++.We have designed and implemented a constrained generics exten-sion for C++ to support modular type checking of generic algo-rithms and to address other issues associated with unconstrainedgenerics. To be as broadly applicable as possible, generic algo-rithms are defined with minimal requirements on their inputs. Atthe same time, to achieve a high degree of efficiency, generic algo-rithms may have multiple implementations that exploit features ofspecific classes of inputs. This process of algorithm specializationrelies on non-local type information and conflicts directly with thelocal nature of modular type checking. In this paper, we review thedesign and implementation of our extensions for generic program-ming in C++, describe the issues of algorithm specialization andmodular type checking in detail, and discuss the important designtradeoffs in trying to accomplish both. We present the particular de-sign that we chose for our implementation, with the goal of hittingthe sweet spot in this interesting design space.Categories and Subject Descriptors D.3.3 [Programming Lan-guages]: Language Constructs and Features—Polymorphism; D.3.2[Programming Languages]: Language Classifications—C++General Terms Languages, TheoryKeywords Generic programming, parametric polymorphism, con-strained generics, concepts, specialization1. IntroductionTemplates are the cornerstone of modern C++ libraries. The Stan-dard Template Library (STL) [42], Boost Graph Library [37], theµBLAS Library [49], and the Computational Geometry AlgorithmsLibrary (CGAL) [12], are all examples of widely-used, heavily-templated libraries. Ironically, the same template system that makesthese libraries so flexible is also a significant source of problems. Inthe unconstrained genericity model of C++, generic functions can-not be compiled, or even type checked, in isolation of their uses.Constrained generics for C++, in the form of type checking forPermission to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citationon the first page. To copy otherwise, to republish, to post on servers or to redistributeto lists, requires prior specific permission and/or a fee.PLDI’06 June 11–14, 2006, Ottawa, Ontario, Canada.Copyrightc 2006 ACM 1-59593-320-4/06/0006. . . $5.00.C++ templates, can remedy many of the problems faced by usersand designers of generic libraries. Early discussions on constrainedgenerics for C++ can be found in [43]. A more recent and seriouseffort was initiated by Stroustrup and Dos Reis [45], laying outdesign goals for C++ constrained generics. This effort draws mo-tivation from generic programming, a paradigm for designing andimplementing efficient and highly reusable algorithm libraries. Pi-oneered by Musser and Stepanov [32], and introduced to C++ withthe STL [41], this approach is the foundation of the design princi-ples of numerous C++ libraries.Based on the goals in [45], an extensive survey of language sup-port for generic programming [13], and experience in developingseveral generic libraries, we have specified a constrained genericsfeature for C++ [16] and implemented the specification as an ex-tension to the GNU C++ compiler [15]. (In this paper, we refer toC++ with our proposed extensions as ConceptC++, and the extendedcompiler as ConceptGCC.) The constrained genericity mechanismwe propose is designed to directly support generic programming.Section 2 explains generic programming in more detail. We includea general overview of ConceptC++ in Section 2.1, but the focus ofthe paper is on features enabling algorithm specialization. We referto a component as specialized when its interface describes the min-imal requirements on its type parameters, but internally the com-ponent takes advantage of additional capabilities not required fromthose type parameters. For example, C++ standard library imple-mentations specialize the copy() algorithm for iterator types withrandom access, for pointer types, for “segmented” iterator types,etc. Such specialization is straightforward in today’s C++, whichlacks enforced interface specifications for template parameters al-together, and is frequently used to simultaneously guarantee goodperformance and generality.Unfortunately, accommodating specialization and modular typechecking together for constrained generics presents a conflict. Withmodular type checking, a component is type checked in isolationof other components (only relying on the declarations but not thedefinitions of components it refers to), guaranteeing that no use ofthat component conforming to its interface will produce type errors.Without specialization, our model of constrained generics for C++reduces to System FG, which has provably modular type check-ing [40]. Adding unrestricted specialization, however, creates vari-ations in the body of a generic component, thereby compromisingthe guarantees that modular type checking provides. For instance,the addition of new specializations and overloads into a genericcomponent can produce ambiguities in the selection process. Thispaper reports on the fundamental tension between specializationand modular type checking and explores the design space of con-strained generics for C++ in search of a “sweet spot” between un-restricted specialization and modular type checking.Our contributions are:•We illustrate how and to what extent specializations compro-mise modular type checking for constrained generics in C++.•We relate these problems to similar problems studied in thecontext of multimethods [8, 29] and Haskell type classes withoverlapping instance declarations [35] [47, §7.4.4.1].•We consider and evaluate solutions proposed for multimethodsin the context of constrained generics for C++.•We justify our decisions about specialization and modular typechecking for constrained generics in C++.2. Constrained generics for C++Generic programming is