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
