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 reply "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
next sibling parent reply 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
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 reply 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
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 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> 


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
 }


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


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.


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
parent reply 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
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
parent reply 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
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 reply 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
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=




om!

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




 luck


 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



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


[snip]

 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