Essential Language Support for Generic ProgrammingJeremy SiekOpen Systems Lab, Indiana [email protected] LumsdaineOpen Systems Lab, Indiana [email protected] are an essential language feature for generic program-ming in the large. Concepts allow for succinct expression of con-straints on type parameters of generic algorithms, enable systematicorganization of problem domain abstractions, and make generic al-gorithms easier to use. In this paper we present the design of a typesystem and semantics for concepts that is suitable for non-type-inferencing languages. Our design shares much in common withthe type classes of Haskell, though our primary influence is frombest practices in the C++community, where concepts are used todocument type requirements for templates in generic libraries. Con-cepts include a novel combination of associated types and same-type constraints that do not appear in type classes, but that are sim-ilar to nested types and type sharing in ML.Categories and Subject Descriptors D.3.3 [Programming Langua-ges]: Language Constructs and Features—abstract data types, con-straints, polymorphism; D.2.13 [Software Engineering]: ReusableSoftware—reusable libraries; D.3.2 [Programming Languages]:Language Classifications—multiparadigm languagesGeneral Terms Languages, DesignKeywords generic programming, polymorphism, C++, StandardML, Haskell1. IntroductionIn the 1980’s Musser and Stepanov developed a methodology forcreating highly reusable algorithm libraries [25,39], using the term“generic programming” for their work. They applied this method-ology to the construction of sequence and graph algorithms in Ada,C, and Scheme [28, 40,58]. In the early 1990’s they applied theirwork to C++and took advantage of templates [60] to construct theStandard Template Library [59] (STL). The STL became part ofthe C++Standard [18], which brought generic programming intothe mainstream. Since then, generic programming has been suc-cessfully applied to the creation of generic libraries for numerousproblem domains [2,29,49,53,56,62,64].A distinguishing characteristic of generic programming is thatgeneric algorithms are expressed in terms of properties of types,rather than in terms of a particular type. A generic algorithm can beused (more importantly, reused) with any type that has the neces-Permission 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’05, June 12–15, 2005, Chicago, Illinois, USA.Copyrightc 2005 ACM 1-59593-080-9/05/0006. .. $5.00.sary properties. Although a statically typed language must thereforeprovide type parameterization (“generics”) to support generic pro-gramming, generic programming as a development methodology ismuch richer than simply type parameterization.A fundamental issue in providing language support for genericprogramming is how to express the set of admissible types for agiven algorithm, or equivalently, how to design a type system thatcan check calls to a generic (type-parameterized) algorithm andseparately check the implementation of the algorithm. An impor-tant complementary issue is providing the run-time mechanism bywhich user-defined operations, such as multiplication for a BigInttype, are connected with uses of operations inside a generic algo-rithm, such as a call to “x ∗ x” in an algorithm parameterized on thenumber type. In today’s programming languages there are four ap-proaches to addressing these issues: subtype bounds, type classes,structural matching, and by-name operation lookup. We describeeach of these approaches below and show examples in Figure 1.Subtype Bounds (Figure 1 (a)) In object-oriented languages,constraints on type parameters are typically expressed via subtyp-ing [6,7,47]. When a generic function constrains a type parameterto be a subtype of an interface, objects passed to the generic func-tion must carry along the necessary operations in a virtual table.This approach is used in Eiffel [35] and in the generics extensionsto Java [4] and C# [27,36].Type Classes (Figure 1 (b)) In Haskell, type classes are usedto describe the set of admissible types to a generic function [63].A type class contains a list of required operations, and a type isdeclared to belong to a type class through an instance declarationthat provides implementations of the required operations. If a typeparameter to a generic function is constrained to be an instance ofa type class, operations from the appropriate instance declarationare implicitly passed into the generic function at a call site. A typeclass is similar to an object-oriented interface in that it specifies aset of required operations. However, unlike interfaces, type classesare not themselves types (e.g., one cannot declare a variable with atype class as its type).Structural Matching (Figure 1 (c)) Many languages take astructural approach to expressing constraints: the name of an in-terface does not matter (as it does for a type class), only the contentof the interface matters (which operations must be provided). Thisis the case for CLU type sets [32, 33], ML signatures [37], andO’Caml object types [31]. In CLU, polymorphic functions are ex-plicitly instantiated on particular types, and the corresponding clus-ter definitions for those types must supply the operations requiredin the where clause. In ML, a functor is explicitly instantiated witha structure, and the structure must match the required signature. InO’Caml, the type of the object passed into a polymorphic functionmust structurally match the parameter’s object type, and if success-ful the polymorphic function is implicitly instantiated.By-Name Operation Lookup (Figure 1 (d)) In Cforall [10,11] and C++, the operations used in a generic function are notnecessarily class methods, but can be free-standing functions. InPLDI’05, 1 2005/4/19public i nterface Number<U> {public U mult(U other);}public c las s B igInt imple ments Number<BigInt> {public B igInt mult(Bi gInt x) { ... }...}public c las s Square {<T extends Number<T>>T square(T x) { return x.mult(x); }public s tatic voi d main(String[] args) {square(BigInt(4));}}(a)