3

Background question: boost.proto + modify expression tree in place

Hi, consider the following transform to extract the value_type from a vector_expr (see previous questions)

template <class T> struct value_type_trait;

template <std::size_t D, class T>
struct value_type_trait<vector<D, T> >
{
    typedef typename vector<D, T>::value_type type;
};

struct deduce_value_type
    : proto::or_<
            proto::when <vector_terminal, value_type_trait<proto::_value>() >
        ,   proto::when <scalar_terminal, proto::_value>
        ,   proto::otherwise <
                    proto::_default<deduce_value_type>()
            >
    >
{};

The above code can be used to provide 'maximal' value_type to the expression tree, which is obtained applying the usual C++ promotion rules and Boost.TypeOf magic. The above is used as follows

template <class Expr>
struct vector_expr : proto::extends <Expr, vector_expr <Expr>, vector_domain>
{
    typedef proto::extends <Expr, vector_expr <Expr>, vector_domain> base_type;
    // OK! now my expression has a 'value_type'
    typedef typename boost::result_of<deduce_value_type(Expr)>::type value_type;

    vector_expr (Expr const &e) : base_type (e) {}
};

But now, the following code (check previous question: boost.proto + modify expression tree in place and the code in the accepted answer) is broken (with the usual humongous template instantiation error backtrace, for my pleasure)

int main ()
{
   double data[] = {1, 2, 3};
   vector<3, double> a(data, data+3), b(data,data+3), c(data,data+3);

   auto iter = vector_begin_algo()(a + b);
   return 0;
}

The reason is simple. The type of typename boost::result_of<vector_begin_algo(a+b)>::type is:

vector_expr<
    basic_expr<
        tag::plus
      , list2< expr<tag::terminal, term<vector_iterator<double*> >, 0l>
             , expr<tag::terminal, term<vector_iterator<double*> >, 0l> 
        >
      , 
    2l>
>

So, the external vector_expr<...> triggers the evaluation of the nested value_type, but the deduce_value_type algorithm doesn't know how to extract the nested value_type from vector_iterator<double*>. One solution is to define a new traits and modify deduce_value_type as follows

// A further trait
template <class Iter>
struct value_type_trait<vector_iterator<Iter> >
{
    typedef typename std::iterator_traits<Iter>::value_type type;
};

// Algorithm to deduce the value type of an expression.
struct deduce_value_type
    : proto::or_<
            proto::when <vector_terminal, value_type_trait<proto::_value>() >
        ,   proto::when <scalar_terminal, proto::_value>
        ,   proto::when <proto::terminal<vector_iterator<proto::_> > , value_type_trait<proto::_value>()> // <- need this now
        ,   proto::otherwise <
                    proto::_default<deduce_value_type>()
            >
    >
{};

There are several problems with this approach, but the most important is: for each typedef or static constant that i find convenient defining in the vector_expr struct, I will need to perform all the above only to have the expression compile, even if an iterator-expression IS-NOT vector-expression and it makes no sense to enlarge the interface of vector_expr to accommodate transformed trees.

The question is: there is a way to transform the vector_expr tree, converting vector nodes into iterator nodes, while at the same time removing the vector-ness from the tree itself so that i do not incur in the above problems? Thanks in advance, best regards!

UPDATE Sorry, i changed the last part of the question now that my mind is more clear about what (i think) should be achieved. In the meantime, i tried to solve the thing by myself with a partial success (?), but I feel that there should be a better way (so I still need help!).

It seems to me that the problems come from having all the tree nodes wrapped in the vector_expr thing, that has the side-effect of putting requirement on the terminals (mainly the static stuff for successfully compiling). OTOH, once a valid vector_exp has been constructed (namely: obeying the vector_grammar), then i can transform it to a valid iterator_tree without further checks.

I tried to create a transform that changes back all vector_expr nodes in a tree into 'proto::expr'. The code is as follows:

template <class Expr, long Arity = Expr::proto_arity_c>
struct deep_copy_unwrap_impl;

template <class Expr>
struct deep_copy_unwrap_impl <Expr,0>
{
    typedef typename proto::tag_of <Expr>::type Tag;
    typedef typename proto::result_of::value<Expr>::type A0;
    typedef typename proto::result_of::make_expr<Tag, proto::default_domain, A0>::type result_type;

    template<typename Expr2, typename S, typename D>
    result_type operator()(Expr2 const &e, S const &, D const &) const
    {
        return proto::make_expr <Tag, proto::default_domain> (e.proto_base().child0);
    }
};

template <class Expr>
struct deep_copy_unwrap_impl <Expr,1>
{
    typedef typename proto::tag_of <Expr>::type Tag;
    typedef typename proto::result_of::child_c<Expr, 0>::type A0;
    typedef typename proto::result_of::make_expr<Tag, proto::default_domain, A0>::type result_type;

    template<typename Expr2, typename S, typename D>
    result_type operator()(Expr2 const &e, S const &, D const &) const
    {
        return proto::make_expr <Tag, proto::default_domain> (e.proto_base().child0);
    }
};

template <class Expr>
struct deep_copy_unwrap_impl <Expr,2>
{
    typedef typename proto::tag_of <Expr>::type Tag;
    typedef typename proto::result_of::child_c<Expr, 0>::type A0;
    typedef typename proto::result_of::child_c<Expr, 1>::type A1;
    typedef typename proto::result_of::make_expr<Tag, proto::default_domain, A0, A1>::type result_type;

    template<typename Expr2, typename S, typename D>
    result_type operator()(Expr2 const &e, S const &, D const &) const
    {
        return proto::make_expr <Tag, proto::default_domain> (e.proto_base().child0, e.proto_base().child1);
    }
};

struct unwrap : proto::callable
{
    template <class Sig> struct result;

    template <class This, class Expr>
    struct result <This(Expr)>
    {
        typedef typename
            deep_copy_unwrap_impl <Expr>
            ::result_type type;
    };

    template <class This, class Expr>
    struct result <This(Expr&)> 
        : result<This(Expr)> {};

    template <class This, class Expr>
    struct result <This(Expr const&)>
        : result<This(Expr)> {};

    template <class Expr>
    typename result <unwrap(Expr)>::type
    operator () (Expr const &e) const
    {
        return deep_copy_unwrap_impl<Expr>()(e, 0, 0);
    }
};


struct retarget
    : proto::otherwise <
                unwrap(proto::nary_expr<proto::_, proto::vararg<retarget> >)
            >
{};


int main ()
{
    int data[] = {1, 2, 3};
    vector<3, int> a(data, data+3), b(data,data+3), c(data,data+3);

    auto x=a+b+c; // <- x is an expression tree made up of vector_expr<...> nodes
    auto y=retarget()(x); // <- y is an expression tree made up of proto::expr<...> nodes
    return 0;
}
Community
  • 1
  • 1
Giuliano
  • 640
  • 3
  • 15
  • Question: why does `vector_begin_algo` produce and expression wrapped in `vector_expr`? Does it really need to? – Eric Niebler Aug 31 '12 at 22:42
  • No, it just happens, and is unwanted. Suppose a,b are vector<3,int>. The type of a+b=vector_expr&>, 0l> >, vector_expr&>, 0l> > >, 2l> >. The vector_begin_algo can remove the inner 'vector_expr' wrappers (around terminals), but not the one around the root node. I was asking if there is a way to modify vector_begin_algo to get rid of that one too. – Giuliano Sep 01 '12 at 06:35
  • Ok, it seems that vector_begin_algo can get rid of vector_exp only around terminals (verified using more complex expressions). So the problem is the proto::otherwise <...> part of the vector_begin_algo, need to modify it to strip away vector_exp at that point! – Giuliano Sep 01 '12 at 07:17
  • ... or not add it in the first place. See my answer below. Hope it helps. – Eric Niebler Sep 01 '12 at 20:52

1 Answers1

3

The problem you're running into is that Proto's pass_through transform creates new expressions that are in the same domain as the original. This happens in your vector_begin_algo algorithm, in the otherwise clause. You don't want this, but it's what pass_through gives you. You have two strategies: don't use pass_through, or trick pass_through into building an expression in the default domain.

If you're using the latest version of Proto (1.51), you can use make_expr and an unpacking expression instead of pass_through:

// Turn all vector terminals into vector iterator terminals
struct vector_begin_algo
  : proto::or_<
        proto::when<
            proto::terminal<std::vector<_, _> >
          , proto::_make_terminal(
                vector_iterator<begin(proto::_value)>(begin(proto::_value))
            )
        >
      , proto::when<
            proto::terminal<_>
          , proto::_make_terminal(proto::_byval(proto::_value))
        >
      , proto::otherwise<
            proto::lazy<
                proto::functional::make_expr<proto::tag_of<_>()>(
                    vector_begin_algo(proto::pack(_))...
                )
            >
        >
    >
{};

proto::lazy is needed here because you first need to build the make_expr function object before you can invoke it. It's not a thing of beauty, but it works.

If you are using an older version of Proto, you can get the same effect by tricking pass_through by first removing the domain-specific wrapper from your expression. First, I write a callable to strip the domain-specific wrapper:

struct get_base_expr
  : proto::callable
{
    template<typename Expr>
    struct result;

    template<typename This, typename Expr>
    struct result<This(Expr)>
    {
        typedef
            typename boost::remove_reference<Expr>::type::proto_base_expr
        type;
    };

    template<typename Expr>
    typename Expr::proto_base_expr operator()(Expr const &expr) const
    {
        return expr.proto_base();
    }
};

Then, the vector_begin_algo would be changed as follows:

// Turn all vector terminals into vector iterator terminals
struct vector_begin_algo
  : proto::or_<
        proto::when<
            proto::terminal<std::vector<_, _> >
          , proto::_make_terminal(
                vector_iterator<begin(proto::_value)>(begin(proto::_value))
            )
        >
      , proto::when<
            proto::terminal<_>
          , proto::_make_terminal(proto::_byval(proto::_value))
        >
      , proto::otherwise<
            proto::_byval(proto::pass_through<
                proto::nary_expr<_, proto::vararg<vector_begin_algo> >
            >(get_base_expr(_)))
        >
    >
{};

This is also not a work of art, but it gets the job done. Don't forget the proto::_byval to work around the const weirdness in the pass_through transform (which is fixed is boost trunk and will be in 1.52, btw).

I can think of one final solution that takes advantage of the fact that Proto expressions are Fusion sequences of their children. You create a Fusion transform_view that wraps the expression and transforms each child with vector_begin_algo. That gets passed to proto::functional::unpack_expr, much like in the first example with make_expr. You'd need proto::lazy there also, for the same reason.

Thanks for pointing out this limitation on Proto's built-in pass_through transform. It'd be good to have a nicer way to do this.

Eric Niebler
  • 5,927
  • 2
  • 29
  • 43
  • Thanks for help, this seems a pretty simple solution compared to what I was doing. My idea was simply to copy the whole tree over a new one while changing the domain wrapper (i used the default domain since it was easier), but there where still copy-by-values vs copy-by-reference issues to solve. BTW your 2nd method is much easier to grasp for me. I digged a lot in proto's internals today trying to find a solution. I didn't know the pass_through transform could be used that way! Thanks again, i will report back what worked for me! – Giuliano Sep 01 '12 at 20:54
  • ... in any case, it would be nice to have some pre-defined method of swapping one domain-specific wrapper with another, copying non-terminals while keeping the terminals stored by ref or value as they where in the original expression. But i'm telling this because i'm not yet at the point of figuring out good solutions using the library's facilities! Tnx again – Giuliano Sep 01 '12 at 20:59
  • There are so many things one may want to do to an expression, I've resisted adding higher-level algorithms like you suggest, preferring instead to provide the low-level Lego blocks and letting users create their own algorithms. However, I can see a real need to customize the `pass_through` transform to specify the target domain. That would have _vastly_ simplified the solution. That said, I am softening on that stance, and would be interested in adding the _right_ high-level facilities if they simplify a large class of common problems. – Eric Niebler Sep 01 '12 at 21:07
  • 1
    By the way, I just added a `Domain` template parameter to the `pass_through` transform. Now, your `vector_begin_algo` can be more simply be written using `otherwise >, basic_default_domain> >`. This should be in 1.52. – Eric Niebler Sep 01 '12 at 23:07
  • That's great! You are an incredibly skilled and responsive coder/library writer. Thanks again for all you help. I must admit that today I was a bit frustrated with this issue. As a newbie user and intermediate C++ programmer, I find that proto is generally intuitive and easy going, but from time to time I've found sort of usability 'gaps' that require high-level skills / digging into the source code just to understand what is going on... I think is normal when using a library with such an high potential and complexity. – Giuliano Sep 01 '12 at 23:36
  • I hear you. You can actually help. Would you be willing to make your code self-contained and send it to me? I can include it as an example. You can also let me know specifically where you hit behavior that was baffling so I can see about improving the docs. But let me make a suggestion: if you try something and you get bizarre results that you don't understand, check the reference section for the part you're using. Although the users' guide is incomplete, Proto's reference section is exhaustive. It should save you from having to look at Proto's source, which is not for the uninitiated. – Eric Niebler Sep 02 '12 at 03:28
  • Sure, i will send you the code in the next days, need to fix a couple of things before that! I'm happy if I can help. Actually the vector_expr example is something i'm doing in parallel with the real thing (sort of fortran array guy) to check is something is feasible or not. I tried to use the reference, but I found it a bit too abstract, sorry. What I really miss in the ref. is a code snippet for **each** documented interface component (there are some), mostly transforms. You know something in the style of the boost.mpl docs. That would be immensely useful! – Giuliano Sep 02 '12 at 08:06