Re: [boost] [proto] transform for flattening an expression - how?

18 Mar 2008

      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;
}