A Formalization of Concepts for Generic Programming

Abstract. Generic programming is a paradigm for systematic design and classification of software components for optimal reuse. It has been the guiding methodology behind the design of the C++ Standard Template Library and numerous other C++ libraries. Generic programming starts with algorithms, seeking to identify the minimal requirements on types necessary for correct and efficient execution of an algorithm or family of algorithms, leading to generic algorithms that can be applied to arguments of many different types. The term concept is used in this context to mean a set of abstractions (such as types) whose membership is determined by a set of requirements. Despite their importance, concepts are not explicitly represented in traditional programming languages. C++, in particular, lacks any means to express concepts, which has forced all concept development to be done outside the language and thus be unavailable to C++ compilers for static checking or optimization. Several other languages do have features than can approximate certain aspects of concepts, but what is missing is a uniform, language-independent definition of concepts. The definition of concepts in this paper provides a unified framework for realizing concept approximations in existing languages, and we present such descriptions for several popular languages used for generic programming. 1