http://www.infoq.com/presentations/Generic-Programming-Galore-Using-D

Andrei

On 4/11/12, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
> http://www.infoq.com/presentations/Generic-Programming-Galore-Using-D
>
> Andrei
>

Cool talk! And it just occurred to me that you can actually use a static assert on a return type in D, e.g.:

import std.traits;
import std.algorithm;

auto min(T1, T2)(T1 t1, T2 t2)
{
    return t1;  // e.g. implementation bug
    static assert(is(typeof(return) == CommonType!(T1, T2)));
}

void main() {
    auto x = min(1, 1.0);
}

I didn't know this until now. It might help in cases where the return type is a very complicated template instance and you want to enforce the return expression to be of that type while simultaneously using auto as the return type in the function declaration.

It does however do this check *after* any implicit conversions to the return type. So, while my first sample correctly won't compile, the following will compile:

import std.traits;
import std.algorithm;

CommonType!(T1, T2) min(T1, T2)(T1 t1, T2 t2)
{
    return t1;
    static assert(is(typeof(return) == CommonType!(T1, T2)));
}

void main() {
    auto x = min(1, 1.0);
}

It's interesting to think about.

Le 11/04/2012 18:23, Andrei Alexandrescu a écrit :
> http://www.infoq.com/presentations/Generic-Programming-Galore-Using-D
>
> Andrei

Great talk ! I am going to start to feel at ease with those is(typeof(...)) constructs ! :)

Olivier

Le 11/04/2012 18:23, Andrei Alexandrescu a écrit :
> http://www.infoq.com/presentations/Generic-Programming-Galore-Using-D
>
> Andrei

You didn't used the new syntax for closures :'(

But nice talk. BTW, it seemed strange to me that you mentioned AST manipulation when talking about mixin, when you didn't seemed to see that as important when we were talking here about AOP/attributes.

IMO the difference between string and AST for code manipulation is just the same as string vs closure as template parameters.

On 4/11/12 11:23 AM, Andrei Alexandrescu wrote:
> http://www.infoq.com/presentations/Generic-Programming-Galore-Using-D

Destroy on reddit: http://www.reddit.com/r/programming/comments/s4qul/infoq_generic_programming_galore_using_d_video/

Andrei

On Wed, 11 Apr 2012 21:34:11 +0200, Olivier Pisano <olivier.pisano@laposte.net> wrote:

> Le 11/04/2012 18:23, Andrei Alexandrescu a écrit :
>> http://www.infoq.com/presentations/Generic-Programming-Galore-Using-D
>>
>> Andrei
>
> Great talk ! I am going to start to feel at ease with those is(typeof(...)) constructs ! :)
>
> Olivier

Don't speak too hastily :) I promise you'll be amazed at the complexities of the is expression many more times

On Wednesday, 11 April 2012 at 16:23:48 UTC, Andrei Alexandrescu wrote:
> http://www.infoq.com/presentations/Generic-Programming-Galore-Using-D
>
> Andrei

Also on HN: http://news.ycombinator.com/item?id=3829871

Andrej Mitrovic:

> it just occurred to me that you can actually use a static assert on a return type in D, e.g.:
>
> import std.traits;
> import std.algorithm;
>
> auto min(T1, T2)(T1 t1, T2 t2)
> {
>     return t1;  // e.g. implementation bug
>     static assert(is(typeof(return) == CommonType!(T1, T2)));
> }
>
> void main() {
>     auto x = min(1, 1.0);
> }
>
> I didn't know this until now.

I'd like to verify the type of what a range yields inside the post-condition of the function, but I can't use code like this, because currently functions with out{} can't use auto as return type:


import std.stdio, std.algorithm, std.traits;
auto foo(int x)
in {
    assert(x >= 0);
} out(result) {
    static assert(is(ForeachType!(typeof(result)) == int));
} body {
    return map!(a => a * 2)([1, 2, 3]);
}
void main() {
    writeln(foo(1));
}


And you have to keep in mind that inside the out{} 'result' is const, and const ranges aren't that useful, you can't even iterate them...

Bye,
bearophile

Andrei Alexandrescu:

> http://www.infoq.com/presentations/Generic-Programming-Galore-Using-D

It was a quite good talk.

Slide 13: very good, I am asking for min([1, 3, 5)) for a lot of time :-) (http://d.puremagic.com/issues/show_bug.cgi?id=4705 ).

I hope to see those new min/max/argMin/argMax functions in Phobos.

I'd also like the mins()/maxs() functions, as explained in Issue 4705, their need is common. I have added some use cases there.

(But your code doesn't work with opApply, so it doesn't work with everything as the slide says).

------------------------------

Slide 15:

auto m = argmin!((x) { return x.length;})(s);

As deadalnix notes, that was a good place to show the new D lambda template syntax and UCFS:

auto m = s.argmin!(x => x.length)();

But it also shows why Python (unlike Ruby) uses a free function for length (that calls a __len__ standard method on objects and built-ins), it allows you to write that code with no need of lambdas (it also shows why Python named arguments are nice):

m = min(s, key=len)

So in D to avoid defining a lambda I sometimes use walkLength as free function (but I have to keep in mind it gives different results on narrow strings!):

auto m = s.argmin!walkLength();

And maybe "argMin" name is more fitting in D than "argmin".

----------------------------

[Attention, uncooked ideas ahead]

Creating a good min() is not so easy. When I did create the dlibs1 in D1 I didn't know this, so I thought of myself as a not so good enough programmer for finding it not so easy to create the min/max functions :-)


At about 40.00 of your talk there was an interesting question and answer. D sees 255 on default as an integer literal:

auto x = 255;
static assert(is(typeof(x) == int));


But D also accepts this, because D knows this is a valid ubyte literal too, it fits in the ubyte interval:

ubyte x = 255;

The D compiler even accepts this with no errros or warnings, requiring no cast to assign z:

void main(string[] args) {
    uint x;
    ubyte y = cast(ubyte)args.length;
    ubyte z = x % y;
}


(A bug on this: http://d.puremagic.com/issues/show_bug.cgi?id=7834 ).


So another possible desiderata for a 'dream' min() function is this to compile, with no need of a cast in the user code:


void main(string[] args) {
    ubyte u = min(args.length, 255);
}


To allow this I think D needs some more static introspection/skills. The template of the min() function needs to be informed not just that the second argument is of type int, but also that it's a literal (or value known at compile time witn no need of running compile-time code to compute it, this is a requirement of the way D CTFE works), and it  also fits in an ubyte range.

The result of that min() is of type size_t, so this is true (so the min of an unsigned short and an unsigned int is an unsigned int type still. Types and their ranges are orthogonal things):

auto u = min(args.length, 255);
static assert(is(typeof(u) == size_t));


But this also compiles because the compiler knows that despite the result of that min() call is a size_t the compile-time range of that size_t value fits inside a ubyte range too (just like for the built-in literal 255 that the compiler knows has a range that fits in an ubyte too):

ubyte u = min(args.length, 255);

So I think this kind of code needs a way to tell statically:
- The actual statically known range of a compile-time known integral value.
- It also needs the ability to _assign_ a statically known range to an integer value. To make things simpler the compiler is not required to prove that this is a correct assignment, it accepts it with an act of faith.

Opionally I'd also like a way to tell, from inside the template:
- If a template argument is a literal (or it's a value known statically with no need to run compile-time code);
- If the result of the function is assigned to a variable or not (if this information is used, then the template instantiates itself again in two variants, according to the boolean result of this query)).


I think a first step is to have something like this, to call from user code the interval analysis engine inside the D compiler. I think this just is just a way to expose to user code stuff already existing inside the compiler, so I think this requires only a small amount of compiler code to be added (I it's better for the result to be an interval closed on the right, unlike most other intervals in D):

uint x = ...;
__traits(interval, x & ubyte.max) ===> TypeTuple!(0, 255)


That alone is not enough to implement that "dream min". Because if you do this:

void foo(T)(T x) {
    writeln([__traits(interval, x)]);
}
void main() {
    foo(255);
}


I think it prints this, because the result of interval analysis gets lot when the expression ends or at function call point:

[-2147483648, 2147483647]

Bye,
bearophile

Question on slide #6:

"Should work at efficiency comparable to hand-written code"

A version of min() that used 'ref' would probably be faster on large structs.  Is that a problem?  How do you make the decision to exclude 'ref'?  Do [generic] algorithms always go with value semantics?

On Wed, Apr 11, 2012 at 11:23 AM, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
> http://www.infoq.com/presentations/Generic-Programming-Galore-Using-D
>
> Andrei