[Proposal] Library which adds n-arity operators support to C++ plus reducing temporaries.
I'm currently working on library "Lazy". Library description: Library eases creation of classes which needs lazy evalution and n-arity operators and I guess will be as efficient as Gnu MP class but with pretty syntax. (Not yet tested but I do believe it is so). Library features are: * n-arity operators support; * operator aliasing, such as a + -b will be computed as a - b; * custom operators; * no unnecessary temporaries during evalution and assigning; * easy usage. Library's sample usage: //Matrix.h #include "lazy.hpp" class transpose_tag {}; //Tag class class Matrix { LAZY_CLASS(Matrix) static lazy::type<Matrix> Matrix_; //Similar to Andrei Alexandrescu's Type2Type template public: Matrix(); Matrix(const Matrix &); void swap(void Matrix &); //Libray won't work without swap function. //If name of your swap function isn't swap then use LAZY_CLASS_EX(Matrix, YourSwapFunctionName) Matrix & operator = (const Matrix &); //lazy constuctors which enables lazy operators Matrix(LAZY_OP(Matix_ + Matrix_)); //Matrix operator +(Matrix, Matrix) Matrix(LAZY_OP(Matrix_ * Matrix_)); //... Matrix(LAZY_OP(-Matrix_); Matrix(LAZY_OP(Matrix_ + Matrix_ * Matrix_)); //ternary operator //Now enable operators LAZY_ENABLE_OP(Matrix_ = Matrix_ + Matrix_); LAZY_ENABLE_OP(Matrix_ = Matrix_ * Matrix_); LAZY_ENABLE_OP(Matrix_ = -Matrix_); LAZY_ENABLE_OP(Matrix_ = Matrix_ + Matrix_ * Matrix_); //Actually we can make declaration of lazy operators and enabling them using only one macro e.g. LAZY_CONSTUCTOR(Matrix_ = Matrix_ * Matrix_ * Matrix_); //Aliasing LAZY_ALIAS(Matrix + -Matrix_ = Matrix_ - Matrix_); //Custom operation Matrix(LAZY_CUSTOM_OP(transpose_tag, (Matrix_))); LAZY_ENABLE_CUSTOM_OP(transpose, Matrix_ = lazy::custom_op<transpose_tag>(Matrix_)); //same as Matrix transpose (const Matrix &) but there won't be any temporary objects }; //Matrix.cpp Matrix::Matrix(LAZY_OP(Matix_ + Matrix_) op) { //Construct matrix object //lhs matrix = op._1 //rhs matrix = op._2 } Matrix::Matrix(LAZY_CUSTOM_OP(transpose_tag, (Matrix_) op) { //Construct matrix object tranposed to op._1 } //etc //Now the use of Matrix class Matrix a, b, c, d; //... a = b + c; //No tempories at all //Using normal practice it will take two temporary objects (no NRVO or RVO ) a = b + -c; //Will be evaluates as a = b - c; No temporaries again //Using normal practice it will take three temporary objects (no NRVO or RVO) a = b + c * d; //Will use ternary operator. No temporaries again a = transpose(b); //Custom lazy operation. No tempories again Maybe the library is very similar to uBLAS's matrix_expression and vector_expression. But with my approach there is no need to code matrix_expression and vector_expression at all and it is easy to create new classes which needs lazy evaluation and n-arity operators. So what do you think? Is there any similar approaches available? Is there any need of such library?
On 03/06/2005 07:59 AM, Pavel Chikulaev wrote:
I'm currently working on library "Lazy".
Library description: Library eases creation of classes which needs lazy evalution and n-arity operators [snip] Library features are: * n-arity operators support; * operator aliasing, such as a + -b will be computed as a - b; [snip] Library's sample usage: [snip] class Matrix { LAZY_CLASS(Matrix) static lazy::type<Matrix> Matrix_; //Similar to Andrei Alexandrescu's [snip] Matrix(LAZY_OP(Matrix_ + Matrix_ * Matrix_)); //ternary operator
//Now enable operators LAZY_ENABLE_OP(Matrix_ = Matrix_ + Matrix_); LAZY_ENABLE_OP(Matrix_ = Matrix_ * Matrix_); LAZY_ENABLE_OP(Matrix_ = -Matrix_); LAZY_ENABLE_OP(Matrix_ = Matrix_ + Matrix_ * Matrix_);
//Actually we can make declaration of lazy operators and enabling them using only one macro e.g. LAZY_CONSTUCTOR(Matrix_ = Matrix_ * Matrix_ * Matrix_);
[snip]
Is there any need of such library?
Maybe. If "aliasing" can convert (a+b+c)*x to a*x+b*x+c*x then maybe it can be used to "normalize" a grammar: X = ('a'|'b'|'c') X | 'd' -> X = 'a'X | 'b'X | 'c'X | 'd' which would enable, I think, conversion to a boolean matrix representation of the First relation of the grammar: X 'a' 'b' 'c' 'd' X 0 1 1 1 1 'a' 0 0 0 0 0 'b' 0 0 0 0 0 'c' 0 0 0 0 0 'd' 0 0 0 0 0 and then the operator* and + could be used to maybe make a lazy transtive closure, First^*, of this relation. Similarly, it could be used for calculation of Last relation and and transitive closure of the transpose of that. These are all needed by the method described here: http://facweb.cs.depaul.edu/tchristopher/grmanl.pdf to generate a parser. In addition to the above, I'd also like to see if the value of a matrix multiplication and addition can be computed at compile time. If so, then I'm guessing that, given enough resources, a spirit grammar (normalized as described above) can be analyzed at compile time and used to generate a parser with compile-time generated look-ahead sets. OK, maybe that's dreaming, but that's me :)
"Larry Evans" <cppljevans@cox-internet.com> wrote in message news:d0fmqa$tfu$1@sea.gmane.org...
Maybe. If "aliasing" can convert (a+b+c)*x to a*x+b*x+c*x then maybe it can be used to "normalize" a grammar: It can convert it easily. In addition to the above, I'd also like to see if the value of a matrix multiplication and addition can be computed at compile time. If so, then I'm guessing that, given enough resources, a spirit grammar (normalized as described above) can be analyzed at compile time and used to generate a parser with compile-time generated look-ahead sets.
OK, maybe that's dreaming, but that's me :) With some restrictions it can be done. For example: template< template<int A11, int A12, int A13>, //As far as I know we can emit the typename name, don't we? template<int A21, int A22, int A23>, template<int A31, int A32, int A33>, > class compile_time_matrix; for compile_time_matrix we can do that. But is what really what you need?
Actually the purpose of the library is to choose best algorithm at compile-time, and then apply it at run-time.
On 03/06/2005 02:17 PM, Pavel Chikulaev wrote:
"Larry Evans" <cppljevans@cox-internet.com> wrote in message [snip] (from Larry Evans' post here: http://article.gmane.org/gmane.comp.lib.boost.devel/119148 )
and then the operator* and + could be used to maybe make a lazy transtive closure, First^*, of this relation. Similarly, it could [snip] In addition to the above, I'd also like to see if the value of a matrix multiplication and addition can be computed at compile time. If so, then I'm guessing that, given enough resources, a spirit grammar (normalized as described above) can be analyzed at compile time and used to generate a parser with compile-time generated look-ahead sets.
Actually the purpose of the library is to choose best algorithm at compile-time, and then apply it at run-time.
Yeah, that's probably where I've misunderstood your library. The values I wanted would all be calculated at runtime; however, I'm afraid the compiler will be overwhelmed and abort (due to max template instantiation depth). Hence, I'm also anticipating I'll may need something like your library. Maybe the expression for transitive closure can be created and then feed with some values to compute the closure. Anyway, what I think will work for compile-time calculation is a combination of fold_seq (see vault under cppljevans/mpl) where the ForwardOp is simply matrix multiplication. Then, if the 1st argument to fold_seq is the a sequence of identical values of some binary relation, M, then the result would be a sequence: { M, M*M, M*M*M, ..., M^n } where n is the size of the 1st arg to fold_seq and the * in the above is simply matrix multiplication, and M^n is M raised to the n-th power. The transitive closure is gotten by maxtrix sum of this. Unfortunately, this is only for types and not values. Maybe you could figure out how to actually use it to calculate the values? If not, I'll try to get to it later.
On 03/06/2005 07:59 AM, Pavel Chikulaev wrote:
I'm currently working on library "Lazy". [snip] Library's sample usage:
//Matrix.h [snip] //lazy constuctors which enables lazy operators Matrix(LAZY_OP(Matix_ + Matrix_)); //Matrix operator +(Matrix, Matrix) Matrix(LAZY_OP(Matrix_ * Matrix_)); //... Matrix(LAZY_OP(-Matrix_); Matrix(LAZY_OP(Matrix_ + Matrix_ * Matrix_)); //ternary operator [snip] So what do you think? Is there any similar approaches available? I've also very curious about how this was done. Many years ago, I read Budd's
_An Apl Compiler_ ( See http://web.engr.oregonstate.edu/~budd/vita/books.html for details ), and IIRC, some of the techniques he used there might be useful for something like this. IOW, he evaluated the data flow for a apl expression and somehow created c code to evaluate the rhs. IIRC, he also mentioned vector machines. Anyway, it may give you some more ideas for lazy evaluation.
"Larry Evans" <cppljevans@cox-internet.com> wrote in message news:d0fomr$2v7$1@sea.gmane.org...
I've also very curious about how this was done. I create operators tree at compile-time of rhs, then I parse it in templates (most challenging). That's all what my library does. Many years ago, I read Budd's _An Apl Compiler_ ( See http://web.engr.oregonstate.edu/~budd/vita/books.html for details ), and IIRC, some of the techniques he used there might be useful for something like this. IOW, he evaluated the data flow for a apl expression and somehow created c code to evaluate the rhs. IIRC, he also mentioned vector machines. Anyway, it may give you some more ideas for lazy evaluation.
I live in Russia, so I think that I can hardly find this book, but if you know where I can get ebook version it would be great.
"Larry Evans" <cppljevans@cox-internet.com> wrote in message news:d0fomr$2v7$1@sea.gmane.org...
I've also very curious about how this was done. I create operators tree at compile-time of rhs, then I parse it using templates (most challenging) and the evaluate the result. That's all what my library does. Many years ago, I read Budd's _An Apl Compiler_ ( See http://web.engr.oregonstate.edu/~budd/vita/books.html for details ), and IIRC, some of the techniques he used there might be useful for something like this. IOW, he evaluated the data flow for a apl expression and somehow created c code to evaluate the rhs. IIRC, he also mentioned vector machines. Anyway, it may give you some more ideas for lazy evaluation.
I live in Russia, so I think that I can hardly find this book, but if you know where I can get ebook version it would be great.
On 03/06/2005 02:53 PM, Pavel Chikulaev wrote:
"Larry Evans" <cppljevans@cox-internet.com> wrote in message news:d0fomr$2v7$1@sea.gmane.org...
I've also very curious about how this was done.
I create operators tree at compile-time of rhs, then I parse it using templates (most challenging) and the evaluate the result.
This "parse it using templates" sound like it might be like the application_parts template in application_parts_test.cpp: http://boost-sandbox.sourceforge.net/vault/index.php?&direction=0&order=&directory=cppljevans/mpl I remember thinking about calling it "parse" also (as I did before for similar problems), but then I was worried people would confuse it with the more conventional meaning of parse. Anyway, application_parts is like mpl::unpack_args in that one of its results is a place_holder expression which, when applied to the other results, gives the original type. With unpack_args, IIUC, the programmer has to explicitly provide the args since, as the name implies, the arguments are "unpacked" leaving just the metafunction.
participants (2)
-
Larry Evans -
Pavel Chikulaev