CSC/ECE 517 Fall 2012/ch1b 1w47 sk

Introduction

Generic Programming is a programming paradigm for developing efficient, reusable software libraries. Generic Programming obtained its first major success when the Standard Template Library became part of the ANSI/ISO C++ standard. Since then, the Generic Programming paradigm has been used to develop many generic libraries.

The Generic Programming process focuses on finding commonality among similar implementations of the same algorithm, then providing suitable abstractions so that a single, generic algorithm can cover many concrete implementations. This process, called lifting, is repeated until the generic algorithm has reached a suitable level of abstraction, where it provides maximal re-usability while still yielding efficient, concrete implementations. The abstractions themselves are expressed as requirements on the parameters to the generic algorithm.

Once many algorithms within a given problem domain have been lifted, we start to see patterns among the requirements. It is common for the same set of requirements to be required by several different algorithms. When this occurs, each set of requirements is bundled into a concept. Concepts describe a set of abstractions, each of which meets all of the requirements of a concept. When the Generic Programming process is carefully followed, the concepts that emerge tend to describe the abstractions within the problem domain in some logical way. A study of graph algorithms will produce Graph concepts that describe the behavior of graphs, whereas a study of linear algebra algorithms will produce Matrix and Vector concepts. Thus, the output of the Generic Programming process is not just a generic, reusable implementation, but a better understanding of the problem domain.