www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - [draft, proposal] Virtual template functions

reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
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
May 29 2012
next sibling parent Gor Gyolchanyan <gor.f.gyolchanyan gmail.com> writes:
On Tue, May 29, 2012 at 3:59 PM, Dmitry Olshansky <dmitry.olsh gmail.com>wrote:


 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


This is a really awesome idea! Not only does it solve a lot of problems, it
also looks very intuitive and doesn't break existing code. If D was the
first language to have virtual template methods, that would be a huge
credit to the language!
+1!

-- 
Bye,
Gor Gyolchanyan.
May 29 2012
prev sibling parent reply Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
On 5/29/12, Dmitry Olshansky <dmitry.olsh gmail.com> wrote:

 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 ;)


I've run into an issue like this, currently I use this sort of workaround:

class Base
{
    abstract void run();

    void runAll(this Child)(Child ch)
    {
        foreach (i; 0 .. 10)  // demo
            ch.templateMethod(i);
    }
}

class Child : Base
{
    override void run()
    {
        runAll(this);
    }

    void templateMethod(T)(T t) { }
}

void main()
{
    auto ch = new Child;
    ch.run();
}

All subclasses of Base need to implement 'templateMethod', but it has
to be a templated function. Unfortunately that means it can't be
virtual so I'm using a 'this' template parameter in a base function
that has to be called. Not very pretty!
May 29 2012
parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 29.05.2012 21:04, Andrej Mitrovic wrote:

 On 5/29/12, Dmitry Olshansky<dmitry.olsh gmail.com>  wrote:

 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 ;)


 I've run into an issue like this, currently I use this sort of workaround:

 class Base
 {
      abstract void run();

      void runAll(this Child)(Child ch)
      {
          foreach (i; 0 .. 10)  // demo
              ch.templateMethod(i);
      }
 }

 class Child : Base
 {
      override void run()
      {
          runAll(this);
      }

      void templateMethod(T)(T t) { }
 }

 void main()
 {
      auto ch = new Child;
      ch.run();
 }


Would this work if say:
       Base ch = new Child;
  	ch.run();

Since all this template this parameter stuff is arcane to me :)
In any event it look like doing hand-written thunks. And that's clear 
indication to me that it needs a better hook in compiler.


 All subclasses of Base need to implement 'templateMethod', but it has
 to be a templated function. Unfortunately that means it can't be
 virtual so I'm using a 'this' template parameter in a base function
 that has to be called. Not very pretty!


The bloat is the same, and even some extra call overhead if I'm not 
mistaken.

-- 
Dmitry Olshansky
May 29 2012