www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - expression templates

reply enuhtac <enuhtac_lists gmx.de> writes:
Hello everyone,

I'm new to D and to this list (although I've had a look onto D a few years
ago). I hope you guys can help me with my questions.

At the moment I'm trying to implement some expression template stuff. My first
goal is to encode an expression into a type representing that expression
without any additional functionality (like the possibility to evaluate that
expression). Actually this is very simple and short in D. This is my approach:

struct OpBinary( string Op, R1, R2 )
{
    alias typeof( mixin( "R1.EvalT.init" ~ Op ~ "R2.EvalT.init" ) ) EvalT;

    enum string Operator = Op;
};

struct Constant( T, T v )
{
    alias T EvalT;

    enum T value = v;
};

struct Expr( R )
{
    auto opBinary( string Op, R2 )( Expr!R2 )
    {
        return Expr!( OpBinary!( Op, R, R2 ) )();
    }

    auto opBinary( string Op, T )( T v ) if( isNumeric!T )
    {
        return Expr!( OpBinary!( Op, R, Constant!( T, v ) ) )();
    }

    auto opBinaryRight( string Op, T )( T v ) if( isNumeric!T )
    {
        return Expr!( OpBinary!( Op, Constant!( T, v ), R ) )();
    }
};

But I cannot figure out how to implement expression templates for comparison
operators, which is crucial for my purpose. The opCmp function is great for
implementing comparison functionality, but when building an expression template
tree the information on the actual comparison operator is needed. opCmp just
knows that a comparison is going on, the actual type of comparison is unknown.
What I would like to have is something like this:

    auto opCmp( string Op, R2 )( Expr!R2 )
    {
        return Expr!( OpBinary!( Op, R, R2 ) )();
    }

So opCmp knows about the actual operator and would just use my OpBinary struct
to encode it. But this is not possible.

The only workaround for I this problem I can imagine is using my own comparison
functions instead of the comparison operators:
op!"<"( a, b ) instead of a < b.
Another possibility would be to call opBinary explicitly:
a.opCmp!"<"( b )
In this case I would not even have to write additional code.

But these workarounds are ugly, if would greatly prefer the normal comparison
operators.
Does anyone has an idea how to use them?

Regards,
enuhtac
Mar 27 2011
next sibling parent reply "Robert Jacques" <sandford jhu.edu> writes:
On Sun, 27 Mar 2011 15:46:54 -0400, enuhtac <enuhtac_lists gmx.de> wrote:

 Hello everyone,

 I'm new to D and to this list (although I've had a look onto D a few  
 years ago). I hope you guys can help me with my questions.

 At the moment I'm trying to implement some expression template stuff. My  
 first goal is to encode an expression into a type representing that  
 expression without any additional functionality (like the possibility to  
 evaluate that expression). Actually this is very simple and short in D.  
 This is my approach:

 struct OpBinary( string Op, R1, R2 )
 {
     alias typeof( mixin( "R1.EvalT.init" ~ Op ~ "R2.EvalT.init" ) )  
 EvalT;

     enum string Operator = Op;
 };

 struct Constant( T, T v )
 {
     alias T EvalT;

     enum T value = v;
 };

 struct Expr( R )
 {
     auto opBinary( string Op, R2 )( Expr!R2 )
     {
         return Expr!( OpBinary!( Op, R, R2 ) )();
     }

     auto opBinary( string Op, T )( T v ) if( isNumeric!T )
     {
         return Expr!( OpBinary!( Op, R, Constant!( T, v ) ) )();
     }

     auto opBinaryRight( string Op, T )( T v ) if( isNumeric!T )
     {
         return Expr!( OpBinary!( Op, Constant!( T, v ), R ) )();
     }
 };

 But I cannot figure out how to implement expression templates for  
 comparison operators, which is crucial for my purpose. The opCmp  
 function is great for implementing comparison functionality, but when  
 building an expression template tree the information on the actual  
 comparison operator is needed. opCmp just knows that a comparison is  
 going on, the actual type of comparison is unknown.
 What I would like to have is something like this:

     auto opCmp( string Op, R2 )( Expr!R2 )
     {
         return Expr!( OpBinary!( Op, R, R2 ) )();
     }

 So opCmp knows about the actual operator and would just use my OpBinary  
 struct to encode it. But this is not possible.

 The only workaround for I this problem I can imagine is using my own  
 comparison functions instead of the comparison operators:
 op!"<"( a, b ) instead of a < b.
 Another possibility would be to call opBinary explicitly:
 a.opCmp!"<"( b )
 In this case I would not even have to write additional code.

 But these workarounds are ugly, if would greatly prefer the normal  
 comparison operators.
 Does anyone has an idea how to use them?

 Regards,
 enuhtac

Hmm... I don't know you're use case exactly, but it sounds like a case of operator overload abuse. The design of opCmp was inspired by the amount of bug prone repetition that happens with C++ style comparison operators. Furthermore, both opCmp and opEquals have fixed return types in order to limit abuse. (D also prevents the overload of certain operators for the same reason). The main reason behind expression templates is to avoid costly intermediates, but the expression is always going to be heavier weight than an int, so why can't you evaluated the expression then and there?
Mar 27 2011
parent reply enuhtac <enuhtac_lists gmx.de> writes:
Am 29.03.2011 20:16, schrieb Caligo:
 enuhtac, may I ask what you are going to use the expression templates
 for? linear algebra library? is it an open source project?

Hi Caligo, I'm going to use the expression templates for CFD (computational fluid dynamics) computations. In this context I need to implement linear and nonlinear operators on 2D and/or 3D variable fields (in my case based on expression templates). It this will not result in a classical linear algebra package but it will include some of its features - i.e. simple algebraic operations on vectors and the solution of sparse linear equation systems. Concerning the type of project: first of all I'm playing around a bit, to see what D has to offer and to refine my ideas of an CFD framework. If things develop well this may lead to an open source project. We'll see... As there are no answers related to opCmp I assume I have to use one of my ugly workarounds... enuhtac
Mar 29 2011
parent reply bearophile <bearophileHUGS lycos.com> writes:
enuhtac:

 As there are no answers related to opCmp I assume I have to use one of
 my ugly workarounds...

The operator overloading done with opCmp is too much coarse even if you want to implement sets with operators like <= < > >= == for subset, etc. So are two use cases enough to question the current design of D opCmp? Bye, bearophile
Mar 29 2011
next sibling parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from bearophile (bearophileHUGS lycos.com)'s article
 The operator overloading done with opCmp is too much coarse even if you want to

Can you please give an example of where <=, >, etc. are useful for representing set operations? My naive opinion (i.e. without understanding your use case) is that using comparison operators to represent anything besides partial or total ordering is a severe abuse of operator overloading. (Their use to represent ordering of corresponding elements of a vector or matrix is a borderline case.)
Mar 29 2011
next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
dsimcha:

Can you please give an example of where <=, >, etc. are useful for representing
set operations?  My naive opinion (i.e. without understanding your use case) is
that using comparison operators to represent anything besides partial or total
ordering is a severe abuse of operator overloading.<

recent Python versions have a built-in set type, I use them very often, so in the dlibs1 I have implemented a set struct with the same API, you see it spread here: http://docs.python.org/library/stdtypes.html#set Most set operations are doable both with an operator and a with method with an English name (the main difference is that the methods accept a generic iterable too beside a set, while operators require both operators to be set). If you try to implement the issubset/isSubset, opCmp is not enough, because as you say a full opCmp can't be defined on sets, in D we can't overload <= >= among sets. This is not terrible, because for those two operations I define only the method with English name, but this is a small limit of opCmp. In expression templates you are able to use the same solution. Is this usage for the set API operator overloading abuse? I am not sure. I think it's acceptablre. Bye, bearophile
Mar 29 2011
parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from bearophile (bearophileHUGS lycos.com)'s article
 This is not terrible, because for those two operations I define only the method

are able to use the same solution.
 Is this usage for the set API operator overloading abuse? I am not sure. I
think

Reasonable people can disagree on this, but I say definitely yes. I don't regret that operator overloading exists in D since I don't believe in throwing the baby out with the bath water when it comes to language design. That said, I believe that unless an operator overload does something conceptually identical to what it does for builtin types, it's an abuse of operator overloading. For example, using '+' for string concatenation, '<<' to write to streams, '+' to append to a stack, or comparison operators for dealing with sets is a severe abuse. I'm even hesitant to use '*' for matrix multiplication since I fail to see how matrix multiplication is conceptually related to scalar multiplication. I wish these were treated as unrelated operations in standard mathematical notation, for example using '.' for matrix multiplication. However, if I ever get around to finishing my SciD enhancements, I will grudgingly defer to de facto standards and use it.
Mar 29 2011
next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
dsimcha:

 Reasonable people can disagree on this, but I say definitely yes.

I think the Python set API was designed by the great Raymond Hettinger, one of the best Python developers regarding data structures, algorithms, etc, and a person able to write the most elegant and clean C code, I respect his skills about as much as Don skills. In years of usage I have had no problems with that API, and from the main Python newsgroup in some years I have not read people complain about that API. For not simple set operations in Python I often use English methods instead of some operators because I prefer my code to be more readable and because in my code the second operand often is not a set, so I can't use operators. In the end I am able to survive even without operator overloading :-) In Bugzilla so far I have never added an enhancement request regarding opCmp. Bye, bearophile
Mar 29 2011
parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 30.03.2011 1:02, bearophile wrote:
   the second operand often is not a set, so I can't use operators.

Implementing simplistic vector struct I made * to work on both vectors (meaning dot product) and scalars (meaning scaling). Template constraints + opBinaryRight for the win! P.S. Though I'd prefer separate functions for that dot and cross product. -- Dmitry Olshansky
Mar 30 2011
parent bearophile <bearophileHUGS lycos.com> writes:
Dmitry Olshansky:

   the second operand often is not a set, so I can't use operators.


I meant in Python :-) That's the way it is designed, probably because of limits of Python operator overloading. Bye, bearophile
Mar 30 2011
prev sibling parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 30.03.2011 2:14, so wrote:
 On Tue, 29 Mar 2011 22:56:10 +0300, dsimcha <dsimcha yahoo.com> wrote:

 Occasionally i encounter this argument that operator overloading is 
 bad thing when it is abused.
 I don't overload operators offensively myself, i use dot(vec, vec) 
 cross(vec, vec) for example because there is not a suitable operator 
 and these names suits much better.

 On the other hand i am not against languages being flexible, quite 
 contrary i don't call it a language if it is not.
 OO is an impressive tool and we need tools like this for better 
 libraries. You can't change a language for a long time but you can 
 update a library in very short period of time.

 vec add(a, b) { return a.x - b.x }
 vec operator+(a, b) { return a.x - b.x }

 Is there a difference?

The second one plays havoc with parsing :) It's not that it's such a big problem but .. BTW when does + denotes a difference? -- Dmitry Olshansky
Mar 30 2011
parent reply Daniel Gibson <metalcaedes gmail.com> writes:
Am 30.03.2011 22:34, schrieb Dmitry Olshansky:
 On 30.03.2011 2:14, so wrote:
 On Tue, 29 Mar 2011 22:56:10 +0300, dsimcha <dsimcha yahoo.com> wrote:

 Occasionally i encounter this argument that operator overloading is
 bad thing when it is abused.
 I don't overload operators offensively myself, i use dot(vec, vec)
 cross(vec, vec) for example because there is not a suitable operator
 and these names suits much better.

 On the other hand i am not against languages being flexible, quite
 contrary i don't call it a language if it is not.
 OO is an impressive tool and we need tools like this for better
 libraries. You can't change a language for a long time but you can
 update a library in very short period of time.

 vec add(a, b) { return a.x - b.x }
 vec operator+(a, b) { return a.x - b.x }

 Is there a difference?

The second one plays havoc with parsing :) It's not that it's such a big problem but .. BTW when does + denotes a difference?

(Probably) Never.. I think his point is that using a bad operator-overload (overload the "+" operator for subtracting) isn't worse than using a bad function name (like "add" when you're really subtracting). Cheers, - Daniel
Mar 30 2011
parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 31.03.2011 0:39, Daniel Gibson wrote:
 Am 30.03.2011 22:34, schrieb Dmitry Olshansky:
 On 30.03.2011 2:14, so wrote:
 On Tue, 29 Mar 2011 22:56:10 +0300, dsimcha <dsimcha yahoo.com> wrote:

 Occasionally i encounter this argument that operator overloading is
 bad thing when it is abused.
 I don't overload operators offensively myself, i use dot(vec, vec)
 cross(vec, vec) for example because there is not a suitable operator
 and these names suits much better.

 On the other hand i am not against languages being flexible, quite
 contrary i don't call it a language if it is not.
 OO is an impressive tool and we need tools like this for better
 libraries. You can't change a language for a long time but you can
 update a library in very short period of time.

 vec add(a, b) { return a.x - b.x }
 vec operator+(a, b) { return a.x - b.x }

 Is there a difference?

The second one plays havoc with parsing :) It's not that it's such a big problem but .. BTW when does + denotes a difference?

(Probably) Never.. I think his point is that using a bad operator-overload (overload the "+" operator for subtracting) isn't worse than using a bad function name (like "add" when you're really subtracting).

Thanks, I see now. Next time I'd better read the whole thread first... -- Dmitry Olshansky
Mar 30 2011
prev sibling parent reply KennyTM~ <kennytm gmail.com> writes:
On Mar 30, 11 03:15, dsimcha wrote:
 == Quote from bearophile (bearophileHUGS lycos.com)'s article
 The operator overloading done with opCmp is too much coarse even if you want to

Can you please give an example of where<=,>, etc. are useful for representing set operations? My naive opinion (i.e. without understanding your use case) is that using comparison operators to represent anything besides partial or total ordering is a severe abuse of operator overloading. (Their use to represent ordering of corresponding elements of a vector or matrix is a borderline case.)

If 'a <= b' means 'a' is a subset of 'b', then (Set, <=) does form a partial order. That said, the current opCmp design is capable of comparing sets and any partial orders if the return type can be relaxed to 'float': if (a == b) return 0; else if (a is subset of b) return -1; else if (b is subset of a) return 1; else /* unordered */ return NaN;
Mar 29 2011
parent dsimcha <dsimcha yahoo.com> writes:
== Quote from KennyTM~ (kennytm gmail.com)'s article
 On Mar 30, 11 03:15, dsimcha wrote:
 == Quote from bearophile (bearophileHUGS lycos.com)'s article
 The operator overloading done with opCmp is too much coarse even if you want to

Can you please give an example of where<=,>, etc. are useful for representing set operations? My naive opinion (i.e. without understanding your use case) is that using comparison operators to represent anything besides partial or total ordering is a severe abuse of operator overloading. (Their use to represent ordering of corresponding elements of a vector or matrix is a borderline case.)

partial order. That said, the current opCmp design is capable of comparing sets and any partial orders if the return type can be relaxed to 'float': if (a == b) return 0; else if (a is subset of b) return -1; else if (b is subset of a) return 1; else /* unordered */ return NaN;

Technically you're right, but I question whether thinking of this as an ordering is ever useful in practice.
Mar 29 2011
prev sibling next sibling parent spir <denis.spir gmail.com> writes:
On 03/29/2011 09:15 PM, dsimcha wrote:
 == Quote from bearophile (bearophileHUGS lycos.com)'s article
 The operator overloading done with opCmp is too much coarse even if you want to

Can you please give an example of where<=,>, etc. are useful for representing set operations? My naive opinion (i.e. without understanding your use case) is that using comparison operators to represent anything besides partial or total ordering is a severe abuse of operator overloading. (Their use to represent ordering of corresponding elements of a vector or matrix is a borderline case.)

Agreed. Wild guess: maybe Bearophile meant < <= > >= as operators for subset/superset predicates? Anyway, this is a very different idea. A different, far less abusing, use of those operators on sets may be to compare cardinality, as in the original theory of natural numbers as sets; here, I guess, the analogy is far more meaningful and totally consistent. Denis -- _________________ vita es estrany spir.wikidot.com
Mar 29 2011
prev sibling parent enuhtac <enuhtac_lists gmx.de> writes:
Am 29.03.2011 21:15, schrieb dsimcha:
 == Quote from bearophile (bearophileHUGS lycos.com)'s article
 The operator overloading done with opCmp is too much coarse even if you want to

Can you please give an example of where <=, >, etc. are useful for representing set operations? My naive opinion (i.e. without understanding your use case) is that using comparison operators to represent anything besides partial or total ordering is a severe abuse of operator overloading. (Their use to represent ordering of corresponding elements of a vector or matrix is a borderline case.)

possible of course and Matlab or Python use this feature which significantly simplifies some operations, but if you consider performance (and that is what you do if you think about expression templates) this is not a good practice as temporary bool vectors are generated. In my case the use of expression templates is twofold: I expect to have some multidimensional templated array variable type, let's call it 'Array', that should support expression templates for algebraic operations. For this purpose comparison operators are not needed (normaly you use reductions instead). But additionally I would like to use expression templates to parse expressions that are used to automatically generate device depend code. In one of my previous posts I gave an example. These expression templates do not work on sets but on scalar expressions. So comparison operators can be useful. E.g.: auto case1 = v[I] < 0.0; auto case2 = !case1; auto result = case1 * v[I] + case2 * v[I+1]; This code mimics the behaviour of an if ... else construct. The difference is that both cases are computed and combined into the result so internally no branches are necessary. This is used to circumvent program path divergence on GPU devices. Also I suppose that this type of code is more efficient on standard CPUs as there are no branch prediction failures. I use scalar expressions to build complex operators that work on arrays. To give an example that includes both types of expression templates I imagine code like this: class Array( T ) { ... }; class Operator( Expr ) { ... }; Operator!( result[I] = (v[I+1] - v[I-1])/h ) derivative; Array!double a, b, c; b = derivative( a ); c = a + b; result, v and I need to be predefined (global) variables of whatever type that encode input and output parameters of operators (maybe result could be omitted) and the position in the array. As I now understand, expression templates are normally used for set operations. For this purpose you normally do not need comparison operators so D is well suited. But I would like to use expression templates in a more general way that is obviously not standard. So D lacks the necessary support. It's a pity...
Mar 31 2011
prev sibling next sibling parent enuhtac <enuhtac_lists gmx.de> writes:
Am 28.03.2011 02:19, schrieb Robert Jacques:
 Hmm... I don't know you're use case exactly, but it sounds like a case
 of operator overload abuse. The design of opCmp was inspired by the
 amount of bug prone repetition that happens with C++ style comparison
 operators. Furthermore, both opCmp and opEquals have fixed return
 types in order to limit abuse. (D also prevents the overload of
 certain operators for the same reason). The main reason behind
 expression templates is to avoid costly intermediates, but the
 expression is always going to be heavier weight than an int, so why
 can't you evaluated the expression then and there?

If my usage of opCmp is an overload abuse then expression templates are an abuse of D. Maybe this is true, I'm not sure. Clearly opCmp and opEquals were not designed with expression templates in mind. What I would like to achieve is to generate source code from an expression. E.g.: expression: lapl[I,J] = (v[I-1,J] + v[I+1,J] + v[I,J-1] + v[I,J+1]) / h^^2 generated source code: for( j = 0; j < ny; ++j ) for( i = 0; i < nx; ++i ) lap[idx(i,j)] = (v[idx(i-1,j)] + v[idx(i+1,j)] + v[idx(i,j-1)] + v[idx(i,j+1)]) / h^^2; If this is D source code it can be immediately be compiled using mixin(). But it is not necessarily D source code, it could also be OpenCL source code for example. So I'm trying to implement an abstraction layer that enables me to formulate expressions and algorithms independant from the the device they are executed on. A software written on top of this abtraction layer would run on CPU or GPU without any modifications. Of course it is necessary to pass some additional hints about the structure of the expression to the code generator to enable specific optimizations - but I think this can be easily done. The first step to implement such a framework is to parse the expression. I thought expression templates would be the easiest way to do so (as compared to string parsing). Also this automatically ensures that parsing is done at compile time which is necessary for the use of mixin() of course. Although not shown above I definitely need comparison operators for the algorithms I would like to implement (e.g. Godunov type advection schemes for the simulation of compressible fluid flows). Regards, enuhtac
Mar 29 2011
prev sibling next sibling parent "Robert Jacques" <sandford jhu.edu> writes:
On Tue, 29 Mar 2011 08:24:01 -0400, enuhtac <enuhtac_lists gmx.de> wrote:

 Am 28.03.2011 02:19, schrieb Robert Jacques:
 Hmm... I don't know you're use case exactly, but it sounds like a case
 of operator overload abuse. The design of opCmp was inspired by the
 amount of bug prone repetition that happens with C++ style comparison
 operators. Furthermore, both opCmp and opEquals have fixed return
 types in order to limit abuse. (D also prevents the overload of
 certain operators for the same reason). The main reason behind
 expression templates is to avoid costly intermediates, but the
 expression is always going to be heavier weight than an int, so why
 can't you evaluated the expression then and there?

If my usage of opCmp is an overload abuse then expression templates are an abuse of D. Maybe this is true, I'm not sure. Clearly opCmp and opEquals were not designed with expression templates in mind. What I would like to achieve is to generate source code from an expression. E.g.: expression: lapl[I,J] = (v[I-1,J] + v[I+1,J] + v[I,J-1] + v[I,J+1]) / h^^2 generated source code: for( j = 0; j < ny; ++j ) for( i = 0; i < nx; ++i ) lap[idx(i,j)] = (v[idx(i-1,j)] + v[idx(i+1,j)] + v[idx(i,j-1)] + v[idx(i,j+1)]) / h^^2; If this is D source code it can be immediately be compiled using mixin(). But it is not necessarily D source code, it could also be OpenCL source code for example. So I'm trying to implement an abstraction layer that enables me to formulate expressions and algorithms independant from the the device they are executed on. A software written on top of this abtraction layer would run on CPU or GPU without any modifications. Of course it is necessary to pass some additional hints about the structure of the expression to the code generator to enable specific optimizations - but I think this can be easily done. The first step to implement such a framework is to parse the expression. I thought expression templates would be the easiest way to do so (as compared to string parsing). Also this automatically ensures that parsing is done at compile time which is necessary for the use of mixin() of course. Although not shown above I definitely need comparison operators for the algorithms I would like to implement (e.g. Godunov type advection schemes for the simulation of compressible fluid flows). Regards, enuhtac

Makes sense. I think, particularly if you're thinking about targeting OpenCl, etc, than instead of using <=, etc, you should use a higher order primitive, like min, filter or map, as this information becomes critical to implementation selection. I've used vectorized booleans in Matlab before, and found that while the syntax is short and sweet, the usage is always a shortcut to another concept.
Mar 29 2011
prev sibling next sibling parent Caligo <iteronvexor gmail.com> writes:
enuhtac, may I ask what you are going to use the expression templates
for? linear algebra library? is it an open source project?
Mar 29 2011
prev sibling next sibling parent Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
Oh my, the C++ streams syntax. I hated that thing.
Mar 29 2011
prev sibling parent so <so so.so> writes:
On Tue, 29 Mar 2011 22:56:10 +0300, dsimcha <dsimcha yahoo.com> wrote:

Occasionally i encounter this argument that operator overloading is bad  
thing when it is abused.
I don't overload operators offensively myself, i use dot(vec, vec)  
cross(vec, vec) for example because there is not a suitable operator and  
these names suits much better.

On the other hand i am not against languages being flexible, quite  
contrary i don't call it a language if it is not.
OO is an impressive tool and we need tools like this for better libraries.  
You can't change a language for a long time but you can update a library  
in very short period of time.

vec add(a, b) { return a.x - b.x }
vec operator+(a, b) { return a.x - b.x }

Is there a difference?
Mar 29 2011