www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Proposal to add 'Elements of Programming' Concepts to std.traits

reply Guillaume Chatelet <chatelet.guillaume gmail.com> writes:
'Elements of Programming' is an amazing book by Alexander Stepanov and
Paul McJones ( M. Stepanov is the primary designer of the C++ STL ).

Here is a rather long but insightful comment about the book :
"Ask a mechanical, structural, or electrical engineer how far they would
get without a heavy reliance on a firm mathematical foundation, and they
will tell you, not far. Yet so-called software engineers often
practice their art with little or no idea of the mathematical
underpinnings of what they are doing. And then we wonder why software is
notorious for being delivered late and full of bugs, while other
engineers routinely deliver finished bridges, automobiles, electrical
appliances, etc., on time and with only minor defects. This book sets
out to redress this imbalance.[...]" Martin Newell, Adobe Fellow

The book carefully crafts foundations for designing efficient,
mathematically sound and generic algorithms.

Apart from the fact this book is an absolute must read, I think the D
community could really benefit from integrating these concepts.

A minimalistic website maintains the concepts defined so far and the C++
code
http://www.elementsofprogramming.com/

As an exercise I started to port the books concepts to D and the
mathematical constructs do really fit nicely within the language.
* D's purity can bring some guaranties that C++ can't ( see the
definition for FunctionalProcedure in
http://www.elementsofprogramming.com/eop-concepts.pdf )
* D's structs being value semantic, default constructible simplifies a lot.
* Concepts translation into D's templates is very readable and
straightforward.

Now on the downside, D being a C-style-system-language, we won't be able
to prevent implicit lossy conversions or add value domain constrains as
in the X10 language for instance. But nonetheless I think it's still a
worthwhile goal to seek. It would give more confidence in the code, both
on correctness and genericity sides.

So without further ado, here is my humble first attempt
https://github.com/gchatelet/phobos/blob/traits_concepts/std/traits2.d
And the associated more readable DDoc
http://bbteam.fr/traits2.html

I would like to hear what you think.

Note : It's called traits2 because of a lack of inspiration not because
I intend it to replace std.traits.

--
Guillaume
Jun 16 2012
next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Guillaume Chatelet:

 A minimalistic website maintains the concepts defined so far 
 and the C++ code
 http://www.elementsofprogramming.com/

That page looks quite interesting. I'll take a better look later (I have not read that book). In a recent (probably no more than one year old) talk by Bjarne Stroustrup, he has shown a list of concepts that fits mostly in one slide. So he has significantly reduced the number of Concepts needed for the STL.
 Now on the downside, D being a C-style-system-language, we 
 won't be able to prevent implicit lossy conversions

D disallows some implicit conversions (float => int, int => short, etc). The conversions like uint=>int and int=>uint are an open problem, waiting for some solution (a simple "solution" is to add a warning, as in GCC. It's not a great solution, but maybe it's better than the current D situation).
 or add value domain constrains as
 in the X10 language for instance.

Please explain, don't assume all people here know X10. Bye, bearophile
Jun 16 2012
parent reply Guillaume Chatelet <chatelet.guillaume gmail.com> writes:
On 06/16/12 17:58, bearophile wrote:
 Guillaume Chatelet:
 
 A minimalistic website maintains the concepts defined so far and the
 C++ code
 http://www.elementsofprogramming.com/

That page looks quite interesting. I'll take a better look later (I have not read that book).

The website is more of a stopgap, the book is way better because it shows the paths from concepts to concepts. I should warn the book is not easy to read, it's hard and it hurts, but it's good hurt.
 In a recent (probably no more than one year old) talk by Bjarne
 Stroustrup, he has shown a list of concepts that fits mostly in one
 slide. So he has significantly reduced the number of Concepts needed for
 the STL.

Yes, you can hear him speak about it there http://channel9.msdn.com/Events/GoingNative/GoingNative-2012/A-Concept-Design-for-C- His proposal is also available ( also I'm not sure it's in sync with the video ) http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3351.pdf My main regrets regarding this proposal : * pervasive use of iterators instead of a more safe Range abstraction. * duplication of code with the xxxx_if variants ( all functions could take a default predicate evaluating to constexp true ).
 Now on the downside, D being a C-style-system-language, we won't be
 able to prevent implicit lossy conversions

D disallows some implicit conversions (float => int, int => short, etc). The conversions like uint=>int and int=>uint are an open problem, waiting for some solution (a simple "solution" is to add a warning, as in GCC. It's not a great solution, but maybe it's better than the current D situation).

Yes it's been debated several times on the ML and I agree a compiler warning could do. Every serious developer should toggle warning-as-errors anyway.
 or add value domain constrains as
 in the X10 language for instance.

Please explain, don't assume all people here know X10.

Sorry about that, you're absolutely right. X10 ( http://x10-lang.org/ ) allows user to add constrains on value domain definition at declaration time. Here are a few lines took from the documentation : * Int{self != 0} is the type of non-zero Ints. * Int{self != 0, self != 1} is the type of Ints which are neither zero nor one. * String{self != null} is the type of non-null strings. * Matrix{self.rows == self.cols} is the type of square matrices. -- Guillaume
Jun 16 2012
next sibling parent Guillaume Chatelet <chatelet.guillaume gmail.com> writes:
On 06/16/12 21:22, bearophile wrote:
 Guillaume Chatelet:
 
 I like hard books, if they give something valuable back.

I think you'll find it rewarding.
 I see. is that semantically different from this (beside being shorter)?
 
 struct NoZero {
     int value;
     this(int x) { value = x; }
     alias value this;
     invariant() { assert(value != 0); }
 }
 void main() {
     auto a = NoZero(5);
     auto b = NoZero(0);
 }

That's a good one ! I forgot about the _invariant_ keyword. It's pretty close. For what I understood of x10 (I'm not using it yet just interested in the language) the compiler will also enforce the invariance at compile time not solely at runtime. ie void main(){ NoZero a = 0; // shouldn't compile } Thx for the design though, I keep it in my toolbox. -- Guillaume
Jun 16 2012
prev sibling next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 6/17/12 1:38 AM, Philippe Sigaud wrote:
 On Sat, Jun 16, 2012 at 9:22 PM, bearophile<bearophileHUGS lycos.com>  wrote:

 I see. is that semantically different from this (beside being shorter)?

 struct NoZero {
     int value;
     this(int x) { value = x; }
     alias value this;
     invariant() { assert(value != 0); }
 }
 void main() {
     auto a = NoZero(5);
     auto b = NoZero(0);
 }

The invariant isn't invoked through alias this, it seems: void main() { auto a = NoZero(5); a = 0; // compiles and runs happily }

To avoid this, expose an rvalue via alias this, not an lvalue. Then implement opAssign etc. Andrei
Jun 17 2012
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 6/16/12 11:29 AM, Guillaume Chatelet wrote:
 On 06/16/12 17:58, bearophile wrote:
 Guillaume Chatelet:

 A minimalistic website maintains the concepts defined so far and the
 C++ code
 http://www.elementsofprogramming.com/

That page looks quite interesting. I'll take a better look later (I have not read that book).

The website is more of a stopgap, the book is way better because it shows the paths from concepts to concepts. I should warn the book is not easy to read, it's hard and it hurts, but it's good hurt.

I'm surprised by such claims. I found EoP very easy to read. Andrei
Jun 17 2012
parent Guillaume Chatelet <chatelet.guillaume gmail.com> writes:
On 06/17/12 18:41, Andrei Alexandrescu wrote:
 I'm surprised by such claims. I found EoP very easy to read.
 
 Andrei

Ok let me restate this. First, those words are originally from Stepanov himself "This is not an easy book" is explicitly written in the inner cover :) Then it's not a *difficult* book if you have a mathematical background - any engineer degree would do - but if you came to programming from a different path, you'd probably find it queasy. I don't expect anyone in this forum to have this background thus the disclaimer but I may be wrong. Moreover if you intend to read it the way it's planned by the author (doing the exercises and proving the lemmas) it's not as fun as reading TDPL. Let's say you need to think while reading, a bit like for 'Modern C++ design'. I hope these few lines gives a more comprehensive view of what I meant and won't discourage anyone from reading it.
Jun 17 2012
prev sibling next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 6/16/2012 8:26 AM, Guillaume Chatelet wrote:
 And then we wonder why software is
 notorious for being delivered late and full of bugs, while other
 engineers routinely deliver finished bridges, automobiles, electrical
 appliances, etc., on time and with only minor defects.

I have a nit to pick with that statement, as a former mechanical engineer who has done professional mechanical designs and has taken apart a lot of others. Bridges, automobiles, electrical appliances, etc., are full of design errors. The engineers who design them aren't any smarter, more professional, or rely on mathematical precision any more than software engineers do. In fact, quite a large fraction of them can do math little more advanced than simple arithmetic. They don't catastrophically fail that often simply because they are way, way overdesigned. A bridge, for example, can withstand several times its design load. That covers an awful lot of sins. Software, on the other hand, can catastrophically fail with the slightest mistake - a single bit being off. The "on time" is equally misinformed. The more new design there is in other engineering projects, the more certain it is to be late.
Jun 16 2012
next sibling parent Guillaume Chatelet <chatelet.guillaume gmail.com> writes:
On 06/16/12 18:11, Walter Bright wrote:
 On 6/16/2012 8:26 AM, Guillaume Chatelet wrote:
 And then we wonder why software is
 notorious for being delivered late and full of bugs, while other
 engineers routinely deliver finished bridges, automobiles, electrical
 appliances, etc., on time and with only minor defects.

I have a nit to pick with that statement, as a former mechanical engineer who has done professional mechanical designs and has taken apart a lot of others. Bridges, automobiles, electrical appliances, etc., are full of design errors. The engineers who design them aren't any smarter, more professional, or rely on mathematical precision any more than software engineers do. In fact, quite a large fraction of them can do math little more advanced than simple arithmetic.

Thanks for sharing your experience, it's definitely an interesting point of view.
 They don't catastrophically fail that often simply because they are way,
 way overdesigned. A bridge, for example, can withstand several times its
 design load. That covers an awful lot of sins. Software, on the other
 hand, can catastrophically fail with the slightest mistake - a single
 bit being off.

Yes. My former studies were also in mechanical engineering so I tend to agree - even if I never done it professionally. Security margins are 'everywhere' from pins to ball bearings...
 The "on time" is equally misinformed. The more new design there is in
 other engineering projects, the more certain it is to be late.

Completely agree here, because you can't rely on a previous experience it's almost impossible to have an accurate estimation of the schedule, even with huge margin on your side :)
Jun 16 2012
prev sibling parent Denis Shelomovskij <verylonglogin.reg gmail.com> writes:
16.06.2012 20:11, Walter Bright пишет:
 On 6/16/2012 8:26 AM, Guillaume Chatelet wrote:
 And then we wonder why software is
 notorious for being delivered late and full of bugs, while other
 engineers routinely deliver finished bridges, automobiles, electrical
 appliances, etc., on time and with only minor defects.

I have a nit to pick with that statement, as a former mechanical engineer who has done professional mechanical designs and has taken apart a lot of others. Bridges, automobiles, electrical appliances, etc., are full of design errors.

You all probably know a canonical example, Tacoma Narrows Bridge: http://www.youtube.com/watch?v=j-zczJXSxnw Let's forgive its designers because it was the first such accident with bridge. But in Russia we still (2010) have this: http://www.youtube.com/watch?v=rVzYDIlBQ0w And this bridge still works without rebuilding, but with attenuator now. -- Денис В. Шеломовский Denis V. Shelomovskij
Jun 18 2012
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
On 6/16/2012 8:26 AM, Guillaume Chatelet wrote:
 So without further ado, here is my humble first attempt
 https://github.com/gchatelet/phobos/blob/traits_concepts/std/traits2.d
 And the associated more readable DDoc
 http://bbteam.fr/traits2.html

 I would like to hear what you think.

I think you're on to some good stuff here.
Jun 16 2012
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Guillaume Chatelet:

 The website is more of a stopgap, the book is way better 
 because it
 shows the paths from concepts to concepts. I should warn the 
 book is not
 easy to read, it's hard and it hurts, but it's good hurt.

I like hard books, if they give something valuable back.
 X10 ( http://x10-lang.org/ ) allows user to add constrains on 
 value domain definition at declaration time. Here are a few
 lines took from the documentation :

 * Int{self != 0} is the type of non-zero Ints.
 * Int{self != 0, self != 1} is the type of Ints which are 
 neither zero
 nor one.
 * String{self != null} is the type of non-null strings.
 * Matrix{self.rows == self.cols} is the type of square matrices.

I see. is that semantically different from this (beside being shorter)? struct NoZero { int value; this(int x) { value = x; } alias value this; invariant() { assert(value != 0); } } void main() { auto a = NoZero(5); auto b = NoZero(0); } Bye, bearophile
Jun 16 2012
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Guillaume Chatelet:

 It's pretty close. For what I understood of x10 (I'm not using 
 it yet just interested in the language) the compiler will also
 enforce the invariance at compile time not solely at runtime. ie

 void main(){
   NoZero a = 0; // shouldn't compile
 }

I have proposed an idea to do something related in D (it's about pre-conditions, not invariants, but this is an easy problem to solve, adding assign/read methods to that NoZero, and giving them pre-conditions): http://d.puremagic.com/issues/show_bug.cgi?id=5906 Bye, bearophile
Jun 16 2012
prev sibling next sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Sat, Jun 16, 2012 at 9:22 PM, bearophile <bearophileHUGS lycos.com> wrot=
e:

 I see. is that semantically different from this (beside being shorter)?

 struct NoZero {
 =C2=A0 =C2=A0int value;
 =C2=A0 =C2=A0this(int x) { value =3D x; }
 =C2=A0 =C2=A0alias value this;
 =C2=A0 =C2=A0invariant() { assert(value !=3D 0); }
 }
 void main() {
 =C2=A0 =C2=A0auto a =3D NoZero(5);
 =C2=A0 =C2=A0auto b =3D NoZero(0);
 }

The invariant isn't invoked through alias this, it seems: void main() { auto a =3D NoZero(5); a =3D 0; // compiles and runs happily }
Jun 16 2012
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Sunday, June 17, 2012 08:38:41 Philippe Sigaud wrote:
 On Sat, Jun 16, 2012 at 9:22 PM, bearophile <bearophileHUGS lycos.com> 

 I see. is that semantically different from this (beside being shorter)?
 
 struct NoZero {
    int value;
    this(int x) { value = x; }
    alias value this;
    invariant() { assert(value != 0); }
 }
 void main() {
    auto a = NoZero(5);
    auto b = NoZero(0);
 }

The invariant isn't invoked through alias this, it seems: void main() { auto a = NoZero(5); a = 0; // compiles and runs happily }

It wouldn't be. No public function was called. All you did was access the public member variable. Having public members and invariants at the same time doesn't work very well. - Jonathan M Davis
Jun 16 2012
prev sibling next sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Sun, Jun 17, 2012 at 8:42 AM, Jonathan M Davis <jmdavisProg gmx.com> wrote:

 It wouldn't be. No public function was called. All you did was access the
 public member variable. Having public members and invariants at the same time
 doesn't work very well.

If I change int value; to private int value; it can still be accessed through alias this (I guess) and no invariant is called.
Jun 17 2012
prev sibling next sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Sunday, June 17, 2012 09:04:16 Philippe Sigaud wrote:
 On Sun, Jun 17, 2012 at 8:42 AM, Jonathan M Davis <jmdavisProg gmx.com> 

 It wouldn't be. No public function was called. All you did was access the
 public member variable. Having public members and invariants at the same
 time doesn't work very well.

If I change int value; to private int value; it can still be accessed through alias this (I guess) and no invariant is called.

Well, I'm not sure if it's supposed to be legal to access value like that if it's private, but public or private has nothing to do with the invariant in this case. The invariant only runs when you call public _functions_ (it may be run with package and protected as well - I don't recall - but never with private). It's run before and after they're executed. You're accessing a member _variable_. That's why the invariant isn't run. It doesn't matter what the access level of a variable is, the invariant is never run just because you accessed it. That's why if you want to be able to guarantee your invariants, you should never have public member variables on types with an invariant. And if alias this allows you to expose a private member variable, then it's in the same boat as a public one. Invariants and public member variables just don't mix. - Jonathan M Davis
Jun 17 2012
parent reply Guillaume Chatelet <chatelet.guillaume gmail.com> writes:
That's a *lot* more code but I think we could do something like

struct NoZero {
    private int _value;

    invariant() { assert(_value != 0); }

    this(int x) { _value = x; }

    NoZero opBinary(string op)(const ref NoZero rhs) {
    	return NoZero(mixin("this._value"~op~"rhs._value"));
    }
    NoZero opBinary(string op)(int rhs) {
    	return NoZero(mixin("this._value"~op~"rhs"));
    }
    ref NoZero opUnary(string op)() if(op=="++"||op=="--"){
    	mixin(op~"this._value;");
    	return this;
    }
    ref NoZero opAssign(int rhs) {
    	value = rhs;
    	return this;
    }

     property int value() const  { return _value; }
     property void value(int newValue) { _value = newValue; }

    alias this value;
}

void main(){
    NoZero a = 1;
    auto b = a; // copyable
    // --b; would assert
    auto c = b+1;
    auto d = c+a;
}

Note the implementation is incomplete, still need to implement
comparison to bool, operator'!' , unary '+', '-', '~', checks for
overflows. It's a bit of work but I think it can be done.
Jun 17 2012
next sibling parent reply Guillaume Chatelet <chatelet.guillaume gmail.com> writes:
On 06/17/12 14:23, Philippe Sigaud wrote:
 An obvious generalization is to template the struct on a predicate:
 
 struct Constrained(T, alias pred) {
    private T _value;
 
    invariant() { assert(pred(_value)); }
 
    this(T x) { _value = x; }
    this(Constrained c) { _value = c._value; }
 
    Constrained opBinary(string op)(const ref Constrained rhs) {
        return Constrained(mixin("this._value"~op~"rhs._value"));
    }
    Constrained opBinary(string op)(T rhs) {
        return Constrained(mixin("this._value"~op~"rhs"));
    }
    ref Constrained opUnary(string op)() if(op=="++"||op=="--"){
        mixin(op~"this._value;");
        return this;
    }
    ref Constrained opAssign(T rhs) {
        value = rhs;
        return this;
    }
    ref Constrained opAssign(Constrained rhs) {
        value = rhs._value;
        return this;
    }
 
     property T value() const  { return _value; }
     property void value(T newValue) { _value = newValue; }
 
    alias this value;
 }
 
 Constrained!(T,pred) constrained(alias pred, T)(T _value){
     return typeof(return)(_value);
 }
 
 void main(){
    auto a = constrained!(x => x > 0)(1);
    auto b = a;
    auto c = b+1;
    auto d = c+a;
    a = b-d;
 }

Very nice :)
Jun 17 2012
next sibling parent Guillaume Chatelet <chatelet.guillaume gmail.com> writes:
On 06/17/12 15:53, Philippe Sigaud wrote:
 x => ... still has some problem as it's a template, but using a
 standard module-level function gives functionalities akin to X10:
 
 bool pos(int x) { return x > 0;}
 alias Constrained!(int, pos) Positive; // works
 
 // alias Constrained!(int, (int x) { return x > 0;}) Positive; // works
 // alias Constrained!(int, (int x) => x > 0) Positive; // works
 // but:
 // alias Constrained!(int, (x) { return x > 0;}) Positive; // ka-boom!
 // alias Constrained!(int, x => x > 0) Positive; // no such luck

I ran into that problem also. I usually tend to define a function for readability. It would be nice to have it working though, the last one is definitely neat.
 enum OK = Positive(1); // OK
 enum NOK = Positive(-1); // Compiling error, cool!
 
 So this works. That's nice to know, I never used an assert inside a CT
 evaluation.
 
 Hmmm, validating XML and/or SQL queries at CT...

Yummy !
Jun 17 2012
prev sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 06/17/2012 03:53 PM, Philippe Sigaud wrote:
 On Sun, Jun 17, 2012 at 3:11 PM, Guillaume Chatelet
 <chatelet.guillaume gmail.com>  wrote:
 On 06/17/12 14:23, Philippe Sigaud wrote:

 void main(){
     auto a = constrained!(x =>  x>  0)(1);
     auto b = a;
     auto c = b+1;
     auto d = c+a;
     a = b-d; // Boom!
 }

Very nice :)

The new syntax for lambdas is delightful to use. A bunch of aliases should give you the X10 examples. x => ... still has some problem as it's a template, but using a standard module-level function gives functionalities akin to X10: bool pos(int x) { return x> 0;} alias Constrained!(int, pos) Positive; // works // alias Constrained!(int, (int x) { return x> 0;}) Positive; // works // alias Constrained!(int, (int x) => x> 0) Positive; // works // but: // alias Constrained!(int, (x) { return x> 0;}) Positive; // ka-boom! // alias Constrained!(int, x => x> 0) Positive; // no such luck

I have reported this bug a few days ago: http://d.puremagic.com/issues/show_bug.cgi?id=8242 Apparently, Kenji Hara has already fixed it.
Jun 17 2012
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 6/17/12 7:23 AM, Philippe Sigaud wrote:
 An obvious generalization is to template the struct on a predicate:

 struct Constrained(T, alias pred) {

Nice idea, but it should be said that making the predicate opaque prevents the implementer from taking advantage of its properties. Andrei
Jun 17 2012
prev sibling next sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Sun, Jun 17, 2012 at 10:20 AM, Guillaume Chatelet
<chatelet.guillaume gmail.com> wrote:

Nice.

You can also add:

   this(NoZero nz) { _value = nz._value; }

and

   ref NoZero opAssign(NoZero rhs) {
       value = rhs._value;
       return this;
   }

this allows code like this:

a = a-a; // asserts
a = a*0; // asserts

An obvious generalization is to template the struct on a predicate:

struct Constrained(T, alias pred) {
   private T _value;

   invariant() { assert(pred(_value)); }

   this(T x) { _value = x; }
   this(Constrained c) { _value = c._value; }

   Constrained opBinary(string op)(const ref Constrained rhs) {
       return Constrained(mixin("this._value"~op~"rhs._value"));
   }
   Constrained opBinary(string op)(T rhs) {
       return Constrained(mixin("this._value"~op~"rhs"));
   }
   ref Constrained opUnary(string op)() if(op=="++"||op=="--"){
       mixin(op~"this._value;");
       return this;
   }
   ref Constrained opAssign(T rhs) {
       value = rhs;
       return this;
   }
   ref Constrained opAssign(Constrained rhs) {
       value = rhs._value;
       return this;
   }

    property T value() const  { return _value; }
    property void value(T newValue) { _value = newValue; }

   alias this value;
}

Constrained!(T,pred) constrained(alias pred, T)(T _value){
    return typeof(return)(_value);
}

void main(){
   auto a = constrained!(x => x > 0)(1);
   auto b = a;
   auto c = b+1;
   auto d = c+a;
   a = b-d;
}
Jun 17 2012
prev sibling next sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Sun, Jun 17, 2012 at 3:11 PM, Guillaume Chatelet
<chatelet.guillaume gmail.com> wrote:
 On 06/17/12 14:23, Philippe Sigaud wrote:

 void main(){
 =C2=A0 =C2=A0auto a =3D constrained!(x =3D> x > 0)(1);
 =C2=A0 =C2=A0auto b =3D a;
 =C2=A0 =C2=A0auto c =3D b+1;
 =C2=A0 =C2=A0auto d =3D c+a;
 =C2=A0 =C2=A0a =3D b-d; // Boom!
 }

Very nice :)

The new syntax for lambdas is delightful to use. A bunch of aliases should give you the X10 examples. x =3D> ... still has some problem as it's a template, but using a standard module-level function gives functionalities akin to X10: bool pos(int x) { return x > 0;} alias Constrained!(int, pos) Positive; // works // alias Constrained!(int, (int x) { return x > 0;}) Positive; // works // alias Constrained!(int, (int x) =3D> x > 0) Positive; // works // but: // alias Constrained!(int, (x) { return x > 0;}) Positive; // ka-boom! // alias Constrained!(int, x =3D> x > 0) Positive; // no such luck enum OK =3D Positive(1); // OK enum NOK =3D Positive(-1); // Compiling error, cool! So this works. That's nice to know, I never used an assert inside a CT evaluation. Hmmm, validating XML and/or SQL queries at CT...
Jun 17 2012
prev sibling next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 6/16/12 10:26 AM, Guillaume Chatelet wrote:
 'Elements of Programming' is an amazing book by Alexander Stepanov and
 Paul McJones ( M. Stepanov is the primary designer of the C++ STL ).

 So without further ado, here is my humble first attempt
 https://github.com/gchatelet/phobos/blob/traits_concepts/std/traits2.d
 And the associated more readable DDoc
 http://bbteam.fr/traits2.html

 I would like to hear what you think.

This is a good idea because the traits are useful within and outside the algorithms discussed in EoP. However, I don't think we need to abide strictly to the nomenclature (e.g. some of the stuff in EoP was already defined with a different name) although some EoP names are more mathematicky (such as "Codomain" vs. "ReturnType"). One issue is when EoP goes off and defines its own terms such as "regular type", which is usually known as "value type". In fact, "regular type" means something completely different in PL research. EoP's terminology didn't catch up outside C++ and sometimes outside a small group within it. If I'm allowed to venture an opinion on EoP itself, it's an interesting book but I don't find it as big or great as some of its fans believe. It's not breaking any new ground, instead it explores more along already well-trodden territory, and it fails to find new mother lodes. Some (many?) chapters (such as transformations and orbits) describe some self-important notions but fail to demonstrate their general applicability. Nevertheless, the code really is exquisitely written, and studying it has significantly changed my approach and style in implementing algorithms. Andrei
Jun 17 2012
next sibling parent Guillaume Chatelet <chatelet.guillaume gmail.com> writes:
On 06/17/12 18:38, Andrei Alexandrescu wrote:
 
 This is a good idea because the traits are useful within and outside the
 algorithms discussed in EoP.
 
 However, I don't think we need to abide strictly to the nomenclature
 (e.g. some of the stuff in EoP was already defined with a different
 name) although some EoP names are more mathematicky (such as "Codomain"
 vs. "ReturnType"). One issue is when EoP goes off and defines its own
 terms such as "regular type", which is usually known as "value type". In
 fact, "regular type" means something completely different in PL
 research. EoP's terminology didn't catch up outside C++ and sometimes
 outside a small group within it.
 
 If I'm allowed to venture an opinion on EoP itself, it's an interesting
 book but I don't find it as big or great as some of its fans believe.
 It's not breaking any new ground, instead it explores more along already
 well-trodden territory, and it fails to find new mother lodes. Some
 (many?) chapters (such as transformations and orbits) describe some
 self-important notions but fail to demonstrate their general
 applicability. Nevertheless, the code really is exquisitely written, and
 studying it has significantly changed my approach and style in
 implementing algorithms.
 
 
 Andrei

What would you recommend ? Something more practical as Stroustrup and Sutton N3351's proposal : http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3351.pdf We can also get inspired by Sutton's origin project : http://code.google.com/p/origin
Jun 17 2012
prev sibling parent reply Guillaume Chatelet <chatelet.guillaume gmail.com> writes:
On 06/17/12 18:38, Andrei Alexandrescu wrote:
 However, I don't think we need to abide strictly to the nomenclature
 (e.g. some of the stuff in EoP was already defined with a different
 name) although some EoP names are more mathematicky (such as "Codomain"
 vs. "ReturnType"). One issue is when EoP goes off and defines its own
 terms such as "regular type", which is usually known as "value type". In
 fact, "regular type" means something completely different in PL
 research. EoP's terminology didn't catch up outside C++ and sometimes
 outside a small group within it.

Yes. As you noticed CoDomain is simply an alias to ReturnType. The purpose of this thread was to measure the interest of the D community in going further in this direction. I thought it would be great to benefit from the work the C++ community has already done in this domain. Brilliant people are working on it for years and the more basic Concepts look stable now so it might be a good starting point. My take on it is that Concept modeling improves in designing and extending complex generic libraries. As an example see the Generic Image Library (GIL) by Adobe and now part of Boost. http://stlab.adobe.com/gil/html/gildesignguide.html Of course, the idioms being different, I was also looking for some feedback. I did ask myself what naming convention should be used considering some traits were already implemented as you pointed out. I sticked to the D _isXXXX_ convention instead of the plain CamelCase name. I was tempted to use a _hasValueSemantic_ traits (Concept) instead of _isRegular_. Also _isPure_ could replace _isFunctionalProcedure_. Basically this is just a proposal and everything can change at this point. I'm also not convinced we should add every single Concepts Stepanov is describing, we have to be pragmatic here. So what do you think should be the next move ? Try to integrate those concepts within phobos ? try to add more of them ? More comments are definitely welcome. Many thanks for everyones feedback.
Jun 17 2012
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 6/17/12 4:47 PM, Guillaume Chatelet wrote:
 On 06/17/12 18:38, Andrei Alexandrescu wrote:
 However, I don't think we need to abide strictly to the nomenclature
 (e.g. some of the stuff in EoP was already defined with a different
 name) although some EoP names are more mathematicky (such as "Codomain"
 vs. "ReturnType"). One issue is when EoP goes off and defines its own
 terms such as "regular type", which is usually known as "value type". In
 fact, "regular type" means something completely different in PL
 research. EoP's terminology didn't catch up outside C++ and sometimes
 outside a small group within it.

Yes. As you noticed CoDomain is simply an alias to ReturnType. The purpose of this thread was to measure the interest of the D community in going further in this direction. I thought it would be great to benefit from the work the C++ community has already done in this domain. Brilliant people are working on it for years and the more basic Concepts look stable now so it might be a good starting point.

That's great. On the other hand D is not C++, and it naturally fosters a different dynamics of idioms. D has static if and restricted templates, which are the concept equivalent of lambda functions. That changes the play field considerably because in C++ the syntactic overhead of expressing any constraint is so high, the normal tendency is to name everything. In D, you only need to name things that are often used and relatively complex. So I don't think copying the laundry list of C++ concepts is the best way to go, because some of those overcome insufficiencies that are obviated by D. Nevertheless, a good design is a good design, and we could and should use is as inspiration.
 My take on it is that Concept modeling improves in designing and
 extending complex generic libraries. As an example see the Generic Image
 Library (GIL) by Adobe and now part of Boost.
 http://stlab.adobe.com/gil/html/gildesignguide.html

 Of course, the idioms being different, I was also looking for some
 feedback. I did ask myself what naming convention should be used
 considering some traits were already implemented as you pointed out. I
 sticked to the D _isXXXX_ convention instead of the plain CamelCase
 name.

I think either way is fine. One convention I tried to foster was to name all symbols that ultimately expand to values starting with a lowercase, e.g. isXXX or hasXXX, and symbols that ultimately yield non-values should start with an uppercase, e.g. Unsigned or Unqual.
 I was tempted to use a _hasValueSemantic_ traits (Concept) instead
 of _isRegular_.

I personally would love that. Honest I think isRegular is provincial. Just google for "regular type" to see what I mean.
 Also _isPure_ could replace _isFunctionalProcedure_.
 Basically this is just a proposal and everything can change at this
 point. I'm also not convinced we should add every single Concepts
 Stepanov is describing, we have to be pragmatic here.

Awesome, my thoughts above (written before I saw this paragraph) reflect the same view.
 So what do you think should be the next move ? Try to integrate those
 concepts within phobos ? try to add more of them ?

 More comments are definitely welcome. Many thanks for everyones feedback.

I think traits are something that we could add piecemeal, without a large proposal - just as pull requests. For each particular concept there should be 1-2 compelling examples in the documentation, enough to make a case that the notion being added is worthwhile. For a simple example I'd like "arity" (I'm unclear whether it belongs in std.traits or std.functional). Sure, I could write ParameterTypeTuple!fun.length, but that's quite a roundabout way to go about it. Andrei
Jun 17 2012
parent reply Guillaume Chatelet <chatelet.guillaume gmail.com> writes:
On 06/18/12 04:18, Andrei Alexandrescu wrote:
 I think traits are something that we could add piecemeal, without a
 large proposal - just as pull requests. For each particular concept
 there should be 1-2 compelling examples in the documentation, enough to
 make a case that the notion being added is worthwhile.
 
 For a simple example I'd like "arity" (I'm unclear whether it belongs in
 std.traits or std.functional). Sure, I could write
 ParameterTypeTuple!fun.length, but that's quite a roundabout way to go
 about it.
 
 
 Andrei

So here it is. A first very small patch to add arity to std.traits. As you stated it could really go either in std.traits or std.functional. I chose to keep it in std.traits because std.functional is more about creating new functions of modifying existing ones whereas std.traits is about deducing properties. Guillaume
Jun 22 2012
next sibling parent Guillaume Chatelet <chatelet.guillaume gmail.com> writes:
On 06/22/12 23:37, Guillaume Chatelet wrote:
 On 06/18/12 04:18, Andrei Alexandrescu wrote:
 I think traits are something that we could add piecemeal, without a
 large proposal - just as pull requests. For each particular concept
 there should be 1-2 compelling examples in the documentation, enough to
 make a case that the notion being added is worthwhile.

 For a simple example I'd like "arity" (I'm unclear whether it belongs in
 std.traits or std.functional). Sure, I could write
 ParameterTypeTuple!fun.length, but that's quite a roundabout way to go
 about it.


 Andrei

So here it is. A first very small patch to add arity to std.traits. As you stated it could really go either in std.traits or std.functional. I chose to keep it in std.traits because std.functional is more about creating new functions of modifying existing ones whereas std.traits is about deducing properties. Guillaume

It's better with a link :-P https://github.com/D-Programming-Language/phobos/pull/643
Jun 22 2012
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 6/22/12 5:37 PM, Guillaume Chatelet wrote:
 On 06/18/12 04:18, Andrei Alexandrescu wrote:
 I think traits are something that we could add piecemeal, without a
 large proposal - just as pull requests. For each particular concept
 there should be 1-2 compelling examples in the documentation, enough to
 make a case that the notion being added is worthwhile.

 For a simple example I'd like "arity" (I'm unclear whether it belongs in
 std.traits or std.functional). Sure, I could write
 ParameterTypeTuple!fun.length, but that's quite a roundabout way to go
 about it.


 Andrei

So here it is. A first very small patch to add arity to std.traits. As you stated it could really go either in std.traits or std.functional. I chose to keep it in std.traits because std.functional is more about creating new functions of modifying existing ones whereas std.traits is about deducing properties.

Great. You should know I'm on vacation with scant access to email. Andrei
Jun 27 2012
prev sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Sun, Jun 17, 2012 at 6:39 PM, Timon Gehr <timon.gehr gmx.ch> wrote:
 // alias Constrained!(int, (x) { return x> =C2=A00;}) Positive; // ka-bo=


 // alias Constrained!(int, x =3D> =C2=A0x> =C2=A00) Positive; // no such=



I have reported this bug a few days ago: http://d.puremagic.com/issues/show_bug.cgi?id=3D8242 Apparently, Kenji Hara has already fixed it.

No wonder, it takes him about 23 minutes, on average, to fix bugs once they are reported :) But, if he really fixed it (in the general case, lambda context botch and all), then he just corrected one of the most annoying bugs as far as I'm concerned. I hit it in every D project I have. Then I'll be, once more, forever grateful to Kenji Hara.
Jun 17 2012