www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Example code: Expression templates in D

reply Norbert Nemec <Norbert Nemec-online.de> writes:
Content-Type: text/plain; charset=iso-8859-15
Content-Transfer-Encoding: 8Bit

Hi there,

triggered by a message from Walter about implicit function template
instantiation, I just sat down and wrote some example code for expression
templates in D. The result is attached.

Short summary: expression template programming is not yet possible in D.
Many details show that the template mechanism in general is very promising
compared to the C++, but implicit function template instantiation is such a
crucial feature for ET that the whole attempt is doomed.

====================================================================== 

For those not acquainted with the expression template technique:

The idea is to handle expressions at compile time in such a way that, p.e.
array operations can be done in a very efficient way without need for
temporary copies.

Traditionally, when implementing an array class, you would do

-----------------
struct array {
 float[] data;

 [...]

 array opAdd(array other) {
  array res;
  res.data = new float[SIZE];
  for(int i=0;i<SIZE;i++)
   res.data[i] = (*this).data[i] + other.data[i];
  return res;
 }

 [...]
}
-----------------

This is as simple as inefficient: Doing 
 a = b+c+d+e
with all quantities being arrays means that you create four temporary arrays
on the heap. It is much more efficient to write an explicit loop by hand.

The expression template technique in C++ allows to write a library that
transforms the above expression into such an efficient loop at compile
time.

=================================================================

The attached code is a first attempt to do the same thing in D. Unless
somebody can point me to completely new ideas solving my problems, this
first crude attempt shows two distinct points:

-----------
* without implicit function template instantiation, D is no powerful enough,
yet to allow writing such a library in any sensible manner.

-----------
* structs in D show several deficiencies:

- structs should be able to have real constructors. The 'static opCall'
trick is a nice hack but not a solution. In this case, the struct carries a
reference to a dynamic array which need to be initialized. This is not
possible by either 'static opCall' or static initializers.

- opAssign is badly needed for structs. Lacking any mechanism for
overloading implicit casting, at least assignment should be overloadable.
Maybe assignment from an identical type should still be restricted to the
default plain-copying. But for assignment between different types, opAssign
should be possible

- opCast is a toy but not a solution. For one, it should apply to implicit
casting as well, for the other, it needs to be selective of the destination
type.

Maybe a powerful implicit casting mechanism would relieve the need of
opAssign. Anyway: opCast can always only describe casting *to* a type,
never *from* it, so extensibility of existing code is restriced if only the
former can be overloaded.
===============================
For the moment, I'll leave it at this. There certainly is enough to swallow
and discuss so far...

Ciao,
Norbert
Jan 30 2005
next sibling parent reply Stewart Gordon <smjg_1998 yahoo.com> writes:
Norbert Nemec wrote:
<snip>
 Traditionally, when implementing an array class, you would do

 This is as simple as inefficient: Doing 
  a = b+c+d+e
 with all quantities being arrays means that you create four temporary arrays 
 on the heap.

Actually, there are only three temporary arrays in this case - the fourth becomes the new referent of a.
 It is much more efficient to write an explicit loop by hand.

When we finally get array operations, presumably the compiler will optimise the temporaries away to this level. Of course, if function calls are involved then this might be harder....
 The expression template technique in C++ allows to write a library that 
 transforms the above expression into such an efficient loop at compile 
 time.

A nice idea. Maybe the underlying implementation of array operations could make use of this. Of course, don't forget multiplication, negation and others, not to mention operations of an array with a scalar. I *guess* the extension to these is fairly straightforward.... <snip>
 - opCast is a toy but not a solution. For one, it should apply to implicit 
 casting as well, for the other, it needs to be selective of the destination 
 type.

I imagine that it was a conscious decision not to have programmer-defined implicit casting, in order to avoid the complication of both implementing it and understanding some more complex expressions. But your second point here remains perfectly valid. Stewart. -- My e-mail is valid but not my primary mailbox. Please keep replies on the 'group where everyone may benefit.
Jan 31 2005
parent reply Norbert Nemec <Norbert Nemec-online.de> writes:
Stewart Gordon wrote:

 Norbert Nemec wrote:
 <snip>
 Traditionally, when implementing an array class, you would do

 This is as simple as inefficient: Doing
  a = b+c+d+e
 with all quantities being arrays means that you create four temporary
 arrays on the heap.

Actually, there are only three temporary arrays in this case - the fourth becomes the new referent of a.

Correct: three temporaries, since opAdd is called three times.
 It is much more efficient to write an explicit loop by hand.

When we finally get array operations, presumably the compiler will optimise the temporaries away to this level.

This is yet another subject. True - once we have array operations as part of the language, the need for an array class is lifted. Anyhow: arrays are just one of many uses of expression templates. Take a look at the boost++ library and you will find many more. I believe both are needed in D: array/vector-operations as well as the possibility for expression template programming. B.t.w: I still believe that array operations as they are currently described in the specs are ill-defined and not implementable. We had the topic a while ago and I'll probably pick it up again sometimes in the future. For now, I think array operations should be purged from the specs and picked up again after 1.0 is out of the door.
 The expression template technique in C++ allows to write a library that
 transforms the above expression into such an efficient loop at compile
 time.

A nice idea. Maybe the underlying implementation of array operations could make use of this.

Array operations as part of the language are a completely different subject. Havint the compiler to computations at compile time is nothing exciting. The key of expression templates is, that these compile-time computations are specified in the library.
 I imagine that it was a conscious decision not to have
 programmer-defined implicit casting, in order to avoid the complication
 of both implementing it and understanding some more complex expressions.
   But your second point here remains perfectly valid.

Same thing as for implicit function template instantiations. Of course, the language becomes simpler to define and implement if the programmer has to do things explicitely. It is just that it prohibits certain programming styles. The key point of expression template programming is, that types are recursive structures of templates. The compiler can easily handle such a tree. Having to write any of these types explicitely in the program code is extremely nasty. I'm pretty sure that Walter did this kind of decisions intentionally. I just don't think he considered expression template programming when he did so.
Jan 31 2005
parent reply Stewart Gordon <smjg_1998 yahoo.com> writes:
Norbert Nemec wrote:
 Stewart Gordon wrote:
 
 Norbert Nemec wrote: <snip>
 
 Traditionally, when implementing an array class, you would do

<snip code snippet>
 This is as simple as inefficient: Doing
 a = b+c+d+e 
 with all quantities being arrays means that you create four 
 temporary arrays on the heap.

Actually, there are only three temporary arrays in this case - the fourth becomes the new referent of a.

Correct: three temporaries, since opAdd is called three times.

Oops, miscounted again. There are only two temporaries - b+c and b+c+d (assuming LTR evaluation, which isn't guaranteed). OTOH, b+c+d+e is a permanent since it is assigned to a by reference.
 It is much more efficient to write an explicit loop by hand.

When we finally get array operations, presumably the compiler will optimise the temporaries away to this level.

This is yet another subject. True - once we have array operations as part of the language, the need for an array class is lifted.

We already do. We just don't have it as part of the compiler.
 Anyhow: arrays are just one of many uses of expression templates. 
 Take a look at the boost++ library and you will find many more. I 
 believe both are needed in D: array/vector-operations as well as the 
 possibility for expression template programming.
 
 B.t.w: I still believe that array operations as they are currently 
 described in the specs are ill-defined and not implementable. We had 
 the topic a while ago and I'll probably pick it up again sometimes in 
 the future. For now, I think array operations should be purged from 
 the specs and picked up again after 1.0 is out of the door.

What would be the point of that? Moreover, if this were to happen, should "Numerical programmers" be removed from the "Who D is for" list? Stewart. -- My e-mail is valid but not my primary mailbox. Please keep replies on the 'group where everyone may benefit.
Jan 31 2005
parent reply Norbert Nemec <Norbert Nemec-online.de> writes:
Stewart Gordon wrote:
 It is much more efficient to write an explicit loop by hand.

When we finally get array operations, presumably the compiler will optimise the temporaries away to this level.

This is yet another subject. True - once we have array operations as part of the language, the need for an array class is lifted.

We already do. We just don't have it as part of the compiler.

See the point below. I don't consider the current specification of array operations well-defined. Proving this point is impossible since the wording is too unclear to really understand what is meant. Unless somebody proves me wrong by producing a working implementation (thereby demonstrating what the words in the specs mean exactly) I consider that section of the specs as non-existant.
 B.t.w: I still believe that array operations as they are currently
 described in the specs are ill-defined and not implementable. We had
 the topic a while ago and I'll probably pick it up again sometimes in
 the future. For now, I think array operations should be purged from
 the specs and picked up again after 1.0 is out of the door.

What would be the point of that? Moreover, if this were to happen, should "Numerical programmers" be removed from the "Who D is for" list?

I am a numerical programmer as well - otherwise I would not rant so much about numerical issues. I think that D has great potential as a numeric language in the future, but currently, numerical programmers are still better of using other languages. (Of course - depending on the kind of work you do: if you need neither top performance nor special libraries, D has everything you need already and many benefits in areas outside of numerics as well.) I personally cannot use D yet for my work, but I have the hope that it will one day have everything needed to reach surpass Fortran and C++. I particular, I believe that powerful multidimensional arrays as part of the language are essential for numerical work. Walter has clearly stated that these will have to wait for 2.0 so at this point, detailed discussion about them is moot. The array operations as they are specified are not very powerful, cannot be extended and do not fit well with multidimensional arrays. I have some idea about how it could be solved differently, but over the past months, I never found the time to really work it out and write it down completely. Currently, the issue does not seem of general interest, but if people start discussing these issues again, I will certainly join in and maybe we'll arrive at some results that can then be implemented whenever Walter decides to do so. Ciao, Norbert
Jan 31 2005
parent reply pragma <pragma_member pathlink.com> writes:
In article <ctlugk$1cqa$1 digitaldaemon.com>, Norbert Nemec says...
Currently, the issue does not seem of general interest, but if people start
discussing these issues again, I will certainly join in and maybe we'll
arrive at some results that can then be implemented whenever Walter decides
to do so.

I fully acknowledge that I am a complete idiot when it comes to "numerics programming". From posts that you, and others, have written on the topic, I find myself on top of a conceptual iceberg. I'm curious about the topic, so I'm doing my best to educate myself enough to understand where D comes up short. So far, I haven't a clue what's beneath the water. So far, all I gather is that D lacks a certain kind of expressiveness, and that mere compiler optimizations, GC and array slicing aren't enough to get the critical performance needed for certain tasks. Is this correct? Are there any resources you reccmomend that I could read so I can be more informed? I don't speak for everyone here, but perhaps the lack of interest in the topic really comes from a general lack of understanding of the problem at hand (and hence its importance for folks like yourself). At least, that's still my situation. I'm not at all disinterested, I just don't know enough to contribute helpfully. - EricAnderton at yahoo
Jan 31 2005
next sibling parent "Ivan Senji" <ivan.senji public.srce.hr> writes:
"pragma" <pragma_member pathlink.com> wrote in message
news:ctm2se$1ie6$1 digitaldaemon.com...
 In article <ctlugk$1cqa$1 digitaldaemon.com>, Norbert Nemec says...
Currently, the issue does not seem of general interest, but if people


discussing these issues again, I will certainly join in and maybe we'll
arrive at some results that can then be implemented whenever Walter


to do so.

I fully acknowledge that I am a complete idiot when it comes to "numerics programming". From posts that you, and others, have written on the topic,

 find myself on top of a conceptual iceberg.  I'm curious about the topic,

 doing my best to educate myself enough to understand where D comes up

 far, I haven't a clue what's beneath the water.

 So far, all I gather is that D lacks a certain kind of expressiveness, and

 mere compiler optimizations, GC and array slicing aren't enough to get the
 critical performance needed for certain tasks.  Is this correct?  Are

 resources you reccmomend that I could read so I can be more informed?

 I don't speak for everyone here, but perhaps the lack of interest in the

 really comes from a general lack of understanding of the problem at hand

 hence its importance for folks like yourself).  At least, that's still my
 situation.  I'm not at all disinterested, I just don't know enough to

 helpfully.

It is the same with me. Don't know much about the topic, but realize that it is important and am interested in discussions about it, but will spend more time reading the discussions than writing.
 - EricAnderton at yahoo

Jan 31 2005
prev sibling next sibling parent "Carlos Santander B." <csantander619 gmail.com> writes:
pragma wrote:
 I fully acknowledge that I am a complete idiot when it comes to "numerics
 programming".  From posts that you, and others, have written on the topic, I
 find myself on top of a conceptual iceberg.  I'm curious about the topic, so
I'm
 doing my best to educate myself enough to understand where D comes up short. So
 far, I haven't a clue what's beneath the water.
 
 So far, all I gather is that D lacks a certain kind of expressiveness, and that
 mere compiler optimizations, GC and array slicing aren't enough to get the
 critical performance needed for certain tasks.  Is this correct?  Are there any
 resources you reccmomend that I could read so I can be more informed?

I'm kinda in the same page, but I wouldn't say I can see the whole top of the iceberg :D.
 
 I don't speak for everyone here, but perhaps the lack of interest in the topic
 really comes from a general lack of understanding of the problem at hand (and
 hence its importance for folks like yourself).  At least, that's still my
 situation.  I'm not at all disinterested, I just don't know enough to
contribute
 helpfully.

Maybe D hasn't drawn that much attention from the numerical community.
 - EricAnderton at yahoo

_______________________ Carlos Santander Bernal
Jan 31 2005
prev sibling parent reply Norbert Nemec <Norbert Nemec-online.de> writes:
pragma wrote:

 I fully acknowledge that I am a complete idiot when it comes to "numerics
 programming".

Thanks for your honesty. Actually two years ago I would have had to say the same, but I probably would not even have realized how little I knew. Since then I worked two years on numerics for my diploma and now PhD thesis. It took me some time to realize, that in high-performance numerics you have to worry about completely other issues than in other fields of programming. Generally, I see two major areas of interest for high-performance numerics where D has the potential of surpassing all existing general purpose languages. Neither of them stands in contrast with the philosophy of being a "general purpose" language. Actually, I believe, if these issues are dealt with correctly, many other areas of programming might benefit as well: ----------------- 1) defining the language in a way that a compiler can efficiently optimize 2) support meta-programming as much as possible to allow writing libraries that do intelligent decisions on the code that should be created. Point 1) leads to multidimensional arrays and vectorized expressions. In modern architectures, the performance of the code depends crucially on the order of the individual machine code operations. Modern processors are pipelined, do branch prediction, have sophisticated command set expansions to deal with vectorized data (MMD extensions, etc.) and have several levels of cache. In a language like C or Fortran 77, the programmer pretty much specifies one command after the other what the program should do: for(int i=0;i<MAX_I;i++) for(int j=0;j<MAX_J;j++) A[i][j] = B[i][j]+C[i][j]; An intelligent compiler might be able to swap the order of some commands, but it is very often not easy to decide whether the order can really safe be changed without changing the overall semantics. Other languages (Fortran 95 and others) allow vectorized expressions: A = B + C; similar to the Array Operations described in the D specs. Here, the order of execution is not specified. The compiler is free to pick one. For more complicated expressions, the compiler might not be able to verify whether the result depends on the order, but still, the programmer using such an expression explicitely allows the compiler to choose the order of execution. It is the responsibility of the programmer to make sure that the order does not matter, but the whole syntax already makes this clear. Inlike the for statements in C, the syntax of vectorized expressions should be done in a way that the programmer does not even specify any order of the single expressions, so he should have little reason to believe that the compiler will stick to any order. Understanding the issues of vectorized programming, it might be an idea to read a bit about the design issues of Fortran 95 (or its predecessor High Performance Fortran) As I said, I believe that Array Operations in D are ill defined, but that is a matter I will probably bring up again another time. -------------- Point 2) is about expression templates. This is a technique only recently developed in C++. Instead of trying to explain it here, I'll just give a few links: Blitz++ - a high-performance library based on expression templates in C++: http://www.oonumerics.org/blitz/ Of special interest: several papers describing the background: http://www.oonumerics.org/blitz/papers/ Boost++ - A huge project making heavy use of advanced C++ techniques http://www.boost.org/ uBlas - A subproject of boost++, dealing with numerics http://www.boost.org/libs/numeric/ublas/doc/index.htm There are several links starting at these pages. Just go through them. A general remark: In C++, expression templates were only recently discovered and exploited. The language was not really designed for them, so it is rather complicated to design a library and use it. For that reason, only a small number of experts deal with them. For D, on the other hand, I think there could be a much greater future for them, since the template system is designed a lot cleaner. It is not complete yet to support the full power of C++ templates, but once this is done, expression templates will hopefully be much easier to use than in C++. So far for now, I have to leave. If there is interested in more discussion on the topic, I'll be happy to join in. Ciao, Norbert
Feb 01 2005
parent pragma <pragma_member pathlink.com> writes:
In article <ctokv8$13pt$1 digitaldaemon.com>, Norbert Nemec says...
...
As I said, I believe that Array Operations in D are ill defined, but that is
a matter I will probably bring up again another time.
...
Point 2) is about expression templates. This is a technique only recently
developed in C++. Instead of trying to explain it here, I'll just give a
few links:

Thank you for the kind words and the informative response! I've spent the last hour or two delving into expression templates and I cannot believe my eyes. I now understand how D's lack of template argument deduction and implicit instancing stand directly in the way of implementing expression templates. From what I gather the tenents of Expression Templates read like an extreme programming contest: - Create a math library that supports all the major math expressions (log,sin,etc) by using templates. - Use solutions that do not copy or duplicate any term of an expression. Any solution should be as close to hand-coded as possible, while being machine generated. - The library should automatically unroll small loops and avoid needless iteration. - String parsers are not allowed. The result is that adding three matricies in a single line (d = a + b + c) should create no temporaries and only one loop. I also now understand a (much, much) older post regarding aliasing, and how implementing the 'restrict' keyword in D would assist the compiler in making optimizations akin to Fortran (non-pointable vars = easier to optimize). I think I'm starting to see the light. I've particularily found anything by Todd Veldhuizen to be particularily digestable, not to mention, packed with code rather than mathematical expressions. To that end, *anyone* interested in the topic should read the following: http://osl.iu.edu/~tveldhui/papers/Expression-Templates/exprtmpl.html It explains the topic blow-by-blow using how ET supports math, rather than how math is mapped to ET. - EricAnderton at yahoo
Feb 01 2005
prev sibling next sibling parent reply "Ben Hinkle" <bhinkle mathworks.com> writes:
"Norbert Nemec" <Norbert Nemec-online.de> wrote in message 
news:ctj46q$f52$1 digitaldaemon.com...
 Hi there,

 triggered by a message from Walter about implicit function template
 instantiation, I just sat down and wrote some example code for expression
 templates in D. The result is attached.

 Short summary: expression template programming is not yet possible in D.
 Many details show that the template mechanism in general is very promising
 compared to the C++, but implicit function template instantiation is such 
 a
 crucial feature for ET that the whole attempt is doomed.

I haven't looked at the details of your code but it reminds me of a similar task I faced when writing the D wrappers around the GMP library (GMP is a C library for performing arithmentic on arbitrary precision floating point and arbitrary size ints). It was similar because I wanted to support opAdd and opMul and friends and I also had data on the heap with these potentially large ints and floats. So what I ended up doing was make a decision that the interface use a free list to recycle temporary values. The impact of this is that the interface is single threaded (by default - users can maintain their own object pools if they want) and that the user has to do a little work to make sure they play nicely with the interface. The benefit is that the code (the library code and the user code) is very simple and any error message you get are easy to debug. There is very little magic. Plus when I ran the D version vs the C++ expression template version for some random computation like for( int k=0; k< 10000; k++) assign(x, x*x - 2*(x+1) ); the D version was *faster* than the C++ version by a large amount (3.2 sec vs 2.7 sec). That could be specific for the GMP C++ expression templates - I don't know if my experience generalizes to other expression template libraries. For more details about the interface the link to the GMP D wrapper is http://home.comcast.net/~benhinkle/gmp-d/ -Ben
Jan 31 2005
parent Norbert Nemec <Norbert Nemec-online.de> writes:
Ben Hinkle wrote:

 the D version was *faster* than the C++ version by a large amount (3.2 sec
 vs 2.7 sec). That could be specific for the GMP C++ expression templates -
 I don't know if my experience generalizes to other expression template
 libraries.

Expression templates certainly are not a technique to solve all problems. Before resorting to expression templates, one should make sure to precisely understand the performance bottleneck, otherwise the chance to pull down performance is just as good as to get a gain. Specifically, the need for avoiding temporaries is not only the problem of memory allocations but also that of exploiting the cache in the right way. If the array that you handle become bigger then the cache (several MB, depending on the architecture) you have to be very careful to work locally as much as possible. For modern architectures, cache optimization may easily give you a 10-fold performance gain for common data-intensive numerical computations. In D, much of that optimization might be possible within the compiler *if we have multidimensional arrays and vectorized expressions* - otherwise the compiler just does not have enough possibilities to change the order of expressions. Alternatively, these optimizations could be done in the library as it is done with boost++ in C++. For that, expression templates are needed. I think that D should go both ways as complements. It will probably always depend on the details of the problem, which of the options might be the better solution.
Jan 31 2005
prev sibling parent reply "Walter" <newshound digitalmars.com> writes:
"Norbert Nemec" <Norbert Nemec-online.de> wrote in message
news:ctj46q$f52$1 digitaldaemon.com...
 Hi there,

 triggered by a message from Walter about implicit function template
 instantiation, I just sat down and wrote some example code for expression
 templates in D. The result is attached.

 Short summary: expression template programming is not yet possible in D.
 Many details show that the template mechanism in general is very promising
 compared to the C++, but implicit function template instantiation is such

 crucial feature for ET that the whole attempt is doomed.

I want to make this work (it's just beyond the scope of 1.0 at the moment).
Feb 03 2005
parent reply Norbert Nemec <Norbert Nemec-online.de> writes:
Walter wrote:

 I want to make this work (it's just beyond the scope of 1.0 at the
 moment).

That's a statement I can live with. Actually, I have thought about the topic a little more considering whether it might be possible to avoid the complexity of C++ implicit instantiation. So far, my resolution is: No. The power of C++ implicit instantiation comes from very sopisticated pattern matching: The compiler can match any type like MyTemplate<int,float,MyTemplate2<5,int> > with a type pattern like MyTemplate<T,U,MyTemplate2<N,T> > while also matching up T with int, U with float and N with 5 The D compiler already does a little bit of pattern matching as well, but it is by far not as flexible and it is not possible yet to retrieve the matched parts: template(T,U: T[5]) already needs some intelligence, but by far not as much, and it is in general not possible to do anything like template(T,U: T[N]) where N is retrieved from the type given for U. Any attempt to avoid the complexity of the C++ behaviour that I could think of so far resulted in severly limited power. I doubt, that a way can be found around it.
Feb 04 2005
next sibling parent reply Georg Wrede <georg.wrede nospam.org> writes:
Norbert Nemec wrote:
 Walter wrote:
I want to make this work (it's just beyond the scope of 1.0 at the
moment).

That's a statement I can live with. Actually, I have thought about the topic a little more considering whether it might be possible to avoid the complexity of C++ implicit instantiation.

 Any attempt to avoid the complexity of the C++ behaviour that I could think
 of so far resulted in severly limited power. I doubt, that a way can be
 found around it.

Just a thought, but: Ideally, we'd have this separated from the rest of D development, for a while. D1.0 would be unhampered by this, and this could go on essentially irrespective of "daily issues" in D development. This is, after all, on a separate conceptual level. Later, when this produces a superior template system, then it would be imported to D. (Be it then D2.0, D1.5 or, hopefully D1.1) In this project, Norbert could lead the template language development. The practical side, i.e. testing the concepts with real code, could be implemented by others with a preprosessor. Ideally that would take any D source, but only transform the constructs relevant to this. The preprocessor could be written in Perl, DMDscript, or D itself, pretty quickly. I assume it wouldn't even need to properly parse D in it's entirety, just the relevant parts. To speed up writing (and rewriting totally different versions of) the preprocessor, we might even decide to have in-comment special markers, or whatever other extras in the input sources. It is, afer all, a language lab, not a production environment. This would essentially free Walter to concentrate on current issues. (Of course Walter'd be around in this too, but you know what I mean.) And the project could go meandering on, free to try even the most controversial things. Once we get a working (and proven and tested!!!) template syntax, we could use it for a while in "d-developers-only" projects, to see if it actually works in real life. We might even have a number of alternative syntaxes examined at the same time!! A good template system being both urgent and important, I feel this is the least we could do right now.
Feb 04 2005
parent reply Norbert Nemec <Norbert Nemec-online.de> writes:
Georg Wrede wrote:

 Just a thought, but:
 
 Ideally, we'd have this separated from the rest of D development, for a
 while. D1.0 would be unhampered by this, and this could go on
 essentially irrespective of "daily issues" in D development. This is,
 after all, on a separate conceptual level. Later, when this produces a
 superior template system, then it would be imported to D. (Be it then
 D2.0, D1.5 or, hopefully D1.1)

Nice idea. However currently, I really don't have much resources left over for that. (Actually - I'm already spending much more time on reading and writing in this list than I should...) I still have the plan to at write down the design of the most central features that I have in mind for future D development. If it becomes clear that a prototype implementation can be done in a preprocessor, that certainly is an option. Anyhow, I believe that most ideas what I have in mind would demands very detailed analysis of the sourcecode for a preprocessor. In any case: I cannot promise when I find the time to write on the design papers. Discussing an implementation does not make sense before that. Of course, if anybody wants to experiment, you are always welcome to start. I'll certainly join in the discussion and it might actually force me to finally sit down and write down clean concepts.
Feb 04 2005
parent reply Georg Wrede <georg.wrede nospam.org> writes:
Norbert Nemec wrote:
 Georg Wrede wrote:
Ideally, we'd have this separated from the rest of D development,
for a while. D1.0 would be unhampered by this, and this could go on
essentially irrespective of "daily issues" in D development.


 Of course, if anybody wants to experiment, you are always welcome
 to start. I'll certainly join in the discussion and it might
 actually force me to finally sit down and write down clean concepts.

Good. This was excactly what I'd hoped for!
 Anyhow, I believe that most ideas what I have in
 mind would demands very detailed analysis of the 
 sourcecode for a preprocessor.

Hmm. Does that contradict with D having a context free grammar?
Feb 04 2005
parent Norbert Nemec <Norbert Nemec-online.de> writes:
Georg Wrede wrote:

 
 Norbert Nemec wrote:
 Georg Wrede wrote:
Ideally, we'd have this separated from the rest of D development,
for a while. D1.0 would be unhampered by this, and this could go on
essentially irrespective of "daily issues" in D development.


> Of course, if anybody wants to experiment, you are always welcome > to start. I'll certainly join in the discussion and it might > actually force me to finally sit down and write down clean concepts. Good. This was excactly what I'd hoped for!
 Anyhow, I believe that most ideas what I have in
 mind would demands very detailed analysis of the

Hmm. Does that contradict with D having a context free grammar?

No, but you simply need more than grammar to preprocess implicit instantiation. Basically, the precompiler would have to understand all the types used in D, which goes far beyond simply parsing the code.
Feb 07 2005
prev sibling parent reply "Walter" <newshound digitalmars.com> writes:
"Norbert Nemec" <Norbert Nemec-online.de> wrote in message
news:ctvj6q$248a$1 digitaldaemon.com...
 The power of C++ implicit instantiation comes from very sopisticated

 matching: The compiler can match any type like
  MyTemplate<int,float,MyTemplate2<5,int> >
 with a type pattern like
  MyTemplate<T,U,MyTemplate2<N,T> >
 while also matching up T with int, U with float and N with 5

So can D. D will do all the pattern matching C++ will, it just won't do implicit instantiation. The above examples are explicit instantiation, which should work fine with D.
 The D compiler already does a little bit of pattern matching as well, but

 is by far not as flexible and it is not possible yet to retrieve the
 matched parts:

  template(T,U: T[5])

 already needs some intelligence, but by far not as much, and it is in
 general not possible to do anything like

  template(T,U: T[N])

 where N is retrieved from the type given for U.

The following does work: template foo(T,N,U:T[N]) { T t; N n; U u; } alias foo!(int,char,int[char]) bar;
Feb 04 2005
parent reply Norbert Nemec <Norbert Nemec-online.de> writes:
Walter wrote:

 "Norbert Nemec" <Norbert Nemec-online.de> wrote in message
 news:ctvj6q$248a$1 digitaldaemon.com...
 The power of C++ implicit instantiation comes from very sopisticated

 matching: The compiler can match any type like
  MyTemplate<int,float,MyTemplate2<5,int> >
 with a type pattern like
  MyTemplate<T,U,MyTemplate2<N,T> >
 while also matching up T with int, U with float and N with 5

So can D. D will do all the pattern matching C++ will, it just won't do implicit instantiation. The above examples are explicit instantiation, which should work fine with D.

I guess, I did not make my point clear enough: as I believe, the pattern matching in C++ is fundamentally more powerful that that in D. To illustrate, it is the simplest way to imagine what implicit instantiation might look like in D without demanding more intelligence of the compiler. The first idea that comes to mind would be the rule that, if 'mytemplate' is the name of a template containing exactly one function with the name 'mytemplate', the call mytemplate(a,b,c) is automatically translated into mytemplate!(typeof(a),typeof(b),typeof(c))(a,b,c) This was my first idea when I thought about the topic. It would be trivial to implement and provide some kind of 'implicit instantiation'. It can make full use of D's pattern matching mechanism, as it will automatically select the appropriate specialization based on the types of the arguments. However, it becomes immediately clear that this is less powerful than C++. The template parameters could only be types and they would have to match one-by-one with the arguments of the encapsulated function. C++, on the other hand allows the template parameters to be used as placeholders in arbitrary places of the function arguments: template<int M,int N> Vector<M> dot(Matrix<M,N> a,Vector<N> b) { Vector<M> res; for(int m=M;m--;) { double r = 0.0; for(int n=N;n--;) r += a[m,n]*b[n] res[m] = r; } return res; } Here, the compiler actually does a complete patter matching on the pair (Matrix<$M,$N>,Vector<$N>) and keeps the integers matched by $M and $N for later use. Furthermore, the compiler matches not only one pattern, but compares several patterns and selects the one that fits "best" (if you do partial specialization) This goes several steps beyond the current power of D.
Feb 08 2005
parent reply Kramer <Kramer_member pathlink.com> writes:
This may be a bit off topic, but since we're talking templates and flexibility
and expandability, would variadic templates be worth anything?  I was playing
around with a function that had a template for it and I converted the function
to be a variadic function.  Then as I was converting the template, I realized I
couldn't do it.  The more I thought about it, the more a variadic template just
seemed to me like a variadic function.  But I just still couldn't come to think
of the two as the same and I couldn't fully get my head around trying to resolve
what felt like differences between them (even though I couldn't think of any, or
come up with an expressive example).  These may just be wasted thought cycles,
but I also thought why not?

-Kramer

In article <cu9ruo$e4o$1 digitaldaemon.com>, Norbert Nemec says...
Walter wrote:

 "Norbert Nemec" <Norbert Nemec-online.de> wrote in message
 news:ctvj6q$248a$1 digitaldaemon.com...
 The power of C++ implicit instantiation comes from very sopisticated

 matching: The compiler can match any type like
  MyTemplate<int,float,MyTemplate2<5,int> >
 with a type pattern like
  MyTemplate<T,U,MyTemplate2<N,T> >
 while also matching up T with int, U with float and N with 5

So can D. D will do all the pattern matching C++ will, it just won't do implicit instantiation. The above examples are explicit instantiation, which should work fine with D.

I guess, I did not make my point clear enough: as I believe, the pattern matching in C++ is fundamentally more powerful that that in D. To illustrate, it is the simplest way to imagine what implicit instantiation might look like in D without demanding more intelligence of the compiler. The first idea that comes to mind would be the rule that, if 'mytemplate' is the name of a template containing exactly one function with the name 'mytemplate', the call mytemplate(a,b,c) is automatically translated into mytemplate!(typeof(a),typeof(b),typeof(c))(a,b,c) This was my first idea when I thought about the topic. It would be trivial to implement and provide some kind of 'implicit instantiation'. It can make full use of D's pattern matching mechanism, as it will automatically select the appropriate specialization based on the types of the arguments. However, it becomes immediately clear that this is less powerful than C++. The template parameters could only be types and they would have to match one-by-one with the arguments of the encapsulated function. C++, on the other hand allows the template parameters to be used as placeholders in arbitrary places of the function arguments: template<int M,int N> Vector<M> dot(Matrix<M,N> a,Vector<N> b) { Vector<M> res; for(int m=M;m--;) { double r = 0.0; for(int n=N;n--;) r += a[m,n]*b[n] res[m] = r; } return res; } Here, the compiler actually does a complete patter matching on the pair (Matrix<$M,$N>,Vector<$N>) and keeps the integers matched by $M and $N for later use. Furthermore, the compiler matches not only one pattern, but compares several patterns and selects the one that fits "best" (if you do partial specialization) This goes several steps beyond the current power of D.

Feb 08 2005
parent Norbert Nemec <Norbert Nemec-online.de> writes:
Kramer wrote:

 This may be a bit off topic, but since we're talking templates and
 flexibility and expandability, would variadic templates be worth anything?

Similar things have been discussed for C++ as well. I don't know whether complete concepts arose from it. Basically, it would be very helpful to have them. There is a fundamental difference between variadic templates and variadic function, in so far that the former are resolved at compile time and the latter at runtime. Maybe this could also be a way to have compile-time checked variadic functions that have been proposed on this list before.
Feb 09 2005