Re: [proto] Manipulating an expression tree
On 4/15/2011 10:45 PM, Karsten Ahnert wrote: @All: Are somewhere more examples and docs for proto transforms. They are quite complicated and maybe a bit underrepresented in the official users guide. (Funny, I *know* I replied to this, but I don't see it in the archive. Sorry if y'all get this twice.) Have you read the Expressive C++ article series on C++Next? It covers grammars and transforms step-by-step. Here's the first one in the series: http://cpp-next.com/archive/2010/08/expressive-c-introduction/ HTH, -- Eric Niebler BoostPro Computing http://www.boostpro.com ___ proto mailing list proto@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/proto
Re: [proto] Manipulating an expression tree
On 04/08/2011 02:16 PM, Bart Janssens wrote: On Fri, Apr 8, 2011 at 2:11 PM, Karsten Ahnert karsten.ahn...@ambrosys.de wrote: Thank you for your example. I have one question: how do you use (or assign something to) the intermediate values in StoredMatrixExpression? Once the wrapping is done, every wrapped node (multiplies expressions in your case) will have the value member. This can be used from within any primitive transform or context, if you are working on the expression after it is transformed by WrapExpression. So instead of eval(your_expr) you would do something like eval(WrapExpression()(your_expr)) and then you can assume value exists when it is needed. Ok, I think I understand how you replace the nodes, but I don't understand how you parse the tree and how you access the value member. Do you use contexts and eval()? Could you please show a small piece of code? Thanks, Cheers, -- Dr. Karsten Ahnert Ambrosys GmbH - Gesellschaft für Management komplexer Systeme Geschwister-Scholl-Str. 63a D-14471 Potsdam Tel: +4917682001688 Fax: +493319791300 Ambrosys GmbH - Gesellschaft für Management komplexer Systems Gesellschaft mit beschränkter Haftung Sitz der Gesellschaft: Geschwister-Scholl-Str. 63a, 14471 Potsdam Registergericht: Amtsgericht Potsdam, HRB 21228 P Geschäftsführer: Dr. Karsten Ahnert, Dr. Markus Abel ___ proto mailing list proto@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/proto
Re: [proto] Manipulating an expression tree
If you need to compute intermediate values, you can use a transform to build a parallel structure. Do you mean to build an entire new tree, or just to replace some nodes? If only some nodes have associated intermediate result, then you could just replace some nodes. Ok, this is a clear hint. In my current algorithm I use callable contexts to do the work. I think this is more favorable since I have to evaluate the tree N times to obtain the result. Why does that matter? Transforms are almost always a better choice. I think it would be nice to replace some nodes and customizing the evaluation context, such that these nodes can be used to store the intermediates. If you're doing calculation *and* tree transformation, then drop the callable contexts. They can't do the job. First I do tree transformation and then calculation. A Callable context will not do the job, since one only gets the tag of the current node, but not the node itself. So I have to implement my own context. I am not sure if transforms can do that job. It is definitely not possible to obtain the full tree for 10th derivative. Maybe some other tricks are possible with transforms. At the moment I don't understand them in detail, but I will try to change this. Thanks for your advice. ___ proto mailing list proto@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/proto
Re: [proto] Manipulating an expression tree
On Thu, Apr 7, 2011 at 12:45 AM, Karsten Ahnert karsten.ahn...@ambrosys.de wrote: Another question is: can a node have a state. In my algorithm it would be nice, if every proto::multiplies node stores some intermediate values which are used during later evaluations of the tree. I did something similar to this to resolve the issue I had with the Eigen matrix library. I am replacing multiplies nodes with an expression that uses proto::extends to add extra state, in this case a correctly sized matrix to store the temporary matrix Eigen generates. I've attached the header that does the node replacement in all the cases that match the WrappableElementExpressions (Wrap in the header means replacing the node). Note that this header is ripped out of the context of a larger application (used for finite elements), so some stuff will not make sense, but the general idea might be helpful. I am using a primitive transform (WrapMatrixExpression) to do the actual node replacement here. An alternative would be to create a domain, and then use the make_... family of transforms to create nodes in that domain. I went for the primitive transform because it seemed to compile faster and with less memory. I intend to post a more detailed example on how I solved the problem with Eigen later on, with examples that are more stand-alone. Cheers, -- Bart // Copyright (C) 2010 von Karman Institute for Fluid Dynamics, Belgium // // This software is distributed under the terms of the // GNU Lesser General Public License version 3 (LGPLv3). // See doc/lgpl.txt and doc/gpl.txt for the license text. #ifndef CF_Solver_Actions_Proto_ElementExpressionWrapper_hpp #define CF_Solver_Actions_Proto_ElementExpressionWrapper_hpp #include ElementGrammar.hpp namespace CF { namespace Solver { namespace Actions { namespace Proto { /// Matches expressions that can be wrapped struct WrappableElementExpressions : boost::proto::or_ boost::proto::multipliesboost::proto::_, boost::proto::_, boost::proto::function boost::proto::terminal IntegralTagboost::proto::_ , boost::proto::_ , boost::proto::functionboost::proto::terminalLinearizeOp, boost::proto::_, FieldTypes, boost::proto::function boost::proto::terminal SFOp CustomSFOpboost::proto::_ , boost::proto::_ { }; /// Less restricitve grammar to get the result of expressions that are in an integral as well struct LazyElementGrammar : boost::proto::or_ ElementGrammar, ElementMathImplicit // Normally this is only legal inside an integral { }; /// Wraps a given expression, so the value that it represents can be stored inside the expression itself templatetypename ExprT, typename MatrixT struct StoredMatrixExpression : boost::proto::extends ExprT, StoredMatrixExpressionExprT, MatrixT { EIGEN_MAKE_ALIGNED_OPERATOR_NEW typedef boost::proto::extends ExprT, StoredMatrixExpressionExprT, MatrixT base_type; typedef MatrixT ValueT; explicit StoredMatrixExpression(ExprT const expr = ExprT()) : base_type(expr) { } /// Temporary storage for the result of the expression mutable ValueT value; }; struct WrapMatrixExpression : boost::proto::transform WrapMatrixExpression { templatetypename ExprT, typename StateT, typename DataT struct impl : boost::proto::transform_implExprT, StateT, DataT { /// Helper to select if the expression is to be wrapped templatebool, int Dummy = 0 struct WrapperSelector; /// Expression must not be wrapped templateint Dummy struct WrapperSelectorfalse, Dummy { typedef typename impl::expr_param result_type; result_type operator()(typename impl::expr_param expr, typename impl::state_param , typename impl::data_param) { return expr; } }; /// Expression is to be wrapped templateint Dummy struct WrapperSelectortrue, Dummy { /// Calculate the type to store typedef typename boost::remove_consttypename boost::remove_reference typename boost::result_ofLazyElementGrammar(typename impl::expr_param, typename impl::state_param, typename impl::data_param)::type ::type::type ValueT; typedef StoredMatrixExpressiontypename boost::remove_consttypename boost::remove_referenceExprT::type::type, ValueT result_type; result_type operator()(typename impl::expr_param expr, typename impl::state_param, typename impl::data_param) { return result_type(expr); } }; typedef WrapperSelector boost::proto::matchesExprT, WrappableElementExpressions::value ResultSelectorT; typedef typename ResultSelectorT::result_type result_type; result_type operator()(typename impl::expr_param expr, typename impl::state_param state, typename impl::data_param data) { return ResultSelectorT()(expr, state, data); } }; }; /// Grammar to do the expression wrapping struct WrapExpression : boost::proto::or_ boost::proto::when
Re: [proto] Manipulating an expression tree
Why not just write a transform that calculates one derivative and call it N times to get the Nth derivative? Yes, that may be easy if you need two or three higher derivatives. For my application I need 10 to 20 or even more. I guess that currently no compiler can handle such large trees. For example, the simple product rule will result in 2^N terms. But in the case of the product rule, one can use Leibnitz rule: If f(x)=g1(x) g2(x), then the N-th derivative of f(x) is sum_{k=0}^N binomial(N , k ) g1^k(x) g2^(N-k)(x). (g1^k is the k-th derivative of g1). This is exactly the point where I need intermediate values, to store previously calculated values of the derivatives of g1 and g2. Nevertheless, thank you for your example. I am a beginner with proto such that every example is highly illuminating. ___ proto mailing list proto@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/proto
Re: [proto] Manipulating an expression tree
Thank you for your example. I have one question: how do you use (or assign something to) the intermediate values in StoredMatrixExpression? On Thu, Apr 7, 2011 at 12:45 AM, Karsten Ahnert karsten.ahn...@ambrosys.de wrote: Another question is: can a node have a state. In my algorithm it would be nice, if every proto::multiplies node stores some intermediate values which are used during later evaluations of the tree. I did something similar to this to resolve the issue I had with the Eigen matrix library. I am replacing multiplies nodes with an expression that uses proto::extends to add extra state, in this case a correctly sized matrix to store the temporary matrix Eigen generates. I've attached the header that does the node replacement in all the cases that match the WrappableElementExpressions (Wrap in the header means replacing the node). Note that this header is ripped out of the context of a larger application (used for finite elements), so some stuff will not make sense, but the general idea might be helpful. I am using a primitive transform (WrapMatrixExpression) to do the actual node replacement here. An alternative would be to create a domain, and then use the make_... family of transforms to create nodes in that domain. I went for the primitive transform because it seemed to compile faster and with less memory. I intend to post a more detailed example on how I solved the problem with Eigen later on, with examples that are more stand-alone. Cheers, -- Bart ___ proto mailing list proto@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/proto Karsten Ahnert Ambrosys GmbH - Gesellschaft für Management komplexer Systeme Geschwister-Scholl-Str. 63a D-14471 Potsdam Tel: +4917682001688 Fax: +493319791300 Ambrosys GmbH - Gesellschaft für Management komplexer Systems Gesellschaft mit beschränkter Haftung Sitz der Gesellschaft: Geschwister-Scholl-Str. 63a, 14471 Potsdam Registergericht: Amtsgericht Potsdam, HRB 21228 P Geschäftsführer: Karsten Ahnert, Dr. Markus Abel Karsten Ahnert Ambrosys GmbH - Gesellschaft für Management komplexer Systeme Geschwister-Scholl-Str. 63a D-14471 Potsdam Tel: +4917682001688 Fax: +493319791300 Ambrosys GmbH - Gesellschaft für Management komplexer Systems Gesellschaft mit beschränkter Haftung Sitz der Gesellschaft: Geschwister-Scholl-Str. 63a, 14471 Potsdam Registergericht: Amtsgericht Potsdam, HRB 21228 P Geschäftsführer: Karsten Ahnert, Dr. Markus Abel ___ proto mailing list proto@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/proto
Re: [proto] Manipulating an expression tree
On Fri, Apr 8, 2011 at 2:11 PM, Karsten Ahnert karsten.ahn...@ambrosys.de wrote: Thank you for your example. I have one question: how do you use (or assign something to) the intermediate values in StoredMatrixExpression? Once the wrapping is done, every wrapped node (multiplies expressions in your case) will have the value member. This can be used from within any primitive transform or context, if you are working on the expression after it is transformed by WrapExpression. So instead of eval(your_expr) you would do something like eval(WrapExpression()(your_expr)) and then you can assume value exists when it is needed. Cheers, -- Bart ___ proto mailing list proto@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/proto
Re: [proto] Manipulating an expression tree
On Fri, Apr 8, 2011 at 2:03 PM, Karsten Ahnert karsten.ahn...@ambrosys.de wrote: Why not just write a transform that calculates one derivative and call it N times to get the Nth derivative? Yes, that may be easy if you need two or three higher derivatives. For my application I need 10 to 20 or even more. I guess that currently no compiler can handle such large trees. For example, the simple product rule will result in 2^N terms. Point taken. The expressions might get very long. However, you could do an algeabric simplification transform (for example constant propagation) after every derivation step. Thus reducing the number of terms. But in the case of the product rule, one can use Leibnitz rule: If f(x)=g1(x) g2(x), then the N-th derivative of f(x) is sum_{k=0}^N binomial(N , k ) g1^k(x) g2^(N-k)(x). (g1^k is the k-th derivative of g1). This is exactly the point where I need intermediate values, to store previously calculated values of the derivatives of g1 and g2. Nevertheless, thank you for your example. I am a beginner with proto such that every example is highly illuminating. ___ proto mailing list proto@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/proto
Re: [proto] Manipulating an expression tree
On Wed, Apr 6, 2011 at 10:29 PM, Karsten Ahnert karsten.ahn...@ambrosys.de wrote: Is there a direct way to transform an expression tree into another one? For example, is it possible that every proto::plus node is transformed to it left child? I tried to solve this problem via protos build-in transforms without success. It seems that they are suited for evaluation of an existing tree, but I might be wrong. Hi Karsten, I'm pretty sure they can do both. For your example, I think something along the lines of this might work (untested): struct LeftPlus : boost::proto::or_ boost::proto::terminalboost::proto::_, boost::proto::when boost::proto::plusboost::proto::_, boost::proto::_, LeftPlus(boost::proto::_left) , boost::proto::nary_expr boost::proto::_, boost::proto::varargLeftPlus {}; This should recurse through expressions and replace sequences of pluses with the left-most terminal. You may need some other criteria to end the recursion depending on your use case. Disclaimer: I'm relatively new to proto myself, so the experts might have better solutions! Cheers, -- Bart ___ proto mailing list proto@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/proto
Re: [proto] Manipulating an expression tree
Great! It works perfectly, alltough I don't understand the code completely yet. Another question is: can a node have a state. In my algorithm it would be nice, if every proto::multiplies node stores some intermediate values which are used during later evaluations of the tree. Thanks, Karsten On 04/06/2011 10:53 PM, Bart Janssens wrote: On Wed, Apr 6, 2011 at 10:29 PM, Karsten Ahnert karsten.ahn...@ambrosys.de wrote: Is there a direct way to transform an expression tree into another one? For example, is it possible that every proto::plus node is transformed to it left child? I tried to solve this problem via protos build-in transforms without success. It seems that they are suited for evaluation of an existing tree, but I might be wrong. Hi Karsten, I'm pretty sure they can do both. For your example, I think something along the lines of this might work (untested): struct LeftPlus : boost::proto::or_ boost::proto::terminalboost::proto::_, boost::proto::when boost::proto::plusboost::proto::_, boost::proto::_, LeftPlus(boost::proto::_left) , boost::proto::nary_expr boost::proto::_, boost::proto::varargLeftPlus {}; This should recurse through expressions and replace sequences of pluses with the left-most terminal. You may need some other criteria to end the recursion depending on your use case. Disclaimer: I'm relatively new to proto myself, so the experts might have better solutions! Cheers, -- Dr. Karsten Ahnert Ambrosys GmbH - Gesellschaft für Management komplexer Systeme Geschwister-Scholl-Str. 63a D-14471 Potsdam Tel: +4917682001688 Fax: +493319791300 Ambrosys GmbH - Gesellschaft für Management komplexer Systems Gesellschaft mit beschränkter Haftung Sitz der Gesellschaft: Geschwister-Scholl-Str. 63a, 14471 Potsdam Registergericht: Amtsgericht Potsdam, HRB 21228 P Geschäftsführer: Dr. Karsten Ahnert, Dr. Markus Abel ___ proto mailing list proto@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/proto
Re: [proto] Manipulating an expression tree
(Please don't top-post. Rearranging...) On 4/7/2011 5:45 AM, Karsten Ahnert wrote: On 04/06/2011 10:53 PM, Bart Janssens wrote: On Wed, Apr 6, 2011 at 10:29 PM, Karsten Ahnert karsten.ahn...@ambrosys.de wrote: Is there a direct way to transform an expression tree into another one? For example, is it possible that every proto::plus node is transformed to it left child? I tried to solve this problem via protos build-in transforms without success. It seems that they are suited for evaluation of an existing tree, but I might be wrong. Hi Karsten, I'm pretty sure they can do both. For your example, I think something along the lines of this might work (untested): struct LeftPlus : boost::proto::or_ boost::proto::terminalboost::proto::_, boost::proto::when boost::proto::plusboost::proto::_, boost::proto::_, LeftPlus(boost::proto::_left) , boost::proto::nary_expr boost::proto::_, boost::proto::varargLeftPlus {}; This should recurse through expressions and replace sequences of pluses with the left-most terminal. You may need some other criteria to end the recursion depending on your use case. Disclaimer: I'm relatively new to proto myself, so the experts might have better solutions! Cheers, Great! It works perfectly, alltough I don't understand the code completely yet. It takes time, but it'll be worth it. You can't do much with Proto with grokking grammars and transforms. Another question is: can a node have a state. In my algorithm it would be nice, if every proto::multiplies node stores some intermediate values which are used during later evaluations of the tree. No. Intermediate expression nodes carry no run-time state in their nodes. They only carry compile-time information in the form of the tag. That's how a plus node is distinguished from a minus node, for instance. If you need to compute intermediate values, you can use a transform to build a parallel structure. -- Eric Niebler BoostPro Computing http://www.boostpro.com signature.asc Description: OpenPGP digital signature ___ proto mailing list proto@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/proto