Difference between revisions of "Runtime Concepts"
(→Generic Polymorphism) 
m (→Semantic Requirement) 

(30 intermediate revisions by one user not shown)  
Line 24:  Line 24:  
from reference semantics. Regularity together with valuesemantics eases  from reference semantics. Regularity together with valuesemantics eases  
reasoning about programs and allows the programmer to perform optimizations  reasoning about programs and allows the programmer to perform optimizations  
−  [DS98].  +  [DS98]. We extend the regular operations defined by [DS98] and add efficient 
+  operations for swap and move. Each regular object is swapable by <math> std::swap </math>  
+  which relies on copy construction and assignment. The explicit swap operation  
+  allows avoiding the creation of temporary objects. Likewise, the addition of  
+  move allows the reuse of part objects that are about to be destructed.  
<Shape example>  <Shape example>  
Line 85:  Line 89:  
Many software projects require working on heterogeneous collections of data. Typically, this polymorphism is expressed through inheritance. However, inheritance tightly couples a type with a set of operations which can be performed on it. This tight coupling is often manifest through implicit data structures and algorithms which hinder the ability to understand and reuse code. Because the polymorphic types can be of different sizes they must be allocated in the free store, this introduces the use of object factories, adds an additional level of indirection, and imposes a need to manage the free store memory. This in terms leads to the use of reference counted pointers and the requirement of controlling multiple references to objects in a threaded environment which negatively impact performance.  Many software projects require working on heterogeneous collections of data. Typically, this polymorphism is expressed through inheritance. However, inheritance tightly couples a type with a set of operations which can be performed on it. This tight coupling is often manifest through implicit data structures and algorithms which hinder the ability to understand and reuse code. Because the polymorphic types can be of different sizes they must be allocated in the free store, this introduces the use of object factories, adds an additional level of indirection, and imposes a need to manage the free store memory. This in terms leads to the use of reference counted pointers and the requirement of controlling multiple references to objects in a threaded environment which negatively impact performance.  
−  
−  
−  
−  
===Outline===  ===Outline===  
Line 106:  Line 106:  
In the process of abstraction the tight binding from an algorithm to concrete  In the process of abstraction the tight binding from an algorithm to concrete  
types is relaxed and replaced with a set of semantic requirements. Types must  types is relaxed and replaced with a set of semantic requirements. Types must  
−  satisfy these  +  satisfy these requirements in order to work properly with a generic algorithm. 
Checking types against arbitrary semantic requirements is in general  Checking types against arbitrary semantic requirements is in general  
undecidable. Thus, semantic requirements are stated in tables, in documentation,  undecidable. Thus, semantic requirements are stated in tables, in documentation,  
Line 112:  Line 112:  
Checker] allow to formally describe semantic requirements, but none of those is  Checker] allow to formally describe semantic requirements, but none of those is  
part of current C++.  part of current C++.  
−  [  +  [''note: we could also mention axioms of the concept proposal'']. 
Instead, the compiler checks for the presence of syntactic constructs, which are  Instead, the compiler checks for the presence of syntactic constructs, which are  
a part of semantic requirements. Consider the following example, which describes  a part of semantic requirements. Consider the following example, which describes  
Line 130:  Line 130:  
}  }  
</pre>  </pre>  
−  
−  
====Concept====  ====Concept====  
Line 168:  Line 166:  
A concept <math> C_r </math> augmenting another concept <math> C_0 </math> with  A concept <math> C_r </math> augmenting another concept <math> C_0 </math> with  
−  additional requirements is a concept refinement and denoted by <math> C_r  +  additional requirements is a concept refinement and denoted by <math> C_r ''pred'' C_0 </math>. 
Therefore the number of types meeting the semantic requirements for <math> C_r </math>  Therefore the number of types meeting the semantic requirements for <math> C_r </math>  
is smaller or equal compared to the number of types that meet the requirements  is smaller or equal compared to the number of types that meet the requirements  
Line 174:  Line 172:  
the number of algorithms that can be expressed with a given concept. For example,  the number of algorithms that can be expressed with a given concept. For example,  
RandomAccessIterator refines BidirectionalIterator and adds the requirement  RandomAccessIterator refines BidirectionalIterator and adds the requirement  
−  for constant time random access ([]operator), which allows  +  for constant time random access ([]operator), which allows writing a binary 
search algorithm.  search algorithm.  
====Algorithm Refinement====  ====Algorithm Refinement====  
−  Parallel to concept refinements, algorithms can be refined to exploit the  +  Parallel to concept refinements, an algorithms <math> A_0 </math> can be refined 
−  stronger requirements  +  by another algorithm <math> A_r </math> to exploit the stronger concept 
−  +  requirements and achieve better space and/or runtime efficiency. For example,  
−  BidirectionalIterator is O(n), while it is O(lg n) for ForwardIterator  +  the complexity of reverse on BidirectionalIterator is O(n), while it is O(lg n) 
−  (assuming less than O(n) memory usage).  +  for ForwardIterator (assuming less than O(n) memory usage). 
====Analogy to Algebraic Structures====  ====Analogy to Algebraic Structures====  
Line 213:  Line 211:  
''[This section is intended to introduce runtimepolymorphism based on concepts and to show that a concept based definition of runtime polymorphism is a super set of the C++ inheritance model of polymorphism.]''  ''[This section is intended to introduce runtimepolymorphism based on concepts and to show that a concept based definition of runtime polymorphism is a super set of the C++ inheritance model of polymorphism.]''  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
In the presented work, we replace a concrete type with a placeholdertype  In the presented work, we replace a concrete type with a placeholdertype  
Line 246:  Line 230:  
Instead of requiring an explicit relationship between runtimeconcept and  Instead of requiring an explicit relationship between runtimeconcept and  
concrete type we apply the external polymorphism pattern (EPP) [CSH96].  concrete type we apply the external polymorphism pattern (EPP) [CSH96].  
−  Therefore, runtime  +  Therefore, a runtimemodel <math> M </math> is a template class that gets 
−  concrete type.  +  instantiated with a concrete type <math> T </math>. Its instantiation is 
−  +  orthogonal to the definition of concrete types. A programmer can specialize the  
−  in order to provide adjustments to the interface if needed.  +  modeltemplate for a particular type in order to provide adjustments to the 
+  interface if needed.  
−  +  The use of polymorphic objects is non regular and  
−  thus problematic. As a matter of fact, polymorphic classes cannot be regular but  +  thus problematic. As a matter of fact, polymorphic classes alone cannot be 
−  neither can regular classes be polymorphic.  +  regular but neither can regular classes alone be polymorphic. Consider a class 
−  +  hierarchy with two classes <math> Base, Derived </math> and copy semantics.  
−  and  +  Writing the code in terms of copy construction would encode the type in the 
−  +  code, but even using a clone function as illustrated in Fig. <?b> would not  
−  +  work, as the returned object of ''Derived::clone'' would be subject to slicing.  
+  Conversely, returning an object by reference, would compromise value semantics  
+  and regularity Fig<?a>.  
+  <pre>  
+  // (a) Nonpolymorphic regularity  
+  Base Base::clone();  
+  Derived Derived::clone();  
+  
+  // (b) Nonregular polymorphism  
+  Base& Base::clone();  
+  Derived& Derived::clone();  
+  </pre>  
+  
+  Our solution to this problem is a combination of both. We represent runtimeconcepts through a regular (<math> R_0 </math>) and polymorphic layer (<math> P0 </math>). The layers of the generic polymorphism pattern are shown in figure <1>. The regularobject leverages its polymorphic pendants and provides a regular interface for them.  
+  <math> R_0 </math> is a concrete class referring to some object that implement the interface ConceptInterface. Thus <math> R_0 </math> can be regarded as a placeholder type for template instantiations. <math> P_0 </math> is an abstract class defining the operations on the objects. The model <math> M_0 </math> is inherits from <math> P_0 </math> and is templatized with a concrete type <math> T </math>. Its instantiation <math> M_0(T) </math> maps the operations defined in <math> P_0 </math> onto operations of <math> T </math>.  
[[Image:Runtime_concept.pngClass Colaboration Figure 1]]  [[Image:Runtime_concept.pngClass Colaboration Figure 1]]  
−  +  Table <?> gives an overview how elements of concept definitions are represented within the regular and polymorphic layer.  
−  +  
−  +  
−  definitions are represented within the regular and polymorphic layer  +  
−  +  
−  +  
−  +  
{ border="1"  { border="1"  
−  + Table <?> :  +  + Table <?> : Regular Type and Runtime Concept 
−  !  +  ! Regular Type !! Regular Layer (R) !! Polymorphic Layer (P) 
    
−    +   Default Constructor  R a   
    
−    +   Copy Constructor  R(const R&)  virtual P& clone() 
    
−    +   Destructor  ~R()  virtual ~P() 
    
−    +   Assignment  R& operator=(R&, const R&)  virtual void assign(const P&) 
−    +   
−    +   Equality  bool operator==(const R&, const R&)  virtual bool equal(const P&) const 
+    
+   Swap  swap(R&)    
+    
+   Move  move(R&)    
}  }  
+  
+  
+  We describe how elements of compile time concepts are mapped in the  
+  regular and polymorphic layer and present an example by means of the  
+  regularity concept.  
+  
'''Functions''' (Operators, Constructors, etc): In the regular layer, any  '''Functions''' (Operators, Constructors, etc): In the regular layer, any  
Line 308:  Line 311:  
operator that allows an integer argument. Since the runtimeconcept model is  operator that allows an integer argument. Since the runtimeconcept model is  
nonintrusive and the concept C does not enforce a particular type for x, data  nonintrusive and the concept C does not enforce a particular type for x, data  
−  members cannot be directly represented  +  members cannot be directly represented. Instead, we use property objects, which sole purpose is 
−  +  
to virtualize member access and invoke the appropriate functions in the  to virtualize member access and invoke the appropriate functions in the  
polymorphic layer. An example for a property object in the regular layer is  polymorphic layer. An example for a property object in the regular layer is  
Line 334:  Line 336:  
'''Concept Refinements''': In the generic polymorphism model, concept  '''Concept Refinements''': In the generic polymorphism model, concept  
−  refinements <math> C_r  +  refinements <math> C_r <: C_0 </math> are represented by regular 
−  <math> R_0  +  <math> R_0, R_r </math> and polymorphic classes <math> P_0, P_r </math>. 
−  +  <math> R_0 </math> and <math> R_r </math> model the  
−  concepts <math> C_0 </math> and <math> C_r </math> respectively. A  +  concepts <math> C_0 </math> and <math> C_r </math> respectively. A subclass 
−  relationship <math> R_r  +  relationship <math> R_r subclass R_0 </math> is possible 
but not required. <math> P_0 </math> and <math> P_r </math> are the polymorphic  but not required. <math> P_0 </math> and <math> P_r </math> are the polymorphic  
counterparts of <math> R_0 </math> and <math> R_r </math> respectively. The  counterparts of <math> R_0 </math> and <math> R_r </math> respectively. The  
−  requirement that <math> P_r  +  requirement that <math> P_r subtype P_0 </math> allows 
−  models <math> M_r </math> wherever <math> M_0 </math> is expected (i.e.: together  +  the use of models <math> M_r </math> wherever <math> M_0 </math> is expected 
−  with <math> R_0 </math>).  +  (i.e.: together with <math> R_0 </math>). 
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
''Given our definition for Generic Programming, we can define runtimepolymorphism for Generic Programming to be a property of algorithms which operate on a collection of models where the types in the model are either partially or fully determined at runtime.''  ''Given our definition for Generic Programming, we can define runtimepolymorphism for Generic Programming to be a property of algorithms which operate on a collection of models where the types in the model are either partially or fully determined at runtime.''  
Line 394:  Line 379:  
are similar to discriminated unions but overcome their limitation in regards to  are similar to discriminated unions but overcome their limitation in regards to  
storing non POD types. A priori information of all involved types enables to  storing non POD types. A priori information of all involved types enables to  
−  determine the size of the variant at compile time, thus eliminating the need  +  determine the size of the variant at compile time, thus eliminating the need for 
−  +  a two layer architecture. In addition, the compiler can fully type check code  
−  compiler can fully type check code against the types inside the variant. The  +  against the types inside the variant. The downside of this approach is the 
−  downside of this approach is the definition of assignmentsemantics, when the  +  definition of assignmentsemantics, when the types stored in the lefthand and 
−  types stored in the lefthand and righthand object differ. Consider the  +  righthand object differ. Consider the following assignment: 
−  following assignment:  +  
<pre>  <pre>  
x = y  x = y  
</pre>  </pre>  
−  
Since, the actual type of x differs from y, its element has to be destructed  Since, the actual type of x differs from y, its element has to be destructed  
Line 427:  Line 410:  
level implementation [Dig05] yields superior performance. However, the reuse of  level implementation [Dig05] yields superior performance. However, the reuse of  
memory leads to similar problems described for the variant alternative.  memory leads to similar problems described for the variant alternative.  
−  +  In contrast to our approach both implementations do not allow to customize the  
+  user interface.  
====Open Variant====  ====Open Variant====  
Line 435:  Line 419:  
types, which are either unknown at compile time, occur rarely, or are too  types, which are either unknown at compile time, occur rarely, or are too  
large, can be represented by one of the open techniques.  large, can be represented by one of the open techniques.  
−  
−  
−  
===JustInTime Virtualizing (Type Erasure)===  ===JustInTime Virtualizing (Type Erasure)===  
Line 443:  Line 424:  
===Runtime Types===  ===Runtime Types===  
====Refinement and Dispatching====  ====Refinement and Dispatching====  
+  
+  Since the polymorphic layer (e.g.: <math> P_r </math>) could model a more  
+  refined concept than the regular layer it is bound too (e.g.: <math> R_0 </math>),  
+  dispatching based on the concept implemented by the regular layer can  
+  lead to suboptimal results. Consider a random access container attached to a  
+  regular layer modeling a sequence. The complexity for lower_bound would be O(n)  
+  compared to O(lg n) if only the regular layer were considered. The runtime could  
+  improve even more if the operations of the concrete container <math> T </math>  
+  were invoked, instead of the virtual functions defined in the polymorphic layer.  
+  
+  Our solution to this problem replaces the algorithm instantiation and calls a  
+  dispatch mechanism instead. Based on the dynamic type of the model the dispatch  
+  mechanism invokes the most suitable function from a family. The function family  
+  is comprised of instantiation(s) of an algorithm family <math> A_0, A_r </math>  
+  with either the concrete type <math> T </math>, or one of the regular classes  
+  <math> R_0, R_r </math>. The dispatch mechanism guarantees the presence of  
+  algorithms that operate on <math> R_0 </math>. It is the responsibility of the  
+  programmer to add more efficient algorithms to the library.  
+  
+  The dispatch mechanism relies on the following propositions:  
+  * <math> P_0 inherits P_r </math>  
+  * <math> P_r inherits M_r </math> and therefore <math> P_0 inherits ... inherits P_r inherits M_r </math>.  
+  * <math> foreach T </math> there is only one model <math> M_t </math> within an inheritance graph rooted in <math> P_0 </math>.  
+  
+  Based on the first two propositions, the dispatcher walks the inheritance chain  
+  from the model <math> M_r(T) </math> over polymorphic representations of refined  
+  concepts <math> P_r </math> to the base class <math> P_0 </math>. The third  
+  proposition guarantees that any mapping between an algorithm instantiated with a  
+  concrete type <math> A(T) </math> and a model <math> M(T) </math> is bijective  
+  within a concept family. When the dispatcher finds an algorithm, it is typically  
+  a stub that either further unwraps the model <math> M_r(T) > T </math> or  
+  rewraps the polymorphic concept in the appropriate regular layer <math> P_r > R_r </math> before the call of the actual algorithm.  
+  
+  ==Performance Experiments==  
+  
+  ===OpenClosed===  
+  ===Generic vs Genericpolymorphic===  
+  
+  ==Related Work==  
+  [KLS04], [IN06]  
+  
==Summary And Future Work==  ==Summary And Future Work== 
Latest revision as of 06:25, 27 November 2006
[This page is being used to collaborate on a paper. You are welcome to read and comment on it, but consider it a work in progress, not a final product.]
Title: Runtime Concepts: Generic Programming and Runtime Polymorphism
Authors: Sean Parent, Mat Marcus, Peter Pirkelbauer
Contents

Abstract
A key premise of Generic Programming is that algorithms can be expressed in terms of concepts and then applied to any model that satisfies these concepts. In C++, the application of Generic Programming has been largely limited to algorithms operating on collections which are statically and homogeneously typed, while Object Oriented Programming has been used where runtime polymorphism is required.
A definition of runtime polymorphism in Generic Programming terms is presented along with techniques for efficiently implementing runtime polymorphism. The implementation techniques allow for existing STL algorithms to be used effectively with heterogeneous collections of types, further decoupling types from algorithms allowing for greater code reuse.
Introduction
General overview of development in GP: since LISP in 60ies [?] (?); popularized in 80ies and 90ies  STL implementation [MS88]. functional language approach [?]; unification of GP [DRJ05]; ConceptC++ [GJS+06].
Generic programming offers a number of abstraction benefits compared to other programming paradigms.
Generic programming fosters regularity and valuesemantics. Regularity essentially describes the semantics of builtin types and requires operations for construction, copyconstruction, destruction, assignment, equalitycomparison, and for a stricter definition also ordering. Builtin type semantics is valuebased and therefore regular semantics is inherently distinct from reference semantics. Regularity together with valuesemantics eases reasoning about programs and allows the programmer to perform optimizations [DS98]. We extend the regular operations defined by [DS98] and add efficient operations for swap and move. Each regular object is swapable by <math> std::swap </math> which relies on copy construction and assignment. The explicit swap operation allows avoiding the creation of temporary objects. Likewise, the addition of move allows the reuse of part objects that are about to be destructed.
<Shape example>
Regular semantics particularly simplifies memory management because the lifetime of any value ends whenever its name goes out of scope or the lifetime of its container ends. Furthermore, the C++ language requires the compiler to manage the lifetime of temporary values. Consider the following loop:
template <typename T> void saxpy(T[] x, T[] y, T a, size_t dim) { for (int i = 0; i < dim; i++) { y[i] = a * x[i] + y[i]; } }
Both functions * and + create temporary values, which are used as input for subsequent function calls (+ and = respectively), and automatically deallocated as soon as the full expression has been evaluated [C++ Standard Draft 2003]. Using reference/pointer semantics for type T instead would obviate those memory management facilities and either require some automatic memory reclamation scheme or put the burden of releasing memory on the programmer.
Generic programming is concerned with providing algorithms and data structures on an abstract level without compromising efficiency. Hence, some algorithms can have several implementations that differ in their concept requirements and efficiency. Since stricter concept requirements improve efficiency, selection of the best algorithm is conceptbased. The current STL implementation distinguishes concepts using associated types and relies on the C++ overload resolution mechanism to select the optimal algorithm. Therefore, the selected algorithm is multivariant in respect to its parameter types.
Generic programming does not make the relationship between concept and types tangible in the code. This weak relationship allows the programmer to focus on the desired behavior of the class without restrictions from prematurely defined interfaces. This typically results in shallow or no hierarchies, which do not disperse implementation across a number of classes. For example, the Adobe Source Libraries uses inheritance only for X classes. Should a class not meet the requirements of a concept, models can be used to shape its behavior.
Using generic programming allows to cleanly separate data structures from algorithms. This is achieved by stepwise abstraction from concrete and efficient algorithms to a more general but equally efficient implementation. For example, the C++ STL [?] introduces iterators, an abstraction for a position within a sequence, as base for algorithms operating on sequential data structures.
The current C++ standard supports generic programming through function overloading and the template mechanism. While templates allow typebased parameterizations of algorithms and classes, the support for concept definition and  checking is limited. Recent research in this area provides first class concept integration and also improves separate compilation [GJS+06]. By mandating distinct instantiations for distinct parameter tuples, C++ ensures optimal performance but simultaneously hampers template use across DLL boundaries and data structures meant to store a heterogeneous set of data.
Motivation
Many software projects require working on heterogeneous collections of data. Typically, this polymorphism is expressed through inheritance. However, inheritance tightly couples a type with a set of operations which can be performed on it. This tight coupling is often manifest through implicit data structures and algorithms which hinder the ability to understand and reuse code. Because the polymorphic types can be of different sizes they must be allocated in the free store, this introduces the use of object factories, adds an additional level of indirection, and imposes a need to manage the free store memory. This in terms leads to the use of reference counted pointers and the requirement of controlling multiple references to objects in a threaded environment which negatively impact performance.
Outline
Body
Definition of Generic Programming
"By generic programming, we mean the definition of algorithms and data structures at an abstract or generic level, thereby accomplishing many related programming tasks simultaneously" [MS88].
The ideal for generic programming is to represent code at the highest level of abstraction without loss of efficiency in both actual execution speed and resource usage compared to the best code written through any other means. The general process to achieve this is known as "lifting", a process of abstraction where the types used within a concrete algorithm are replaced by the semantic properties of those types necessary for the algorithm to perform.
Semantic Requirement
In the process of abstraction the tight binding from an algorithm to concrete types is relaxed and replaced with a set of semantic requirements. Types must satisfy these requirements in order to work properly with a generic algorithm. Checking types against arbitrary semantic requirements is in general undecidable. Thus, semantic requirements are stated in tables, in documentation, and may at times be asserted within the code. Some systems [? Alloy Model Checker] allow to formally describe semantic requirements, but none of those is part of current C++. [note: we could also mention axioms of the concept proposal]. Instead, the compiler checks for the presence of syntactic constructs, which are a part of semantic requirements. Consider the following example, which describes the requirement that equality holds after a value x is copy constructed from another value y of the same type T. The compiler will check any type for the presence of the copy constructor and equality operator.
template <class T> concept CopyEquality { void foo(T x) { T y(x); assert(x == y); } }
Concept
Dealing with individual semantic requirements would be cumbersome in practice. However, it is observed that sets of consistent requirements cluster into natural groups which are known as "concepts". As an example, even the trivial requirement for copy given above relies on an equality comparison. The notion of copy and equality are very tightly coupled. Although any collection of requirements may define a concept, only concepts which enable new classes of algorithms are interesting. It is also important to distinguish between the syntactic and semantic requirements of concepts. As an example, an algorithm may require that a type be copyable, which is part of the concept known as "Regular"  although the algorithm does not require that the types be equality comparable, we would say that it's defined for regular types because even if the type doesn't implement equality comparison, the result of copying must be equivalent objects. Such a type is said to be pseudo regular.
Model
Neither is it desireable nor possible to forsee all algorithms and their concept requirements with which a type would be used. Consequently, models are introduced as decoupling mechanism allowing clean separation of concrete types from concepts. The designer of a class should be able to focus on providing the correct semantics without distraction from potential requirements, some of which he might not even know. When the type is used in context of an algorithm a model shapes its interface and behaviour to meet the concept requirements.
Algorithm
"The central notion is that of generic algorithms, which are parameterized procedural schemata that are completely independent of the underlying data representation and are derived from concrete, efficient algorithms" [MS88].
Concept Refinement
A concept <math> C_r </math> augmenting another concept <math> C_0 </math> with additional requirements is a concept refinement and denoted by <math> C_r pred C_0 </math>. Therefore the number of types meeting the semantic requirements for <math> C_r </math> is smaller or equal compared to the number of types that meet the requirements of <math> C_0 </math>. In turn, extending the semantic requirements increases the number of algorithms that can be expressed with a given concept. For example, RandomAccessIterator refines BidirectionalIterator and adds the requirement for constant time random access ([]operator), which allows writing a binary search algorithm.
Algorithm Refinement
Parallel to concept refinements, an algorithms <math> A_0 </math> can be refined by another algorithm <math> A_r </math> to exploit the stronger concept requirements and achieve better space and/or runtime efficiency. For example, the complexity of reverse on BidirectionalIterator is O(n), while it is O(lg n) for ForwardIterator (assuming less than O(n) memory usage).
Analogy to Algebraic Structures
We emphasize the analogy of our view of generic programming with algebraic structures. At the core of algebraic structures is a set of axioms and derivation rules on which base useful theorems can be expressed. Concrete Models map undefined terms onto real systems. The more independent axioms a systems has the more theorems can be expressed, but the fewer concrete models exist, which are consistent with the axioms. The following table makes the relationship of generic programming with algebra explicit.
Generic Programming  Algebra 

Semantic Requirement  Axiom 
Concept  Algebraic Structure 
Model  Model 
Algorithms  Theorems 
Function  Function 
Generic Polymorphism
[This section is intended to introduce runtimepolymorphism based on concepts and to show that a concept based definition of runtime polymorphism is a super set of the C++ inheritance model of polymorphism.]
In the presented work, we replace a concrete type with a placeholdertype called runtimeconcept when instantiating STLcontainers. Analogue to the compiletime definition, we define a runtimeconcept as a number of runtimemodels, which satisfy a common set of requirements. Although the containers are type checked based on the runtimeconcept, they can store any object whose type models that runtimeconcept. Unlike the generic programming paradigm, our implementation expresses the relationship between a runtimeconcept and its models inside the C++ type system using inheritance.
Representing the conceptmodel relationship based on OOP polymorphism is not a novel idea and languages such as Eiffel [?], Java [?], and C# [?] implement that technique. Conversely, the C++ language designers have repeatedly explored and rejected to adopt this base/derived class scheme for compile time concept checking. The identified problems include intrusiveness, rigid signatures, type proliferation, and performance issues [Str03].
Instead of requiring an explicit relationship between runtimeconcept and concrete type we apply the external polymorphism pattern (EPP) [CSH96]. Therefore, a runtimemodel <math> M </math> is a template class that gets instantiated with a concrete type <math> T </math>. Its instantiation is orthogonal to the definition of concrete types. A programmer can specialize the modeltemplate for a particular type in order to provide adjustments to the interface if needed.
The use of polymorphic objects is non regular and thus problematic. As a matter of fact, polymorphic classes alone cannot be regular but neither can regular classes alone be polymorphic. Consider a class hierarchy with two classes <math> Base, Derived </math> and copy semantics. Writing the code in terms of copy construction would encode the type in the code, but even using a clone function as illustrated in Fig. <?b> would not work, as the returned object of Derived::clone would be subject to slicing. Conversely, returning an object by reference, would compromise value semantics and regularity Fig<?a>.
// (a) Nonpolymorphic regularity Base Base::clone(); Derived Derived::clone(); // (b) Nonregular polymorphism Base& Base::clone(); Derived& Derived::clone();
Our solution to this problem is a combination of both. We represent runtimeconcepts through a regular (<math> R_0 </math>) and polymorphic layer (<math> P0 </math>). The layers of the generic polymorphism pattern are shown in figure <1>. The regularobject leverages its polymorphic pendants and provides a regular interface for them. <math> R_0 </math> is a concrete class referring to some object that implement the interface ConceptInterface. Thus <math> R_0 </math> can be regarded as a placeholder type for template instantiations. <math> P_0 </math> is an abstract class defining the operations on the objects. The model <math> M_0 </math> is inherits from <math> P_0 </math> and is templatized with a concrete type <math> T </math>. Its instantiation <math> M_0(T) </math> maps the operations defined in <math> P_0 </math> onto operations of <math> T </math>.
Table <?> gives an overview how elements of concept definitions are represented within the regular and polymorphic layer.
Regular Type  Regular Layer (R)  Polymorphic Layer (P) 

Default Constructor  R a   
Copy Constructor  R(const R&)  virtual P& clone() 
Destructor  ~R()  virtual ~P() 
Assignment  R& operator=(R&, const R&)  virtual void assign(const P&) 
Equality  bool operator==(const R&, const R&)  virtual bool equal(const P&) const 
Swap  swap(R&)   
Move  move(R&)   
We describe how elements of compile time concepts are mapped in the
regular and polymorphic layer and present an example by means of the
regularity concept.
Functions (Operators, Constructors, etc): In the regular layer, any
signature or use case pattern requirement can be directly represented by member
or freestanding functions. These functions typically forward calls to the
polymorphic layer, where these functions are realized as member functions.
Notably, swap and move operations are exceptions to these rule and can be
implemented more efficiently by swapping (or moving) the pointer to the
polymorphic part.
Data Members: Consider the following concept member_x written in usage pattern style:
template <typename C> concept member_x { C c; c.x = 1; }
The concept requires the presence of a data member x, where x has an assignment operator that allows an integer argument. Since the runtimeconcept model is nonintrusive and the concept C does not enforce a particular type for x, data members cannot be directly represented. Instead, we use property objects, which sole purpose is to virtualize member access and invoke the appropriate functions in the polymorphic layer. An example for a property object in the regular layer is given by the next code fragment.
struct runtime_concept_member_x { struct x_property { void operator=(int); }; x_property x; };
The runtimeconcept definition for data members of user defined types can be derived by applying the modeling rules recursively.
Associated Types: In the regular layer, associated types are directly represented and identify another regular layer type in the case runtime polymorphism is needed. Then, the polymorphic objectparts are constructed by factory methods [GoF?] which create objects of different dynamic types.
Concept Refinements: In the generic polymorphism model, concept refinements <math> C_r <: C_0 </math> are represented by regular <math> R_0, R_r </math> and polymorphic classes <math> P_0, P_r </math>. <math> R_0 </math> and <math> R_r </math> model the concepts <math> C_0 </math> and <math> C_r </math> respectively. A subclass relationship <math> R_r subclass R_0 </math> is possible but not required. <math> P_0 </math> and <math> P_r </math> are the polymorphic counterparts of <math> R_0 </math> and <math> R_r </math> respectively. The requirement that <math> P_r subtype P_0 </math> allows the use of models <math> M_r </math> wherever <math> M_0 </math> is expected (i.e.: together with <math> R_0 </math>).
Given our definition for Generic Programming, we can define runtimepolymorphism for Generic Programming to be a property of algorithms which operate on a collection of models where the types in the model are either partially or fully determined at runtime.
Relationship To Object Oriented Programming
In Object Oriented Programming the notion of inheritance is used to model an "isa" relationship. The base class(s) provides a syntactic template for modeling a concept where the derived classes must provide the implementation satisfying the semantic requirements for the interface. Normally, type variance is only allowed for a single type (the type which is derived) and not from any affiliated types. Likewise, operations may only be type variant on the first parameter.
Degrees of Runtime Variability
In this paper we have developed our notion of polymorphism in generic programming and presented an implementation. We can classify alternative designs for heterogeneous containers according to the runtime variability they permit.
Static
The elements of a container are statically and homogeneously typed. This model is directly supported by C++ and results in very efficient machine code but is inflexible in respect to types of objects. If heterogeneous containers are needed, programmers typically turn to object oriented polymorphism and store pointers to objects.
Variant
In many applications, the set of types stored in a container is known at compiletime. In these cases a variant type that is the setunion of all potential data types suffices to implement the desired behavior. Hence, variant types, such as the Boost.Variant are similar to discriminated unions but overcome their limitation in regards to storing non POD types. A priori information of all involved types enables to determine the size of the variant at compile time, thus eliminating the need for a two layer architecture. In addition, the compiler can fully type check code against the types inside the variant. The downside of this approach is the definition of assignmentsemantics, when the types stored in the lefthand and righthand object differ. Consider the following assignment:
x = y
Since, the actual type of x differs from y, its element has to be destructed before the assignment can be carried out. However, when the copy construction fails x is left in an undefined state. A detailed discussion of this problem and its potential solutions is given by Boost:"NeverEmpty" Guarantee
Open
Some application require to store also datatypes, for example defined in DLLs, that are not statically known at compile and linktime. Implementations, like the presented one, which do not impose such restrictions are called open. Other existing designs include Boost.Any and [Dig05]. The boost implementation is similar to ours insofar as it uses the virtual functions mechanism and EPP to achieve polymorphism. The operations supported include copyconstruction, assignment, destruction, safe, and unsafe cast operations. Instead of having the polymorphic object allocated separately [Dig05] integrates them into one layer. Only, if the polymorphic part exceed some size it will be stored apart. Instead of virtual functions each object has a static function table. Due to memory locality, reduced heap allocations, and the low level implementation [Dig05] yields superior performance. However, the reuse of memory leads to similar problems described for the variant alternative. In contrast to our approach both implementations do not allow to customize the user interface.
Open Variant
Openvariance is a hybrid of the variant and open techniques. To achieve better performance some types are directly represented in the variant. Other types, which are either unknown at compile time, occur rarely, or are too large, can be represented by one of the open techniques.
JustInTime Virtualizing (Type Erasure)
Polymorphism Parameterized By Concept
Runtime Types
Refinement and Dispatching
Since the polymorphic layer (e.g.: <math> P_r </math>) could model a more refined concept than the regular layer it is bound too (e.g.: <math> R_0 </math>), dispatching based on the concept implemented by the regular layer can lead to suboptimal results. Consider a random access container attached to a regular layer modeling a sequence. The complexity for lower_bound would be O(n) compared to O(lg n) if only the regular layer were considered. The runtime could improve even more if the operations of the concrete container <math> T </math> were invoked, instead of the virtual functions defined in the polymorphic layer.
Our solution to this problem replaces the algorithm instantiation and calls a dispatch mechanism instead. Based on the dynamic type of the model the dispatch mechanism invokes the most suitable function from a family. The function family is comprised of instantiation(s) of an algorithm family <math> A_0, A_r </math> with either the concrete type <math> T </math>, or one of the regular classes <math> R_0, R_r </math>. The dispatch mechanism guarantees the presence of algorithms that operate on <math> R_0 </math>. It is the responsibility of the programmer to add more efficient algorithms to the library.
The dispatch mechanism relies on the following propositions:
 <math> P_0 inherits P_r </math>
 <math> P_r inherits M_r </math> and therefore <math> P_0 inherits ... inherits P_r inherits M_r </math>.
 <math> foreach T </math> there is only one model <math> M_t </math> within an inheritance graph rooted in <math> P_0 </math>.
Based on the first two propositions, the dispatcher walks the inheritance chain from the model <math> M_r(T) </math> over polymorphic representations of refined concepts <math> P_r </math> to the base class <math> P_0 </math>. The third proposition guarantees that any mapping between an algorithm instantiated with a concrete type <math> A(T) </math> and a model <math> M(T) </math> is bijective within a concept family. When the dispatcher finds an algorithm, it is typically a stub that either further unwraps the model <math> M_r(T) > T </math> or rewraps the polymorphic concept in the appropriate regular layer <math> P_r > R_r </math> before the call of the actual algorithm.
Performance Experiments
OpenClosed
Generic vs Genericpolymorphic
Related Work
[KLS04], [IN06]
Summary And Future Work
Runtime Type Functions
Runtime Type References
Acknowledgments
Bibliography
[DRJ05] Dos Reis, Gabriel; Järvi, Jaako: What is Generic Programming? LCSD'05.
[GJS+06] Gregor, Douglas; Järvi, Jaako; Siek, Jeremy; Stroustrup, Bjarne; Dos Reis, Gabriel; Lumsdaine, Andrew: Concepts: FirstClass Language Support for Generic Programming in C++. to appear OOPSLA'06.
[MS88] Musser, David R.; Stepanov, Alexander A.: Generic Programming. ISSAC '88.
[Vel00] Veldhuizen, Todd: Five compilation models for C++ templates. TMPW '00.
[Str03] Stroustrup, Bjarne: Concept checking  a more abstract way to type checking. C++ Committee, Paper 1510, 2003.
[CSH96] Cleeland, C.; Schmidt, D.; Harrison, T.: External Polymorphism PLoPD '96.
[DS98] James C. Dehnert and Alexander Stepanov. Fundamentals of Generic Programming. In Report of the Dagstuhl Seminar on Generic Programming, volume 1766 of Lecture Notes in Computer Science, pages 1–11, Schloss Dagstuhl, Germany, April 1998.
[IN06] Igarashi, Atsushi; Nagira, Hideshi: Union Types for ObjectOriented Programming SAC '06.
[KLS04] Kiselyov, Oleg; Lämmel, Ralf; Schupke, Keean: Strongly Typed Heterogeneous Collections, Haskell '04.
[Dig05] Diggins, Christopher: An Efficient Variant Type. CUJ 2005.
Appendix
The Proxy Dilemma
In C++ the concept of a reference to a type is tightly bound to the specific type generated by the T& type operation. At times it is desirable to construct a user defined type which acts as a form of reference to another type. We refer to this as a proxy type.
The standard template library tries to allow for arbitrary proxy types by including "reference" as one of the traits for an iterator but this is insufficient. The problem becomes apparent when we look at the implementation of swap:
template <typename T> void swap(T& x, T& y) { T tmp(x); x = y; y = tmp; }
If T is itself a proxy then this code will swap the two proxies, not the underlying values. Ideally what we would like is that the syntax T& would match "any type which is a reference to T" not generate a reference to the proxy type. This failure in type deduction leaves the copy construction of T ambiguous  in this case a copy of the value, not just the proxy, is desired. No actual harm occurs, however, until we assign through the reference.
The best that we are able to easily achieve is a proxy type which behaves as a reference when the referenced value is not mutable.
The original code for the C++ standard template library works, to a very limited extent, with proxies because few algorithms actually require full copy semantics (move is sufficient) and the code makes use of a function iter_swap() for swap operations which avoids the above problem with swap by using the iterators associated value type rather than trying to deduce the type from the proxy. However, the requirement for standard algorithms to be implemented in terms of iter_swap() was never stated and cannot be relied upon. The problem also isn't limited to only swap operations, any calls which take the proxy by mutable reference will fail.
To test the ideas presented in this paper with the standard algorithms we used the following scheme:
 proxies maintain a reference count to the number of proxies to a value.
 when assigning through a proxy if the reference count is greater than one, then a copy of the value is made and all other proxies referring to the value are set to refer to the copy.
This relies on the fact that it would be inefficient to make a copy of a value and then assign over the top of it. This is a very fragile and costly solution but it was sufficient to test the ideas in this paper. Solving the proxy dilemma properly in C++ is an open problem.