www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - How does D's templated functions implementation differ from generics

reply aberba <karabutaworld gmail.com> writes:
Syntactically they look the same (although D's can do more 
things) so I'm trying to understand how why in D it's called 



I guess I have fair understanding of D's code generation but 
isn't it same as what what is available in those languages too? 
How are the implementation different?
Aug 07 2020
next sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Fri, Aug 07, 2020 at 09:03:47PM +0000, aberba via Digitalmars-d-learn wrote:

 Syntactically they look the same (although D's can do more things) so
 I'm trying to understand how why in D it's called template but in

 
 I guess I have fair understanding of D's code generation but isn't it
 same as what what is available in those languages too? How are the
 implementation different?


They are *very* different.

Java generics are based on "type erasure", i.e., at the syntactic level,
containers are parametrized with the element types, but at the
implementation level, the element types are merely "erased" and replaced
with Object (a top type of sorts). There is only one container
instantiation, which is shared across all parametrizations.  I don't
know exactly why this approach was chosen, but my guess is, to avoid the
complexities associated with templates (esp. as seen in C++, which was
the prevailing language with type parametrization when Java generics was
being designed), and to avoid template bloat.  But because of how this
implementation works, Java generics are very limited in a lot of ways
that make them feel straitjacketed once you've gotten used to a more
powerful template system like in C++ or especially D. Since the
container does not retain any information about the type parameter, you
cannot perform any type-specific operations on elements (unless you do
runtime introspection -- and I'm not even sure Java lets you do this),
and you cannot make compile-time decisions based on type properties --
because the single container implementation must be able to handle all
type arguments.

D templates do not type-erase, and the generated code retains full
knowledge about the type parameters. Therefore, you can do very powerful
things with them, like Design by Introspection, performing type-specific
operations, generate different code depending on type properties, etc..
Since each template instantiation is distinct, it has the flexibility of
doing completely different things depending on the type arguments,
independently of any other instantiation of the same template.
Furthermore, it can dispatch to a type-erased implementation ala Java --
at your choice; and it can even conditionally do so by inspecting the
properties of the type arguments. IOW, it is a strict superset of Java
generics.

Unfortunately, the power of D templates does come at a cost: if used
carelessly, it can result in a lot of template bloat. Reducing this
bloat often requires delicate code surgery or restriction on some of the
flexibility. (Though IMO, this is not a bad thing -- the user is given
the *choice* to use a type-erased implementation if he so chooses, or
control the template bloat in other ways; in Java, you have no choice
but to live with the limitations of a type-erased generics system. But
then again, Java has always been a bondage-and-discipline kind of
language, so this isn't anything unexpected. People just learn to live
with it.)


T

-- 
Time flies like an arrow. Fruit flies like a banana.
Aug 07 2020
next sibling parent reply jmh530 <john.michael.hall gmail.com> writes:
On Friday, 7 August 2020 at 21:39:44 UTC, H. S. Teoh wrote:

 [snip]


"Furthermore, it can dispatch to a type-erased implementation ala 
Java -- at your choice;"

This is interesting. Would you just cast to Object?
Aug 07 2020
parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Sat, Aug 08, 2020 at 01:47:27AM +0000, jmh530 via Digitalmars-d-learn wrote:

 On Friday, 7 August 2020 at 21:39:44 UTC, H. S. Teoh wrote:

 [snip]


 
 "Furthermore, it can dispatch to a type-erased implementation ala Java
 -- at your choice;"
 
 This is interesting. Would you just cast to Object?


You could. Or you could introspect a type and dispatch a subset of types
to a type-erased implementation, say under some base class of your
choice or something. Or even something else altogether, like a C-style
void*-based implementation.

Or a hybrid, like this:

	class ContainerBase {
		class Node {
			Node next, prev;
			... // generic methods independent of element type
		}
		...
	}

	class Container(T) : ContainerBase {
		class Node : ContainerBase.Node {
			T payload;
			... // T-specific methods
		}
		...
	}

The code in ContainerBase deals with the element-independent part of the
container, essentially the type-erased component, whereas Container!T
retains type information for working with type-specific operations.
Result: reduced template bloat like Java generics, yet without giving up
the advantages of retaining element type information.

You couldn't do such a thing in Java, because Java-style generics simply
aren't powerful enough.


T

-- 
Truth, Sir, is a cow which will give [skeptics] no more milk, and so they are
gone to milk the bull. -- Sam. Johnson
Aug 07 2020
prev sibling parent Jacob Carlborg <doob me.com> writes:
On 2020-08-07 23:39, H. S. Teoh wrote:


 They are *very* different.
 
 Java generics are based on "type erasure", i.e., at the syntactic level,
 containers are parametrized with the element types, but at the
 implementation level, the element types are merely "erased" and replaced
 with Object (a top type of sorts). There is only one container
 instantiation, which is shared across all parametrizations.  I don't
 know exactly why this approach was chosen


I'm guessing a strong reason was to be backwards compatible with earlier 
versions of Java.

The type erasure is also most likely the reason why Java generic types 
don't accept primitive types. They need to be boxed, i.e. `int` need to 
be wrapped in an object of type `Integer`.

-- 
/Jacob Carlborg
Aug 08 2020
prev sibling next sibling parent Adam D. Ruppe <destructionator gmail.com> writes:
On Friday, 7 August 2020 at 21:03:47 UTC, aberba wrote:

 Syntactically they look the same (although D's can do more 
 things) so I'm trying to understand how why in D it's called 



In D, a copy of the function is created for each new template 

sure), there's just one copy of the function and the types are 
erased to call it.

So let's take a D template `sort(T)(T list)`. The compiler 
generates nothing until you pass it arguments; it is just a 
template in its memory. Pass it int[] and it generates a whole 
new function sort(int[] list). Pass it float[] and it generates 
another, totally separate function sort(float[] list).

Now, take a Java generic function `sort(List<T> list)`. The 
compiler will generate a function `sort(List list)`. Pass it a 
List<Integer> and the compiler actually will just cast it back to 
the List interface and pass it into the one function it already 
generated; this creates no new code. At runtime, you cannot tell 
it was a List<Integer>, only the compiler knew that*.

Pass it a List<Float> and again, the compiler will just cast it 
back to the interface and give it to the same `sort(List list)` 
function. The actual generic type is known only to the Java 
compiler and at runtime it is basically a bunch of hidden casts 
to make it work.

* the java runtime is free to optimize a bit more based on usage 
with its jit compiler but that doesn't change much in the concept.

you can read some more here 
https://en.wikipedia.org/wiki/Generics_in_Java#Problems_with_type_erasure

A cool thing with Java's thing though is since they are just 
special kinds of interface methods you can access generics 
through runtime reflection in it, whereas D's templates cease to 
exist at runtime. Only the generated instances of them are around 
by then since the template itself only lives in the compiler's 
memory for it to make copies of to generate instances.
Aug 07 2020
prev sibling next sibling parent Jacob Carlborg <doob me.com> writes:
On 2020-08-07 23:03, aberba wrote:

 Syntactically they look the same (although D's can do more things) so 
 I'm trying to understand how why in D it's called template but in 

 
 
 I guess I have fair understanding of D's code generation but isn't it 
 same as what what is available in those languages too? How are the 
 implementation different?


Objective-C recently added support for generics. It uses the same 
approach as Java, type erasure. Basically the only reason why this was 
added is to make the Swift APIs better and more type safe.

Swift also has quite an interesting implementation of generics. IIRC 
correctly it supports both a more Java like implementation where you 
only get one instantiation and a more D/C++ like implementation where 
the compiler generates one instantiation per type.

This is supposed to give the best of both worlds. Little binary bloat 
and high performance.

-- 
/Jacob Carlborg
Aug 08 2020
prev sibling parent 12345swordy <alexanderheistermann gmail.com> writes:
On Friday, 7 August 2020 at 21:03:47 UTC, aberba wrote:

 Syntactically they look the same (although D's can do more 
 things) so I'm trying to understand how why in D it's called 



 I guess I have fair understanding of D's code generation but 
 isn't it same as what what is available in those languages too? 
 How are the implementation different?


I think this is relevent:
https://github.com/dotnet/csharplang/issues/110
Aug 08 2020