# Difference between revisions of "Runtime Concepts"

(→Generic Polymorphism) |
m (→Semantic Requirement) |
||

(30 intermediate revisions by one other user not shown) | |||

Line 24: | Line 24: | ||

from reference semantics. Regularity together with value-semantics eases | from reference semantics. Regularity together with value-semantics 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, | ||

RandomAccess-Iterator refines Bidirectional-Iterator and adds the requirement | RandomAccess-Iterator refines Bidirectional-Iterator 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, | |

− | Bidirectional-Iterator is O(n), while it is O(lg n) for Forward-Iterator | + | the complexity of reverse on Bidirectional-Iterator is O(n), while it is O(lg n) |

− | (assuming less than O(n) memory usage). | + | for Forward-Iterator (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 runtime-polymorphism 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 runtime-polymorphism 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 placeholder-type | In the presented work, we replace a concrete type with a placeholder-type | ||

Line 246: | Line 230: | ||

Instead of requiring an explicit relationship between runtime-concept and | Instead of requiring an explicit relationship between runtime-concept 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 runtime-model <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. | + | model-template 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) Non-polymorphic regularity | ||

+ | Base Base::clone(); | ||

+ | Derived Derived::clone(); | ||

+ | |||

+ | // (b) Non-regular polymorphism | ||

+ | Base& Base::clone(); | ||

+ | Derived& Derived::clone(); | ||

+ | </pre> | ||

+ | |||

+ | Our solution to this problem is a combination of both. We represent runtime-concepts 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 regular-object 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.png|Class Colaboration Figure 1]] | [[Image:Runtime_concept.png|Class 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 runtime-concept model is | operator that allows an integer argument. Since the runtime-concept model is | ||

non-intrusive and the concept C does not enforce a particular type for x, data | non-intrusive 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 runtime-polymorphism 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 runtime-polymorphism 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 assignment-semantics, when the | + | definition of assignment-semantics, when the types stored in the left-hand and |

− | types stored in the left-hand and right-hand object differ. Consider the | + | right-hand 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. | ||

− | |||

− | |||

− | |||

===Just-In-Time Virtualizing (Type Erasure)=== | ===Just-In-Time 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== | ||

+ | |||

+ | ===Open-Closed=== | ||

+ | ===Generic vs Generic-polymorphic=== | ||

+ | |||

+ | ==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

- 1 Abstract
- 2 Introduction
- 3 Body
- 4 Performance Experiments
- 5 Related Work
- 6 Summary And Future Work
- 7 Acknowledgments
- 8 Bibliography
- 9 Appendix

## 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 *value-semantics*. Regularity
essentially describes the semantics of built-in types and requires operations
for construction, copy-construction, destruction, assignment,
equality-comparison, and for a stricter definition also ordering. Built-in type
semantics is value-based and therefore regular semantics is inherently distinct
from reference semantics. Regularity together with value-semantics 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 concept-based. 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 *multi-variant* 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 type-based 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,
RandomAccess-Iterator refines Bidirectional-Iterator 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 Bidirectional-Iterator is O(n), while it is O(lg n) for Forward-Iterator (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 runtime-polymorphism 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 placeholder-type
called *runtime-concept* when instantiating STL-containers. Analogue to the
compile-time definition, we define a runtime-concept as a number of
runtime-models, which satisfy a common set of requirements. Although the
containers are type checked based on the runtime-concept, they can store any
object whose type models that runtime-concept. Unlike the generic programming
paradigm, our implementation expresses the relationship between a
runtime-concept and its models inside the C++ type system using inheritance.

Representing the concept-model 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 runtime-concept and concrete type we apply the external polymorphism pattern (EPP) [CSH96]. Therefore, a runtime-model <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 model-template 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) Non-polymorphic regularity Base Base::clone(); Derived Derived::clone(); // (b) Non-regular polymorphism Base& Base::clone(); Derived& Derived::clone();

Our solution to this problem is a combination of both. We represent runtime-concepts 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 regular-object 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 free-standing 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 runtime-concept model is non-intrusive 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 runtime-concept 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 object-parts 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 runtime-polymorphism 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 "is-a" 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
compile-time. In these cases a *variant* type that is the set-union 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 assignment-semantics, when the types stored in the left-hand and
right-hand 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:"Never-Empty" Guarantee

#### Open

Some application require to store also data-types, for example defined in DLLs, that are not statically known at compile- and link-time. 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 copy-construction, 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

Open-variance 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.

### Just-In-Time 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

### Open-Closed

### Generic vs Generic-polymorphic

## 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: First-Class 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.