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

From: Eric Niebler (eric_at_[hidden])
Date: 2008-03-17 22:15:57

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