Tim M wrote:
> On Sun, 08 Mar 2009 20:12:20 +1300, Daniel Keep <daniel.keep.lists@gmail.com> wrote:
> 
>>
>> One issue with this is that template functions can't be virtual.
>>
>> You can work around it, but it's really putting barriers up to easy use of the new const system, which I think is a bad thing.
>>
>>   -- Daniel
> 
> I'd rather have virtual template functions, even if it means I have to re-compile all subclasses when the vtbls get modified. Is there any technicality causing it to be impossible to implement or just something rather tricky?

Tricky?!  /gobsmacked

> class C
> {
>     void fn(T);
> }

T can be anything, and can do anything.

The ONLY way for this to work, as far as I know, is for one of two things to happen:

1. The compiler has to know every single invocation of fn that takes place, and instantiate the template for that type for every class that derives from C.

   This, of course, means that you can't ever load code at runtime
through, say, a dynamic library, because it might try to call a method
that doesn't exist, but is actually defined.

   This also means that the D compilers have to be changed to no longer
use single-file compilation.

   Additionally, you still can't ever have a compiled library with
virtual template members, since there's no way for the library to know
what types it should be compiled with: there's an infinite number!

2. The runtime has to be able to instantiate the template at run-time. This means you have to store the source for the template in the executable, along with a full symbol table.  The D runtime then has to contain a full D compiler, including all libraries and probably a linker, too.  Remember that the template could contain string mixins, so you really can't be "clever": you have to include the whole thing.

Saying this is "tricky" is a tremendous understatement.

  -- Daniel

Firstly option 2 was just crazy and I don't know why you said that. For option 1 you identifying the limitations and are just trying to apply as many problems as you can though the main barriers can easily be lowered.

As you already know templates are a compile time feature, so that statement about the compiler needs to every possible call doesn't make that much sense, the template inference works only for compile time type recognition and that is all that my sample code I posted used:



import std.stdio;

class A
{
      char[] name;
      this()
      {
            name = "A".dup;
      }
      T max(T)(T a, T b)
      {
            writefln(name ~ "- A.max()");
            return a > b ? a : b;
      }

}

class B : A
{
      this()
      {
            name = "B".dup;
      }
      T max(T)(T a, T b)
      {
            writefln(name ~ "- B.max()");
            return a > b ? a : b;
      }
}


void main()
{
      A b = new B();
      invariant int i = 2;
      invariant int j = 4;
      auto k = b.max(i,j); //invariant int is the only template compiled in

}

This code when run will print: B- A.max()

It is still a "B" but compiler can only see the "A.(T)max(T,T)" being called. What can actually be computed by the compiler is that another member function with the same exact signature exists in one or more subclasses. With this knowledge it can compile the "max" template as it did with "A" for all it's subclasses and insert the runtime type checking to decide which of them to call.

So just to help clarify the template is not instantiated in different ways but the same instantiation is done for each compatible class function.

The example currently compiles in:

A.max(invariant int)()

I am suggesting to compile in:

A.max(invariant int)()
B.max(invariant int)()
//any other subclasses

+ runtime type checking

Tim M wrote:
> Firstly option 2 was just crazy and I don't know why you said that.

Because it's how .NET does it.  Granted, .NET doesn't really have templates; just deferred type erasure.  Still, it's basically the same idea.

.NET has it a lot easier since its binaries include considerable reflection information, plus the standard library has a platform-independent assembler.

> For
> option 1 you identifying the limitations and are just trying to apply as
> many problems as you can though the main barriers can easily be lowered.

That's how I think: it's easy to come up with simple cases where a design works.  The trick is to come up with a design that works even for the complex cases.

> As you already know templates are a compile time feature, so that statement about the compiler needs to every possible call doesn't make that much sense, the template inference works only for compile time type recognition and that is all that my sample code I posted used:
>
> ...
> 
> This code when run will print: B- A.max()
> 
> It is still a "B" but compiler can only see the "A.(T)max(T,T)" being called. What can actually be computed by the compiler is that another member function with the same exact signature exists in one or more subclasses. With this knowledge it can compile the "max" template as it did with "A" for all it's subclasses and insert the runtime type checking to decide which of them to call.

It's somewhat hypocritical to say "the compiler [needing to know] every possible call doesn't make that much sense" and then require the compiler know of every possible subclass of a given class.  It's the same issue, dressed in different clothes and a fake beard.

Avoiding dynamic instantiation, you HAVE to know what template instances are going to be needed at compile time.  You can't wave your hands and make it go away.

> So just to help clarify the template is not instantiated in different
> ways but the same instantiation is done for each compatible class function.
> 
> The example currently compiles in:
> 
> A.max(invariant int)()
> 
> I am suggesting to compile in:
> 
> A.max(invariant int)()
> B.max(invariant int)()
> //any other subclasses
> 
> + runtime type checking

OK: an instance has a pointer to its vtable.  Virtual method resolution
works by assigning each method an offset in this table at compile time.
 When called, the method's slot is found and the method's address is
read out.

So in order to have virtual templated members, you have to stuff the instantiations into the vtable, or something like the vtable, somewhere.

Let's take your example: the compiler knows all subclasses.  This requires all-at-once compiling to be mandated by the language; any given file will depend not only on the modules it directly references, but all modules that subclass any classes it references.  It also means you cannot ever have classes subclassed by an external library, since these will be unavailable at compile time.

You still need to find a vtable for these methods.  Since you don't want to know all function calls, we can't extend the existing vtable because otherwise we can't predict the order in which extra entries will show up.

So let's add a new hidden field for each instance that points to a
hashtable of methods, indexed by mangled template name, for that class.
 The compiler then generates a static ctor that fills in the hashtable
at program startup.  Calling a virtual template member now requires a
hashtable lookup, plus another 4 bytes for every object instance.

Knowing every function invocation isn't much better: the one advantage of that method is that the vtable can be fixed, so we don't need the hashtable any more.

But in either case, I don't think the tradeoff is anywhere near worth it.

The only solution that I think would be acceptable would be the second I mentioned; and that's obviously a tremendous amount of work.

But I could be wrong.  It could be that there's a really easy way of implementing this.  That said, I have no idea what it is, and I've never seen anyone suggest anything feasible.

  -- Daniel

On Sun, 08 Mar 2009 23:12:31 +1300, Daniel Keep <daniel.keep.lists@gmail.com> wrote:


> That's how I think: it's easy to come up with simple cases where a
> design works.  The trick is to come up with a design that works even for
> the complex cases.

What I am suggesting has strong importance without any changes to syntax, or any changes that may brake existing code.

>
> It's somewhat hypocritical to say "the compiler [needing to know] every
> possible call doesn't make that much sense" and then require the
> compiler know of every possible subclass of a given class.

That argument has no validity as non templated functions have been working as virtual for years.

>
> Avoiding dynamic instantiation, you HAVE to know what template instances
> are going to be needed at compile time.  You can't wave your hands and
> make it go away.

I'm not saying guess the template instance. I'm saying use the same exact types for instance in class A to instantiate template in class B where the signature is exactly the same. There is absolutely no guess work as everything is KNOWN.


> OK: an instance has a pointer to its vtable.  Virtual method resolution
> works by assigning each method an offset in this table at compile time.
>  When called, the method's slot is found and the method's address is
> read out.
>
> So in order to have virtual templated members, you have to stuff the
> instantiations into the vtable, or something like the vtable, somewhere.

Don't worry the class won't feel a thing as long as the subclasses are recompiled. This is required for non templated functions anyway but a different subject for another day.

>
> Let's take your example: the compiler knows all subclasses.  This
> requires all-at-once compiling to be mandated by the language; any given
> file will depend not only on the modules it directly references, but all
> modules that subclass any classes it references.  It also means you
> cannot ever have classes subclassed by an external library, since these
> will be unavailable at compile time.

There is really no extra complexities that non template functions already deal with.

PS: .net is in a whole different ball game and is storred in a common intermediate language not source but that kind of a high level is still not required to have a virtual templated function.

On Sun, 08 Mar 2009 06:44:48 +0300, Jason House <jason.james.house@gmail.com> wrote:

> The ugly const thread got me thinking about the old problem of returning an
> input while preserving const safety.  I have an idea that seems
> reasonable...
>
> In a nutshell, I'm thinking that const(T) should be a base type for T,
> immutable(T) and return(T).  return(T) is treated in a read-only fashion,
> just like const(T) and immutable(T). Here are some of the key things I think
> this achieves:
>   * Input arguments are never mutated
>   * Use of input parameters in calls to functions as const(T) is 100% legal.
>   * Temporary variables can legally be defined and used
>   * Calling other functions that return return(T) is allowed
>   * No code duplication
>   * No code bloat (compiler only needs to generate one version of the code)
>   * Functions can be virtual
>
> Let's take a relatively simple example: max
>
> return(T) max(return(T) a, return(T) b){ return (a>b)?a:b; }
>
> When max is called, the compiler would examine the inputs for a and b to
> determine what the true type for return(T) is from the callee's
> perspective...  So a call with T and immutable(T) would use const(T) as the
> perceived return type while an argument of T and T would use T as the return
> type.
>
> At the call site, the compiler would ensure type safety of how the return
> type is used.  Within max, the compiler would ensure that the arguments are
> either treated as const(T) in function calls but not mixed with with types
> T, const(T), or immutable(T)
>
> PS: The return(T) notation is an arbitrary one for the purposes of this
> post.  We need a technical solution before worrying about the color of the
> bicycle shed
>

How about this one?

class Foo {
   T value() {
       return _value;
   }
   T value() const {
       return _value;
   }
}

You suggest turning it into:

return(T) value() {
   return _value;
}

Which is fine but it doesn't say anything about constness of 'this'.

In fact, you propose *exactly* the same thing I've been proposing multiply times in past under a different name, though:

sameconst(T) max(sameconst(T) a, sameconst(T) b) {
   return (a > b) ? a : b;
}

class Foo {
   sameconst(T) value() sameconst(this) { // return value has the same constness as 'this' (mutable, const or immutable)
       return _value;
   }
}

The constness is automatically propogated based on parameters. For example,
- sameconst(T) == T if all the parameters are mutable
- sameconst(T) == immutable(T) if all the parameters are immutable
- sameconst(T) == const(T) otherwise

Tim M wrote:
> On Sun, 08 Mar 2009 23:12:31 +1300, Daniel Keep <daniel.keep.lists@gmail.com> wrote:
>>
>> It's somewhat hypocritical to say "the compiler [needing to know] every possible call doesn't make that much sense" and then require the compiler know of every possible subclass of a given class.
> 
> That argument has no validity as non templated functions have been working as virtual for years.

That doesn't have any bearing on this.

>> Avoiding dynamic instantiation, you HAVE to know what template instances are going to be needed at compile time.  You can't wave your hands and make it go away.
> 
> I'm not saying guess the template instance. I'm saying use the same exact types for instance in class A to instantiate template in class B where the signature is exactly the same. There is absolutely no guess work as everything is KNOWN.

Virtual functions do NOT require the compiler to know about all subclasses.  Subclasses override the entries in the vtable, which only requires the subclass to know about the superclass, not vice versa.

In order to be able to instantiate the template member for B, the compiler MUST KNOW ALL SUBCLASSES OF A.  It cannot know all subclasses of A unless you feed it the entire program at compile time.

It cannot know about subclasses which are loaded at run time.  This means a host application cannot use subclasses in a library, and a library cannot use virtual template members in any class in the host application unless it lucks out and they're compiled.

>> OK: an instance has a pointer to its vtable.  Virtual method resolution
>> works by assigning each method an offset in this table at compile time.
>>  When called, the method's slot is found and the method's address is
>> read out.
>>
>> So in order to have virtual templated members, you have to stuff the instantiations into the vtable, or something like the vtable, somewhere.
> 
> Don't worry the class won't feel a thing as long as the subclasses are recompiled. This is required for non templated functions anyway but a different subject for another day.

Changing a line in an unrelated module does NOT require an entire class hierarchy to be recompiled.

>> Let's take your example: the compiler knows all subclasses.  This requires all-at-once compiling to be mandated by the language; any given file will depend not only on the modules it directly references, but all modules that subclass any classes it references.  It also means you cannot ever have classes subclassed by an external library, since these will be unavailable at compile time.
> 
> There is really no extra complexities that non template functions already deal with.

If you can't see that, yes, there are extra complexities, then there's no point in continuing this thread as we're obviously just talking past each other.

  -- Daniel

On 2009-03-08 06:38:13 -0400, "Tim M" <a@b.com> said:

>> Avoiding dynamic instantiation, you HAVE to know what template instances
>> are going to be needed at compile time.  You can't wave your hands and
>> make it go away.
> 
> I'm not saying guess the template instance. I'm saying use the same exact  types for instance in class A to instantiate template in class B where the  signature is exactly the same. There is absolutely no guess work as  everything is KNOWN.

If you introduce a way to limit templates to what generics can do in Java and C#, you can have virtual template functions. Java and C# generics can do only do a subset of what templates can do, but this ensure there's only one compiled code instanciation. So perhaps non-final non-static member template functions could be constrained to generic-like operations and thus could become virtual.

I remembrer myself proposing this a few months ago, but it didn't caught on.

-- 
Michel Fortin
michel.fortin@michelf.com
http://michelf.com/

Denis Koroskin Wrote:

> On Sun, 08 Mar 2009 06:44:48 +0300, Jason House <jason.james.house@gmail.com> wrote:
> 
> > The ugly const thread got me thinking about the old problem of returning
> > an
> > input while preserving const safety.  I have an idea that seems
> > reasonable...
> >
> > In a nutshell, I'm thinking that const(T) should be a base type for T,
> > immutable(T) and return(T).  return(T) is treated in a read-only fashion,
> > just like const(T) and immutable(T). Here are some of the key things I
> > think
> > this achieves:
> >   * Input arguments are never mutated
> >   * Use of input parameters in calls to functions as const(T) is 100%
> > legal.
> >   * Temporary variables can legally be defined and used
> >   * Calling other functions that return return(T) is allowed
> >   * No code duplication
> >   * No code bloat (compiler only needs to generate one version of the
> > code)
> >   * Functions can be virtual
> >
> > Let's take a relatively simple example: max
> >
> > return(T) max(return(T) a, return(T) b){ return (a>b)?a:b; }
> >
> > When max is called, the compiler would examine the inputs for a and b to
> > determine what the true type for return(T) is from the callee's
> > perspective...  So a call with T and immutable(T) would use const(T) as
> > the
> > perceived return type while an argument of T and T would use T as the
> > return
> > type.
> >
> > At the call site, the compiler would ensure type safety of how the return
> > type is used.  Within max, the compiler would ensure that the arguments
> > are
> > either treated as const(T) in function calls but not mixed with with
> > types
> > T, const(T), or immutable(T)
> >
> > PS: The return(T) notation is an arbitrary one for the purposes of this
> > post.  We need a technical solution before worrying about the color of
> > the
> > bicycle shed
> >
> 
> How about this one?
> 
> class Foo {
>     T value() {
>         return _value;
>     }
>     T value() const {
>         return _value;
>     }
> }

My proposal did not handle that. I wasn't thinking of that case.


> You suggest turning it into:
> 
> return(T) value() {
>     return _value;
> }
> 
> Which is fine but it doesn't say anything about constness of 'this'.
> 
> In fact, you propose *exactly* the same thing I've been proposing multiply times in past under a different name, though:
> 
> sameconst(T) max(sameconst(T) a, sameconst(T) b) {
>     return (a > b) ? a : b;
> }
> 
> class Foo {
>     sameconst(T) value() sameconst(this) { // return value has the same constness as 'this' (mutable, const or immutable)
>         return _value;
>     }
> }
> 
> The constness is automatically propogated based on parameters. For example,
> - sameconst(T) == T if all the parameters are mutable
> - sameconst(T) == immutable(T) if all the parameters are immutable
> - sameconst(T) == const(T) otherwise


I'll take another look at your proposal. I thought of sameconst as a type alias rather than a typedef. I was mostly thinking of how this problem could be handled by the type system.

On Mon, 09 Mar 2009 00:58:14 +1300, Michel Fortin <michel.fortin@michelf.com> wrote:

>
> If you introduce a way to limit templates to what generics can do in Java and C#, you can have virtual template functions. Java and C# generics can do only do a subset of what templates can do, but this ensure there's only one compiled code instanciation. So perhaps non-final non-static member template functions could be constrained to generic-like operations and thus could become virtual.
>
> I remembrer myself proposing this a few months ago, but it didn't caught on.
>



I remember you blogging about a way of compiling base classes with new methods and not needing to recompile the sub classes, I will read up on those genrics in C# and java later. If that doesn't work out, what if the compiler could check for all sub class functions within the same module and allowing a sort of limited virtual template functions, so no work through external libraries. I would prefer limited virtual over no virtual.

Tim M wrote:
> On Sun, 08 Mar 2009 20:12:20 +1300, Daniel Keep <daniel.keep.lists@gmail.com> wrote:
> 
>>
>> One issue with this is that template functions can't be virtual.
>>
>> You can work around it, but it's really putting barriers up to easy use
>> of the new const system, which I think is a bad thing.
>>
>>   -- Daniel
> 
> I'd rather have virtual template functions, even if it means I have to re-compile all subclasses when the vtbls get modified. Is there any technicality causing it to be impossible to implement or just something rather tricky?

You can have virtual template functions, but you have to compile your entire application and all its libraries at once, or record the instantiated virtual template functions somewhere and handle all affected classes in a different phase of compilation.

If Walter merely forbid creating object files, it would be relatively easy. It'd be a much larger change if you wanted to support compiling files one at a time or creating libraries. Still possible, though.