Constraints & Concepts [Was: Re: C++0x news]

[bearophile]

Walter Bright:

> Here's a comparison I did of C++0x proposed features and D a while back. 
> It's out of date and incomplete, but it's a reasonable overview:
> http://www.digitalmars.com/d/2.0/cpp0x.html
> I suppose I need to revisit it now that C++0x is nearing completion.

In the past I didn't understand the section about Concepts of that page , now I am understanding most of it, thanks to this very nice article that explains the semantics and usefulness of concept maps:
http://www.devx.com/SpecialReports/Article/38864/1954?pf=true
This article has let me understand why concept maps are much more powerful (and probably more useful) than D template Constraints.


General comment on the cpp0x.html page: C++/C++0x and Java are legacy languages (but the most successful), so they can't be enough to design D. So I suggest to try for few days the C#3.5+ and Scala languages too, they probably already solve some of the problems that need to be found D still...

Specific comments on that cpp0x.html page:

>Concept maps: No (but could be done with proxy objects)<

I don't fully understand, I'd like to see a small example of this (it can be added to that page too).


>Axioms: Yes (as static asserts and function preconditions)<

This is a (too much) common example of axiom from Wikipedia:
http://en.wikipedia.org/wiki/Concepts_%28C%2B%2B%29#Axioms

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);
  }
}

Function precoditions are currently used at run-time (a sufficiently smart compiler can use some of them at compile time, but it's not easy). And static asserts don't help a lot here.


>All operations on constrained types must be specified in concept/constraint: No<

After reading that article on devx.com I think this can be a nice feature to have in D too, because some times the lack of semantic analysis on uninstantiated D templates unnerves me a little (while I think the other two features like concept maps inheritance and the adaptors inside concept maps are less important). But I am not sure how it can be implemented. If someone has ideas I'd like to know them.


In D a template Constraints can contain the methods that must exist, as in a C++0x Concept, I think this is the way to express it, using the methods inside a __traits(compiles):


import std.stdio: writeln;

template IsPolygon(P) { // like a Concept
    enum bool IsPolygon = __traits(compiles, { int x = num_sides(P());
                                               auto d = side_len(P(), 0);
                                               typeof(d) r = 0;
                                               r += d;
                                             });
}

typeof(P.sides[0]) perimeter(P)(const ref P poly) if (IsPolygon!P) {
    typeof(return) sum = 0;
    foreach (i; 0 .. num_sides(poly))
        sum += side_len(poly, i);
    return sum;
}

// class Int { // problem!
struct Int {
    int x;
    void opOpAssign(string Op:"+=")(Int other) { this.x += other.x; }
    static Int opCall(int value) { Int i; i.x = value; return i; }
}

struct Triangle { Int[3] sides; }
int num_sides(const ref Triangle tri) { return Triangle.sides.length; }
typeof(Triangle.sides[0]) side_len(const ref Triangle tri, int index) { return tri.sides[index]; }
static assert(IsPolygon!Triangle); // this makes sure Triangle is a polygon

void main() {
    Triangle t = Triangle([Int(10), Int(20), Int(30)]);
    auto p = perimeter(t);
    writeln(typeid(typeof(p)), " ", p);
}


There's no good way to let templates detect an operator missing in the concept, like explained in that article.

A possible syntax can be to modify this:

typeof(P.sides[0]) perimeter(P)(const ref P poly) if (IsPolygon!P) {

Into a syntax that asks the compiler to perform the semantic tests even on the uninstantiated template. Maybe something like:

typeof(P.sides[0]) perimeter(P)(const ref P poly) if (__traits(satisfiesConcept, perimeter, IsPolygon)) {

Bye,
bearophile