Concept (generic programming)

Last updated

In generic programming, a concept is a description of supported operations on a type, including syntax and semantics. In this way, concepts are related to abstract types but concepts do not require a subtype relationship.

Contents

Language use

The term was in use as early as 1998 for STL, [1] as this was one of the first libraries that extensively used templates. The term concept (and its popularization) is credited to Alexander Stepanov, [2] [3] the primary designer of the STL.

In the C++ 1998 standard, the Concept term was introduced to name just a simple description of the requirements for particular type, usually being a template parameter. It was not encoded in the language explicitly – the concept was expressed only by what operations are attempted on objects of that type and what is expected to work (that is, to compile correctly). There was a proposal to add concepts as an explicit language feature in C++11, though it was rejected as "not ready". C++20 eventually accepted the refined design of concept.

As generics in Java and C# have some similarities to C++'s templates, the role of concepts there is played by interfaces. However, there is one important difference between concepts and interfaces: when a template parameter is required to implement a particular interface, the matching type can only be a class that implements (explicitly) that interface. Concepts bring more flexibility because they can be satisfied in two ways:

But the C# language has several constructs where the used type does not need to explicitly implement a defined interface, it is only required to match the respective pattern (however, these patterns are not called concepts). E.g. the foreach iteration statement allows the iterated object to be of any type, as long as it implements an appropriate GetEnumerator method. [4] (Compare with the using statement which requires the resource to implement the System.IDisposable interface. [5] )

The Nim programming language implements concepts as a series of arbitrary compile-time boolean predicates. [6]

Another language implementing something very similar to concepts is Haskell, where the feature is called type classes.


Examples

Total ordering

The total ordering concept describes the semantics of the < operator. A type is totally ordered when < is a binary predicate and satisfies the following properties: [7] [8]

Many algorithms rely on these properties to function properly. For example the min function can be safely defined on totally ordered types: 

#include<concepts>template<typenameT>requiresstd::totally_ordered<T>Tmin(Ta,Tb){// < is defined.if(b<a){returnb;}else{// !(b < a) implies a == b or a < breturna;}}

Iterator

If a type I satisfies the Trivial Iterator concept in C++, and i is of type I, the following are valid expressions with corresponding semantics: [9]

See also

Related Research Articles

<span class="mw-page-title-main">Bjarne Stroustrup</span> Danish computer scientist, creator of C++ (born 1950)

Bjarne Stroustrup is a Danish computer scientist, most notable for the invention and development of the C++ programming language. Stroustrup served as a visiting professor of computer science at Columbia University beginning in 2014, where he has been a full professor since 2022.

Templates are a feature of the C++ programming language that allows functions and classes to operate with generic types. This allows a function or class declaration to reference via a generic variable another different class without creating full declaration for each of these different classes.

Java and C++ are two prominent object-oriented programming languages. By many language popularity metrics, the two languages have dominated object-oriented and high-performance software development for much of the 21st century, and are often directly compared and contrasted. Java's syntax was based on C/C++.

<span class="mw-page-title-main">C++</span> General-purpose programming language

C++ is a high-level, general-purpose programming language created by Danish computer scientist Bjarne Stroustrup. First released in 1985 as an extension of the C programming language, it has since expanded significantly over time; as of 1997, C++ has object-oriented, generic, and functional features, in addition to facilities for low-level memory manipulation for making things like microcomputers or to make operating systems like Linux or Windows. It is almost always implemented as a compiled language, and many vendors provide C++ compilers, including the Free Software Foundation, LLVM, Microsoft, Intel, Embarcadero, Oracle, and IBM.

Generic programming is a style of computer programming in which algorithms are written in terms of data types to-be-specified-later that are then instantiated when needed for specific types provided as parameters. This approach, pioneered by the ML programming language in 1973, permits writing common functions or types that differ only in the set of types on which they operate when used, thus reducing duplicate code.

The Standard Template Library (STL) is a software library originally designed by Alexander Stepanov for the C++ programming language that influenced many parts of the C++ Standard Library. It provides four components called algorithms, containers, functions, and iterators.

In object-oriented programming, the iterator pattern is a design pattern in which an iterator is used to traverse a container and access the container's elements. The iterator pattern decouples algorithms from containers; in some cases, algorithms are necessarily container-specific and thus cannot be decoupled.

In computer programming, an iterator is an object that enables a programmer to traverse a container, particularly lists. Various types of iterators are often provided via a container's interface. Though the interface and semantics of a given iterator are fixed, iterators are often implemented in terms of the structures underlying a container implementation and are often tightly coupled to the container to enable the operational semantics of the iterator. An iterator performs traversal and also gives access to data elements in a container, but does not itself perform iteration.

In programming language theory and type theory, polymorphism is the use of a single symbol to represent multiple different types.

In the C++ programming language, the C++ Standard Library is a collection of classes and functions, which are written in the core language and part of the C++ ISO Standard itself.

<span class="mw-page-title-main">Alexander Stepanov</span> Russian-American computer programmer (born 1950)

Alexander Alexandrovich Stepanov is a Russian-American computer programmer, best known as an advocate of generic programming and as the primary designer and implementer of the C++ Standard Template Library, which he started to develop around 1992 while employed at HP Labs. He had earlier been working for Bell Labs close to Andrew Koenig and tried to convince Bjarne Stroustrup to introduce something like Ada generics in C++. He is credited with the notion of concept.

C++/CLI is a variant of the C++ programming language, modified for Common Language Infrastructure. It has been part of Visual Studio 2005 and later, and provides interoperability with other .NET languages such as C#. Microsoft created C++/CLI to supersede Managed Extensions for C++. In December 2005, Ecma International published C++/CLI specifications as the ECMA-372 standard.

This article describes the syntax of the C# programming language. The features described are compatible with .NET Framework and Mono.

In C++ computer programming, allocators are a component of the C++ Standard Library. The standard library provides several data structures, such as list and set, commonly referred to as containers. A common trait among these containers is their ability to change size during the execution of the program. To achieve this, some form of dynamic memory allocation is usually required. Allocators handle all the requests for allocation and deallocation of memory for a given container. The C++ Standard Library provides general-purpose allocators that are used by default, however, custom allocators may also be supplied by the programmer.

Concepts are an extension to the templates feature provided by the C++ programming language. Concepts are named Boolean predicates on template parameters, evaluated at compile time. A concept may be associated with a template, in which case it serves as a constraint: it limits the set of arguments that are accepted as template parameters.

In the C++ programming language, decltype is a keyword used to query the type of an expression. Introduced in C++11, its primary intended use is in generic programming, where it is often difficult, or even impossible, to express types that depend on template parameters.

In computing, sequence containers refer to a group of container class templates in the standard library of the C++ programming language that implement storage of data elements. Being templates, they can be used to store arbitrary elements, such as integers or custom classes. One common property of all sequential containers is that the elements can be accessed sequentially. Like all other standard library components, they reside in namespace std.

The following outline is provided as an overview of and topical guide to C++:

Uniform Function Call Syntax (UFCS) or Uniform Call Syntax (UCS) or sometimes Universal Function Call Syntax is a programming language feature in D, Nim, Koka, and Effekt that allows any function to be called using the syntax for method calls, by using the receiver as the first parameter and the given arguments as the remaining parameters. The same technique is used in the AviSynth scripting language under the name "OOP notation".

Although C++ is one of the most widespread programming languages, many prominent software engineers criticize C++ for being overly complex and fundamentally flawed. Among the critics have been: Robert Pike, Joshua Bloch, Linus Torvalds, Donald Knuth, Richard Stallman, and Ken Thompson. C++ has been widely adopted and implemented as a systems language through most of its existence. It has been used to build many pieces of very important software.

References

  1. ↑ Austern, M.H. Generic programming and the STL: using and extending the C++ Standard Template Library. 1998. pp 17–18
  2. ↑ a bit of background for concepts and C++17—Bjarne Stroustrup, by Bjarne Stroustrup | Feb 26, 2016
  3. ↑ Alex Stepanov, by Bjarne Stroustrup | Jan 21, 2016
  4. ↑ C# 6.0 draft specification, The foreach statement
  5. ↑ C# 6.0 draft specification, The using statement
  6. ↑ "Nim Experimental Features". nim-lang.org. Retrieved 2023-06-19.
  7. ↑ Stepanov, Alexander (2009). Elements of Programming. Addison-Wesley Professional. p. 49. ISBN   9780321635372.
  8. ↑ Total Orderings - Efficient Programming with Components
  9. ↑ Trivial Iterator
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.