Kirk McDonald wrote:
> Walter Bright wrote:
>> Kirk McDonald wrote:
>>> Never mind what this actually does. The problem at hand is somehow generating a class like this at compile-time, possibly given only the class Foo.
>>
>> Tell me exactly what you need.
> 
> Given a class, I need a way to get a list of all of its member functions at compile-time. 

Probably also a couple of bits per method telling whether the method is static or final.

Andrei

Andrei Alexandrescu (See Website For Email) wrote:
> Kirk McDonald wrote:
>> Walter Bright wrote:
>>> Kirk McDonald wrote:
>>>> Never mind what this actually does. The problem at hand is somehow generating a class like this at compile-time, possibly given only the class Foo.
>>>
>>> Tell me exactly what you need.
>>
>> Given a class, I need a way to get a list of all of its member functions at compile-time. 
> 
> Probably also a couple of bits per method telling whether the method is static or final.
> 
> Andrei

Right, right, all that stuff, too. :-)

-- 
Kirk McDonald
http://kirkmcdonald.blogspot.com
Pyd: Connecting D and Python
http://pyd.dsource.org

Kirk McDonald wrote:
> Given a class, I need a way to get a list of all of its member functions at compile-time.

static member functions? non-virtual member functions?

Andrei Alexandrescu (See Website For Email) wrote:
> Walter Bright wrote:
>> I know from these messages it seems that all we talk about is metaprogramming, but actually most of our discussions (and most of Andrei's work on D) are about filling in mundane gaps in the language, like the lack of a proper const. 
> 
> Ehm. Somehow I thought it's actually interesting. Reminds me of Tom Sawyer's neighbors painting the fence for him :o).

It's mundane in the sense that if we do it right, like the foundation of a house, nobody will notice it. If we do it wrong, it'll be front page like the crane that fell over last month and sliced through a high rise condo.

I couldn't be in this business if I didn't enjoy the mundane details <g>.

Walter Bright wrote:
> Kirk McDonald wrote:
>> Given a class, I need a way to get a list of all of its member functions at compile-time.
> 
> static member functions? non-virtual member functions?

Okay, I think I do need to clarify this.

Let's take this class:

class Foo {
    void foo() {} // A regular method
    static void bar() {} // A static member function
    final void baz() {} // A non-virtual member function
}

Here's one possible interface:

get_member_functions!(Foo) => Tuple!(Foo.foo, Foo.bar, Foo.baz)

To distinguish between these attributes, we could define an enum, like:

enum MemberAttribute { Virtual, Final, Static }

Then we would have another template or built-in function or whatever these are supposed to be:

get_member_attributes!(Foo) => Tuple!(MemberAttribute.Virtual, MemberAttribute.Static, MemberAttribute.Final)

Where the order of this tuple's elements corresponds exactly to the first tuple's.

This is one idea. If anyone thinks of a better interface (and these names are probably unacceptable, at least), please speak up.

-- 
Kirk McDonald
http://kirkmcdonald.blogspot.com
Pyd: Connecting D and Python
http://pyd.dsource.org

Walter Bright wrote:
> Andrei Alexandrescu (See Website For Email) wrote:
>> Walter Bright wrote:
>>> I know from these messages it seems that all we talk about is metaprogramming, but actually most of our discussions (and most of Andrei's work on D) are about filling in mundane gaps in the language, like the lack of a proper const. 
>>
>> Ehm. Somehow I thought it's actually interesting. Reminds me of Tom Sawyer's neighbors painting the fence for him :o).
> 
> It's mundane in the sense that if we do it right, like the foundation of a house, nobody will notice it. If we do it wrong, it'll be front page like the crane that fell over last month and sliced through a high rise condo.
> 
> I couldn't be in this business if I didn't enjoy the mundane details <g>.

It's interesting to me that the features I requested back around DMD 0.135, which made elementary metaprocessing of strings possible, were so mundane  --- "abcd"[2..4] being exactly equivalent to "bc", for example.
It seems to me that some other languages (*cough* C# *cough*) have tried to reach for the flashy stuff without getting the mundane things right.
Mundane is good.

Andrei Alexandrescu (See Website for Email) wrote:
> Bill Baxter wrote:
>> Andrei Alexandrescu (See Website For Email) wrote:
>>> This is a misunderstanding. The syntax is not to be extended. It stays fixed, and that is arguably a good thing. The semantics become more flexible. For example, they will make it easy to write a matrix operation:
>>>
>>> A = (I - B) * C + D
>>>
>>> and generate highly performant code from it. (There are many reasons for which that's way harder than it looks.)
>>
>> This is one thing I haven't really understood in the discussion.  How do the current proposals help that case?  From what I'm getting you're going to have to write every statement like the above as something like:
>>
>> mixin {
>>    ProcessMatrixExpr!( "A = (I - B) * C + D;" );
>> }
>>
>> How do you get from this mixin/string processing stuff to an API that I might actually be willing to use for common operations?
> 
> That's a great starting point for a good conversation. And no, you
> wouldn't do it with strings, you'd do it exactly as I wrote, with
> regular code. You could use strings if you want to use more math-looking
> operators and Greek symbols etc.
> 
>>> I think there is a lot of apprehension and misunderstanding surrounding what metacode is able and supposed to do or simplify. Please, let's focus on understanding _before_ forming an opinion.
>>
>> I think that's exactly what Tom's getting at.  He's asking for examples of how this would make like better for him and others.  I think given your background you take it for granted that metaprogramming is the future.  But D is attracts folks from all kinds of walks of life, because it promises to be a kinder, gentler C++.  So some people here aren't even sure why D needs templates at all.  Fortran doesn't have 'em after all.  And Java just barely does.
> 
> Then such people would be hard-pressed to figure why tuples (which are
> essentially typelists, the single most used component in Loki) have
> engendered, according to Walter himself, a surge in language popularity.
> 
> I don't even think metaprogramming is the future. I think that it's one
> of many helpful tools for writing good libraries, as are GC, modules, or
> interfaces. *Everybody* appreciates good libraries.
> 
>> Anyway, I think it would help get everyone on board if some specific and useful examples were given of how this solves real problems (and no I don't really consider black and white holes as solving real problems.  I couldn't even find any non-astronomical uses of the terms in a google search.)
> 
> The terms are recent and introduced by the Perl community. I happened to
> like the metaphor. The consecrated name is "null object pattern".
> 
>> For instance, it would be nice to see some more concrete discussion about
>> * the "rails" case.
>> * the X = A*B + C matrix/vector expressions case.
>> * the case of generating bindings to scripting langauges / ORB stubs
>> * the Spirit/parser generator case
>>
>> So here's my take on vector expressions since that's the only one I know anything about.
>>
>> *Problem statement*:
>> Make the expression A=(I-B)*C+D efficient, where the variables are large vectors (I'll leave out matrices for now).
>>
>> *Why it's hard*:
>> The difficulty is that (ignoring SSE instruction etc) the most efficient way to compute that is do all operations component-wise.  So instead of computing I-B then multiplying by C, you compute
>>     A[i] = (I[i]-B[i])*C[i]+D[i];
>> for each i.  This eliminates the need to allocate large intermediate vectors.
> 
> There's much more than that. (First off, things are more complicated in
> the case of matrices.) You want to be gentle on cache, so when you have
> any column-wise iteration you want to do matrix blocking. Depending on
> the expression, you want to select different block sizes.
> 
> Then you also want to do optionally partial unrolling *on top of
> blocking*. Again, the amount of unrolling might depend on the
> expression. (You don't want to unroll large expressions.) At this point
> things are utterly messy.
> 
> Iterating may also be better row-wise or column-wise, depending on the
> expression. Some subexpressions have a "preferential" row-wise scanning
> order and a "possible" column-wise order. Others must do things one way
> or the other. For all this the appropriate code must be generated.
> 
>> *Existing solutions*:
>>   Expression templates in C++, e.g. The Blitz++ library.  Instead of making opSub in I-B return a new Vector object, you make opSub return an ExpressionTemplate object.  This is a little template struct that contains a reference to I and to B, and knows how to subtract the two in a component-wise manner.  The types of I and B are template parameters, LeftT and RightT. Its interface also allows it to be treated just like a Vector.  You can add a vector to it, subtract a Vector from it etc.
>>
>> Now we go and try to multiply that result times C.  The result of that is a new MultExpressionTemplate with two paramters, the LeftT being our previous SubExpressionTemplate!(Vector,Vector) and the RightT being Vector.
>>
>> Proceeding on in this way eventually the result of the math is of type:
>>
>> AddExpressionTemplate!(
>>    MultExpressionTemplate!(
>>       SubExpressionTemplate!(Vector,Vector),
>>       Vector),
>>    Vector)
>>
>> And you can see that we basically have a parse tree expressed as nested templates.  The final trick is that a Vector.opAssign that takes an ExpressionTemplate is provided and that method calls a method of the expression template to finally trigger the calculation, like expr.eval(this).  eval() has the top-level loop over the components of the answer.
>>
>> *Why Existing solutions are insufficient*
>> For that all that effort to actually be useful the compiler has to be pretty agressive about inlining everything so that in the end all the temporary template structs and function calls go away and you're just left with one eval call.  It can be tricky to get the code into just the right configuration so that the compiler will do the inlining.  And even then results will depend on the quality of the compiler.  My attempts using MSVC++ several years ago always came out to be slower than the naive version, but with about 10x the amount of code.  The code is also pretty difficult to follow because of all those different types of expression templates that have to be created.
>>
>> If you include matrices things are even trickier because there are special cases like "A*B+a*C" that can be computed efficiently by a single optimized routine.  You'd like to recognize such cases and turn them into single calls to that fast routine.  You might also want to recognize "A*B+C" as a special case of that with a==1.
>>
>> *How it could be improved*:
>> ??? this is what I'd like to see explained better.
> 
> Great. One problem is that building ET libraries is exceedingly hard
> because of the multiple issues that must be solved simultaneously. To
> get a glimpse into the kind of problems that we are talking about, see
> e.g. http://www.adtmag.com/joop/carticle.aspx?ID=627. Libraries cannot
> afford to implement an optimal solution, partly because they have so
> much language-y mud to go through, and partly because the C++ language
> simply does not offer the code generation abilities that are needed.
> 
> I haven't sat down to design a linear algebra using D's new abilities,
> but they are definitely helpful in that specifying an elementary matrix
> operation (the core of a loop) only needs one template. For example, if
> you want to specify the kernel of a matrix addition, you can say it as a
> type:
> 
> MatrixOp!("lhs[i, j] + rhs[i, j]", rowwise, columnwise)
> 
> The type specifies the kernel of the operation, conventionally expressed
> in terms of lhs, rhs, i, and j, then the preferred iteration order, and
> finally the alternate order. The MatrixOp template defines a member
> function get(uint i, uint j) that expands the string given in the
> 
> The kernel of multiplication is:
> 
> MatrixOp!("sum!(k, 0, n, lhs[i, k] * rhs[k, j])", rowwise, columnwise,
> blocking!(8), unrolling!(8))
> 
> (sum is not doable in today's D because D lacks the ability to inject a
> new alias name into a template upon invocation.)
> 
> This type specifies how an element of the multiplication is obtained,
> again what preferred and alternate method of iteration is possible, and
> also specifies blocking and unrolling suggestions.
> 
> In a complex expression, lhs and rhs will bind to subexpressions; it's
> easy to then generate the appropriate code upon assignment to the
> target, with heuristically chosen blocking and unrolling parameters
> based on the suggestions made by the subexpressions. All this is doable
> without difficulty through manipulating and generating code during
> compilation.
> 
> 
> Andrei

I've also done some experimentation on this problem.
To do a perfect solution, you'd need to be able to identify when a variable is used twice, for example,

a = 3.0 * b + (c - a * 1.5);
The compiler knows that 'a' occurs twice, but that information is not transferred into expression templates. The compiler may also know the length of some of the arrays, and that is also lost.

I've almost completed a BLAS1 generator for x87 (not SSE), which spits out _optimal_ asm code for any combination of vector-scalar operations (vec+vec, vec-vec, vec*real, dot(vec, vec), for any mixture of 32-,64-, and 80- bit vectors. The cache effects are simple in this case.
The code to do this is amazingly compact, thanks to tuples and the new 1.005 mixins (in fact, it is a small fraction of the size of an asm BLAS1 kernal).
I noticed that the 'expression template' part of the code contained almost nothing specific to vectors; I think there's potential for a library mixin component to do it.

Of course another approach would be to add
opAssignExpression(char [] expr)()
{
}
where "expr" is the verbatim expression.
a = b*5 + c*d;

would become
mixin a.opAssignExpression!("a=b*5+c*d");

since it seems that with expression templates, you're fighting the compiler, attempting to undo everything it has done.

Don Clugston wrote:
> Andrei Alexandrescu (See Website for Email) wrote:
>> Bill Baxter wrote:
>>> Andrei Alexandrescu (See Website For Email) wrote:
>>>> This is a misunderstanding. The syntax is not to be extended. It stays fixed, and that is arguably a good thing. The semantics become more flexible. For example, they will make it easy to write a matrix operation:
>>>>
>>>> A = (I - B) * C + D
>>>>
>>>> and generate highly performant code from it. (There are many reasons for which that's way harder than it looks.)
>>>
>>> This is one thing I haven't really understood in the discussion.  How do the current proposals help that case?  From what I'm getting you're going to have to write every statement like the above as something like:
>>>
>>> mixin {
>>>    ProcessMatrixExpr!( "A = (I - B) * C + D;" );
>>> }
>>>
>>> How do you get from this mixin/string processing stuff to an API that I might actually be willing to use for common operations?
>>
>> That's a great starting point for a good conversation. And no, you
>> wouldn't do it with strings, you'd do it exactly as I wrote, with
>> regular code. You could use strings if you want to use more math-looking
>> operators and Greek symbols etc.
>>
>>>> I think there is a lot of apprehension and misunderstanding surrounding what metacode is able and supposed to do or simplify. Please, let's focus on understanding _before_ forming an opinion.
>>>
>>> I think that's exactly what Tom's getting at.  He's asking for examples of how this would make like better for him and others.  I think given your background you take it for granted that metaprogramming is the future.  But D is attracts folks from all kinds of walks of life, because it promises to be a kinder, gentler C++.  So some people here aren't even sure why D needs templates at all.  Fortran doesn't have 'em after all.  And Java just barely does.
>>
>> Then such people would be hard-pressed to figure why tuples (which are
>> essentially typelists, the single most used component in Loki) have
>> engendered, according to Walter himself, a surge in language popularity.
>>
>> I don't even think metaprogramming is the future. I think that it's one
>> of many helpful tools for writing good libraries, as are GC, modules, or
>> interfaces. *Everybody* appreciates good libraries.
>>
>>> Anyway, I think it would help get everyone on board if some specific and useful examples were given of how this solves real problems (and no I don't really consider black and white holes as solving real problems.  I couldn't even find any non-astronomical uses of the terms in a google search.)
>>
>> The terms are recent and introduced by the Perl community. I happened to
>> like the metaphor. The consecrated name is "null object pattern".
>>
>>> For instance, it would be nice to see some more concrete discussion about
>>> * the "rails" case.
>>> * the X = A*B + C matrix/vector expressions case.
>>> * the case of generating bindings to scripting langauges / ORB stubs
>>> * the Spirit/parser generator case
>>>
>>> So here's my take on vector expressions since that's the only one I know anything about.
>>>
>>> *Problem statement*:
>>> Make the expression A=(I-B)*C+D efficient, where the variables are large vectors (I'll leave out matrices for now).
>>>
>>> *Why it's hard*:
>>> The difficulty is that (ignoring SSE instruction etc) the most efficient way to compute that is do all operations component-wise.  So instead of computing I-B then multiplying by C, you compute
>>>     A[i] = (I[i]-B[i])*C[i]+D[i];
>>> for each i.  This eliminates the need to allocate large intermediate vectors.
>>
>> There's much more than that. (First off, things are more complicated in
>> the case of matrices.) You want to be gentle on cache, so when you have
>> any column-wise iteration you want to do matrix blocking. Depending on
>> the expression, you want to select different block sizes.
>>
>> Then you also want to do optionally partial unrolling *on top of
>> blocking*. Again, the amount of unrolling might depend on the
>> expression. (You don't want to unroll large expressions.) At this point
>> things are utterly messy.
>>
>> Iterating may also be better row-wise or column-wise, depending on the
>> expression. Some subexpressions have a "preferential" row-wise scanning
>> order and a "possible" column-wise order. Others must do things one way
>> or the other. For all this the appropriate code must be generated.
>>
>>> *Existing solutions*:
>>>   Expression templates in C++, e.g. The Blitz++ library.  Instead of making opSub in I-B return a new Vector object, you make opSub return an ExpressionTemplate object.  This is a little template struct that contains a reference to I and to B, and knows how to subtract the two in a component-wise manner.  The types of I and B are template parameters, LeftT and RightT. Its interface also allows it to be treated just like a Vector.  You can add a vector to it, subtract a Vector from it etc.
>>>
>>> Now we go and try to multiply that result times C.  The result of that is a new MultExpressionTemplate with two paramters, the LeftT being our previous SubExpressionTemplate!(Vector,Vector) and the RightT being Vector.
>>>
>>> Proceeding on in this way eventually the result of the math is of type:
>>>
>>> AddExpressionTemplate!(
>>>    MultExpressionTemplate!(
>>>       SubExpressionTemplate!(Vector,Vector),
>>>       Vector),
>>>    Vector)
>>>
>>> And you can see that we basically have a parse tree expressed as nested templates.  The final trick is that a Vector.opAssign that takes an ExpressionTemplate is provided and that method calls a method of the expression template to finally trigger the calculation, like expr.eval(this).  eval() has the top-level loop over the components of the answer.
>>>
>>> *Why Existing solutions are insufficient*
>>> For that all that effort to actually be useful the compiler has to be pretty agressive about inlining everything so that in the end all the temporary template structs and function calls go away and you're just left with one eval call.  It can be tricky to get the code into just the right configuration so that the compiler will do the inlining.  And even then results will depend on the quality of the compiler.  My attempts using MSVC++ several years ago always came out to be slower than the naive version, but with about 10x the amount of code.  The code is also pretty difficult to follow because of all those different types of expression templates that have to be created.
>>>
>>> If you include matrices things are even trickier because there are special cases like "A*B+a*C" that can be computed efficiently by a single optimized routine.  You'd like to recognize such cases and turn them into single calls to that fast routine.  You might also want to recognize "A*B+C" as a special case of that with a==1.
>>>
>>> *How it could be improved*:
>>> ??? this is what I'd like to see explained better.
>>
>> Great. One problem is that building ET libraries is exceedingly hard
>> because of the multiple issues that must be solved simultaneously. To
>> get a glimpse into the kind of problems that we are talking about, see
>> e.g. http://www.adtmag.com/joop/carticle.aspx?ID=627. Libraries cannot
>> afford to implement an optimal solution, partly because they have so
>> much language-y mud to go through, and partly because the C++ language
>> simply does not offer the code generation abilities that are needed.
>>
>> I haven't sat down to design a linear algebra using D's new abilities,
>> but they are definitely helpful in that specifying an elementary matrix
>> operation (the core of a loop) only needs one template. For example, if
>> you want to specify the kernel of a matrix addition, you can say it as a
>> type:
>>
>> MatrixOp!("lhs[i, j] + rhs[i, j]", rowwise, columnwise)
>>
>> The type specifies the kernel of the operation, conventionally expressed
>> in terms of lhs, rhs, i, and j, then the preferred iteration order, and
>> finally the alternate order. The MatrixOp template defines a member
>> function get(uint i, uint j) that expands the string given in the
>>
>> The kernel of multiplication is:
>>
>> MatrixOp!("sum!(k, 0, n, lhs[i, k] * rhs[k, j])", rowwise, columnwise,
>> blocking!(8), unrolling!(8))
>>
>> (sum is not doable in today's D because D lacks the ability to inject a
>> new alias name into a template upon invocation.)
>>
>> This type specifies how an element of the multiplication is obtained,
>> again what preferred and alternate method of iteration is possible, and
>> also specifies blocking and unrolling suggestions.
>>
>> In a complex expression, lhs and rhs will bind to subexpressions; it's
>> easy to then generate the appropriate code upon assignment to the
>> target, with heuristically chosen blocking and unrolling parameters
>> based on the suggestions made by the subexpressions. All this is doable
>> without difficulty through manipulating and generating code during
>> compilation.
>>
>>
>> Andrei
> 
> I've also done some experimentation on this problem.
> To do a perfect solution, you'd need to be able to identify when a variable is used twice, for example,
> 
> a = 3.0 * b + (c - a * 1.5);
> The compiler knows that 'a' occurs twice, but that information is not transferred into expression templates.

I think what you really need is aliasing information (e.g. two names referring to the same vector), and that is typically not easily computable.

> The compiler may also know the length of some of the arrays, and that is also lost.

Ah, indeed. So that would mean better error checking and probably less runtime bounds checking.

> I've almost completed a BLAS1 generator for x87 (not SSE), which spits out _optimal_ asm code for any combination of vector-scalar operations (vec+vec, vec-vec, vec*real, dot(vec, vec), for any mixture of 32-,64-, and 80- bit vectors. The cache effects are simple in this case.
> The code to do this is amazingly compact, thanks to tuples and the new 1.005 mixins (in fact, it is a small fraction of the size of an asm BLAS1 kernal).
> I noticed that the 'expression template' part of the code contained almost nothing specific to vectors; I think there's potential for a library mixin component to do it.
> 
> Of course another approach would be to add
> opAssignExpression(char [] expr)()
> {
> }
> where "expr" is the verbatim expression.
> a = b*5 + c*d;
> 
> would become
> mixin a.opAssignExpression!("a=b*5+c*d");
> 
> since it seems that with expression templates, you're fighting the compiler, attempting to undo everything it has done.

Not everything - e.g., precedence of operators remains unchanged. In the string-based approach you'd have to write a little parser to reimplement operator precedences. But point taken.


Andrei

Don Clugston wrote:
> Walter Bright wrote:
>> It's mundane in the sense that if we do it right, like the foundation of a house, nobody will notice it. If we do it wrong, it'll be front page like the crane that fell over last month and sliced through a high rise condo.
>>
>> I couldn't be in this business if I didn't enjoy the mundane details <g>.
> 
> It's interesting to me that the features I requested back around DMD 0.135, which made elementary metaprocessing of strings possible, were so mundane  --- "abcd"[2..4] being exactly equivalent to "bc", for example.
> It seems to me that some other languages (*cough* C# *cough*) have tried to reach for the flashy stuff without getting the mundane things right.
> Mundane is good.

Oh, I agree. Making a great product (as Apple demonstrated) is about getting the mundane details right.

The only problem is that such details don't make for a great presentation. Nobody is going to switch to D because of const. But if they do, they'll find it hard to switch away because of const (and things like it) <g>.

The flashy stuff, though, is the stuff that piques peoples' interests enough to give D a try.

Walter Bright wrote:
> Don Clugston wrote:
> 
>> Walter Bright wrote:
>>
>>> It's mundane in the sense that if we do it right, like the foundation of a house, nobody will notice it. If we do it wrong, it'll be front page like the crane that fell over last month and sliced through a high rise condo.
>>>
>>> I couldn't be in this business if I didn't enjoy the mundane details <g>.
>>
>>
>> It's interesting to me that the features I requested back around DMD 0.135, which made elementary metaprocessing of strings possible, were so mundane  --- "abcd"[2..4] being exactly equivalent to "bc", for example.
>> It seems to me that some other languages (*cough* C# *cough*) have tried to reach for the flashy stuff without getting the mundane things right.
>> Mundane is good.
> 
> 
> Oh, I agree. Making a great product (as Apple demonstrated) is about getting the mundane details right.
> 
> The only problem is that such details don't make for a great presentation. Nobody is going to switch to D because of const. But if they do, they'll find it hard to switch away because of const (and things like it) <g>.

Aye

> 
> The flashy stuff, though, is the stuff that piques peoples' interests enough to give D a try.

Bling is very much in the eye of the beholder, and often has the inverse effect?