Possible solution to template bloat problem?

[John Colvin]

On Tuesday, 20 August 2013 at 17:59:35 UTC, H. S. Teoh wrote:
> On Tue, Aug 20, 2013 at 07:18:50PM +0200, Ramon wrote:
>> On Tuesday, 20 August 2013 at 17:05:21 UTC, Dicebot wrote:
>> >On Tuesday, 20 August 2013 at 16:59:00 UTC, Ramon wrote:
>> >>I'm afraid the issue is bigger.
>> >
>> >Your insight about variety of modern programming language
>> >applications is extremely limited. If you are willing to 
>> >introduce
>> >random runtime costs for nothing, there are lot of other 
>> >awesome
>> >languages that can satisfy your needs.
>> >
>> >As someone who does not want to write embedded'ish code in C
>> >anymore (and hopes to drag D there eventually) I am 
>> >dangerously
>> >close to hating you.
>> 
>> And that shows. Well, if that fits your definition of
>> "professional", so be it.
>> 
>> To avoid misunderstandings: I still like D and think that it's 
>> a
>> great language/solution. I still see very attractive points. I 
>> still
>> think that even templates can be attractive and are way better 
>> done
>> in D than in C++.
>> 
>> I just don't agree that writing "generics" in the brochure and
>> actually delivering templates is a good thing. And I happen to 
>> think
>> that real generics are a very good thing.
> [...]
>
> I think the problem is that your definition of "generic" is not 
> the same
> as ours. :)
>
> Templates actually include your definition of generics if you 
> use it
> correctly. Here's an example:
>
> 	interface LessThanComparable {
> 		bool opCmp(LessThanComparable b);
> 	}
>
> 	interface LessThanComparableRange {
> 		@property bool empty();
> 		@property LessThanComparable front();
> 		void popFront();
> 	}
>
> 	void sortRange(LessThanComparableRange range) {
> 		// Note: single template instantiation of sort here
> 		std.algorithm.sort(range);
> 	}
>
> 	class MyClass : LessThanComparable {
> 		override bool opCmp(LessThanComparable b) { ... }
> 		...
> 	}
>
> 	class MyClassRange : LessThanComparableRange {
> 		override @property bool empty() { ... }
> 		override @property LessThanComparable front() { ... }
> 		override void popFront() { ... }
> 	}
>
> 	class MyOtherClass : LessThanComparable {
> 		override bool opCmp(LessThanComparable b) { ... }
> 		...
> 	}
>
> 	class MyOtherClassRange : LessThanComparableRange {
> 		override @property bool empty() { ... }
> 		override @property LessThanComparable front() { ... }
> 		override void popFront() { ... }
> 	}
>
> 	void main() {
> 		MyClassRange firstRange = ...;
> 		MyOtherClassRange secondRange = ...;
> 		...
> 		sortRange(firstRange);
> 		sortRange(secondRange);
> 	}
>
> A few notes:
>
> - LessThanComparable lets you do polymorphism at runtime, so 
> sortRange
>   is a non-template "real generic" function that can sort any 
> range
>   involving LessThanComparable.
>
> - LessThanComparableRange provides a single ABI for any range of
>   LessThanComparable elements.
>
> - sortRange instantiates the template function 
> std.algorithm.sort
>   exactly *once*, and it will work with any runtime type that 
> implements
>   LessThanComparableRange.
>
> - The rest of the code shows how you can define a bunch of 
> classes that
>   implement these interfaces, and they can be used with the 
> sortRange
>   function with full runtime polymorphism.
>
> You will note that there's some amount of boilerplate here -- 
> because I
> just typed this up off the top of my head for illustration 
> purposes; in
> real code you'd use mixins or other such stuff, perhaps *cough* 
> use a
> template for generating all the xxxRange classes *cough* 
> automatically.
>
> So this lets you have "real generics" which, as you can see, is 
> really
> just a subset of what is covered by the template 
> std.algorithm.sort,
> which can handle *any* concrete type, even those that don't 
> implement
> any runtime polymorphic interfaces.
>
> Now let's talk about about how templates and "real generics" 
> can work
> together.
>
> If you think about the above code carefully, you will realize 
> that, at
> the machine level, you cannot avoid the overhead of 
> dereferencing
> pointers to the various interfaces and class vtables, because 
> the CPU
> can only deal with concrete types, it doesn't know how to work 
> with data
> that can be any type. So, at *some* level, whether visible at 
> the code
> level or not, everything must be translated down to 
> type-specific code
> that the CPU can actually run. In "real generics", this is 
> accomplished
> by having a single ABI (the interfaces LessThanComparable and
> LessThanComparableRange) that all concrete types must 
> implement. Once
> implemented, the sortRange function doesn't have to deal with 
> concrete
> types anymore: it can express the sorting algorithm directly in 
> terms of
> the interfaces, and when a concrete operation like '<' is 
> desired, it
> invokes LessThanComparable's opCmp method to accomplish it. 
> (Which, in
> turn, essentially dereferences a function pointer that points 
> to the
> actual machine code that does the comparison of the concrete 
> type.)
>
> This, of course, has a lot of runtime costs: you need space to 
> store the
> vtables, you need to initialize the pointers to these vtables 
> every time
> you create a new instance of a class, it requires runtime 
> overhead for
> calling a function via a function pointer instead of directly, 
> etc.. The
> advantage, though, is that it allows sortRange to be "real 
> generic", in
> the sense that you can load up a dynamic library at runtime 
> that returns
> a range of elements of unknown type, and sortRange will be able 
> to sort
> it just by using the LessThanComparable* interfaces.
>
> Now let's think about the template version of sortRange, which 
> is just
> std.algorithm.sort. Here, the binding to the concrete type 
> happens at
> compile-time; rather than produce a single machine code for 
> sortRange
> that handles polymorphism via indirection (interfaces, function
> pointers, etc.), the template produces code that sorts a range 
> of a
> *specific* type. Since we know exactly what concrete types 
> we're dealing
> with, we don't need any of the indirections of the "real 
> generic"
> approach; the compiler's optimizer can take advantage of 
> characteristics
> of the concrete type to produce the most optimized machine code 
> for
> sorting ranges of that kind. Each instantiation of 
> std.algorithm.sort
> produces optimal machine code for sorting that particular 
> range, because
> all the bindings to the concrete type is done at compile-time 
> rather
> than runtime. This gives you the top performance.
>
> Of course, in programming, nothing comes for free; so the price 
> for this
> top performance is that you need to produce many copies of the 
> sort
> function -- one for each type of range, each optimized for that
> particular type of range. And on the surface, it would appear 
> that it
> would be unable to handle runtime polymorphism either, because 
> the
> template must be bound to the concrete types at compile-time. 
> Right?
>
> Actually, this is where the power of templates is shown: in the 
> example
> code I gave above, I deliberately implemented sortRange with
> std.algorithm.sort. But actually, the way I wrote it is kind of
> unnecessary, because std.algorithm.sort can be instantiated 
> *directly*
> with LessThanComparableRange! So actually, we don't even need 
> sortRange
> at all -- we can just call std.algorithm.sort directly on our 
> "real
> generic" containers, and the compiler will produce a "real 
> generic"
> version of sort that has all the runtime indirections that I 
> described
> above, for handling runtime polymorphic objects, 
> dynamically-loaded
> objects, etc..
>
> Armed with this insight, we can now see that we can actually 
> have the
> best of both worlds: if we already know the concrete types at
> compile-time, the template system optimizes the sort function at
> compile-time to deal specifically with that concrete type -- 
> you get
> optimal performance. But if we don't know the concrete type at
> compile-time, we create an interface to be implemented by future
> concrete types (say by a 3rd party vendor), and the template 
> system
> produces a "real generic" version of sort that can handle 
> runtime
> polymorphism.
>
> IOW, the templating system *includes* what you describe as "real
> generics"; it is not inferior to it at all! In fact, the 
> templating
> system can do what "real generics" can't: produce optimal code 
> for a
> specific type without needing to copy-n-paste code (either 
> manually or
> with an IDE or whatever). It's the *compiler* that instantiates 
> the
> template with the concrete type, so it has access to all the 
> specific
> implementation details of said concrete type which it can use 
> to produce
> the best machine code for it -- automatically.
>
>
> T

Yet again, D proves to be a powerful enough language to not need 
extra language extensions to support a wide variety of paradigms.

We should have some template mixins for this stuff in 
std.patterns or something.