• Norbert Nemec (65/65) Jan 30 2005 Hi there,
• Stewart Gordon (23/35) Jan 31 2005
• Norbert Nemec (27/52) Jan 31 2005 This is yet another subject. True - once we have array operations as par...
• Stewart Gordon (13/47) Jan 31 2005 Oops, miscounted again.
• Norbert Nemec (30/48) Jan 31 2005 See the point below. I don't consider the current specification of array
• pragma (16/20) Jan 31 2005 I fully acknowledge that I am a complete idiot when it comes to "numeric...
• Ivan Senji (17/38) Jan 31 2005 start
• Carlos Santander B. (6/23) Jan 31 2005 I'm kinda in the same page, but I wouldn't say I can see the whole top
• Norbert Nemec (72/74) Feb 01 2005 Thanks for your honesty. Actually two years ago I would have had to say ...
• pragma (29/36) Feb 01 2005 Thank you for the kind words and the informative response!
• Ben Hinkle (25/34) Jan 31 2005 I haven't looked at the details of your code but it reminds me of a simi...
• Norbert Nemec (21/25) Jan 31 2005 Expression templates certainly are not a technique to solve all problems...
• Walter (4/12) Feb 03 2005 a
• Norbert Nemec (23/25) Feb 04 2005 That's a statement I can live with.
• Georg Wrede (30/41) Feb 04 2005 Just a thought, but:
• Norbert Nemec (15/23) Feb 04 2005 Nice idea. However currently, I really don't have much resources left ov...
• Georg Wrede (4/14) Feb 04 2005 Good. This was excactly what I'd hoped for!
• Norbert Nemec (4/22) Feb 07 2005 No, but you simply need more than grammar to preprocess implicit
• Walter (15/29) Feb 04 2005 pattern
• Norbert Nemec (39/52) Feb 08 2005 I guess, I did not make my point clear enough: as I believe, the pattern
• Kramer (12/64) Feb 08 2005 This may be a bit off topic, but since we're talking templates and flexi...
• Norbert Nemec (8/10) Feb 09 2005 Similar things have been discussed for C++ as well. I don't know whether

Norbert Nemec <Norbert Nemec-online.de> writes:

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

Stewart Gordon <smjg_1998 yahoo.com> writes:

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.

 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.

<snip>

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.

Norbert Nemec <Norbert Nemec-online.de> writes:

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.

 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.

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.

<snip>

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.

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.

 <snip>
 
 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

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

"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


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.

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

"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

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

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

"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 

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.

"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

a
 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).

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.

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.

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.

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?

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

  > sourcecode for a preprocessor.
 
 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.

"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

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

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

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.

The following does work:

template foo(T,N,U:T[N])
{
    T t;
    N n;
    U u;
}

alias foo!(int,char,int[char]) bar;

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

 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

 
 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.

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

 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

 
 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.

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.