May 13, 2008
Yigal Chripun Wrote:

> Dee Girl wrote:
> <snip>
> maybe I still didn't explain myself properly. I've used the term
> "sort-with-delegates" meaning a specific instance of sort when given a
> delegate as input. I thought this was clear enough, otherwise I would
> have simply said "sort".
> before you start sending me assembly code, let's go over it again and
> make sure we both understand each other:
> you take the sort template, stick in a delegate, mix for five minutes
> let is simmer for one more and viola: you got the exact same thing if
> you would have written sort as a regular function which receives a
> delegate parameter.
> the template takes the symbol it receives (the delegate name) and
> "embeds" it in the sort instance.
> both ways you get:
> 1) a call to sort
> 2) a call to the delegate
> the only difference is the number of parameters the sort function
> receives when called.
> the regular sort function can run different delegates at runtime (this
> is what you call "dynamic". the template has the call to the specific
> delegate embedded so for different delegates you need different sort
> instances.

Good. I think I understand. I want to be very sure, so I have a question from this code.

int array[] = [1, 2, 3];
int x = 5;
sort!((int a, int b) { return a + x < b + x; })(array);

Two questions not one ^_^

1. Is the code inside sort!() as powerful as delegate?

2. Is the call inside sort direct or indirect? Thank you, Dee Girl
May 13, 2008
== Quote from Dee Girl (deegirl@noreply.com)'s article
> Yigal Chripun Wrote:
> > Dee Girl wrote:
> > <snip>
> > maybe I still didn't explain myself properly. I've used the term
> > "sort-with-delegates" meaning a specific instance of sort when given a
> > delegate as input. I thought this was clear enough, otherwise I would
> > have simply said "sort".
> > before you start sending me assembly code, let's go over it again and
> > make sure we both understand each other:
> > you take the sort template, stick in a delegate, mix for five minutes
> > let is simmer for one more and viola: you got the exact same thing if
> > you would have written sort as a regular function which receives a
> > delegate parameter.
> > the template takes the symbol it receives (the delegate name) and
> > "embeds" it in the sort instance.
> > both ways you get:
> > 1) a call to sort
> > 2) a call to the delegate
> > the only difference is the number of parameters the sort function
> > receives when called.
> > the regular sort function can run different delegates at runtime (this
> > is what you call "dynamic". the template has the call to the specific
> > delegate embedded so for different delegates you need different sort
> > instances.
> Good. I think I understand. I want to be very sure, so I have a question from this code.
> int array[] = [1, 2, 3];
> int x = 5;
> sort!((int a, int b) { return a + x < b + x; })(array);
> Two questions not one ^_^
> 1. Is the code inside sort!() as powerful as delegate?

It depends what you mean by "powerful."  Passing a comparator as a template parameter, as with sort!(), means that the choice of comparator must be made at compile-time rather than run-time.  This may be problematic in some instances.

> 2. Is the call inside sort direct or indirect? Thank you, Dee Girl

Do you mean inline or not inline?  It's hard to say.  DMD's inlining mechanism is a bit quirky, so it could go either way.  For example, I've had struct member functions which would be inlined if static and not inlined if not static, and other member functions which were the reverse.  I haven't found any way to be sure other than trying it out and examining the ASM from the object file.


Sean
May 13, 2008
Sean Kelly Wrote:

> == Quote from Dee Girl (deegirl@noreply.com)'s article
> > Yigal Chripun Wrote:
> > > Dee Girl wrote:
> > > <snip>
> > > maybe I still didn't explain myself properly. I've used the term
> > > "sort-with-delegates" meaning a specific instance of sort when given a
> > > delegate as input. I thought this was clear enough, otherwise I would
> > > have simply said "sort".
> > > before you start sending me assembly code, let's go over it again and
> > > make sure we both understand each other:
> > > you take the sort template, stick in a delegate, mix for five minutes
> > > let is simmer for one more and viola: you got the exact same thing if
> > > you would have written sort as a regular function which receives a
> > > delegate parameter.
> > > the template takes the symbol it receives (the delegate name) and
> > > "embeds" it in the sort instance.
> > > both ways you get:
> > > 1) a call to sort
> > > 2) a call to the delegate
> > > the only difference is the number of parameters the sort function
> > > receives when called.
> > > the regular sort function can run different delegates at runtime (this
> > > is what you call "dynamic". the template has the call to the specific
> > > delegate embedded so for different delegates you need different sort
> > > instances.
> > Good. I think I understand. I want to be very sure, so I have a question from this code.
> > int array[] = [1, 2, 3];
> > int x = 5;
> > sort!((int a, int b) { return a + x < b + x; })(array);
> > Two questions not one ^_^
> > 1. Is the code inside sort!() as powerful as delegate?
> 
> It depends what you mean by "powerful."  Passing a comparator as a template parameter, as with sort!(), means that the choice of comparator must be made at compile-time rather than run-time.  This may be problematic in some instances.

Maybe you did not read previous discussion. Choice of comparator can be made at runtime. sort!(dg) works for a dynamic delegate dg. Just try it! It was hard to believe for me. The way D compiler insantiates sort is ingenious. This makes sort very powerful because it works with both static and dynamic code at the same time! I never found that in a language.

> > 2. Is the call inside sort direct or indirect? Thank you, Dee Girl
> 
> Do you mean inline or not inline?  It's hard to say.  DMD's inlining mechanism is a bit quirky, so it could go either way.  For example, I've had struct member functions which would be inlined if static and not inlined if not static, and other member functions which were the reverse.  I haven't found any way to be sure other than trying it out and examining the ASM from the object file.

Question was not about inlining. It was about indirect call with a pointer to function or a regular call. The regular call could be inlined but the pointer call is much harder. The answer is deterministic and very interesting. I think I undestand now how the D compiler generates functions from templates. Thank you, Dee Girl
May 13, 2008
== Quote from Dee Girl (deegirl@noreply.com)'s article
> Sean Kelly Wrote:
> > == Quote from Dee Girl (deegirl@noreply.com)'s article
> > > Yigal Chripun Wrote:
> > > > Dee Girl wrote:
> > > > <snip>
> > > > maybe I still didn't explain myself properly. I've used the term
> > > > "sort-with-delegates" meaning a specific instance of sort when given a
> > > > delegate as input. I thought this was clear enough, otherwise I would
> > > > have simply said "sort".
> > > > before you start sending me assembly code, let's go over it again and
> > > > make sure we both understand each other:
> > > > you take the sort template, stick in a delegate, mix for five minutes
> > > > let is simmer for one more and viola: you got the exact same thing if
> > > > you would have written sort as a regular function which receives a
> > > > delegate parameter.
> > > > the template takes the symbol it receives (the delegate name) and
> > > > "embeds" it in the sort instance.
> > > > both ways you get:
> > > > 1) a call to sort
> > > > 2) a call to the delegate
> > > > the only difference is the number of parameters the sort function
> > > > receives when called.
> > > > the regular sort function can run different delegates at runtime (this
> > > > is what you call "dynamic". the template has the call to the specific
> > > > delegate embedded so for different delegates you need different sort
> > > > instances.
> > > Good. I think I understand. I want to be very sure, so I have a question from this code.
> > > int array[] = [1, 2, 3];
> > > int x = 5;
> > > sort!((int a, int b) { return a + x < b + x; })(array);
> > > Two questions not one ^_^
> > > 1. Is the code inside sort!() as powerful as delegate?
> >
> > It depends what you mean by "powerful."  Passing a comparator as a template parameter, as with sort!(), means that the choice of comparator must be made at compile-time rather than run-time.  This may be problematic in some instances.
> Maybe you did not read previous discussion. Choice of comparator can be made at runtime. sort!(dg)
works for a dynamic delegate dg. Just try it! It was hard to believe for me. The way D compiler insantiates sort is ingenious. This makes sort very powerful because it works with both static and dynamic code at the same time! I never found that in a language.

So you're saying I could do this:

void myfunc( bool delegate(int,int) dg )
{
    int[] buf = [1,2,3,4,5].dup;
    sort!(dg)( buf );
}

I thought alias parameters had to be resolvable at compile-time.  Interesting.

> > > 2. Is the call inside sort direct or indirect? Thank you, Dee Girl
> >
> > Do you mean inline or not inline?  It's hard to say.  DMD's inlining mechanism is a bit quirky, so it could go either way.  For example, I've had struct member functions which would be inlined if static and not inlined if not static, and other member functions which were the reverse.  I haven't found any way to be sure other than trying it out and examining the ASM from the object file.
> Question was not about inlining. It was about indirect call with a pointer to function or a regular call.
The regular call could be inlined but the pointer call is much harder. The answer is deterministic and very interesting. I think I undestand now how the D compiler generates functions from templates. Thank you, Dee Girl

Harder but still possible.  DMD doesn't do this right now, but Walter has said it may in the future.


Sean
May 13, 2008
Sean Kelly Wrote:

> == Quote from Dee Girl (deegirl@noreply.com)'s article
> > Sean Kelly Wrote:
> > > == Quote from Dee Girl (deegirl@noreply.com)'s article
> > > > Yigal Chripun Wrote:
> > > > > Dee Girl wrote:
> > > > > <snip>
> > > > > maybe I still didn't explain myself properly. I've used the term
> > > > > "sort-with-delegates" meaning a specific instance of sort when given a
> > > > > delegate as input. I thought this was clear enough, otherwise I would
> > > > > have simply said "sort".
> > > > > before you start sending me assembly code, let's go over it again and
> > > > > make sure we both understand each other:
> > > > > you take the sort template, stick in a delegate, mix for five minutes
> > > > > let is simmer for one more and viola: you got the exact same thing if
> > > > > you would have written sort as a regular function which receives a
> > > > > delegate parameter.
> > > > > the template takes the symbol it receives (the delegate name) and
> > > > > "embeds" it in the sort instance.
> > > > > both ways you get:
> > > > > 1) a call to sort
> > > > > 2) a call to the delegate
> > > > > the only difference is the number of parameters the sort function
> > > > > receives when called.
> > > > > the regular sort function can run different delegates at runtime (this
> > > > > is what you call "dynamic". the template has the call to the specific
> > > > > delegate embedded so for different delegates you need different sort
> > > > > instances.
> > > > Good. I think I understand. I want to be very sure, so I have a question from this code.
> > > > int array[] = [1, 2, 3];
> > > > int x = 5;
> > > > sort!((int a, int b) { return a + x < b + x; })(array);
> > > > Two questions not one ^_^
> > > > 1. Is the code inside sort!() as powerful as delegate?
> > >
> > > It depends what you mean by "powerful."  Passing a comparator as a template parameter, as with sort!(), means that the choice of comparator must be made at compile-time rather than run-time.  This may be problematic in some instances.
> > Maybe you did not read previous discussion. Choice of comparator can be made at runtime. sort!(dg)
> works for a dynamic delegate dg. Just try it! It was hard to believe for me. The way D compiler insantiates sort is ingenious. This makes sort very powerful because it works with both static and dynamic code at the same time! I never found that in a language.
> 
> So you're saying I could do this:
> 
> void myfunc( bool delegate(int,int) dg )
> {
>     int[] buf = [1,2,3,4,5].dup;
>     sort!(dg)( buf );
> }
> 
> I thought alias parameters had to be resolvable at compile-time.  Interesting.
> 
> > > > 2. Is the call inside sort direct or indirect? Thank you, Dee Girl
> > >
> > > Do you mean inline or not inline?  It's hard to say.  DMD's inlining mechanism is a bit quirky, so it could go either way.  For example, I've had struct member functions which would be inlined if static and not inlined if not static, and other member functions which were the reverse.  I haven't found any way to be sure other than trying it out and examining the ASM from the object file.
> > Question was not about inlining. It was about indirect call with a pointer to function or a regular call.
> The regular call could be inlined but the pointer call is much harder. The answer is deterministic and very interesting. I think I undestand now how the D compiler generates functions from templates. Thank you, Dee Girl
> 
> Harder but still possible.  DMD doesn't do this right now, but Walter has said it may in the future.

Thank you for the information. But still there is no answer to my questions. It seems nobody is interested in the actual answer. So I will keep it secret. :x Dee Girl
May 13, 2008
Dee Girl wrote:
<snip>
> 1. Is the code inside sort!() as powerful as delegate?
>
>2. Is the call inside sort direct or indirect? Thank you, Dee Girl

well, you've been answered by an expert (Thanks Sean!)
I didn't know that Walter is working on making inlining delegates
possible, that this is indeed great news. :)
to answer your questions:
as I understand it, a delegate is internally a struct with two pointers:
a context pointer and a function pointer. the context pointer has the
address of the outer function for nested functions, or the this pointer
for methods. so, when passing a delegate you pass this struct.
based on that, I think that the answer to your second question is that
the call is indirect. this is true for both cases, otherwise that trick
of using a sort!() instance inside a mySort function wouldn't work. all
you pass to the template version is just a D symbol, in our case the
name of the delegate. in both cases you need to call that delegate.
you can pass regular function pointers to the template too (they are
written either with the function reserved word, or with the C syntax)
and those are simpler to inline. you can overload a non-templated sort
function to receive those as well.
I hope, some day function pointers would be implicitly castable to
delegates (just make the context pointer contain null) and this will
remove the need for providing two identical functions (one for delegates
and one for function pointers)
btw, another way of changing the delegate for a specific sort!()
instance is simply to assign it; no need for a wrapper function.
delegate bool(int a, int b) dg;
dg = aDelegate;
sort!(dg)(array);
dg = otherDelegate;
sort!(dg)(array); // the same instance should be used.




May 13, 2008
2008/5/13 Yigal Chripun <yigal100@gmail.com>:
>  I want the following API:
>  (I don't care now for the internal implementation and the wrapper
>  functions/aliases should be provided by the standard library)
>
>  array.sort; //same as array.sort(ASC);

    That one already works.

>  array.sort(DESC);

    alias std.algorithm.sort!("b<a") sort_reverse;
    array.sort_reverse;

Is that close enough?


>  array.sort(someStaticComperator);
>  array.sort(aDelegateComperator);
>  array.someOtherfunction(params);

That will never be possible either with or without templates.

Guess why?

Well, to save you guessing, I'll tell you. It's because "sort" is a built-in property of D's dynamic arrays. (Like length and ptr are built in). In general, we can define a function foo upon arrays which can be called as either

    foo(array,otherParams);
    array.foo(otherParams);

But unfortunately, you can't do that if the function happens to be named "sort". (Likewise "length", "ptr", "init", and so on). As I said, this is /not/ a limitation of templates.

If Walter were to remove the built-in sort property of arrays, then all of a sudden you would have:

    array.sort(someStaticComperator);
    array.sort(aDelegateComperator);

which I /think/ would work, because of type-deduction. (The compiler will match it with sort!(delegate)). If it doesn't, then you could file a bugzilla report that type deduction fails, and eventually it will be fixed. In short, the solution to your problem is to REMOVE the built-in property "sort" from arrays, so that libary versions can take over.
May 13, 2008
2008/5/13 Yigal Chripun <yigal100@gmail.com>:
>  Good Points! I thought about the IDE issue, but I wasn't sure how the
>  IDE handles this.

I don't have an IDE, but in my text editor,

    "a < b"

is colored like a string, but

    q{ a < b }

is colored like D code throughout. So I can choose my quoting method depending on how I want my code colored. This works, not because my IDE is smart, but precisely because it isn't! It doesn't realise that q{...} is a string, so it gets colored like code.
May 13, 2008
2008/5/13 Dee Girl <deegirl@noreply.com>:
>  int array[] = [1, 2, 3];
>  int x = 5;
>  sort!((int a, int b) { return a + x < b + x; })(array);
>
>  Two questions not one ^_^
>
>  1. Is the code inside sort!() as powerful as delegate?

The code inside sort!() /is/ a delegate. It's an anonymous delegate, but its implementation is exactly the same as a delegate with a name. It's equivalent to

    int foo (int a, int b) { return a + x < b + x; };
    sort!(foo)(array);
May 13, 2008
2008/5/13 Sean Kelly <sean@invisibleduck.org>:
>  It depends what you mean by "powerful."  Passing a comparator as a template parameter,
>  as with sort!(), means that the choice of comparator must be made at compile-time rather
>  than run-time.  This may be problematic in some instances.

I think you meant to say, the choice of comparator /may/ be made at compile-time. Not must.

    sort!(compare)(array); // compile time
    sort(compare, array); // run time