www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Concepts, axioms

reply bearophile <bearophileHUGS lycos.com> writes:
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
Apr 14 2009
next sibling parent "Nick Sabalausky" <a a.a> writes:
"bearophile" <bearophileHUGS lycos.com> wrote in message 
news:gs1ton$isl$1 digitalmars.com...

 Among the new things added to C++0x there are "concepts":


Once upon a time, I used C/C++ exclusively. Now it just confuses the crap 
out of me. Sooo...from browsing through that wikipedia link, it looks like
Apr 14 2009
prev sibling parent bearophile <bearophileHUGS lycos.com> writes:
I have written a bit more about more or less the same topic, it's mostly about
type systems:
http://leonardo-m.livejournal.com/81028.html

I don't know if axioms can be useful to D2, but a formalized and powerful way
to do concepts now seems very useful.

Bye,
bearophile
Apr 15 2009