'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

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

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.

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.

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

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

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

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

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

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
}