[draft, proposal] Virtual template functions

[Dmitry Olshansky]

I'm reiterating prior info on the subject and provide some motivating 
examples. For those convinced of necessity of virtual function templates 
already - skip to the bottom ;)

Ultimately template is a way to use the same source code for multiple 
entities (typically called instantiations).
In the light of the above simple definition it's painfully obvious that 
if functions generated by template are final vs virtual is completely 
separate orthogonal matter.
The fact that templates are final is rather a happenstance,
"it's 'cause it's too hard, lad" kind of thing.

The fundamental problem is that given an interface
interface I
{
	TA funcA();
	TB funcB();
	TC funcC();
	...
}

compiler needs to plot _final_ layout of a v-table so that separate 
compilation works without hassle. (there are possible ways around it, 
though non-trivial and breaking current toolchains).

Now since even constrained template technically can accommodate infinite 
number of instantiations it sure becomes problematic.

But surely the template below has exactly X instantiations,
since there is only X operators in the whole D language that are ever 
overloadable, X being constant (sorry didn't care to count).

interface Matrix
{
	void opOpAssign(string op)(Matrix rhs);
}

And this one is even down to 3:

interface Matrix
{
	void opOpAssign(string op)(Matrix rhs)
	if(op == "+" || op == "-" || op == "*");
}

Of course, having compiler to deduce these kind of special cases can be 
described as a fragile hack at best. Thus a more clean and general 
solution is proposed.

Before moving on to syntax and the feature itself. Another motivating 
example to illustrate a need for virtual functions to be templates.
Though I'm you know a lot of uses cases as well, so feel free to skip it.

Suppose you define Set as interface for sets, and provide some 
implementations of it like BitSet, HashSet, TreeSet, SparceSet.

Now we are back to operator overloading, some might argue that having 
final operators is enough, it's not:

interface Set(V, K)
{
	V get(K key);
	void put(V value, K key);
	void remove(K key);
	//even opApply won't save us ;)
	int opApply(scope delegate(K, V));
	
	void opOpAssign(string op)(Set rhs)
	{
		
		//foreach(k, v; rhs)
		//	remove(k);
		//Okay, now try to be efficient, punk !
		...
	}
}

It's immediately obvious that doing low-level operations via high-level 
primitives is no good. Certain combination of sets are obviously can be 
done faster. And for instance 2 small enough bitsets can be merged in a 
blink of an eye, (similar things for sparse set). And nobody is willing 
to give up speed nor polymorphism.

(e.g. Set & Set should use the best overload for '&' for concrete sets 
at hand == virtual operator).

The only current way is forwarding to virtual methods and that may work. 
Though templates and new operator overloading in particular aim to 
reduce amount of repetition and boilerplate.


Enough of talk, to the proposal, synopsis is to enhance template 
declaration:

T func(string id, T, Args...)(...)
	if( ... ) //optional
	for(	//optional
		id : "a", "b", "c";
		T: double, float;
		Args : (int, int), (uint, int), (int, uint);
	)//syntax debatable, 'for' is not ;)

It would then instantate all of possible overloads immediately in this 
particular module.  (another use case for it is explicit instantiation 
for shared libraries)

If it happens to be inside of class/interface the by default all of 
overloads would work as virtual.

Other then this for implies the following if condition ANDed together to 
existing if clause if any:
.... & (
(id == "a" || id == "b" || id == "c") &&
(is(T == double)|| is(T == float)) &&
(
		(is(Args[0] == int) && is(Args[1]==int))
	|| 	(is(Args[0] == uint) && is(Args[1]==int))
	||	(is(Args[0] == int) && is(Args[1]==uint))

)

)
A remarkable boilerplate, underlines the fact that trying to have 
compiler to deduce all types from it for you is not realistic in general 
case.

Of course the coma separated typelists can be constructed via 
meta-programming. In fact all tuples should be flattened (as is 
everywhere else).

And that's it, so new 'for' clause for templates does:
	- explicitly instantes entities, ensuring bounded number of 
instantiations (makes virtual possible)
	- provides alternative sugar for 'if' syntax
	- fits with the rest of language, via typetuple and meta-programming
	- allows simple techniques to curb down accidental duck-typing

-- 
Dmitry Olshansky