[proto] transform for flattening an expression - how?
Hi! Sorry, Eric, if this is a lot of work. Reject to do it, if you like, or provide only some of these. ---- Task 1 -------------- Consider I need to flatten a tree into a sum: template<int I> struct arg {}; proto::terminal<arg<1> >::type a; proto::terminal<arg<2> >::type b; proto::terminal<arg<3> >::type c; proto::terminal<arg<4> >::type d; a + b + c + d has type expr<tag::plus, arg2<a tree structure> > but I need a template function make_flat taking arbitray expressions and return expressions of type expr<sum, args4<all args in the typelist> > How can I do this in proto? ----------- Task 2: Next step: a - b + c should first be transformed into a + (-b) + c and then transformed into the sum. Could you please provide full compilable examples? ------ Task 3: Next step: I want to detect simultaneous occurences of x and -x and have them dropped from the typelist of my sum. Please provide an example that detects this for terminals only, then one which also works for (a*b - a*b) and returns expr<tag::nil, nulllist> (BTW, is there a nil/null tag in proto?) --------- Task 4: Write an expand function that for a*(b+c) returns a type representation a*b+a*c ----- Markus
Markus Werle wrote:
a + b + c + d
has type expr<tag::plus, arg2<a tree structure> >
but I need a template function make_flat taking arbitray expressions and return expressions of type
expr<sum, args4<all args in the typelist> >
How can I do this in proto?
Do you *really* want to use proto::expr<> to hold the result, or will any Fusion sequence do? The reason I ask is because if you use expr<>, you are limited to BOOST_PROTO_MAX_ARITY elements, which is probably too low. And bumping BOOST_PROTO_MAX_ARITY gets expensive. -- Eric Niebler Boost Consulting www.boost-consulting.com
Eric Niebler <eric <at> boost-consulting.com> writes:
Markus Werle wrote: [...]
How can I do this in proto?
Do you *really* want to use proto::expr<> to hold the result, or will any Fusion sequence do?
proto::expr, I want to stay within proto context (sic!)
The reason I ask is because if you use expr<>, you are limited to BOOST_PROTO_MAX_ARITY elements, which is probably too low. And bumping BOOST_PROTO_MAX_ARITY gets expensive.
Alarm level red: You have measurements: what is the implication of setting BOOST_PROTO_MAX_ARITY to values greater than 10 considering compile time? Markus
Markus Werle wrote:
Eric Niebler <eric <at> boost-consulting.com> writes:
The reason I ask is because if you use expr<>, you are limited to BOOST_PROTO_MAX_ARITY elements, which is probably too low. And bumping BOOST_PROTO_MAX_ARITY gets expensive.
Alarm level red: You have measurements: what is the implication of setting BOOST_PROTO_MAX_ARITY to values greater than 10 considering compile time?
Here are the compile times for libs/xpressive/test/test2.cpp, a fairly rigorous workout for Proto, for different max arities. Arity Compile time (sec) ------------------------- 5 5.132 10 5.725 15 6.895 20 8.517 25 11.091 30 14.492 35 18.922 40 25.100 As you can see, beyond 20 things begin to get bad, but not dramatically so. One of the big sources of slow-down is the operator() overloads on expr<> ... there are N specializations of expr<>, and each one has N overloads of operator(). That's O(N^2) growth. With a variadic operator(), I should be able to knock that down to O(N). In picking a max arity for a DSEL, I think we reach the limits of human readability (a function that takes 20 arguments?! Really?) before we reach Proto's breaking point. -- Eric Niebler Boost Consulting www.boost-consulting.com
Eric Niebler wrote:
In picking a max arity for a DSEL, I think we reach the limits of human readability (a function that takes 20 arguments?! Really?) before we reach Proto's breaking point.
I am dreaming of: scalar_field<0> rho; scalar_field<1> u; scalar_field<2> v; .... Solver.AddPDESystem() [ddt(rho) + ddx(rho * u) + ddy(rho * v) + sourceterm == 0], [ddt(rho * u) + ddx(rho * pow<2, 1>(u)) + ddy(rho * u * v) == 0], [.. some other 10-20 partial differential eqns. omitted ]; What is not readable here and how many operands are in the whole expression? In chemistry there are systems with more than 100 equations of this form. One day proto will bend before such usecases. You've been warned ;-) Of course I can stick with what I have now, where I add one PDE after the other, but that could be improved. Markus P.S.: rational power is missing in proto! tss, tss ...
Markus Werle wrote:
Eric Niebler wrote:
In picking a max arity for a DSEL, I think we reach the limits of human readability (a function that takes 20 arguments?! Really?) before we reach Proto's breaking point.
I am dreaming of:
scalar_field<0> rho; scalar_field<1> u; scalar_field<2> v; ....
Solver.AddPDESystem() [ddt(rho) + ddx(rho * u) + ddy(rho * v) + sourceterm == 0], [ddt(rho * u) + ddx(rho * pow<2, 1>(u)) + ddy(rho * u * v) == 0], [.. some other 10-20 partial differential eqns. omitted ];
Cool!
What is not readable here and how many operands are in the whole expression?
I don't see anything besides unary and binary expressions here, so a max arity of 2 would suffice for your purposes. (But Proto requires max arity to be at least 3 to support the ternary ?: operator.)
P.S.: rational power is missing in proto! tss, tss ...
Proto also doesn't have abs, sign, cos, sin, etc., etc. These are functions, not operators. You would probably handle pow<2,1>(u) like I handle construct<T>(_1, _2) in the Expression Construction Utilities section. -- Eric Niebler Boost Consulting www.boost-consulting.com
AMDG Eric Niebler wrote:
What is not readable here and how many operands are in the whole expression?
I don't see anything besides unary and binary expressions here, so a max arity of 2 would suffice for your purposes.
If you want to iterate over all the terms in a transform use fold_tree. I don't see any benefit of flattening the expression, besides making things harder for proto :) In Christ, Steven Watanabe
Steven Watanabe <watanabesj <at> gmail.com> writes:
If you want to iterate over all the terms in a transform use fold_tree. I don't see any benefit of flattening the expression, besides making things harder for proto :)
We are talking about a general purpose ET library here. There are n-ary operators and function calls in the RealWorld. So these _must_ be first class citizens in proto. Having (a+b+c+d) represented has expr<sum, etc.> is crucial for what I want to do with proto, namely compile-time analytic differentiation in conjunction with expression simplification. Looking at expressions as tree is only half of the truth and I always found this was lovely (citing Todd V.), but not useful everywhere. Eric took the correct path using the expr<op, typelist> idiom. Lets not step behind that one. Markus
AMDG Markus Werle wrote:
Steven Watanabe <watanabesj <at> gmail.com> writes:
If you want to iterate over all the terms in a transform use fold_tree. I don't see any benefit of flattening the expression, besides making things harder for proto :)
We are talking about a general purpose ET library here. There are n-ary operators and function calls in the RealWorld. So these _must_ be first class citizens in proto.
Of course. But that doesn't mean that a + b + c + d + e + f + g has to hold all the elements a to f directly.
Having (a+b+c+d) represented has expr<sum, etc.> is crucial for what I want to do with proto, namely compile-time analytic differentiation in conjunction with expression simplification.
I'm afraid that I still don't understand why creating a flattened view when you process it doesn't work. If this still bothers you, think of it as a cons list instead of a tree. In Christ, Steven Watanabe
Steven Watanabe wrote:
I'm afraid that I still don't understand why creating a flattened view when you process it doesn't work. If this still bothers you, think of it as a cons list instead of a tree.
Maybe it's just because I am not very known to fusion yet. Since you have the overview: you've seen the examples I requested from Eric for expand and collect. Actually I thought that transforms only work on expr<> not on fusion sequences. I just don't want to switch the library in order to do all this CT magic. I have to take a closer look at that. Hope I find enough time for this ... Markus
Markus Werle wrote:
Actually I thought that transforms only work on expr<> not on fusion sequences. I just don't want to switch the library in order to do all this CT magic.
Right, transforms accept expressions. There's nothing stopping you from writing a transform that accepts an expression, creates a flat view, and manipulates the flat view with Fusion algorithms. In fact, there is a Proto transform that does just that: fold<>. When you use transform::fold<Seq, State, Fun>, Seq is a transform that accepts an expression and returns a Fusion sequence. The fold<> transform then just calls fusion::fold() on that sequence. Usually Seq is proto::_, which causes you to fold the children of the current expression. That's because "_" is an identity transform ... it just returns the expression passed to it. And expressions are valid Fusion sequences of their children. My point is, you don't have to "switch libraries" ... you can use them both because they're designed to work together. -- Eric Niebler Boost Consulting www.boost-consulting.com
On 03/18/08 17:23, Markus Werle wrote: [snip]
I am dreaming of:
scalar_field<0> rho; scalar_field<1> u; scalar_field<2> v; ....
Solver.AddPDESystem() [ddt(rho) + ddx(rho * u) + ddy(rho * v) + sourceterm == 0], [ddt(rho * u) + ddx(rho * pow<2, 1>(u)) + ddy(rho * u * v) == 0], [.. some other 10-20 partial differential eqns. omitted ];
[snip]
In chemistry there are systems with more than 100 equations of this form. One day proto will bend before such usecases. You've been warned ;-)
Spirit has something similar except it's equations always have a single variable (a.k.a. nonterminal in grammar parlance) on one side of the equation. For example, the calculator::definition CTOR here: http://www.boost.org/libs/spirit/example/fundamental/full_calc.cpp Spirit uses pointer's to the rhs stored in spirit::rule's which avoids, somewhat, the compiler limitations. Maybe you could do something similar. This sequence of grammar equations (a.k.a. productions) and a solution to these equations for non-terminal lookaheads is prototyped using proto in cfg_lookahead_extends.zip here: http://www.boost-consulting.com/vault/index.php?&directory=Strings%20-%20Text%20Processing However, instead of using '[]' to separate the equations, like spirit, this prototype uses ','. Maybe the lookahead prototype could give you some ideas for constructing the equations and solving them for your PDE solver.
AMDG Eric Niebler wrote:
Here are the compile times for libs/xpressive/test/test2.cpp, a fairly rigorous workout for Proto, for different max arities.
<snip>
As you can see, beyond 20 things begin to get bad, but not dramatically so. One of the big sources of slow-down is the operator() overloads on expr<> ... there are N specializations of expr<>, and each one has N overloads of operator(). That's O(N^2) growth. With a variadic operator(), I should be able to knock that down to O(N).
In picking a max arity for a DSEL, I think we reach the limits of human readability (a function that takes 20 arguments?! Really?) before we reach Proto's breaking point.
In that case, since Marcus wants a larger arity for automatically generated exprs rather than ones created using operators, couldn't you set the max arity for the function call overloads separately from the max expr arity? How are compile times if you keep the function call arity fixed at 5? In Christ, Steven Watanabe
Steven Watanabe wrote:
In that case, since Marcus wants a larger arity for automatically generated exprs rather than ones created using operators, couldn't you set the max arity for the function call overloads separately from the max expr arity? How are compile times if you keep the function call arity fixed at 5?
That's an interesting suggestion. I'll try that when I have a chance and report the results. -- Eric Niebler Boost Consulting www.boost-consulting.com
Steven Watanabe wrote:
Eric Niebler wrote:
One of the big sources of slow-down is the operator() overloads on expr<> ... there are N specializations of expr<>, and each one has N overloads of operator(). That's O(N^2) growth. With a variadic operator(), I should be able to knock that down to O(N).
In that case, since Marcus wants a larger arity for automatically generated exprs rather than ones created using operators, couldn't you set the max arity for the function call overloads separately from the max expr arity? How are compile times if you keep the function call arity fixed at 5?
A quick test shows this to be a very good way to keep compile times under control. Max arity Max Function call arity Compile time (sec) ------------------------------------------------------------------ 40 40 24.1 40 5 14.0 Thanks for the suggestion. -- Eric Niebler Boost Consulting www.boost-consulting.com
On 03/17/08 16:35, Markus Werle wrote:
Hi!
Sorry, Eric, if this is a lot of work. Reject to do it, if you like, or provide only some of these.
---- Task 1 -------------- Consider I need to flatten a tree into a sum:
template<int I> struct arg {};
proto::terminal<arg<1> >::type a; proto::terminal<arg<2> >::type b; proto::terminal<arg<3> >::type c; proto::terminal<arg<4> >::type d;
a + b + c + d
has type expr<tag::plus, arg2<a tree structure> >
but I need a template function make_flat taking arbitray expressions and return expressions of type
expr<sum, args4<all args in the typelist> >
How can I do this in proto?
----------- Task 2: Next step:
a - b + c should first be transformed into a + (-b) + c and then transformed into the sum.
Could you please provide full compilable examples?
------
Task 3: Next step:
I want to detect simultaneous occurences of x and -x and have them dropped from the typelist of my sum. Please provide an example that detects this for terminals only, then one which also works for (a*b - a*b) and returns expr<tag::nil, nulllist> (BTW, is there a nil/null tag in proto?)
---------
Task 4: Write an expand function that for a*(b+c) returns a type representation a*b+a*c
-----
Me too! In general, there should be an n-ary version of all the binary ops. This should also be extended to the or_ also. I remember having a problem with folding or_ because it was an n-ary op and had to define my own binary or which just forwarded to the or_. That was a "kludge". So maybe define or_ as binary and then define the n-ary version based on this binary.
Larry Evans wrote:
Me too!
I couldn't tell from your email -- what are you me too-ing?
In general, there should be an n-ary version of all the binary ops.
Do you mean, you'd like to create an expression expr<tag::plus, args4<A,B,C,D> > ? There's nothing stopping you from doing that today. make_expr<tag::plus>(1,2,3,4) The only problem is that default_context won't know what to do with it, but that's not big a problem ... just write your own context.
This should also be extended to the or_ also. I remember having a problem with folding or_ because it was an n-ary op and had to define my own binary or which just forwarded to the or_. That was a "kludge". So maybe define or_ as binary and then define the n-ary version based on this binary.
IIRC, your problem was that or_ requires at least 2 parameters. I had agreed to change that, but haven't yet. -- Eric Niebler Boost Consulting www.boost-consulting.com
On 03/17/08 17:55, Eric Niebler wrote:
Larry Evans wrote:
Me too!
I couldn't tell from your email -- what are you me too-ing?
flattening a sequence of binary operators into one list with a tag indicating the operator to be applied between elements in the list.
In general, there should be an n-ary version of all the binary ops.
Do you mean, you'd like to create an expression expr<tag::plus, args4<A,B,C,D> > ? There's nothing stopping you from doing that today.
make_expr<tag::plus>(1,2,3,4)
The only problem is that default_context won't know what to do with it, but that's not big a problem ... just write your own context.
Actually, I was thinking an n-ary expression with a tag like: reduce<BinOp> For example, make_expr<reduce<tag::plus> >(1,2,3,4). The reason for the name "reduce" is that what apl uses. Or maybe fold<BinOp>, since that's what other boost libraries use.
This should also be extended to the or_ also. I remember having a problem with folding or_ because it was
[snip]
IIRC, your problem was that or_ requires at least 2 parameters. I had agreed to change that, but haven't yet.
Yep, now I remember.
On 03/17/08 17:55, Eric Niebler wrote:
Larry Evans wrote:
Me too! I couldn't tell from your email -- what are you me too-ing?
flattening a sequence of binary operators into one list with a tag indicating the operator to be applied between elements in the list. [snip] And also the means for simplifying an expression somewhat
On 03/17/08 23:45, Larry Evans wrote: like described by Markus:
I want to detect simultaneous occurences of x and -x and have them dropped from the typelist of my sum.
Use case1: translating a grammar expression: x | x to: x Use case2: Step 1: translating grammar expression: A | B to an expression representing if it can derive empty string: empty<A> | empty<B> which, if A is a the epsilon symbol then emptt<A> == true_ and the whole expression simplifies to: true_
Larry Evans wrote:
On 03/17/08 23:45, Larry Evans wrote:
On 03/17/08 17:55, Eric Niebler wrote:
Larry Evans wrote:
Me too! I couldn't tell from your email -- what are you me too-ing? flattening a sequence of binary operators into one list with a tag indicating the operator to be applied between elements in the list.
See my reply to Markus. Use proto::flatten() and proto::unpack_expr().
And also the means for simplifying an expression somewhat like described by Markus:
I want to detect simultaneous occurences of x and -x and have them dropped from the typelist of my sum.
Use case1:
translating a grammar expression:
x | x
to:
x
Use case2:
Step 1: translating grammar expression: A | B to an expression representing if it can derive empty string: empty<A> | empty<B> which, if A is a the epsilon symbol then emptt<A> == true_ and the whole expression simplifies to:
true_
These are domain-specific use cases. The code for that belongs in your DSEL, not in Proto. -- Eric Niebler Boost Consulting www.boost-consulting.com
On 03/18/08 10:30, Eric Niebler wrote:
Larry Evans wrote:
On 03/17/08 23:45, Larry Evans wrote:
On 03/17/08 17:55, Eric Niebler wrote:
Larry Evans wrote:
Me too! I couldn't tell from your email -- what are you me too-ing? flattening a sequence of binary operators into one list with a tag indicating the operator to be applied between elements in the list.
See my reply to Markus. Use proto::flatten() and proto::unpack_expr().
OK. Thanks.
And also the means for simplifying an expression somewhat like described by Markus:
I want to detect simultaneous occurences of x and -x and have them dropped from the typelist of my sum. Use case1:
translating a grammar expression:
x | x
to:
x
Use case2:
Step 1: translating grammar expression: A | B to an expression representing if it can derive empty string: empty<A> | empty<B> which, if A is a the epsilon symbol then emptt<A> == true_ and the whole expression simplifies to:
true_
These are domain-specific use cases. The code for that belongs in your DSEL, not in Proto.
OK. But so is: -x + x -> 0 0 + x -> x domain specific, which is what Markus was asking for. Now I could just translate: Empty( A | B ) -> Empty<A> * Empty<B> Empty(grammar_terminal) -> 1 Empty(epsilon) -> 0 and I've got what I want and it's in the domain Markus was talking about. So, if you do it for the arith domain (Markus'), then you'd have to have a set of "simplification rule" for that domain. Replace the simplification rules for arith domain with simplification rules for domain X, where X is boolean expressions or grammar expressions or some other domain, and you've generalized what you can simplify. My point was that If you can do it for Markus' domain, then you can to it for domain X. IOW, provide a set of simplification rules for a particular domain. Maybe the next version? ;)
Larry Evans wrote:
On 03/18/08 10:30, Eric Niebler wrote:
These are domain-specific use cases. The code for that belongs in your DSEL, not in Proto.
OK. But so is:
-x + x -> 0
0 + x -> x
domain specific, which is what Markus was asking for.
Right, Markus was just looking for some examples. He didn't want me to put those transforms in Proto.
Now I could just translate:
Empty( A | B ) -> Empty<A> * Empty<B> Empty(grammar_terminal) -> 1 Empty(epsilon) -> 0
and I've got what I want and it's in the domain Markus was talking about. So, if you do it for the arith domain (Markus'), then you'd have to have a set of "simplification rule" for that domain. Replace the simplification rules for arith domain with simplification rules for domain X, where X is boolean expressions or grammar expressions or some other domain, and you've generalized what you can simplify.
My point was that If you can do it for Markus' domain, then you can to it for domain X. IOW, provide a set of simplification rules for a particular domain.
Maybe the next version? ;)
It still doesn't belong in Proto. I see it as analogous to custom grammars and Spirit. Just because someone has written a useful grammar doesn't mean that Joel should make it part of Spirit. Instead, there is a separate Spirit app repository for these bits of useful Spirit code. Maybe there should be a Proto app repository, or maybe you and Markus can write the expression reduction transform and I can put it in libs/proto/example. -- Eric Niebler Boost Consulting www.boost-consulting.com
Eric Niebler wrote:
Right, Markus was just looking for some examples. He didn't want me to put those transforms in Proto.
Actually you _have_ to leave me something extra for daixtrose_2!
[...] Maybe the next version? ;)
It still doesn't belong in Proto. I see it as analogous to custom grammars and Spirit. Just because someone has written a useful grammar doesn't mean that Joel should make it part of Spirit. Instead, there is a separate Spirit app repository for these bits of useful Spirit code. Maybe there should be a Proto app repository, or maybe you and Markus can write the expression reduction transform and I can put it in libs/proto/example.
Yeah. Collect and expand really belong to the examples section. Markus
Markus Werle wrote:
---- Task 1 -------------- Consider I need to flatten a tree into a sum:
template<int I> struct arg {};
proto::terminal<arg<1> >::type a; proto::terminal<arg<2> >::type b; proto::terminal<arg<3> >::type c; proto::terminal<arg<4> >::type d;
a + b + c + d
has type expr<tag::plus, arg2<a tree structure> >
but I need a template function make_flat taking arbitray expressions and return expressions of type
expr<sum, args4<all args in the typelist> >
How can I do this in proto?
This one is easy: proto::unpack_expr<sum>( fusion::as_vector( proto::flatten(a + b + c + d) ) ); fusion::as_vector() is needed because proto::unpack_expr() currently requires a random access sequence, and proto::flatten() returns a forward sequence. I should loosen that requirement.
----------- Task 2: Next step:
a - b + c should first be transformed into a + (-b) + c and then transformed into the sum.
Could you please provide full compilable examples?
See attached. The transform you're looking for is: struct Transform : or_< terminal<_> , when< minus<Transform, Transform> , _make_plus( Transform(_left) , _make_negate(Transform(_right)) ) > , nary_expr<_, vararg<Transform> > > {};
Task 3: Next step:
I want to detect simultaneous occurences of x and -x and have them dropped from the typelist of my sum. Please provide an example that detects this for terminals only, then one which also works for (a*b - a*b) and returns expr<tag::nil, nulllist> (BTW, is there a nil/null tag in proto?)
---------
Task 4: Write an expand function that for a*(b+c) returns a type representation a*b+a*c
I'm afraid I don't have the time for these right now, but I would approach them by using the Transform and then flatten() to produce a flat Fusion sequence. Then I would manipulate the Fusion sequence using Fusion algorithms. After I have reduced the sequence, I would use unpack_expr() to build the resulting "sum" expression. To detect whether some complicated Proto expression E1 is the same as another E2, you can use proto::matches<E1, E2>, because every expression type is a grammar that matches itself. Good luck! -- Eric Niebler Boost Consulting www.boost-consulting.com #include <iostream> #include <boost/fusion/include/as_vector.hpp> #include <boost/xpressive/proto/proto.hpp> #include <boost/xpressive/proto/debug.hpp> #include <boost/xpressive/proto/context.hpp> #include <boost/xpressive/proto/transform.hpp> using namespace boost; template<int I> struct arg { friend std::ostream &operator <<(std::ostream &sout, arg) { return sout << "arg<" << I << ">"; } }; proto::terminal<arg<1> >::type a; proto::terminal<arg<2> >::type b; proto::terminal<arg<3> >::type c; proto::terminal<arg<4> >::type d; struct sum { friend std::ostream &operator <<(std::ostream &sout, sum) { return sout << "sum"; } }; using namespace proto; struct Transform : or_< terminal<_> , when< minus<Transform, Transform> , _make_plus(Transform(_left), _make_negate(Transform(_right))) > , nary_expr<_, vararg<Transform> > > {}; int main() { int ignore = 0; // 1) display_expr( unpack_expr<sum>( fusion::as_vector( flatten(a + b + c + d) ) ) ); // 2) display_expr( a - b + c ); display_expr( Transform()(a - b + c, ignore, ignore) ); display_expr( Transform()(a - b + c, ignore, ignore) ); display_expr( unpack_expr<sum>( fusion::as_vector( flatten(Transform()(a - b + c, ignore, ignore)) ) ) ); return 0; }
Eric Niebler <eric <at> boost-consulting.com> writes:
This one is easy:
proto::unpack_expr<sum>( fusion::as_vector( proto::flatten(a + b + c + d) ) );
fusion::as_vector() is needed because proto::unpack_expr() currently requires a random access sequence, and proto::flatten() returns a forward sequence. I should loosen that requirement.
This means an interface change. Can we have your word on that it will be changed before official release? Markus
Markus Werle wrote:
Eric Niebler <eric <at> boost-consulting.com> writes:
This one is easy:
proto::unpack_expr<sum>( fusion::as_vector( proto::flatten(a + b + c + d) ) );
fusion::as_vector() is needed because proto::unpack_expr() currently requires a random access sequence, and proto::flatten() returns a forward sequence. I should loosen that requirement.
This means an interface change. Can we have your word on that it will be changed before official release?
It's not a breaking interface change, no. Everything that worked before will continue to work after I make this change. I'll fix it, but I don't see it as a high priority, since there's a workaround. -- Eric Niebler Boost Consulting www.boost-consulting.com
Markus Werle wrote:
Task 4: Write an expand function that for a*(b+c) returns a type representation a*b+a*c
The Expand transform defined below does this. #include <iostream> #include <boost/xpressive/proto/proto.hpp> #include <boost/xpressive/proto/debug.hpp> #include <boost/xpressive/proto/context.hpp> #include <boost/xpressive/proto/transform.hpp> using namespace boost; template<int I> struct arg { friend std::ostream &operator <<(std::ostream &sout, arg) { return sout << "arg<" << I << ">"; } }; proto::terminal<arg<1> >::type a; proto::terminal<arg<2> >::type b; proto::terminal<arg<3> >::type c; proto::terminal<arg<4> >::type d; using namespace proto; struct Expand; struct Recurse; struct Distribute : or_< when< plus<_,_> , _make_plus(Recurse(_left), Recurse(_right)) > , when< minus<_,_> , _make_minus(Recurse(_left), Recurse(_right)) > > {}; struct Recurse : or_< Distribute , when<Expand, _make_multiplies(_state, Expand)> > {}; struct Expand : or_< terminal<_> , when<multiplies<_, Distribute>, Distribute(_right, _left)> , nary_expr<_, vararg<Expand> > > {}; int main() { int ignore = 0; display_expr( Expand()(a*(b+c-d), ignore, ignore) ); } The above code fragment displays: minus( plus( multiplies( terminal(arg<1>) , terminal(arg<2>) ) , multiplies( terminal(arg<1>) , terminal(arg<3>) ) ) , multiplies( terminal(arg<1>) , terminal(arg<4>) ) ) I think that's right. That's a fun little problem. :-) -- Eric Niebler Boost Consulting www.boost-consulting.com
participants (4)
-
Eric Niebler -
Larry Evans -
Markus Werle -
Steven Watanabe