www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Template instantiation and overloaded functions

reply Falk Henrich <schreibmalwieder hammerfort.de> writes:
Hi,

I'm troubled by D's template instantiation algorithm in combination with
overloaded functions. If I have

Z[] zip(X,Y,Z)(Z function(X, Y) f, X[] x, Y[] y)
{ Z[] z; z.length = x.length;
  for(size_t i = 0; i < x.length; i++) { z[i] = f(x[i], y[i]); }
  return z;
}

and some functions

double plus(double x, double y) {return x+y;}
long plus(long x, long y) {return x+y;}
int plus(int x, int y) {return x+y;}

and now do

int[] a = [1,2,0]; int[] b = [0,1,0];
writefln(zip(&plus, a,b));

the compiler (gdc 0.23) tells me:

functional.d:186: template functional.zip(X,Y,Z) does not match any template
declaration
functional.d:186: template functional.zip(X,Y,Z) cannot deduce template
function from argument types (double(*)(double x, double y),int[],int[])

By switching the order of declaration of the overloaded plus functions I
discovered that the compiler will only consider the first declaration, no
matter what. Does this behavior adhere to the D specification?

Falk
Mar 25 2007
parent reply Daniel Keep <daniel.keep.lists gmail.com> writes:
Falk Henrich wrote:
 Hi,
 
 I'm troubled by D's template instantiation algorithm in combination with
 overloaded functions. If I have
 
 Z[] zip(X,Y,Z)(Z function(X, Y) f, X[] x, Y[] y)
 { Z[] z; z.length = x.length;
   for(size_t i = 0; i < x.length; i++) { z[i] = f(x[i], y[i]); }
   return z;
 }
 
 and some functions
 
 double plus(double x, double y) {return x+y;}
 long plus(long x, long y) {return x+y;}
 int plus(int x, int y) {return x+y;}
 
 and now do
 
 int[] a = [1,2,0]; int[] b = [0,1,0];
 writefln(zip(&plus, a,b));
 
 the compiler (gdc 0.23) tells me:
 
 functional.d:186: template functional.zip(X,Y,Z) does not match any template
 declaration
 functional.d:186: template functional.zip(X,Y,Z) cannot deduce template
 function from argument types (double(*)(double x, double y),int[],int[])
 
 By switching the order of declaration of the overloaded plus functions I
 discovered that the compiler will only consider the first declaration, no
 matter what. Does this behavior adhere to the D specification?
 
 Falk

As far as I understand it, the problem is that there's no way to directly specify which overload of a method you want. I believe there was a trick involving casting the pointer, but I never really used it :P I think what's happening here is that when you specify &plus, since it's overloaded, it takes the first one it finds. It then grabs a and b, and then tries to instantiate the template. Problem is that the first argument is a double(*)(double,double), but the template parameters say that it's supposed to be... well, it doesn't actually say, really. But it's the wrong one, at any rate :P One solution is to put your operator functions in a template, and always access them explicitly, like so:
 T plus(T)(T a, T b) { return a + b; }

 zip(&plus!(int), a, b);

Another solution, which is a bit more hacky, would be to overload the zip function with a second version that looks like this:
 tZipResult!(fn, X, Y)[] zip(alias fn, X, Y)(X[] a, Y[] b)
 {
     // ...
 }

And use that casting trick I mentioned earlier to derive the 'Z' type, and get the function overload you actually want. So to the user, it would look like this:
 zip!(plus)(a, b);

Incidentally, I never wrote a 'zip' function because you can't return tuples from functions yet[1]. :P Yours looks more like two-argument map... n-argument map should be possible using variadic templates (so long as the collection types aren't iterators, in which case you're screwed), I just never got around to doing it. :P In any case, a few people have suggested a number of times that it be possible to pick out one particular instance of an overload, but no nice way of doing it has actually emerged. :( -- Daniel [1] *And* because, as far as I know, there's no way to iterate over multiple iterators at once without bringing some form of threading into the mix. Ick. -- int getRandomNumber() { return 4; // chosen by fair dice roll. // guaranteed to be random. } http://xkcd.com/ v2sw5+8Yhw5ln4+5pr6OFPma8u6+7Lw4Tm6+7l6+7D i28a2Xs3MSr2e4/6+7t4TNSMb6HTOp5en5g6RAHCP http://hackerkey.com/
Mar 25 2007
parent Falk-Florian Henrich <schreibmalwieder hammerfort.de> writes:
Am Mon, 26 Mar 2007 08:27:03 +1000 schrieb Daniel Keep:

 Falk Henrich wrote:
 I'm troubled by D's template instantiation algorithm in combination
 with overloaded functions. If I have
 ...

overloaded, it takes the first one it finds. It then grabs a and b, and then tries to instantiate the template.

I think the compiler should be able to handle this situation (although the D spec doesn't answer this question). Its type inference algorithm is just too weak. Certainly, doing more type inference would make the compiler slower, but it eases the programmer's life a lot.
 One solution is to put your operator functions in a template, and always
 access them explicitly, like so:
 
 T plus(T)(T a, T b) { return a + b; }

 zip(&plus!(int), a, b);


I know, but that's ugly.
 Another solution, which is a bit more hacky, would be to overload the
 zip function with a second version that looks like this:
 
 tZipResult!(fn, X, Y)[] zip(alias fn, X, Y)(X[] a, Y[] b) {
     // ...
 }

And use that casting trick I mentioned earlier to derive the 'Z' type, and get the function overload you actually want. So to the user, it would look like this:
 zip!(plus)(a, b);


Maybe I will try to figure that out...
 Incidentally, I never wrote a 'zip' function because you can't return
 tuples from functions yet[1]. :P  Yours looks more like two-argument
 map... n-argument map should be possible using variadic templates (so
 long as the collection types aren't iterators, in which case you're
 screwed), I just never got around to doing it. :P

Of course, it's a matter of definition. I'm just reimplementing this one: http://uebb.cs.tu-berlin.de/~opal/ocs/doc/html/BibOpalicaManual/ SeqZip.html#IDX2882
 In any case, a few people have suggested a number of times that it be
 possible to pick out one particular instance of an overload, but no nice
 way of doing it has actually emerged.  :(

As I mentioned above, I think the root of all these problems - deduce the correct overload of a function - infer arguments to a delegate / function literal - ... seems to be a weak type inference algorithm. It will get worse with every advanced feature that is introduced to the language (i.e., AST macros, ...). In my opinion, introducing killer features doesn't help if one has to apply subtle tricks to get things to work. And D runs the risk of becoming an awkward potpourri of features like C++. Don't get me wrong, I really appreciate that D includes a number of major improvements compared to C/C++/C#/Java (which makes learning D worthwhile even if one uses templates only in a restricted manner). Falk
Mar 26 2007