A Comparative Study of Language Support for Generic Programming

Text-only Preview

A Comparative Study of Language Support for
Generic Programming
Ronald Garcia
Jaakko J ¨arvi
Andrew Lumsdaine
Jeremy Siek
Jeremiah Willcock
Open Systems Lab
Indiana University Bloomington
Bloomington, IN USA
Many modern programming languages support basic generic pro-
Generic programming is an increasingly popular and important
gramming, suf?cient to implement type-safe polymorphic contain-
paradigm for software development and many modern program-
ers. Some languages have moved beyond this basic support to
ming languages provide basic support for it. For example, the use
a broader, more powerful interpretation of generic programming,
of type-safe polymorphic containers is routine programming prac-
and their extensions have proven valuable in practice. This pa-
tice today. Some languages have moved beyond elementary gener-
per reports on a comprehensive comparison of generics in six pro-
ics to a broader, more powerful interpretation, and their extensions
gramming languages: C++, Standard ML, Haskell, Eiffel, Java (with
have proven valuable in practice. One domain where generic pro-
its proposed generics extension), and Generic C#. By implement-
gramming has been particularly effective is reusable libraries of
ing a substantial example in each of these languages, we identify
software components, an example of which is the Standard Tem-
eight language features that support this broader view of generic
plate Library (STL), now part of the C++ Standard Library [23, 45].
programming. We ?nd these features are necessary to avoid awk-
As the generic programming paradigm gains momentum, it is im-
ward designs, poor maintainability, unnecessary run-time checks,
portant to clearly and deeply understand the language issues. In
and painfully verbose code. As languages increasingly support
particular, it is important to understand what language features are
generics, it is important that language designers understand the fea-
required to support the broader notion of generic programming.
tures necessary to provide powerful generics and that their absence
To aid in this process, we present results of an in-depth study
causes serious dif?culties for programmers.
comparing six programming languages that support generics: Stan-
dard ML [35], C++ [17], Haskell [21], Eiffel [30], Java (with the pro-
posed genericity extension) [6], and Generic C# [24, 33]. The ?rst
Categories and Subject Descriptors
four currently support generics while the latter two have proposed
extensions (and prototype implementations) that do so. These lan-
D.2.13 [Software Engineering]: Reusable Software—reusable li-
guages were selected because they are widely used and represent
braries; D.3.2 [Programming Languages]: Language Classi?ca-
the state of the art in programming languages with generics.
tions—multiparadigm languages; D.3.3 [Programming Langua-
Our high-level goals for this study were the following:
ges]: Language Constructs and Features—abstract data types, con-
straints, polymorphism

• Understand what language features are necessary to support
generic programming;
General Terms
• Understand the extent to which speci?c languages support
generic programming;
Languages, Design, Standardization
• Provide guidance for development of language support for
generics; and
• Illuminate for the community some of the power and sub-
generics, generic programming, polymorphism, C++, Standard ML,
tleties of generic programming.
Haskell, Eiffel, Java, C#
It is decidedly not a goal of this paper to demonstrate that one lan-
guage is “better” than any other language. This paper is also not
a comparison of generic programming to object-oriented program-
Permission to make digital or hard copies of all or part of this work for
ming (or to any other paradigm).
personal or classroom use is granted without fee provided that copies are
To conduct the study, we designed a model library by extract-
not made or distributed for pro?t or commercial advantage and that copies
ing a small but signi?cant example of generic programming from a
bear this notice and the full citation on the ?rst page. To copy otherwise, to
state-of-the art generic library (the Boost Graph Library [41]). The
republish, to post on servers or to redistribute to lists, requires prior speci?c
model library was fully implemented in all six target languages.
permission and/or a fee.
This example was chosen because it includes a variety of generic
OOPSLA’03, October 26–30, 2003, Anaheim, California, USA.
Copyright 2003 ACM 1-58113-712-5/03/0010 ...$5.00.
programming techniques (some beyond the scope of, say, the STL)

and could therefore expose many subtleties of generic program-
Generic programming is a sub-discipline of computer science
ming. We attempted to create a uniform implementation across
that deals with ?nding abstract representations of ef?cient al-
all of the languages while still using the standard techniques and
gorithms, data structures, and other software concepts, and
idioms of each language. For each implementation, we evaluated
with their systematic organization. The goal of generic pro-
the language features available to realize different facets of generic
gramming is to express algorithms and data structures in a
programming. In addition, we evaluated each implementation with
broadly adaptable, interoperable form that allows their direct
respect to software quality issues that generic programming en-
use in software construction. Key ideas include:
ables, such as modularity, safety, and conciseness of expression.
• Expressing algorithms with minimal assumptions about
The results of this process constitute the main results of this pa-
data abstractions, and vice versa, thus making them as
per and are summarized in Table 1. The table lists the eight lan-
interoperable as possible.
guage features that we identi?ed as being important to generic pro-
gramming and shows the level of support for that feature in each
• Lifting of a concrete algorithm to as general a level as
language. We ?nd these features are necessary for the development
possible without losing ef?ciency; i.e., the most abstract
of high-quality generic libraries. Incomplete support of these fea-
form such that when specialized back to the concrete
tures can result in awkward designs, poor maintainability, unnec-
case the result is just as ef?cient as the original algo-
essary run-time checks, and painfully verbose code. As languages
increasingly support generics, it is important that language design-
ers understand the features necessary to provide powerful generics
• When the result of lifting is not general enough to cover
and that their absence causes serious dif?culties for programmers.
all uses of an algorithm, additionally providing a more
The rest of this paper describes how we reached the conclusions
general form, but ensuring that the most ef?cient spe-
in the table and why those language properties are important. The
cialized form is automatically chosen when applicable.
paper is organized as follows. Section 2 provides a brief introduc-

tion to generic programming and de?nes the terminology we use
Providing more than one generic algorithm for the same
in the paper. Section 3 describes the design of the generic graph li-
purpose and at the same level of abstraction, when none
brary that forms the basis for our comparisons. Sections 4 through 9
dominates the others in ef?ciency for all inputs. This
present the individual implementations of the graph library in the
introduces the necessity to provide suf?ciently precise
selected languages. Each of these sections also evaluates the level
characterizations of the domain for which each algo-
of support for generic programming provided by each language.
rithm is the most ef?cient.
In Section 10 we discuss in detail the most important issues we
Figure 1: De?nition of Generic Programming
encountered during the course of this study and provide a detailed
explanation of Table 1. We present some conclusions in Section 11.
concepts are used to constrain type parameters.
Traditionally, a concept consists of associated types, valid ex-
pressions, semantic invariants, and complexity guarantees. The
De?nitions of generic programming vary. Typically, generic pro-
associated types of a concept specify mappings from the model-
gramming involves type parameters for data types and functions.
ing type to other collaborating types (see Figure 4 for an example).
While it is true that type parameters are required for generic pro-
Valid expressions specify the operations that must be implemented
gramming, there is much more to generic programming than just
for the modeling type. At this point in the state of the art, type sys-
type parameters. Inspired by the STL, we take a broader view of
tems typically do not include semantic invariants and complexity
guarantees. Therefore, we state that for a type to properly model a
generic programming and use the de?nition from [18] reproduced
in Figure 1.
concept, the associated types and valid expressions speci?ed by the
Associated with this de?nition, terminology and techniques for
concept must be de?ned.
carrying out generic programming (and for supporting these key
These primary aspects of generic programming, i.e., generic al-
ideas) have emerged.
gorithms, concepts, re?nement, modeling, and constraints, are re-
alized in different ways in our different target programming lan-
guages. The speci?c language features that are used to support
generic programming are summarized in Table 2.
Fundamental to realizing generic algorithms is the notion of ab-
straction: generic algorithms are speci?ed in terms of abstract prop-
erties of types, not in terms of particular types. Following the ter-
minology of Stepanov and Austern, we adopt the term concept to
A simple example illustrates these generic programming issues.
mean the formalization of an abstraction as a set of requirements
The example is initially presented in C++; Figure 2 shows versions
on a type (or on a set of types) [1]. These requirements may be
in all six languages.
semantic as well as syntactic. A concept may incorporate the re-
In C++, type parameterization of functions is accomplished with
quirements of another concept, in which case the ?rst concept is
templates. The following is an example of a generic algorithm,
said to re?ne the second. Types that meet the requirements of a
realized as a function template in C++:
concept are said to model the concept. Note that it is not necessar-
template <class T>
ily the case that a concept will specify the requirements of just one
const T& pick(const T& x, const T& y) {
type—it is sometimes the case that a concept will involve multiple
if (better(x, y)) return x; else return y;
types and specify their relationships.
Concepts play an important role in specifying generic algorithms.
This algorithm applies the better function to its arguments and re-
Since a concept may be modeled by any concrete type meeting its
turns the ?rst argument if better returns true, otherwise it returns
requirements, algorithms speci?ed in terms of concepts must be
the second argument.
able to be used with multiple types. Thus, generic algorithms must
Not every type can be used with pick. The concept Comparable
be polymorphic. For languages that explicitly support concepts,
is de?ned to represent types that may be used with pick. Unfortu-

Standard ML
Java Generics
Generic C#
Multi-type concepts
Multiple constraints

Associated type access
Retroactive modeling
Type aliases
Separate compilation
Implicit instantiation

Concise syntax
?Using the multi-parameter type class extension to Haskell 98 [22].†Planned language additions. ‡Planned for inclusion in Whidbey release of C#.
Table 1: The level of support for important properties for generic programming in the evaluated languages. “Multi-type concepts” indicates
whether multiple types cane be simultaneously constrained. “Multiple constraints” indicates whether more than one constraint can be placed
on a type parameter. “Associated type access” rates the ease in which types can be mapped to other types within the context of a generic
function. “Retroactive modeling” indicates the ability to add new modeling relationships after a type has been de?ned. “Type aliases”
indicates whether a mechanism for creating shorter names for types is provided. “Separate compilation” indicates whether generic functions
are type-checked and compiled independently from their use. “Implicit instantiation” indicates that type parameters can be deduced without
requiring explicit syntax for instantiation. “Concise syntax” indicates whether the syntax required to compose layers of generic components
is independent of the scale of composition. The rating of “-” in the C++ column indicates that while C++ does not explicitly support the feature,
one can still program as if the feature were supported due to the ?exibility of C++ templates.
Java generics
Generic C#
Generic algorithm
function template
polymorphic function
generic class
generic method
generic method
type class
deferred class
inheritance (?)
inherit (:)
inherit (:)
param sig (:)
context (?)
conformance (?)
Table 2: The roles of language features used for generic programming.
nately, C++ does not support concepts directly so naming and docu-
bool better(const Orange& a, const Orange& b)
mentation conventions have been established to represent them [1].
{ return lexicographical compare(b.name.begin(), b.name.end(),
The Comparable concept is documented this way in C++:
a.name.begin(), a.name.end()); }
Apple and Orange model the Comparable concept implicitly via
the existence of the better function for those types.
bool better(const T&, const T&)
We ?nish by calling the generic algorithm pick with arguments
Any type T is a model of Comparable if there is a better function
of type int, Apple, and Orange.
with the given signature. For int to model Comparable, we simply
int main(int, char?[]) {
de?ne a better function for ints:
int i = 0, j = 2;
Apple a1(3), a2(5);

bool better(int i, int j) { return j < i; }
Orange o1(”Miller”), o2(”Portokalos”);
In C++ it is customary to identify concepts by appropriately nam-
int k = pick(i, j);
ing template parameters. The previous example would normally be
Apple a3 = pick(a1, a2);
Orange o3 = pick(o1, o2);
template <class Comparable>
const Comparable&
pick(const Comparable& x, const Comparable& y) {
if (better(x, y)) return x; else return y;
We de?ne two types, Apple and Orange
To evaluate support for generic programming, a library of graph
data structures was implemented in each language. The library
struct Apple {
Apple(int r) : rating(r) {}
provides generic algorithms associated with breadth-?rst search,
int rating;
including Dijkstra’s single-source shortest paths and Prim’s min-
imum spanning tree algorithms [13, 39]. The design presented here
bool better(const Apple& a, const Apple& b)
descends from the generic graph library presented in [43], which
{ return b.rating < a.rating; }
evolved into the Boost Graph Library (BGL) [41].
Figure 3 depicts the graph algorithms, their relationships, and
struct Orange {
Orange(const string& s) : name(s) { }
how they are parameterized. Each large box represents an algo-
string name;
rithm and the attached small boxes represent type parameters. An
arrow from one algorithm to another speci?es that one algorithm is

signature Comparable =
// concept Comparable:
// bool better(const T&, const T&)
type value t
val better : value t
? value t ? bool
template <class Comparable>
class Comparable t where
const Comparable& pick(const Comparable& x,
better :: (t, t) ? Bool
const Comparable& y) {
functor MakePick(C : Comparable) =
if (better(x, y)) return x; else return y;
pick :: Comparable t ? (t, t) ? t
type value t = C.value t
pick (x, y) = if (better (x, y)) then x else y
fun pick x y = if C.better(x,y) then x else y
struct Apple {
data Apple = MkApple Int
Apple(int r) : rating(r) {}
int rating;
structure Apple =
instance Comparable Apple where
better = (? (MkApple m, MkApple n) ? n < m)
bool better(const Apple& a, const Apple& b)
datatype value t = AppleT of int
{ return b.rating < a.rating; }
fun create n = AppleT n
a1 = MkApple 3; a2 = MkApple 5
fun better ((AppleT x),(AppleT y)) = y < x
a3 = pick(a1, a2)
int main(int, char?[]) {
Apple a1(3), a2(5);
Apple a3 = pick(a1, a2);

structure PickApples = MakePick(Apple)
val a1 = Apple.create 5 and a2 = Apple.create 3
val a3 = PickApples.pick a1 a2

Java Generics
Generic C#
deferred class COMPARABLE[T]

better (a: T) : BOOLEAN is deferred end

interface Comparable<T> {
go (a: T; b: T) : T is do
interface Comparable<T> {
boolean better(T x);
if a.better(b) then
bool better(T x);
Result := a
class pick {
Result := b
class pick {
static <T extends Comparable<T>>
static T go<T>(T a, T b)
T pick(T a, T b) {
where T : Comparable<T> {
if (a.better(b)) return a; else return b;
if (a.better(b)) return a; else return b;
class APPLE inherit COMPARABLE[APPLE] end
create make
class Apple implements Comparable<Apple> {
class Apple : Comparable<Apple> {
Apple(int r) { rating = r; }
make(r: INTEGER) is do rating := r end
public Apple(int r) {rating = r;}
public boolean better(Apple x)
better (a: APPLE) : BOOLEAN is do
public bool better(Apple x)
{ return x.rating < rating;}
Result := rating < a.rating;
{ return x.rating < rating; }
int rating;
private int rating;
feature {APPLE}
rating : INTEGER
public class Main {
public class Main eg {
public static void main(String[] args) {
public static int Main(string[] args) {
Apple a1 = new Apple(3),
Apple a1 = new Apple(3),
a2 = new Apple(5);
create make
a2 = new Apple(5);
Apple a3 = pick.go(a1, a2);
feature make is
Apple a3 = pick.go<Apple>(a1,a2);
return 0;
a1, a2, a3 : APPLE;
picker: pick[APPLE];
create picker;
create a1.make(3); create a2.make(5);
a3 := picker.go(a1, a2);

Figure 2: Comparing Apples to Apples. The Comparable concept, pick function, and Apple data type are implemented in each of our target
languages. A simple example using each language is also shown.

implemented using the other. An arrow from a type parameter to
implemented using other library algorithms: breadth-?rst search
an unboxed name speci?es that the type parameter must model that
and Dijkstra’s shortest paths use graph search, Prim’s minimum
concept. For example, the breadth-?rst search algorithm has three
spanning tree algorithm uses Dijkstra’s algorithm, and Johnson’s
type parameters: G, C, and Vis. Each of these have requirements: G
all-pairs shortest paths algorithm uses both Dijkstra’s and Bellman-
must model the Vertex List Graph and Incidence Graph concepts, C
Ford shortest paths. Type parameters for some algorithms, such as
must model the Read/Write Map concept, and Vis must model the
the G parameter to breadth-?rst search, must model multiple con-
BFS Visitor concept. Finally, breadth-?rst search is implemented
cepts. In addition, the algorithms require certain relationships be-
using the graph search algorithm.
tween type parameters. For example, consider the graph search
The core algorithm of this library is graph search, which tra-
algorithm. The C type argument, as a model of Read/Write Map, is
verses a graph and performs user-de?ned operations at certain points
required to have an associated key type. The G type argument is
in the search. The order in which vertices are visited is controlled
required to have an associated vertex type. Graph search requires
by a type argument, B, that models the Bag concept. This concept
that these two types be the same.
abstracts a data structure with insert and remove operations but no
The graph library is used throughout the remainder of this paper
requirements on the order in which items are removed. When B is
as a common basis for discussion. Though the entire library was
bound to a FIFO queue, the traversal order is breadth-?rst. When
implemented in each language, discussion is limited for brevity.
it is bound to a priority queue based on distance to a source vertex,
We focus on the interface of the breadth-?rst search algorithm and
the order is closest-?rst, as in Dijkstra’s single-source shortest paths
the infrastructure surrounding it, including concept de?nitions and
algorithm. Graph search is also parameterized on actions to take at
an example use of the algorithm. The interested reader can ?nd the
event points during the search, such as when a vertex is ?rst dis-
full implementations for each language, including instructions for
covered. This parameter, Vis, must model the Visitor concept. The
compilation, at the following URL:
graph search algorithm also takes a type parameter C for mapping
each vertex to its color and C is required to model the Read/Write
Map concept.
The Read Map and Read/Write Map concepts represent variants
C++ generics were intentionally designed to exceed what is re-
of an important abstraction in the graph library: the property map.
quired to implement containers. The resulting template system
In practice, graphs represent domain-speci?c entities. For exam-
provides a platform for experimentation with, and insight into the
ple, a graph might depict the layout of a communication network,
expressive power of, generic programming. Before templates, C++
vertices representing endpoints and edges representing direct links.
was primarily considered an object-oriented programming language.
In addition to the number of vertices and the edges between them,
Templates were added to C++ for the same reason that generics
a graph may associate values to its elements. Each vertex of a com-
were added to several other languages in our study: to provide
munication network graph might have a name and each edge a max-
a means for developing type safe containers [46, §15.2]. Greater
imum transmission rate. Some algorithms require access to domain
emphasis was placed on clean and consistent design than restric-
information associated with the graph representation. For example,
tion and policy. For example, although function templates are not
Prim’s minimum spanning tree algorithm requires “weight” infor-
necessary to develop type-safe polymorphic containers, C++ has al-
mation associated with each edge in a graph. Property maps pro-
ways supported classes and standalone functions equally; support-
vide a convenient implementation-agnostic means of expressing, to
ing function templates in addition to class templates preserves that
algorithms, relations between graph elements and domain-speci?c
design philosophy. Early experiments in developing generic func-
data. Some graph data structures directly contain associated val-
tions suggested that more comprehensive facilities would be bene-
ues with each node; others use external associative data structures
?cial. These experiments also inspired design decisions that differ
to express these relationships. Interfaces based on property maps
from the object-oriented generics designs (Java generics, Generic
work equally well with both representations.
C#, and Eiffel). For example, C++ does not contain any explicit
The graph algorithms are all parameterized on the graph type.
mechanism for constraining template parameters. During C++ stan-
Graph search takes one type parameter G, which must model two
dardization, several mechanisms were proposed for constraining
concepts, Incidence Graph and Vertex List Graph. The Incidence
template parameters, including subtype-based constraints. All pro-
Graph concept de?nes an interface for accessing out-edges of a ver-
posed mechanisms were found to either undermine the expressive
tex. Vertex List Graph speci?es an interface for accessing the ver-
power of generics or to inadequately express the variety of con-
tices of a graph in an unspeci?ed order. The Bellman-Ford shortest
straints used in practice [46, §15.4].
paths algorithm [4] requires a model of the Edge List Graph con-
Two C++ language features combine to enable generic program-
cept, which provides access to all the edges of a graph.
ming: templates and function overloading. C++ includes both func-
That graph capabilities are partitioned among three concepts il-
tion templates and class templates; we use function templates to
lustrates generic programming’s emphasis on algorithm require-
represent generic algorithms. We discuss the role of function over-
ments. The Bellman-Ford shortest paths algorithm requires of a
loading in the next section. In C++, templates are not separately
graph only the operations described by the Edge List Graph con-
type checked. Instead, type checking is performed after instantia-
cept. Graph search, in contrast, requires the functionality of both
tion at each call site. Type checking of the bound types can only
its required concepts. By partitioning the functionality of graphs,
succeed when the input types have satis?ed the type requirements
each algorithm can be used with any data type that meets its mini-
of the function template body. Unfortunately, because of this, if a
mum requirements. If the three graph concepts were replaced with
generic algorithm is invoked with an improper type, byzantine and
one, each algorithm would require more from its graph type param-
potentially misleading error messages may result.
eter than necessary—and would thus unnecessarily restrict the set
of types with which it could be used.
The graph library design is suitable for evaluating generic pro-
The breadth ?rst search function template is shown in Figure 4.
gramming capabilities of languages because it includes a rich vari-
C++ does not provide direct support for constraining type parame-
ety of generic programming techniques. Most of the algorithms are
ters; standard practice is to express constraints in documentation in

Read/Write-Map BFS Visitor
<models> Visitor
Edge List Graph
Incidence Graph
Vertex List Graph
G C Vis
G C B Vis
Breadth-First Search
Graph Search
Bellman-Ford Shortest Paths
Vertex List Graph <models>
Prim Min Span Tree
Dijkstra Shortest Paths
Johnson All-Pairs
Figure 3: Graph algorithm parameterization and reuse within the graph library. Arrows for redundant models relationships are not shown.
For example, the type parameter G of breadth-?rst search must also model Incidence Graph because breadth-?rst search uses graph search.
template <class G, class C, class Vis>
void breadth ?rst search(const G& g,
typename graph traits<G>::vertex s, C c, Vis vis);
graph traits<G>::vertex
graph traits<G>::edge
G models Vertex List Graph and Incidence Graph
vertex src(edge, const G&);
C models Read/Write Map
vertex tgt(edge, const G&);
map traits<C>::key == vertex
Incidence Graph re?nes Graph
map traits<C>::value models Color
graph traits<G>::out edge iter models Iterator
Vis models BFS Visitor
pair<out edge iter> out edges(vertex, const G&);
Figure 4: Breadth-?rst search as a function template.
int out degree(vertex, const G&);
Vertex List Graph
graph traits<G>::vertex iter models Iterator
conjunction with meaningful template parameter names [1]. Tech-
pair<vertex iter> vertices(const G&);
niques for checking constraints in C++ can be implemented as a li-
int num vertices(const G&);
brary [29, 42]. These techniques, however, are distinct from ac-
tual language support and involve insertion of what are essentially
Table 3: Documentation for the graph concepts.
compile-time assertions into the bodies of generic algorithms.
The graph traits class template provides access to the associated
types of the graph type. Here we use graph traits to access the ver-
tex type. Traits classes are an idiom used in C++ to map types to
class AdjacencyList {
other types or functions [37]. A traits class is a class template. For
each type in the domain of the map a specialized version of the class
template is created containing nested typedefs and member func-
vector< list<int> > adj lists;
tions. In Figure 5 we specialize graph traits for the AdjacencyList
class, which models Graph.
template <> struct graph traits<AdjacencyList> {
Inside the breadth ?rst search function, calls to functions asso-
typedef int vertex;
ciated with the concepts, such as out edges from Incidence Graph,
typedef pair<int, int> edge;
are resolved by the usual function overloading rules for C++. That is,
typedef list<int>::const iterator out edge iter;
each is resolved to the best overload for the given argument types.
Documentation for the graph concepts is shown in Table 3. In
addition to function signatures, the concepts specify access to as-
Figure 5: Sketch of a concrete graph implementation.
sociated types such as vertex, edge, and iterator types through the
graph traits class.
A sketch of a concrete adjacency list implementation is shown
in Figure 5. The AdjacencyList class is a model of the
Read Map
Graph and Vertex List Graph concepts, but this fact is implicit. There
map traits<M>::key
is no mechanism for specifying that AdjacencyList models these
map traits<M>::value
concepts. The graph traits class is specialized for AdjacencyList
value get(const M&, key);
so the associated types can be accessed from within function tem-
Read/Write Map re?nes Read Map
void put(M&, key, value);
The de?nitions of the Read/Write Map and Read Map concepts
are in Table 4 and the de?nition of the BFS Visitor concept is in
Table 4: Documentation for the mapping concepts.
Table 5.

BFS Visitor
up”). As a result, any function call inside a function template may
void V::discover vertex(vertex, G);
resolve to functions in other namespaces. Sometimes this may be
void V::?nish vertex(vertex, G);
the desired result, but other times not. Typically, the operations
void V::examine edge(edge, G);
required by the constraints of the function template are meant to
void V::tree edge(edge, G);
bind to functions in the client’s namespace, whereas other calls are
void V::non tree edge(edge, G);
meant to bind to functions in the namespace of the generic library.
void V::gray target(edge, G);
With argument-dependent lookup, these other calls can be acci-
void V::black target(edge, G);
dentally hijacked by functions with the same name in the client’s
Table 5: Documentation for the BFS Visitor concept.
Nevertheless, C++ templates still provide type safety with gener-
icity; there is no need to use downcasts or similar mechanisms
In the code below, an example use of the breadth ?rst search
when constructing generic libraries. Of course, C++ itself is not
function is presented. The vertices of a graph are output in breadth-
fully type safe because of various loopholes that exist in the type
?rst order by creating the test vis visitor that overrides the function
system. These loopholes, however, are orthogonal to templates.
discover vertex; empty implementations of the other visitor func-
The template system does not introduce new issues with respect to
tions are provided by default bfs visitor. A graph is constructed us-
type safety.
ing the AdjacencyList class, and then the call to breadth ?rst search
Finally, since templates are purely a means for obtaining static
is made. The call site is the point where type checking occurs for
(compile-time) polymorphism, there is no run-time performance
the body of the breadth ?rst search function template; function
penalty due to templates per se. Generic libraries, however, make
templates are not separately type checked. This type check ensures
heavy use of procedural and data abstraction which can induce
that the argument types satisfy the needs of the body of the generic
run-time overheads, though good optimizing compilers are adept
function, but it does not verify that the types model the concepts
at at ?attening these layers of abstraction. C++ can therefore be an
required by the algorithm (because the needs of the body may be
excellent tool for applications where run-time ef?ciency is criti-
less than the declared constraints for the function).
cal [44, 47]. Heavy use of templates can sometimes lead to signif-
typedef graph traits<AdjacencyList>::vertex vertex;
icant increases in executable size, although there are programming
idioms that ameliorate this problem.
struct test vis : public default bfs visitor {
void discover vertex(vertex v, const AdjacencyList& g)
{ cout << v << ” ”; }
Generic programs in Standard ML leverage three language fea-
tures: structures, signatures, and functors. Structures group pro-
int main(int, char?[]) {
int n = 7;
gram components into named modules. They manage the visibil-
typedef pair<int,int> E;
ity of identi?ers and at the same time package related functions,
E edges[] = { E(0,1), E(1,2), E(1,3), E(3,4),
types, values, and other structures. Signatures constrain the con-
E(0,4), E(4,5), E(3,6) };
tents of structures. A signature prescribes what type names, values,
AdjacencyList g(n, edges);
and nested structures must appear in a structure. A signature also
vertex s = get vertex(0, g);
prescribes a type for each value, and a signature for each nested
vector property map color(n, white);
breadth ?rst search(g, s, color, test vis());

structure. In essence, signatures play the same role for structures
as types play for values. Functors are templates for creating new
structures and are parameterized on values, types, and structures.
Multiple structures of similar form can be represented using a sin-
Evaluation of C++ Generics
gle functor that emphasizes characteristics the structures hold in
common. Differences between these structures are captured by the
C++ templates succeed in enabling the expression of generic algo-
functor’s parameters. Functors represent ML’s primary mechanism
rithms, even for large and complex generic libraries. It is relatively
for generics. As illustrated in the following, structures, signatures,
easy to convert concrete functions to function templates, and func-
and functors together enable generic programming.
tion templates are just as convenient for the client to call as normal
functions. The traits mechanism provides a way to access associ-
ated types, an area where several other languages fail.
Concepts are expressed in ML using signatures. The following
The C++ template mechanism, however, has some drawbacks in
code shows ML representations of graph concepts for the breadth-
the area of modularity. The complete implementations of templates
?rst search algorithm:
reside in header ?les (or an equivalent). Thus, users must recom-
pile when template implementations change. In addition, at call
signature GraphSig =
sites to function templates, the arguments are not type checked
type graph t
against the interface of the function—the interface is not expressed
eqtype vertex t
in the code— but instead the body of the function template is type
checked. As a result, when a function template is misused, the re-
sulting error messages point to lines within the function template.
signature IncidenceGraphSig =
The internals of the library are thus needlessly exposed to the user
and the real reason for the error becomes harder to ?nd.
include GraphSig
type edge t

Another problem with modularity is introduced by the C++ over-
val out edges : graph t ? vertex t ? edge t list
load resolution rules. During overload resolution, functions within
val source : graph t ? edge t ? vertex t
namespaces that contain the de?nitions of the types of the argu-
val target : graph t ? edge t ? vertex t
ments are considered in the overload set (“argument-dependent look-

tex List Graph, and Incidence Graph concepts. ALGraph de?nes
signature VertexListGraphSig =
additional functions that fall outside the requirements of the three
signatures. The create function, for example, constructs a value of
include GraphSig
type graph t, which represents a graph with nv vertices.
val vertices : graph t ? vertex t list
val num vertices : graph t
? int
In ML, algorithms are implemented using functors. The follow-
ing code illustrates the general structure of a generic breadth-?rst
search implementation:
For signature names, we use the convention of af?xing Sig to the
end of corresponding concept names. The GraphSig signature rep-
functor MakeBFS(Params : BFSPSig) =
resents the Graph concept and requires graph t and vertex t types.
fun breadth ?rst search g v vis map = ...
It also requires vertex t to be an equality type, meaning vertex t
values can be compared using the = operator.
IncidenceGraphSig and VertexListGraphSig demonstrate con-
Generic algorithms are instantiated by way of functor application.
cept re?nement in ML. The clause include GraphSig in each sig-
When a functor is applied to parameters that satisfy certain require-
nature imports the contents of the GraphSig signature. The include
ments, it creates a new structure specialized for the functor param-
directive cannot, however, represent all re?nements between con-
eters. The MakeBFS functor takes one parameter, a structure that
cepts. Though a signature may include more than one other signa-
ful?lls the requirements of the following signature:
ture, all included signatures must declare different identi?ers. Con-
signature BFSPSig =
sider the following code:
(? ERROR: VertexListGraphSig and IncidenceGraphSig overlap ?)
structure G1 : IncidenceGraphSig
signature VertexListAndIncidenceGraphSig =
structure G2 : VertexListGraphSig
structure C : ColorMapSig
include VertexListGraphSig
structure Vis : BFSVisitorSig
include IncidenceGraphSig
sharing G1 = G2 = Vis
sharing type C.key t = G1.vertex t
This example shows an incorrect attempt to describe a Vertex List
And Incidence Graph concept that re?nes both the Vertex List Graph
The signature dictates that Params must contain four nested struc-
and Incidence Graph concepts. The ML type system rejects this ex-
tures, each corresponding to an algorithm parameter. BFSPSig en-
ample because both VertexListGraphSig and IncidenceGraphSig
forces concept requirements by constraining its nested structures
share the vertex t and graph t names from the GraphSig signa-
with signatures. The G1 structure, for example, is constrained by
ture. To work around this issue, an algorithm that would other-
the IncidenceGraphSig signature.
wise require a model of the Vertex List and Incidence Graph con-
The breadth-?rst search algorithm ideally requires a graph type
cept instead requires two arguments, a model of Vertex List Graph
argument that models both the Incidence Graph and Vertex List
and a model of Incidence Graph, and places additional restrictions
Graph concepts. Because the signatures that represent these two
on those arguments. The implementation of breadth-?rst search in
concepts cannot be composed, the implementation requires two
ML, shown later, demonstrates this technique.
arguments, constrained by the signatures IncidenceGraphSig and
Program components that model concepts are implemented as
VertexListGraphSig respectively. When the MakeBFS functor is
structures. The following code shows the adjacency list graph im-
applied, the same structure is bound to both type parameters.
plemented in ML:
In addition to listing required structures, BFSPSig speci?es that
some type names in the structures must refer to identical types.
structure ALGraph =
These are denoted as sharings. Two sharings appear in the BFSPSig
signature. The ?rst is a structure sharing among G1, G2, and Vis.
datatype graph t = Data of int ? int list Array.array
type vertex t = int

It states that if the three structures share any nested element name in
type edge t = int ? int
common, then the name must refer to the same entity for all three
structures. For example, each of the three structures is required
fun create(nv : int) = Data(nv,Array.array(nv,[]))
by its signature to contain a nested type vertex t. The sharing re-
quires that G1.vertex t, G2.vertex t, and Vis.vertex t must refer to
fun add edge (G as Data(n,g),(src:int),(tgt:int)) =
the same type. The second sharing, a type sharing, declares that
( Array.update(g,src,tgt::Array.sub(g,src)); G )
C.key t and G1.vertex t must be the same type. Sharings emphasize
fun vertices (Data(n,g)) = List.tabulate(n,fn a => a);
that in addition to the signature requirements placed on each sub-
fun num vertices (Data(n,g)) = n
structure of Params, certain relationships between structures must
fun out edges (Data(n,g)) v = map (fn n => (v,n)) (Array.sub(g,v))
also hold.
fun adjacent vertices (Data(n,g),v) = Array.sub(g,v)
ML supports multi-parameter functors, but it does not support
fun source (Data(n,g)) (src,tgt) = src
sharing speci?cations among the parameters. As a workaround,
fun target (Data(n,g)) (src,tgt) = tgt
functors that implement generic algorithms accept a single struc-
fun edges (Data(n,g)) =
ture parameter whose signature lists the algorithm’s arguments and
#2(Array.foldl (fn (tgts:int list,(src,sofar:(int?int) list)) =>
speci?es the necessary relationships among them. Since the struc-
(src+1,(map (fn n => (src,n)) tgts) @ sofar))
ture argument to the functor can be de?ned at the point of applica-
(0,[]) g)
tion, the single parameter solution is reasonable.
The following code shows a call to breadth ?rst search:
The ALGraph structure encapsulates types that represent graph val-
structure BFS =
ues and functions that operate on them. Because it meets the re-
quirements of the GraphSig, VertexListGraphSig, and Incidence-
structure G1 = ALGraph
GraphSig signatures, ALGraph is said to model the Graph, Ver-
structure G2 = ALGraph

structure C = ALGColorMap
ues, a generic algorithm takes a dictionary for each concept model
structure Vis = VisitImpl
it requires. The algorithm is then implemented in terms of the func-
tions from the dictionaries.
This style of generic programming in ML, though possible, is
BFS.breadth ?rst search g src (VisitImpl.create())
not ideal. In larger ML programs, managing dictionaries man-
ually becomes cumbersome and increases the code base signi?-
First, the algorithm is instantiated by applying MakeBFS to a struc-
cantly. This situation is analogous to implementing virtual tables in
ture, de?ned in place, that meets BFSPSig’s requirements. The
C rather than leveraging the object-oriented programming features
ALGraph structure is used to match both the IncidenceGraphSig
of C++. In fact, some Haskell environments lower programs that use
and VertexListGraphSig signatures. Although this is awkward, it
generics (type classes) to equivalent Haskell programs that use this
avoids the explicit declaration of a VertexListAndIncidenceGraph-
dictionary-passing style. Automating the mechanisms of generic
Sig signature, which cannot be constructed by composing the two
programming is preferable to implementing them manually.
mentioned signatures. The ALGColorMap structure models the
Using ML functors to implement generic algorithms enables the
Read/Write Map concept. The VisitImpl structure models the BFS
convenient application of algorithms to a variety of user-de?ned
Visitor concept and encapsulates user-de?ned callbacks. The three
components. Functors in ML only require their arguments to con-
structures together meet the sharing requirements of BFSPSig. Ap-
form structurally to the speci?ed signatures. Since ML structures
plication of the MakeBFS functor de?nes the BFS structure, which
can implicitly conform to signatures, a structure need not be de-
encapsulates a breadth ?rst search function specialized with the
signed with a signature in mind. Thus, a generic ML algorithm,
above structures. Finally, BFS.breadth ?rst search is called with
written in terms of signatures, can operate on any structures that
parameters that match the now concrete type requirements.
meets its requirements.
Evaluation of ML
In order to promote modularity, a language may allow program
components that model concepts to be statically checked against
ML language mechanisms provide good support for generic pro-
concepts prior to their use with generic algorithms. When a struc-
gramming. Signatures and structures conveniently express con-
ture is de?ned in ML, it may be constrained by a signature. In this
cepts and concept models using nested types and functions to im-
manner a structure’s conformity to a signature can be con?rmed
plement associated types and valid expressions. The structure rep-
apart from its use in a generic algorithm. Constraining a structure
resentation of concept models enables modularity by managing iden-
with a signature limits its interface to that described by the sig-
ti?er visibility. Functors can express any generic algorithm of sim-
nature. This may not be the desired result if the structure de?nes
ilar complexity to the described graph library algorithms. Signa-
members that the signature does not declare. For example, if the
tures effectively constrain generic algorithms with respect to the
ALGraph structure were declared:
concepts upon which the algorithms are parameterized. Sharing
structure ALGraph : IncidenceGraphSig = ...
speci?cations enable separate type checking of generic algorithms
and their call sites. They capture additional requirements on the
then it would no longer meet the VertexListGraphSig requirements
concept parameters to an algorithm. All necessary sharing rela-
because vertices and num vertices would not be visible.
tionships between functor parameters must be declared explicitly.
Rather than constrain the structure directly, the conformity of
If not, ML will issue type checking errors when the functor is an-
ALGraph to the necessary signatures can be checked as shown in
alyzed. When a functor is applied, ML veri?es that its arguments
the following code outline:
also meet the sharing and signature requirements imposed on the
structure ALGraph =
Technically, functors are not the only means for implementing
generic algorithms. ML programmers often use polymorphic func-
tions and parameterized data types to achieve genericity. An exam-
ple of this style of programming follows.
structure ALGraphCheck1 : IncidenceGraphSig = ALGraph;
structure ALGraphCheck2 : VertexListGraphSig = ALGraph;

(? concept ?)
datatype ’a Comparable = Cmp of (’a
? ’a ? bool);
The structures ALGraphCheck1 and ALGraphCheck2 are both as-
signed ALGraph and constrained by the IncidenceGraphSig and
(? models ?)
VertexListGraphSig signatures respectively. Each of these struc-
datatype Apples = Apple of int;
tures con?rms statically that ALGraph conforms to the correspond-
fun better apple (Apple x) (Apple y) = x > y;
ing signature without limiting access to its structure members. This
datatype Oranges = Orange of int;
technique as a side effect introduces the unused ALGraphCheck1
fun better orange (Orange x) (Orange y) = x > y;
and ALGraphCheck2 structures.
As previously described, the include mechanism for signature
(? algorithm ?)
combination in ML cannot express concept re?nements that involve
fun pick ((Cmp better):’a Comparable) (x:’a) (y:’a) =
overlapping concepts. Ramsey [40] discusses this shortcoming and
if (better x y) then x else y;
suggests language extensions to address it.
(? examples ?)
pick (Cmp better apple) (Apple 4) (Apple 3);

pick (Cmp better orange) (Orange 3) (Orange 4);
The Haskell community uses the term “generic” to describe a
This example implements the better algorithm in terms of the Com-
form of generative programming with respect to algebraic datatypes
parable concept. Here a concept is realized using a parameterized
[2, 15, 19]. Thus the typical use of the term “generic” with respect
data type that holds a table of functions or dictionary. The con-
to Haskell is somewhat different from our use of the term. How-
cept’s associated types are the data type’s parameters, and its valid
ever, Haskell does provide support for generic programming as we
expressions are the dictionary functions. In addition to other val-
have de?ned it here and that is what we present in this section.

The speci?cation of the graph library in Figure 3 translates natu-
data AdjacencyList = AdjList (Array Int [Int])
rally into polymorphic functions in Haskell. In Haskell, a function
deriving (Read, Show)
is polymorphic if an otherwise unde?ned type name appears in the
data Vertex = V Int deriving (Eq, Ord, Read, Show)
type of a function; such a type is treated as a parameter. Constraints
data Edge = E Int Int deriving (Eq, Ord, Read, Show)
on type parameters are given in the context of the function, i.e., the
adj list :: Int ? [(Int,Int)] ? AdjacencyList
code between :: and ?. The context contains class assertions. In
adj list n elist =
Haskell, concepts are represented with type classes. Although the
AdjList (accumArray (++) [] (0, n ? 1)
keyword Haskell uses is class, type classes are not to be confused
[ (s, [t]) | (s,t) ? elist])
with object-oriented classes. In traditional object-oriented termi-
nology, one talks of objects being instances of a class, whereas in
instance Graph AdjacencyList Edge Vertex where
Haskell, types are instances of type classes. A class assertion de-
src (E s t) g = V s
tgt (E s t) g = V t

clares which concepts the type parameters must model. In Haskell,
the term instance corresponds to our term model. So instead of
instance IncidenceGraph AdjacencyList Edge Vertex where
saying that a type models a concept, one would say a type is an
out edges (V s) (AdjList adj) = [ E s t | t ? (adj!s) ]
instance of a type class.
out degree (V s) (AdjList adj) = length (adj!s)
instance VertexListGraph AdjacencyList Vertex where
vertices (AdjList adj) = [V v | v ? (iota n) ]
As with the previous languages, we focus on th