Concepts, axioms

bearophile bearophileHUGS at lycos.com
Tue Apr 14 04:58:15 PDT 2009


Among the new things added to C++0x there are "concepts":
http://en.wikipedia.org/wiki/C%2B%2B0x#Concepts

There are comparisons of concepts with Haskell type classes:
http://sms.cs.chalmers.se/publications/papers/2008-WGP.pdf
http://www.cs.uwyo.edu/~skothari/cppvshaskell.pdf

Template constraints of D2 can do more or less the same things C++0x concepts can do (and the same things can be written in D1 too, using static ifs and static asserts), but they seem less formalized. 

D2 template constraints are better because they are more free, they need zero new keywords, the usage is more natural, and the programmer has less things to remember.

But they are worse because they are a less standard formalism, so it may end up being used less or in a worse way. Often it's quite important to have a name to define something, plus a standard way to do it. Reification can be quite important.


(In C++0x there are also "concept maps", they are like compile-time "interfaces" for templates. I don't know if/how they map on D2.)

---------

Related to concepts, in C++0x there are "axioms" too:
http://en.wikipedia.org/wiki/C%2B%2B0x#Axioms

They are explained well enough here, from page 22:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2081.pdf

They allow to express the semantic properties of concepts, few examples:

concept Semigroup< typename Op, typename T> : CopyConstructible<T> {
  T operator()(Op, T, T);
 
  axiom Associativity(Op op, T x, T y, T z) {
    op(x, op(y, z)) == op(op(x, y), z);
  }
}

concept Monoid<typename Op, typename T> {
  T identity element(Op);

  axiom Identity(Op, T x) {
    op(x, identity element(op)) == x;
    op(identity element(op), x) == x;
  }
};

concept CopyConstructible<typename T> {
  T::T(const T&);

  axiom CopyEquivalence(T x) {
    T(x) == x; // okay, uses implicit == for type-checking
  }
};

Where axioms state the equality of two expressions, implementations are permitted to replace one expression with the other. Example:

template<typename Op, typename T> where Monoid<Op, T>
  T identity(const Op& op, const T& t) {
    return op(t, identity element(op)); // can compile as "return t;"
  }

Wikipedia adds:

>Compilers are allowed, but not required, to take advantage of the semantics specified by axioms to perform optimizations that possibly have side-effects on the observable behavior of the program, which are typically prohibited (with few exceptions such as copy constructor elision). In the above example, compilers may reassociate nested calls to operator() of type Op on several values of type T provided that there is a concept map for types Op and T to the concept Semigroup. Axioms can also assist in software verification, software testing, and other program analyses and transformations.<

I think today no C++ compiler uses axioms to perform optimizations.

Such axioms seem cute, and maybe a bit useful too, but I think in most programs you don't need a very large amount of them. Probably with just 10-20 standard axioms from the standard lib you can already do lot of things.

Bye,
bearophile



More information about the Digitalmars-d mailing list