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] )

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 [6] [7] :

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

// requires: T satisfies Totally Orderedtemplate<typenameT>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: [8]

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. As of July 2022, Stroustrup is a professor of Computer Science at Columbia University.

CLU is a programming language created at the Massachusetts Institute of Technology (MIT) by Barbara Liskov and her students starting in 1973. While it did not find extensive use, it introduced many features that are used widely now, and is seen as a step in the development of object-oriented programming (OOP).

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 to work on many different data types without being rewritten for each one.

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 appeared about 10 years later and its syntax was based on C/C++.

In computer science, control flow is the order in which individual statements, instructions or function calls of an imperative program are executed or evaluated. The emphasis on explicit control flow distinguishes an imperative programming language from a declarative programming language.

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

C++ is a general-purpose programming language created by Danish computer scientist Bjarne Stroustrup as an extension of the C programming language, or "C with Classes". The language has expanded significantly over time, and modern C++ now has object-oriented, generic, and functional features in addition to facilities for low-level memory manipulation. 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, so it is available on many platforms.

Generic programming is a style of computer programming in which algorithms are written in terms of 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 duplication. Such software entities are known as generics in Ada, C#, Delphi, Eiffel, F#, Java, Nim, Python, Go, Rust, Swift, TypeScript and Visual Basic .NET. They are known as parametric polymorphism in ML, Scala, Julia, and Haskell ; templates in C++ and D; and parameterized types in the influential 1994 book Design Patterns.

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 provision of a single interface to entities of different types or the use of a single symbol to represent multiple different types. The concept is borrowed from a principle in biology where an organism or species can have many different forms or stages.

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

The void type, in several programming languages derived from C and Algol68, is the return type of a function that returns normally, but does not provide a result value to its caller. Usually such functions are called for their side effects, such as performing some task or writing to their output parameters. The usage of the void type in such context is comparable to procedures in Pascal and syntactic constructs which define subroutines in Visual Basic. It is also similar to the unit type used in functional programming languages and type theory. See Unit type#In programming languages for a comparison.

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.

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

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++ was 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. ↑ Stepanov, Alexander (2009). Elements of Programming. Addison-Wesley Professional. p. 49. ISBN   9780321635372.
  7. ↑ Total Orderings - Efficient Programming with Components
  8. ↑ 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.