View Full Document

Algorithm Specialization in Generic Programming



View the full content.
View Full Document
View Full Document

5 views

Unformatted text preview:

Algorithm Specialization in Generic Programming Challenges of Constrained Generics in C Jaakko Ja rvi Texas A M University jarvi cs tamu edu Douglas Gregor Jeremiah Willcock Andrew Lumsdaine Jeremy Siek Rice University Jeremy G Siek rice edu Indiana University dgregor jewillco lums osl iu edu Abstract Generic programming has recently emerged as a paradigm for developing highly reusable software libraries most notably in C We have designed and implemented a constrained generics extension for C to support modular type checking of generic algorithms and to address other issues associated with unconstrained generics To be as broadly applicable as possible generic algorithms are defined with minimal requirements on their inputs At the same time to achieve a high degree of efficiency generic algorithms may have multiple implementations that exploit features of specific classes of inputs This process of algorithm specialization relies on non local type information and conflicts directly with the local nature of modular type checking In this paper we review the design and implementation of our extensions for generic programming in C describe the issues of algorithm specialization and modular type checking in detail and discuss the important design tradeoffs in trying to accomplish both We present the particular design that we chose for our implementation with the goal of hitting the sweet spot in this interesting design space Categories and Subject Descriptors D 3 3 Programming Languages Language Constructs and Features Polymorphism D 3 2 Programming Languages Language Classifications C General Terms Languages Theory Keywords Generic programming parametric polymorphism constrained generics concepts specialization 1 Introduction Templates are the cornerstone of modern C libraries The Standard Template Library STL 42 Boost Graph Library 37 the BLAS Library 49 and the Computational Geometry Algorithms Library CGAL 12 are all examples of widely used heavilytemplated libraries



Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Algorithm Specialization in Generic Programming and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Algorithm Specialization in Generic Programming and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?