www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Problem with implicit template instantiation

reply Clemens Hofreither <clemens.hofreither gmx.net> writes:
Hi all.

I'm currently playing around with template metaprogramming in D. I've
encountered a problem with implicit instantiation of templates that I don't
really understand, and I thought somebody here could shed some light on it.
Consider the following code:

template MyType(T)
{
	alias T MyType;
}

void mytest(T)(MyType!(T) x)
{
}

void main()
{
	MyType!(int) x;
	mytest(x);
}

This does not work. I would expect the template mechanism to recognize that the
argument to mytest is an instance of MyType!(int) and hence instantiate T with
int, but instead I get the errors
template mytest(T) does not match any template declaration
template mytest(T) cannot deduce template function from argument types (int)

I've also tried replacing alias by typedef, with the same results.
Instantiating the template explicitly seems to work, but I would first like to
know *why* I can't do it like this before I use any workarounds. Any pointers?
Thanks in advance.

Oh, and this is DMD v1.029.

Regards,
Clemens.
Jul 06 2008
next sibling parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Clemens Hofreither wrote:

 Hi all.
 
 I'm currently playing around with template metaprogramming in D. I've
encountered a problem with implicit instantiation of templates that I don't
really understand, and I thought somebody here could shed some light on it.
Consider the following code:
 
 template MyType(T)
 {
 	alias T MyType;
 }
 
 void mytest(T)(MyType!(T) x)
 {
 }
 
 void main()
 {
 	MyType!(int) x;
 	mytest(x);
 }
 
 This does not work. I would expect the template mechanism to recognize that
the argument to mytest is an instance of MyType!(int) and hence instantiate T
with int, but instead I get the errors
 template mytest(T) does not match any template declaration
 template mytest(T) cannot deduce template function from argument types (int)
 
 I've also tried replacing alias by typedef, with the same results.
Instantiating the template explicitly seems to work, but I would first like to
know *why* I can't do it like this before I use any workarounds. Any pointers?
Thanks in advance.
 
 Oh, and this is DMD v1.029.


It's just not that smart.  It's a specialization so you have to use 
specialization syntax.  Something like:

void mytest(T : MyType!(S), S) {}

But note that using specialization also disables IFTI.
In D2 you should be able to use a constraint to do something like

void mytest(T) if(is(T : MyType!(S))) {}

My syntax is probably all wrong here, but that's the idea anyway.


Here's a bug marked fixed with a similar goal to yours:
     http://d.puremagic.com/issues/show_bug.cgi?id=1661
The discussion may be useful.

--bb
Jul 06 2008
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Bill Baxter" <dnewsgroup billbaxter.com> wrote in message 
news:g4s05a$2l0l$1 digitalmars.com...

 Clemens Hofreither wrote:

 Hi all.

 I'm currently playing around with template metaprogramming in D. I've 
 encountered a problem with implicit instantiation of templates that I 
 don't really understand, and I thought somebody here could shed some 
 light on it. Consider the following code:

 template MyType(T)
 {
 alias T MyType;
 }

 void mytest(T)(MyType!(T) x)
 {
 }

 void main()
 {
 MyType!(int) x;
 mytest(x);
 }

 This does not work. I would expect the template mechanism to recognize 
 that the argument to mytest is an instance of MyType!(int) and hence 
 instantiate T with int, but instead I get the errors
 template mytest(T) does not match any template declaration
 template mytest(T) cannot deduce template function from argument types 
 (int)

 I've also tried replacing alias by typedef, with the same results. 
 Instantiating the template explicitly seems to work, but I would first 
 like to know *why* I can't do it like this before I use any workarounds. 
 Any pointers? Thanks in advance.

 Oh, and this is DMD v1.029.


 It's just not that smart.  It's a specialization so you have to use 
 specialization syntax.  Something like:

 void mytest(T : MyType!(S), S) {}

 But note that using specialization also disables IFTI.
 In D2 you should be able to use a constraint to do something like

 void mytest(T) if(is(T : MyType!(S))) {}

 My syntax is probably all wrong here, but that's the idea anyway.


 Here's a bug marked fixed with a similar goal to yours:
     http://d.puremagic.com/issues/show_bug.cgi?id=1661
 The discussion may be useful.


I have an open enhancement request on this:

http://d.puremagic.com/issues/show_bug.cgi?id=1653

I think the main issue is really that there is no 'reverse' path from the 
alias to the parameter to a specific template.  That is given the type 
MyType!(T), which is really an alias for T, What template should the 
compiler use to deduce the argument?  What if there were multiple templates 
that aliased to T, should those also be assumed to be MyType!(T)?  What if 
you pass in just a T?  Technically it's the same thing.

I think these are the issues that makes it tough to do the IFTI.  I think we 
are spoiled because things like:

void f(T)(T[] x)

but that's a much simpler case to solve.

-Steve
Jul 06 2008
parent reply Clemens Hofreither <clemens.hofreither gmx.net> writes:
Steven Schveighoffer Wrote:


 
 "Bill Baxter" <dnewsgroup billbaxter.com> wrote in message 
 news:g4s05a$2l0l$1 digitalmars.com...

 Clemens Hofreither wrote:

 Hi all.

 I'm currently playing around with template metaprogramming in D. I've 
 encountered a problem with implicit instantiation of templates that I 
 don't really understand, and I thought somebody here could shed some 
 light on it. Consider the following code:

 template MyType(T)
 {
 alias T MyType;
 }

 void mytest(T)(MyType!(T) x)
 {
 }

 void main()
 {
 MyType!(int) x;
 mytest(x);
 }

 This does not work. I would expect the template mechanism to recognize 
 that the argument to mytest is an instance of MyType!(int) and hence 
 instantiate T with int, but instead I get the errors
 template mytest(T) does not match any template declaration
 template mytest(T) cannot deduce template function from argument types 
 (int)

 I've also tried replacing alias by typedef, with the same results. 
 Instantiating the template explicitly seems to work, but I would first 
 like to know *why* I can't do it like this before I use any workarounds. 
 Any pointers? Thanks in advance.

 Oh, and this is DMD v1.029.


 It's just not that smart.  It's a specialization so you have to use 
 specialization syntax.  Something like:

 void mytest(T : MyType!(S), S) {}

 But note that using specialization also disables IFTI.
 In D2 you should be able to use a constraint to do something like

 void mytest(T) if(is(T : MyType!(S))) {}

 My syntax is probably all wrong here, but that's the idea anyway.


 Here's a bug marked fixed with a similar goal to yours:
     http://d.puremagic.com/issues/show_bug.cgi?id=1661
 The discussion may be useful.


 
 I have an open enhancement request on this:
 
 http://d.puremagic.com/issues/show_bug.cgi?id=1653
 
 I think the main issue is really that there is no 'reverse' path from the 
 alias to the parameter to a specific template.  That is given the type 
 MyType!(T), which is really an alias for T, What template should the 
 compiler use to deduce the argument?  What if there were multiple templates 
 that aliased to T, should those also be assumed to be MyType!(T)?  What if 
 you pass in just a T?  Technically it's the same thing.
 
 I think these are the issues that makes it tough to do the IFTI.  I think we 
 are spoiled because things like:
 
 void f(T)(T[] x)
 
 but that's a much simpler case to solve.
 
 -Steve 
 
 


I understand the issue. On the other hand, if I use a typedef instead of an
alias, shouldn't the compiler be (conceptually) able to know exactly whether
the passed in type is of the right type, because typedefs are uniquely
identified? In other words, would you think the compiler could possibly be
extended to accept my program if I use typedef instead of alias? It seems like
a useful feature to have, if it is possible.

Clemens
Jul 07 2008
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Clemens Hofreither" wrote

 Steven Schveighoffer Wrote:


 "Bill Baxter" <dnewsgroup billbaxter.com> wrote in message
 news:g4s05a$2l0l$1 digitalmars.com...

 Clemens Hofreither wrote:

 Hi all.

 I'm currently playing around with template metaprogramming in D. I've
 encountered a problem with implicit instantiation of templates that I
 don't really understand, and I thought somebody here could shed some
 light on it. Consider the following code:

 template MyType(T)
 {
 alias T MyType;
 }

 void mytest(T)(MyType!(T) x)
 {
 }

 void main()
 {
 MyType!(int) x;
 mytest(x);
 }

 This does not work. I would expect the template mechanism to recognize
 that the argument to mytest is an instance of MyType!(int) and hence
 instantiate T with int, but instead I get the errors
 template mytest(T) does not match any template declaration
 template mytest(T) cannot deduce template function from argument types
 (int)

 I've also tried replacing alias by typedef, with the same results.
 Instantiating the template explicitly seems to work, but I would first
 like to know *why* I can't do it like this before I use any 
 workarounds.
 Any pointers? Thanks in advance.

 Oh, and this is DMD v1.029.


 It's just not that smart.  It's a specialization so you have to use
 specialization syntax.  Something like:

 void mytest(T : MyType!(S), S) {}

 But note that using specialization also disables IFTI.
 In D2 you should be able to use a constraint to do something like

 void mytest(T) if(is(T : MyType!(S))) {}

 My syntax is probably all wrong here, but that's the idea anyway.


 Here's a bug marked fixed with a similar goal to yours:
     http://d.puremagic.com/issues/show_bug.cgi?id=1661
 The discussion may be useful.


 I have an open enhancement request on this:

 http://d.puremagic.com/issues/show_bug.cgi?id=1653

 I think the main issue is really that there is no 'reverse' path from the
 alias to the parameter to a specific template.  That is given the type
 MyType!(T), which is really an alias for T, What template should the
 compiler use to deduce the argument?  What if there were multiple 
 templates
 that aliased to T, should those also be assumed to be MyType!(T)?  What 
 if
 you pass in just a T?  Technically it's the same thing.

 I think these are the issues that makes it tough to do the IFTI.  I think 
 we
 are spoiled because things like:

 void f(T)(T[] x)

 but that's a much simpler case to solve.

 -Steve


 I understand the issue. On the other hand, if I use a typedef instead of 
 an alias, shouldn't the compiler be (conceptually) able to know exactly 
 whether the passed in type is of the right type, because typedefs are 
 uniquely identified? In other words, would you think the compiler could 
 possibly be extended to accept my program if I use typedef instead of 
 alias? It seems like a useful feature to have, if it is possible.


Yes, typedef would be easier to infer, because the original template that 
constructed the type would be embedded in the type.  However, you lose a lot 
of usefulness by using typedef instead of alias.  But I doubt Walter will 
add the functionality just for typedef, as it is not the common case.

In any case, here is a good counter example for the alias:

template MyType!(T)
{
    static if(is(T == int))
       alias long MyType!(T);
    else
       alias T MyType!(T);
}

T f(T)(MyType!(T) t) {}

If f is passed a long, how should it infer the original type?  As a 
MyType!(int) or MyType!(long)?  It is important because the function needs 
to know which is correct so it can return the correct type.  Maybe this just 
becomes an error (if the requested functionality is implemented), similar to 
ambiguous overload.

I'll put this counter-example in the bugzilla report.

-Steve
Jul 07 2008
prev sibling parent Clemens Hofreither <clemens.hofreither gmx.net> writes:
For what it's worth, I have circumvented my original problem by making
the templated type in question a class. Since the code seems to work
nicely now, I figured I could as well post it; it's a generic memoize function
which works (type-safely) on functions with any return type and any
number and type of arguments (well, as long as they can be AA indices). I
would be interested in any improvement suggestions. Also, I'd really like to
know why I have to use "inout" for the AA argument in store(); I thought
AAs had reference semantics, but without inout it doesn't work as
expected.

Well, here's the code:


/*****************************************/
import tango.io.Stdout;

class MultiMap(S, T...)
{
	private template MultiMapT(R, Q...)
	{
		static if (Q.length <= 1)
			alias R[Q[0]] MultiMapT;
		else
			alias MultiMapT!(R,Q[1..length])[Q[0]] MultiMapT;
	}
	
	private alias MultiMapT!(S,T) M;
	private M map;
	
	private static S *lookup(R, Q...)(R[Q[0]] map, Q key)
	{
		static if (key.length <= 1)
			return key[0] in map;
		else {
			auto inner = key[0] in map;
			if (inner != null)
				return lookup!(typeof(R[Q[0]]), Q[1..length])(*inner, key[1..length]);
			else
				return null;
		}
	}
	
	private static void store(R, Q...)(inout R[Q[0]] map, S value, Q key)
	{
		static if (key.length <= 1)
			map[key[0]] = value;
		else
			store!(typeof(R[Q[0]]), Q[1..length])(map[key[0]], value, key[1..length]);
	}

	S *get(T key) {
		return lookup!(typeof(M[T[0]]), T)(map, key);
	}
	void set(S value, T key) {
		store!(typeof(M[T[0]]), T)(map, value, key);
	}
}



class Memo(R, P...)
{
	private R function(P) func;
	private MultiMap!(R,P) values;
	
	this(R function(P) f)
	{
		func = f;
		values = new MultiMap!(R,P);
	}
	
	R opCall(P args)
	{
		R *val = values.get(args);
		if (val != null)
			return *val;
		else {
			R v = func(args);
			values.set(v, args);
			return v;
		}
	}
}

Memo!(R, P) memoize(R, P...)(R function(P) myfunc)
{
	return new Memo!(R,P)(myfunc);
}


float foo(float x, float y)
{
	Stdout.format("foo called.\n");
	return x / y;
}

void main()
{
	auto f = memoize(&foo);
	Stdout.format("{}\n", f(3f, 4f));
	Stdout.format("{}\n", f(3f, 4f));
}
/*****************************************/

-Clemens
Jul 07 2008