www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - template magic

reply spir <denis.spir gmail.com> writes:
Hello,

This post is about the various roles D templates can play. I had to write a 
higher-order function (hof) that takes as parameter a func which itself returns 
any kind of type. Thus, the hof is also templated. (Below the simplest case I 
could find as example.)

Unlike in functional style, in Phobos hof's often define their func parameter 
as a template parameter, not as a regular one. Following this example, I thus I 
ended up in something like this:

P[] hof1 (P, alias f) (uint n) {
     // just n times f's result
     P[] ps;
     foreach (i ; 0..n)
         ps ~= f();
     return ps;
}
// example parameter function:
int f () { return 1; }

This runs fine. A conceptual issue that itched my brain is that the type 
parameter P is in fact defined twice, once explicitely & implicitely as f's 
return type. I thus re-placed f as an ordinary parameter:

P[] hof2 (P) (uint n, P function () f) {
     // same as above
     P[] ps;
     foreach (i ; 0..n)
         ps ~= f();
     return ps;
}

This runs fine as well. But, guessing that Phobos's way of placing funcs as 
template parameters may be due to a good reason, I tried to do the same and 
still avoid P beeing defined twice. Used std.traits' ReturnType! for this:

auto hof3 (alias f) (uint n) {
     // below the magic
     alias ReturnType!f P;
     P[] ps;
     foreach (i ; 0..n)
         ps ~= f();
     return ps;
}

As you see, this also requires using 'auto' for the hof's return type. But we 
can use the same magic trick there as well. Really ugly, but works:

ReturnType!f[] hof4 (alias f) (uint n) {
     alias ReturnType!f P;
     P[] ps;
     foreach (i ; 0..n)
         ps ~= f();
     return ps;
}

The latter trick also solves the case where P / ReturnType!f is needed 
elsewhere in the hof's signature, eg:

ReturnType!f[] hof5 (alias f) (uint n, ReturnType!f p) {
     alias ReturnType!f P;
     P[] ps;
     foreach (i ; 0..n)
         ps ~= f(p);
     return ps;
}

Can you believe all of those versions work fine? See whole test code below.
Now, 3 questions?

1. Is the fact that we have so many ways to define the same thing a Good Thing, 
according to you?

2. What is the reason for Phobos defining param funcs as template params? 
Efficiency? Why?

3. What is the meaning of 'alias f'? How does it work? This is a totally 
enigmatic feature for me. Seems it allows placing anything of any type as 
template param. Far more versatile than common use of templates as 'simple' 
generics. Note that if I remove the seemingly useless 'alias' from version 1 , 
I get:
     Error: template instance hof1!(int,f) does not match template declaration 
hof1(P,f)
???
(could not find any explanation on alias params anywhere -- pointers also
welcome)

Denis

============ test code =================
import std.stdio;
import std.traits;

P[] hof1 (P, alias f) (uint n) {
     P[] ps;
     foreach (i ; 0..n)
         ps ~= f();
     return ps;
}
P[] hof2 (P) (uint n, P function () f) {
     P[] ps;
     foreach (i ; 0..n)
         ps ~= f();
     return ps;
}
auto hof3 (alias f) (uint n) {
     alias ReturnType!f P;
     P[] ps;
     foreach (i ; 0..n)
         ps ~= f();
     return ps;
}
ReturnType!f[] hof4 (alias f) (uint n) {
     alias ReturnType!f P;
     P[] ps;
     foreach (i ; 0..n)
         ps ~= f();
     return ps;
}
ReturnType!f[] hof5 (alias f) (uint n, ReturnType!f p) {
     alias ReturnType!f P;
     P[] ps;
     foreach (i ; 0..n)
         ps ~= f(p);
     return ps;
}

int f () { return 1; }
int f2 (int i) { return i; }

unittest {
     writeln( hof1!(int, f)(3) );

     writeln( hof2!int(3, &f) );
     writeln( hof2(3, &f) );

     writeln( hof3!f(3) );
     writeln( hof4!f(3) );

     writeln( hof5!f2(3, 1) );
}
void main () {}
=======================================
-- 
_________________
vita es estrany
spir.wikidot.com
Jan 25 2011
next sibling parent "Simen kjaeraas" <simen.kjaras gmail.com> writes:
spir <denis.spir gmail.com> wrote:

 1. Is the fact that we have so many ways to define the same thing a Good  
 Thing, according to you?

Yes.
 2. What is the reason for Phobos defining param funcs as template  
 params? Efficiency? Why?

Efficiency is one reason, as DMD is unable to inline functions passed as parameters. It is also a kind of currying, allowing one to define the function as foo!bar, and for instance store it in an alias.
 3. What is the meaning of 'alias f'? How does it work? This is a totally  
 enigmatic feature for me. Seems it allows placing anything of any type  
 as template param. Far more versatile than common use of templates as  
 'simple' generics. Note that if I remove the seemingly useless 'alias'  
 from version 1 , I get:
      Error: template instance hof1!(int,f) does not match template  
 declaration hof1(P,f)
 ???
 (could not find any explanation on alias params anywhere -- pointers  
 also welcome)

D templates take three kinds of parameters - types, aliases, and values. While the other two are easy to understand, aliases are somewhat more complex. In short, an alias can reference anything that has a name. The details may be more complex, but that's the gist of it. -- Simen
Jan 25 2011
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 25 Jan 2011 10:21:29 -0500, spir <denis.spir gmail.com> wrote:

 Hello,

 This post is about the various roles D templates can play. I had to  
 write a higher-order function (hof) that takes as parameter a func which  
 itself returns any kind of type. Thus, the hof is also templated. (Below  
 the simplest case I could find as example.)

[snip]
 Can you believe all of those versions work fine? See whole test code  
 below.
 Now, 3 questions?

 1. Is the fact that we have so many ways to define the same thing a Good  
 Thing, according to you?

 2. What is the reason for Phobos defining param funcs as template  
 params? Efficiency? Why?

 3. What is the meaning of 'alias f'? How does it work? This is a totally  
 enigmatic feature for me. Seems it allows placing anything of any type  
 as template param. Far more versatile than common use of templates as  
 'simple' generics. Note that if I remove the seemingly useless 'alias'  
 from version 1 , I get:
      Error: template instance hof1!(int,f) does not match template  
 declaration hof1(P,f)
 ???
 (could not find any explanation on alias params anywhere -- pointers  
 also welcome)

Your confusion probably stems from your lack of test cases :) aliases work as any definable symbol -- template (even uninstantiated ones!), function, delegate, symbol, struct, variable, etc. For instance, this also works (using your already-defined hof3)! void main() { int n; struct S { this(int step) {this.step = step;} int step; int opCall() {return (n = (n + step));} } S s = S(1); // step of 1 S s2 = S(2); // step of 2 auto intarr = hof3!s(5); // returns [1,2,3,4,5] auto intarr2 = hof3!s2(5); // returns [7,9,11,13,15] } Note how the alias maps to a *specific local variable* at compile-time, now that's kick ass. Alias is the coolest part of templates I've seen in D. It works for just about anything. What I'd say is to make your template definition "correct" is to add some constraints to ensure the functor (the alias parameter) is a callable type. auto hof3(alias f)(uint n) if (isCallable!f) -Steve
Jan 25 2011
prev sibling next sibling parent reply Trass3r <un known.com> writes:
 2. What is the reason for Phobos defining param funcs as template

Correct me if I'm wrong but there's no way to pass an arbitrary function to a function in a type-safe way. If you use pointers and casts you can't check if the passed function meets certain requirements (parameters, return type, attributes, etc.)
 3. What is the meaning of 'alias f'? How does it work? This is a

 enigmatic feature for me. Seems it allows placing anything of any

 template param.

http://digitalmars.com/d/2.0/template.html#TemplateAliasParameter It allows you to pass any D symbol. As the name already suggests, think of it as being a template-local alias to a symbol passed in the instantiation (but note that you can also pass literals as arguments to alias parameters).
Jan 25 2011
next sibling parent reply Jesse Phillips <jessekphillips+D gmail.com> writes:
Trass3r Wrote:

 2. What is the reason for Phobos defining param funcs as template

Correct me if I'm wrong but there's no way to pass an arbitrary function to a function in a type-safe way. If you use pointers and casts you can't check if the passed function meets certain requirements (parameters, return type, attributes, etc.)

How do you not pass them in a safe manner? If you are casting things, of course you don't get type safety.
Jan 25 2011
parent Trass3r <un known.com> writes:
 How do you not pass them in a safe manner? If you are casting things,

Yep, I was talking about non-template functions. Only way to pass an arbitrary function is via void*
Jan 25 2011
prev sibling parent reply spir <denis.spir gmail.com> writes:
On 01/25/2011 06:03 PM, Simen kjaeraas wrote:
 Of course, given a non-template function, it is impossible to safely
 pass a function to it.

Dont you count this as typesafe function passing? void writeRounding (int function (float) roundingScheme) {...} Denis -- _________________ vita es estrany spir.wikidot.com
Jan 25 2011
parent Jesse Phillips <jessekphillips+D gmail.com> writes:
spir Wrote:

 On 01/25/2011 06:03 PM, Simen kjaeraas wrote:
 Of course, given a non-template function, it is impossible to safely
 pass a function to it.

Dont you count this as typesafe function passing? void writeRounding (int function (float) roundingScheme) {...}

He means accepting any function no matter the return type or arguments. With templates you can do this and it will remain type safe, non-templates can't do this while remaining type safe. But then again you shouldn't really expect an arbitrary function to be type safe at runtime, unless of course you specify the types it must be, but then it isn't arbitrary in that context...
Jan 25 2011
prev sibling parent "Simen kjaeraas" <simen.kjaras gmail.com> writes:
Trass3r <un known.com> wrote:

 2. What is the reason for Phobos defining param funcs as template

Correct me if I'm wrong but there's no way to pass an arbitrary function to a function in a type-safe way. If you use pointers and casts you can't check if the passed function meets certain requirements (parameters, return type, attributes, etc.)

It is perfectly possible to typesafely pass a function or delegate to a function: void foo( F )( F fn ) { fn(); } You can then add other things to pass parameters: void foo( F )( F fn, ParameterTypeTuple!F args ) { fn( arg ); } Of course, given a non-template function, it is impossible to safely pass a function to it. -- Simen
Jan 25 2011