[Proto] implementing an computer algebra system with proto
Hi all, considering the following expression created with proto: "3 *var_+5=2; .. The tree would be : = / \ + 2 / \ * 5 / \ 3 var_ Here the term "var_" is somewhat a placeholder. I wonder wheter it is possible now to change the structure of the tree. That is i want to define a grammar that is able to produce another expression like this. "var_=(2-5)/3;" In tree: = / \ var_ div / \ - 3 / \ 2 5 With this expression i can now define a context that return the final result of the right hand side. But is this possible in proto with the existing functions? This situation is somewhat different from the examples in the documentation. Here i dont want to replace the child node. The whole structure of the input tree should be transformed in another one. Cheers Kim Tang
Kim Kuen Tang wrote:
Hi all,
considering the following expression created with proto:
"3 *var_+5=2;
.. The tree would be : = / \ + 2 / \ * 5 / \ 3 var_
Here the term "var_" is somewhat a placeholder.
I wonder wheter it is possible now to change the structure of the tree. That is i want to define a grammar that is able to produce another expression like this.
"var_=(2-5)/3;"
In tree:
= / \ var_ div / \ - 3 / \ 2 5
With this expression i can now define a context that return the final result of the right hand side. But is this possible in proto with the existing functions?
Yes.
This situation is somewhat different from the examples in the documentation. Here i dont want to replace the child node. The whole structure of the input tree should be transformed in another one.
A general equation solver will be challenging to write, but should be possible. You'll need to familiarize yourself with Proto grammars and transforms. Here is a toy example to get you started. Hope it helps. #include <iostream> #include <boost/proto/proto.hpp> namespace mpl = boost::mpl; namespace proto = boost::proto; namespace fusion = boost::fusion; using proto::_; struct placeholder { friend std::ostream &operator <<(std::ostream &sout, placeholder) { return sout << "var_"; } }; proto::terminal<placeholder>::type const var_ = {{}}; // Work around annoyng msvc compiler bugs ... #if BOOST_WORKAROUND(BOOST_MSVC, BOOST_TESTED_AT(1500)) #define _left(x) call<proto::_left(x)> #define _right(x) call<proto::_right(x)> #define _make_minus(x,y) call<proto::_make_minus(x,y)> #define _make_assign(x,y) call<proto::_make_assign(x,y)> #endif struct Solve : proto::or_< // Solved: proto::assign<proto::terminal<placeholder>, _> // Rewrite "var_ + x = y" to "var_ = y - x" , proto::when< proto::assign< proto::plus<proto::terminal<placeholder>, _> , _ > , proto::_make_assign( proto::_left(proto::_left) , proto::_make_minus( proto::_right , proto::_right(proto::_left) ) ) > > {}; int main() { proto::display_expr( var_ + 1 = 2 ); proto::display_expr( Solve()( var_ + 1 = 2 ) ); } It displays the following:
assign( plus( terminal(var_) , terminal(1) ) , terminal(2) ) assign( terminal(var_) , minus( terminal(2) , terminal(1) ) )
HTH, -- Eric Niebler BoostPro Computing http://www.boostpro.com
"Eric Niebler" <eric@boost-consulting.com> wrote in message news:4978F428.8080107@boost-consulting.com...
A general equation solver will be challenging to write, but should be possible. You'll need to familiarize yourself with Proto grammars and transforms. Here is a toy example to get you started. Hope it helps.
Suppose you want to move a series of additions to the right hand side. For example, transforming "var_ + 1 + 3 = 2" into "var_ = 2 - 3 - 1". Is there a general way to iterate the Solve() transform until all the plusses are consumed? Or do you need multiple calls to Solve(), e.g. "proto::display_expr( Solve()Solve()( var_ + 1 + 3 = 2 ) );" Thanks, Dave Jenkins
Dave Jenkins schrieb:
"Eric Niebler" <eric@boost-consulting.com> wrote in message news:4978F428.8080107@boost-consulting.com...
A general equation solver will be challenging to write, but should be possible. You'll need to familiarize yourself with Proto grammars and transforms. Here is a toy example to get you started. Hope it helps.
Thank you very much for this starting project.
Suppose you want to move a series of additions to the right hand side. For example, transforming "var_ + 1 + 3 = 2" into "var_ = 2 - 3 - 1".
Is there a general way to iterate the Solve() transform until all the plusses are consumed? Or do you need multiple calls to Solve(), e.g. "proto::display_expr( Solve()Solve()( var_ + 1 + 3 = 2 ) );"
The grammar Solve should call himself recursively until it matches a desired expression. The stopping rule is the grammar "proto::when<proto::assign<proto::terminal<placeholder>, _> >" . So once the grammar "proto::when< proto::assign< proto::plus<proto::terminal<placeholder>, _>, _ > ,proto::_make_assign( proto::_left(proto::_left) , proto::_make_minus( proto::_right, proto::_right(proto::_left) ) ) >" is extended with the feature of calling Solve recursively, then multiple calls to Solve is not needed. (I am trying to implement this feature.) Btw Eric, do you plan to give a session in proto in boostcon 09? With regards, Kim Tang
Kim Kuen Tang wrote:
Dave Jenkins schrieb:
Suppose you want to move a series of additions to the right hand side. For example, transforming "var_ + 1 + 3 = 2" into "var_ = 2 - 3 - 1".
Is there a general way to iterate the Solve() transform until all the plusses are consumed? Or do you need multiple calls to Solve(), e.g. "proto::display_expr( Solve()Solve()( var_ + 1 + 3 = 2 ) );"
The grammar Solve should call himself recursively until it matches a desired expression. The stopping rule is the grammar
"proto::when<proto::assign<proto::terminal<placeholder>, _> >" .
So once the grammar "proto::when< proto::assign< proto::plus<proto::terminal<placeholder>, _>, _ > ,proto::_make_assign( proto::_left(proto::_left) , proto::_make_minus( proto::_right, proto::_right(proto::_left) ) ) >" is extended with the feature of calling Solve recursively, then multiple calls to Solve is not needed. (I am trying to implement this feature.)
That's exactly the right approach. With Proto grammars and transforms, you replace iteration with recursion.
Btw Eric, do you plan to give a session in proto in boostcon 09?
No, but I gave a session about Proto at the last 2 boostcons, and the slides are online here: http://www.boostcon.com/site-media/var/sphene/sphwiki/attachment/2009/01/26/... HTH, -- Eric Niebler BoostPro Computing http://www.boostpro.com
Dave Jenkins schrieb:
"Eric Niebler" <eric@boost-consulting.com> wrote in message news:4978F428.8080107@boost-consulting.com...
A general equation solver will be challenging to write, but should be possible. You'll need to familiarize yourself with Proto grammars and transforms. Here is a toy example to get you started. Hope it helps.
Suppose you want to move a series of additions to the right hand side. For example, transforming "var_ + 1 + 3 = 2" into "var_ = 2 - 3 - 1".
Is there a general way to iterate the Solve() transform until all the plusses are consumed? Or do you need multiple calls to Solve(), e.g. "proto::display_expr( Solve()Solve()( var_ + 1 + 3 = 2 ) );"
Hi Dave, this version of Solve "struct Solve : proto::or_< // Solved: proto::assign<proto::terminal<placeholder>, _> // Rewrite "var_ + x = y" to "var_ = y - x" , proto::when< proto::assign< proto::plus<proto::terminal<placeholder>, _>, _ > ,Solve(proto::_make_assign( proto::_left(proto::_left) , proto::_make_minus( proto::_right, proto::_right(proto::_left) ) ) ) > , proto::when< proto::assign< proto::minus<proto::terminal<placeholder>, _>, _ > ,Solve(proto::_make_assign( proto::_left(proto::_left) , proto::_make_plus( proto::_right, proto::_right(proto::_left) ) ) ) >
{}; "
has the feature of calling itsel recursively. So writing "Solve()( var_ + 1 + 3 = 2 )" is enough to produce "var_ = 2-1-3". It takes me about 1 to 2 hour to figure this out. So i would say that proto is not difficult to learn and you really will gain more. The next step will be to extend the grammar with the feature of transforming such expression "1+2+var_+3=4" into this "var_=4-1-2-3". Cheers Kim Tang
Thanks, Dave Jenkins
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
"Kim Kuen Tang" <kuentang@vodafone.de> wrote in message news:497F760C.1030408@vodafone.de...
this version of Solve has the feature of calling itsel recursively. So writing "Solve()( var_ + 1 + 3 = 2 )" is enough to produce "var_ = 2-1-3". It takes me about 1 to 2 hour to figure this out. So i would say that proto is not difficult to learn and you really will gain more.
Thanks, Kim Tang. I see that your example works. However, when I tried playing with it I found one mystery. It seems that any placeholder will match, not just the one you specify in the grammar. Below is an example program showing what I mean. I would expect that only placeholder1 would match, but both placeholder1 and placeholder2 match and produce the same output. I even tried using proto::exact to get the program to reject placeholder2, but that made no difference. #include <iostream> #include <boost/proto/proto.hpp> namespace mpl = boost::mpl; namespace proto = boost::proto; namespace fusion = boost::fusion; using proto::_; // Work around annoyng msvc compiler bugs ... #if BOOST_WORKAROUND(BOOST_MSVC, BOOST_TESTED_AT(1500)) #define _left(x) call<proto::_left(x)> #define _right(x) call<proto::_right(x)> #define _make_minus(x,y) call<proto::_make_minus(x,y)> #define _make_plus(x,y) call<proto::_make_plus(x,y)> #define _make_assign(x,y) call<proto::_make_assign(x,y)> #endif struct placeholder1 { friend std::ostream &operator <<(std::ostream &sout, placeholder1) { return sout << "var1_"; } }; struct placeholder2 { friend std::ostream &operator <<(std::ostream &sout, placeholder2) { return sout << "var2_"; } }; proto::terminal<placeholder1>::type const var1_ = {{}}; proto::terminal<placeholder2>::type const var2_ = {{}}; struct Solve : proto::when< // Match "var1_ + x = y" proto::assign< proto::plus< proto::terminal<proto::exact<placeholder1>> , _> , _ > // Rewrite as "var1_ = y - x" , proto::_make_assign( proto::_left(proto::_left) , proto::_make_minus( proto::_right, proto::_right(proto::_left) ) ) > {}; int main() { proto::display_expr( var1_ + 1 = 2 ); proto::display_expr( Solve()( var1_ + 1 = 2 ) ); proto::display_expr( var2_ + 1 = 2 ); proto::display_expr( Solve()( var2_ + 1 = 2 ) ); }
The next step will be to extend the grammar with the feature of transforming such expression "1+2+var_+3=4" into this "var_=4-1-2-3".
I would be interested in your solution to this also. Thanks, Dave Jenkins
Dave Jenkins wrote:
It seems that any placeholder will match, not just the one you specify in the grammar.
Below is an example program showing what I mean. I would expect that only placeholder1 would match, but both placeholder1 and placeholder2 match and produce the same output. I even tried using proto::exact to get the program to reject placeholder2, but that made no difference.
<snip> Hi Dave, You're passing an expression to a grammar to be evaluated with its transforms. That expression must match the grammar. It's undefined behavior if it doesn't, and in this case, it doesn't. "Performing the transform" falls withing UB. It would be possible to add a compile-time check to all grammars function call operators to catch this error, but that comes with a compile-time cost. -- Eric Niebler BoostPro Computing http://www.boostpro.com
"Eric Niebler" <eric@boost-consulting.com> wrote in message news:49807DB5.2080307@boost-consulting.com...
You're passing an expression to a grammar to be evaluated with its transforms. That expression must match the grammar. It's undefined behavior if it doesn't, and in this case, it doesn't. "Performing the transform" falls withing UB.
It would be possible to add a compile-time check to all grammars function call operators to catch this error, but that comes with a compile-time cost.
I think it would be a useful check. Could you either (1) always check in proto::exact (2) check when a compile time flag is defined
Dave Jenkins wrote:
"Eric Niebler" <eric@boost-consulting.com> wrote in message news:49807DB5.2080307@boost-consulting.com...
You're passing an expression to a grammar to be evaluated with its transforms. That expression must match the grammar. It's undefined behavior if it doesn't, and in this case, it doesn't. "Performing the transform" falls withing UB.
It would be possible to add a compile-time check to all grammars function call operators to catch this error, but that comes with a compile-time cost.
I think it would be a useful check. Could you either (1) always check in proto::exact
That would essentially involve a full evaluation.
(2) check when a compile time flag is defined
That is not a half-bad suggestion. It's funny that we have NDEBUG to avoid costly runtime checks but no equivalent for costly compile-time checks. I've never particularly cared for the "N" in "NDEBUG" ... it seems the wrong default. Perhaps we can have a boost-wide macro for expensive compile-time checks. How about BOOST_COMPILE_TIME_DEBUG? -- Eric Niebler BoostPro Computing http://www.boostpro.com
"Eric Niebler" <eric@boost-consulting.com> wrote in message news:49808FDC.5040006@boost-consulting.com...
That is not a half-bad suggestion. It's funny that we have NDEBUG to avoid costly runtime checks but no equivalent for costly compile-time checks.
I've never particularly cared for the "N" in "NDEBUG" ... it seems the wrong default. Perhaps we can have a boost-wide macro for expensive compile-time checks. How about BOOST_COMPILE_TIME_DEBUG?
I think a BOOST_COMPILE_TIME_DEBUG flag is a good idea. I was surprised that transforming an invalid expression produced exactly the same output as transforming a valid expression. It was undetectable that you were depending on compile time UB. To be sure that you aren't getting compile time UB, you have to test each expression against each transform grammar for a match. I doubt people will think to do that without help. Regards, Dave Jenkins
Dave Jenkins wrote:
"Eric Niebler" <eric@boost-consulting.com> wrote in message news:49808FDC.5040006@boost-consulting.com...
That is not a half-bad suggestion. It's funny that we have NDEBUG to avoid costly runtime checks but no equivalent for costly compile-time checks.
I've never particularly cared for the "N" in "NDEBUG" ... it seems the wrong default. Perhaps we can have a boost-wide macro for expensive compile-time checks. How about BOOST_COMPILE_TIME_DEBUG?
I think a BOOST_COMPILE_TIME_DEBUG flag is a good idea.
I was surprised that transforming an invalid expression produced exactly the same output as transforming a valid expression. It was undetectable that you were depending on compile time UB.
To be sure that you aren't getting compile time UB, you have to test each expression against each transform grammar for a match. I doubt people will think to do that without help.
I have the same idea a while back. I'll suggest not making it a flag but an integer that gives the level of debugging. That way, you have 0 == no CT debug, 1..3 CT debug levels. Regards, -- Joel de Guzman http://www.boostpro.com http://spirit.sf.net
Dave Jenkins schrieb:
Below is an example program showing what I mean. I would expect that only placeholder1 would match, but both placeholder1 and placeholder2 match and produce the same output. I even tried using proto::exact to get the program to reject placeholder2, but that made no difference.
I see that this is a problem. (What does UB stand for?) But can a correct implemented grammar be a workaround? Perhaps we can first check wehter var1_ appears in the expression. If not we can return the expression unmodified. Cheers Kim Tang
"Kim Kuen Tang" <kuentang@vodafone.de> wrote in message news:4980CB95.2010706@vodafone.de...
I see that this is a problem. (What does UB stand for?)
UB = Undefined Behavior (the compiler can crash, produce wrong results, or anything else)
But can a correct implemented grammar be a workaround?
The grammar was correct, but it was given an invald expression (that sort-of looked valid).
Perhaps we can first check whether var1_ appears in the expression. If not we can return the expression unmodified.
The way to check if the expression is valid for a grammar is something like the code below. I'm hoping Eric can automatically do this check when a compile-time debug flag is defined. Regards, Dave Jenkins template< typename Expr > void Solve_check( Expr const & expr ) { if ( !proto::matches< Expr, Solve >::value ) { std::cout << "Expression does not match grammar\n\n"; } } int main() { Solve_check(var_ + 1 = 2); proto::display_expr( var_ + 1 = 2 ); proto::display_expr( Solve()( var_ + 1 = 2 ) ); }
Dave Jenkins wrote:
"Kim Kuen Tang" wrote:
Perhaps we can first check whether var1_ appears in the expression. If not we can return the expression unmodified.
The way to check if the expression is valid for a grammar is something like the code below. I'm hoping Eric can automatically do this check when a compile-time debug flag is defined.
The way I'll do this is add an MPL assert that the expression matches the grammar before invoking its transform. I can do this in proto::transform::operator(), and I can compile it conditionally only if BOOST_COMPILE_TIME_DEBUG is defined. -- Eric Niebler BoostPro Computing http://www.boostpro.com
"Kim Kuen Tang" <kuentang@vodafone.de> wrote in message news:497F760C.1030408@vodafone.de...
The next step will be to extend the grammar with the feature of transforming such expression "1+2+var_+3=4" into this "var_=4-1-2-3".
Hi Kim Tang, I think the attached program solves that problem. The problem I've been working on is to use the distributive law to simplify expressions at compile time. For example, I'd like to transform "var_ * 2 + var_ * 3 = 4" to "var_ * (2 + 3) = 4". Then, you could transform it to "var_ = 4 / (2 + 3)", all at compile time. Wouldn't that be cool? I think it's possible using Proto, but I haven't worked out the details yet. Any suggestions are welcome. Regards, Dave Jenkins
Dave Jenkins wrote:
"Kim Kuen Tang" wrote:
The next step will be to extend the grammar with the feature of transforming such expression "1+2+var_+3=4" into this "var_=4-1-2-3".
I think the attached program solves that problem.
The problem I've been working on is to use the distributive law to simplify expressions at compile time. For example, I'd like to transform "var_ * 2 + var_ * 3 = 4" to "var_ * (2 + 3) = 4". Then, you could transform it to "var_ = 4 / (2 + 3)", all at compile time. Wouldn't that be cool?
Yes!
I think it's possible using Proto, but I haven't worked out the details yet. Any suggestions are welcome.
<snip> Pretty cool, Dave. I wish I had more time to lend a hand, but you and Kim seem to be doing just fine on your own. It makes me really happy to see folks finding interesting uses for Proto transforms. -- Eric Niebler BoostPro Computing http://www.boostpro.com
I think the attached program solves that problem. eq_solver.cpp
Thank you for posting the compile-time solver code. Specially thanks to Eric N. for writing proto and proposing the sketch of the solution. I few years ago, I tried to experiment writing a mini computer algebra in-C++-for-C++. Think for example, if we want to *implicitly* define a differential equation in the C++-code to be solved numerically by any existing routine which only takes *explicit* differential equation. There were two approaches: A) Every expression could be dynamic (like an dynamic expression-tree generated from a C++-code via a DSEL) and the solver in this case was some run-time transformation between expression-trees. But then I was missing the compile-time efficiency of simple operations (like passing addition terms as described in this topic). In order to improve that, very soon I realized that, *in principle*, B) many (if not all) of the operations could be done at compile-time (using metaprogramming) provided that the problem is well defined at compile time. For the static version (case B), the code became very obfuscated very soon and the my code itself began to be unmanageable. I guess that to really go forward I should have to have invented Proto first. That was of course in the pre-Proto era. It seems that having Proto now opens the opportunity to enjoyably continuing with that project. But I see two problems ahead, 1) The (meta-)code is still obfuscated (but may be the best we can do, at worst it looks like LISP), 2) Even if we manage to write a fairly complete (compile-time) computer algebra there will be two problems 2a) the compilation can become really slow if not overflown (compilers are not yet optimized to do this kind of job). Imagine for example, an automatic derivation meta-code, it will create an unmanageable number of template-expressions very rapidly. (Think of the fourth derivative of sin(exp(x^2)) ) For an automatic integrator is even worst. 2b) as soon as we want to introduce some run-time aspect to the problem, all the static expression-templates should be converted to some dynamic-expression. In case I am not missing something (let me know), it seems that a completely compile-time solution is doomed to become unusable except for very simple operation and difficult to extend. On the other hand a completely dynamic solution is more of what we already have (e.g. maple, mathematica, reduce) and will be no better than them (in any single aspect), an will not take advantage of compilation optimizations (think of interfacing the results with numeric libraries) So I think that a combination of a compile-time solvers and dynamic- time solvers is the only way to make something useful and innovative. Say for example, if we transform template expression only to some degree during compilation and as soon as the problem becomes too complicated (e.g. the expression is too long, or there are many expressions in the compilation stack) we let the run-time code handle the rest of the problem. Any one has any ideas on how to do this in practice? For example, in the original example of this posting, we can handle the outer-most sums at compile time and the product at runtime 1) at compile-time transform "2+var_*5=4" into this "var_*5=4-2" 2) at run-time transform the type "var_*5=4-2" (expression template) into a dynamic-tree (not expression template) representing the same equation"var_*5 = 4-2" and then this into another dynamic-tree "var_= (4-2)/5". It will naturally look like a runtime extension of Proto plus some transformation rules (some of them duplicated from the meta-program part). From the few features I understood from the Proto manual, there is a printing of expression capability that gives me the clue that constructing a run-time tree of an expression is doable. Is that dynamic tree-generation implemented in Proto? Am I trying to reinvent the wheel here? Thanks, Alfredo On Jan 30, 8:38 am, "Dave Jenkins" <da...@jenkins.net> wrote:
"Kim Kuen Tang" <kuent...@vodafone.de> wrote in messagenews:497F760C.1030408@vodafone.de...
The next step will be to extend the grammar with the feature of transforming such expression "1+2+var_+3=4" into this "var_=4-1-2-3".
Hi Kim Tang,
I think the attached program solves that problem.
The problem I've been working on is to use the distributive law to simplify expressions at compile time. For example, I'd like to transform "var_ * 2 + var_ * 3 = 4" to "var_ * (2 + 3) = 4". Then, you could transform it to "var_ = 4 / (2 + 3)", all at compile time. Wouldn't that be cool? I think it's possible using Proto, but I haven't worked out the details yet. Any suggestions are welcome.
Regards, Dave Jenkins
eq_solver.cpp 3KViewDownload
_______________________________________________ Boost-users mailing list Boost-us...@lists.boost.orghttp://lists.boost.org/mailman/listinfo.cgi/boost-users
alfC schrieb:
I think the attached program solves that problem. eq_solver.cpp
Hi Alfredo, thank for your posting.
Thank you for posting the compile-time solver code. Specially thanks to Eric N. for writing proto and proposing the sketch of the solution.
I few years ago, I tried to experiment writing a mini computer algebra in-C++-for-C++. Think for example, if we want to *implicitly* define a differential equation in the C++-code to be solved numerically by any existing routine which only takes *explicit* differential equation.
If the grammar is properly implemented than one can easily switch between the implicit/explicit and crank-nicholson method. This is also the reason why i want to implement the algebra-grammar.
It seems that having Proto now opens the opportunity to enjoyably continuing with that project. But I see two problems ahead, 1) The (meta-)code is still obfuscated (but may be the best we can do, at worst it looks like LISP), 2) Even if we manage to write a fairly complete (compile-time) computer algebra there will be two problems 2a) the compilation can become really slow if not overflown (compilers are not yet optimized to do this kind of job). yes i see that this can be an issue. But it will also be interesting to see how slow the compiler will really become. (Perhaps we can substitute some grammars using preprocessors to increase the compilation time ?)
Imagine for example, an automatic derivation meta-code, it will create an unmanageable number of template-expressions very rapidly. (Think of the fourth derivative of sin(exp(x^2)) ) For an automatic integrator is even worst.
especially for calculating the derivate, the method of automatic differentiation will help to reduce the numbers of template-expressions.
2b) as soon as we want to introduce some run-time aspect to the problem, all the static expression-templates should be converted to some dynamic-expression.
In case I am not missing something (let me know), it seems that a completely compile-time solution is doomed to become unusable except for very simple operation and difficult to extend. On the other hand a completely dynamic solution is more of what we already have (e.g. maple, mathematica, reduce) and will be no better than them (in any single aspect), an will not take advantage of compilation optimizations (think of interfacing the results with numeric libraries)
So I think that a combination of a compile-time solvers and dynamic- time solvers is the only way to make something useful and innovative.
I am not sure if this is possible in proto. Perhaps Eric can give some comments?
Say for example, if we transform template expression only to some degree during compilation and as soon as the problem becomes too complicated (e.g. the expression is too long, or there are many expressions in the compilation stack) we let the run-time code handle the rest of the problem.
Cheers Kim
Dave Jenkins schrieb:
"Kim Kuen Tang" <kuentang@vodafone.de> wrote in message news:497F760C.1030408@vodafone.de...
Hi Kim Tang,
I think the attached program solves that problem.
The problem I've been working on is to use the distributive law to simplify expressions at compile time. For example, I'd like to transform "var_ * 2 + var_ * 3 = 4" to "var_ * (2 + 3) = 4". Then, you could transform it to "var_ = 4 / (2 + 3)", all at compile time. Wouldn't that be cool? I think it's possible using Proto, but I haven't worked out the details yet. Any suggestions are welcome.
Hi Dave, thank you for the code. The grammar looks great. Here is a grammar that is able to perform the distributive law. It is not perfect because it doesnt cover all expressions. struct DistributiveLaw : proto::or_< // Solved: proto::multiplies<proto::terminal<placeholder>, _> // Rewrite "var_ *3+var_*2 to var_*(3+2)" , proto::when< proto::plus< proto::multiplies<proto::terminal<placeholder> ,proto::terminal<_> > ,proto::multiplies<proto::terminal<placeholder> ,proto::terminal<_> > > //, proto::_make_multiplies( proto::terminal<placeholder> , proto::_make_plus( proto::_right, proto::_left ) ) ,proto::_make_multiplies(proto::_left(proto::_left), proto::_make_plus(proto::_right(proto::_left),proto::_right(proto::_right) ) ) >
{};
struct Solve : proto::or_< // Solved: proto::assign<proto::terminal<placeholder>, _> // Rewrite "var_ + x = y" to "var_ = y - x" , proto::when< proto::assign< proto::plus< proto::terminal<placeholder>, _>, _ > , proto::_make_assign( proto::_left(proto::_left) , proto::_make_minus( proto::_right, proto::_right(proto::_left) ) ) >
I am not sure wheter this line is needed.
// Rewrite "x + var_ = y" to "var_ = y - x" , proto::when< proto::assign< proto::plus< _, proto::terminal<placeholder>>, _ > , proto::_make_assign( proto::_right(proto::_left) , proto::_make_minus( proto::_right, proto::_left(proto::_left) ) ) > // Rewrite "x + ? = y" to "Solve(? = y - x)" , proto::when< proto::assign< proto::plus< proto::terminal<_>, _>, _ > , Solve( proto::_make_assign( proto::_right(proto::_left) , proto::_make_minus( proto::_right, proto::_left(proto::_left) ) ) ) > // Rewrite "? + x = y" to "Solve(? = y - x)" , proto::when< proto::assign< proto::plus< _, proto::terminal<_> >, _ > , Solve( proto::_make_assign( proto::_left(proto::_left) , proto::_make_minus( proto::_right, proto::_right(proto::_left) ) ) ) >
{};
Cheers Kim
"Kim Kuen Tang" <kuentang@vodafone.de> wrote in message news:49838C04.3010700@vodafone.de...
Here is a grammar that is able to perform the distributive law. It is not perfect because it doesnt cover all expressions.
Kim, Thanks for the code. It seems like a good start. I'll see if I can broaden it to handle more cases. Regards, Dave Jenkins
Hi Dave and Eric, i have written an grammar to do some transformations on an expression and would like to know your opinions. If the grammar matches the pattern var_+a, then it should transform the tree to var_=(0-a)/1. So the resulting callable transform would be : proto::when< //var_+a proto::plus<proto::terminal<placeholder>, proto::terminal<proto::_> > ,proto::_make_assign( proto::_left ,proto::_make_divides(proto::_make_minus(Zero ,proto::_right),One ) ) How should one implement the two macros Zero and One. My solution is to implement a callable transform like this struct ReturnAsTerminal : proto::callable { template<class Sig> struct result; template<class This, class T> struct result<This(T)> : proto::result_of::as_expr<typename boost::remove_reference<T>::type > {}; template<class T> typename result< ReturnAsTerminal(T const&) >::type operator()(T const& t) const { return proto::as_expr(t); } }; with #define Zero ReturnAsTerminal(mpl::int_<0>() ) #define One ReturnAsTerminal(mpl::int_<1>() ) But is this implementation necessary? Can we use predefined functions in proto to reduce the number of codes? My second question regards the issue of testing the correctness of my transformation. I understand that with proto::matches i am able to test whether a given expression type matches a grammar. But what if i want to test the correctness of my transformation? Is the transformation of the above code really var_=(0-a)/1 and not something else? To test the correctness i use boost::is_same to test the type of the transformation. BOOST_PROTO_AUTO( expr ,var_+a ); BOOST_PROTO_AUTO( result, var_=(ReturnAsTerminal()(mpl::int_<0>())-a)/ReturnAsTerminal()(mpl::int_<1>())); BOOST_MPL_ASSERT( (boost::is_same< boost::result_of<BeginLeft(BOOST_TYPEOF(expr))>::type, BOOST_TYPEOF(result)>) ); Is this enough and is this necessary? Here is the full program: #include <iostream> #include <boost/proto/proto.hpp> #include <boost/proto/proto_typeof.hpp> #include <boost/mpl/int.hpp> #include <boost/type_traits/remove_reference.hpp> #include <boost/type_traits/is_same.hpp> #include <boost/typeof/typeof.hpp> namespace mpl=boost::mpl; namespace proto=boost::proto; namespace fusion=boost::fusion; struct placeholder { friend std::ostream& operator<<(std::ostream& out, placeholder) { return out<<"var_"; } }; proto::terminal<placeholder>::type const var_={{}}; proto::terminal<char>::type const a={'a'}; #if BOOST_WORKAROUND( BOOST_MSVC,BOOST_TESTED_AT(1500) ) #define _left(x) call<proto::_left( proto::call<x> )> #define _right(x) call<proto::_right( proto::call<x> )> #define _make_minus(x,y) call<proto::_make_minus(proto::call<x>, proto::call<y> )> #define _make_plus(x,y) call<proto::_make_plus(proto::call<x>, proto::call<y>)> #define _make_assign(x,y) call<proto::_make_assign(proto::call<x>, proto::call<y>)> #define _make_divides(x,y) call<proto::_make_divides(proto::call<x>, proto::call<y>)> #define _make_multiplies(x,y) call<proto::_make_multiplies(proto::call<x>, proto::call<y>)> #define _make_terminal(x) call<proto::_make_terminal(proto::call<x>)> #endif struct ReturnAsTerminal : proto::callable { template<class Sig> struct result; template<class This, class T> struct result<This(T)> : proto::result_of::as_expr<typename boost::remove_reference<T>::type > {}; template<class T> typename result< ReturnAsTerminal(T const&) >::type operator()(T const& t) const { return proto::as_expr(t); } }; #define Zero ReturnAsTerminal(mpl::int_<0>() ) #define One ReturnAsTerminal(mpl::int_<1>() ) // struct BeginLeft : proto::or_< proto::when< //var_+a proto::plus<proto::terminal<placeholder>, proto::terminal<proto::_> > ,proto::_make_assign( proto::_left ,proto::_make_divides(proto::_make_minus(Zero ,proto::_right),One ) ) > ,proto::when< //var_-a proto::minus<proto::terminal<placeholder>, proto::terminal<proto::_> > ,proto::_make_assign( proto::_left ,proto::_make_divides(proto::_make_plus(Zero,proto::_right),One ) ) > ,proto::when< //var_*a proto::multiplies< proto::terminal<placeholder>, proto::terminal<proto::_> > ,proto::_make_assign( proto::_right ,proto::_make_divides(Zero,proto::_right ) ) > ,proto::when< //var_/a proto::divides< proto::terminal<placeholder>, proto::terminal<proto::_> > ,proto::_make_assign( proto::_left ,proto::_make_divides(Zero,proto::_make_divides(One,proto::_right) ) ) > > {}; int main() { BOOST_PROTO_AUTO( expr ,var_+a ); BOOST_PROTO_AUTO( result, var_=(ReturnAsTerminal()(mpl::int_<0>())-a)/ReturnAsTerminal()(mpl::int_<1>())); BOOST_MPL_ASSERT( (proto::matches<BOOST_TYPEOF(expr) ,BeginLeft>) ); BOOST_MPL_ASSERT( (boost::is_same< boost::result_of<BeginLeft(BOOST_TYPEOF(expr))>::type, BOOST_TYPEOF(result)>) ); std::cout<<" \n ---------------------------------------------------- \n"; return 0; } Thanks for any and all help and comments. Cheers, Kim
Kim Kuen Tang wrote:
Hi Dave and Eric,
i have written an grammar to do some transformations on an expression and would like to know your opinions.
If the grammar matches the pattern var_+a, then it should transform the tree to var_=(0-a)/1. So the resulting callable transform would be :
proto::when< //var_+a proto::plus<proto::terminal<placeholder>, proto::terminal<proto::_> > ,proto::_make_assign( proto::_left ,proto::_make_divides(proto::_make_minus(Zero ,proto::_right),One ) )
How should one implement the two macros Zero and One.
Try this: // default-constructs an int struct Zero : proto::make<int> {}; // initializes and int with a default-constructed mpl::int_<1> // object (which is convertible to an int with value of 1). struct One : proto::make<int(mpl::int_<1>())> {}; HTH, -- Eric Niebler BoostPro Computing http://www.boostpro.com
Hi Eric,
Here is a toy example to get you started.
, proto::when< proto::assign< proto::plus<proto::terminal<placeholder>, _> , _ >
It looks like this "when" matches everything (at least with my compiler), not only plus (as supposed to), for example it matches multiplication as well: proto::display_expr( var_ * 1 = 2 ); proto::display_expr( Solve()( var_ * 1 = 2 ) ); Output: assign( multiplies( // <<<<< multiplication terminal(var_) , terminal(1) ) , terminal(2) ) assign( terminal(var_) , minus( // <<<<< minus terminal(2) , terminal(1) ) ) I'm using proto from boost 1.37.0, gcc 3.4.6. Thanks, Maxim
"MaximYanchenko" <maximyanchenko@yandex.ru> wrote in message news:loom.20090128T054136-488@post.gmane.org...
It looks like this "when" matches everything (at least with my compiler), not only plus (as supposed to), for example it matches multiplication as well: proto::display_expr( var_ * 1 = 2 ); proto::display_expr( Solve()( var_ * 1 = 2 ) );
I think you're seeing the "undefined behavior" we've been discussing. Try adding the following check to your program and see if it asserts. BOOST_MPL_ASSERT(( proto::matches<BOOST_TYPEOF(var_ * 1 = 2 ), Solve>)); Regards, Dave Jenkins
participants (6)
-
alfC -
Dave Jenkins -
Eric Niebler -
Joel de Guzman -
Kim Kuen Tang -
MaximYanchenko