boost.proto + modify expression tree in place

Question

Background question: boost.proto + detect invalid terminal before building the expression tree.

Hi, what i'm trying to achieve is

1. create a copy of an expression tree, where all vectors are substituted with their begin iterators (in my case is a raw pointer)
2. increment the iterators in place
3. dereference iterators in the tree, but that part should be relatively easy.

So, for 1. I ended up with this code

///////////////////////////////////////////////////////////////////////////////
// A transform that converts all vectors nodes in a tree to iterator nodes
struct vector_begin : proto::transform <vector_begin>
{
    template<typename Expr, typename Unused1, typename Unused2>
    struct impl : boost::proto::transform_impl<Expr, Unused1, Unused2>
    {
        // must strip away the reference qualifier (&)
        typedef typename proto::result_of::value<
                typename boost::remove_reference<Expr>::type
            >::type vector_type;

        typedef typename proto::result_of::as_expr
            <typename vector_type::const_iterator>::type result_type;

        result_type operator ()(
              typename impl::expr_param var
            , typename impl::state_param
            , typename impl::data_param) const
        {
            typename vector_type::const_iterator iter(proto::value(var).begin());
            return proto::as_expr(iter); // store iterator by value
        }
    };
};

struct vector_grammar_begin
        : proto::or_ <
            proto::when <vector_terminal, vector_begin>
            // scalars want to be stored by value (proto stores them by const &), if not the code does not compile... 
          , proto::when <scalar_terminal, boost::proto::_make_terminal(boost::proto::_byval(boost::proto::_value))>
            // descend the tree converting vectors to begin() iterators
          , proto::when <proto::nary_expr<_, proto::vararg<vector_grammar_begin> > >
        >
{};

The above succeeds to create a tree where all vectors are replaced by pointers. So far, so good. Now, try to increment iterators. I realized that is would be better to advance iterators, so with just one transform, i could get most of the behavior of a random access iterator (dereference is the other missing piece). For 2., the required transform should be

///////////////////////////////////////////////////////////////////////////////
// A transform that advances all iterators in a tree
struct iter_advance : proto::transform <iter_advance>
{
    template<typename Expr, typename Index, typename Dummy>
    struct impl : boost::proto::transform_impl<Expr, Index, Dummy>
    {
        typedef void result_type;
        result_type operator ()(
              typename impl::expr_param var
            , typename impl::state_param index // i'm using state to pass a data :(
            , typename impl::data_param) const
        {
            proto::value(var)+=index; // No good... compile error here :(
        }
    };
};

// Ok, this is brittle, what if I decide the change vector<D,T>'s iterator type ?
struct iter_terminal
        :   proto::and_<
                proto::terminal<_>
             ,  proto::if_<boost::is_pointer<proto::_value>()> 
            >
{};


struct vector_grammar_advance
        : proto::or_ <
            proto::when <iter_terminal, iter_advance>
          , proto::terminal<_>
          , proto::when <proto::nary_expr<_, proto::vararg<vector_grammar_advance> > >
        >
{};

Now, in the main function

template <class Expr>
void check_advance (Expr const &e)
{
    proto::display_expr (e);

    typedef typename boost::result_of<vector_grammar_begin(Expr)>::type iterator_type;
    iterator_type iter = vector_grammar_begin()(e);
    proto::display_expr (iter);

    vector_grammar_advance ()(iter,1);
    proto::display_expr (iter);
 }

 int main (int, char**)
 {
    vec<3, double> a(1), b(2), c(3);
    check_advance(2*a+b/c);
    return 0;
 }

I get the following error message (filtered out the junk):

array.cpp:361:13: error: assignment of read-only location

'boost::proto::value<boost::proto::exprns_::expr<boost::proto::tagns_::tag::terminal,
 boost::proto::argsns_::term<const double*>, 0l> >((* & var))'

What bothers me is the '((* & var))' part... cannot understand what to do to fix this. Thanks in advance, best regards

PS Unrelated thing: after playing a little with transforms, the general pattern i'm using is:

1. Decide what to do to the tree
2. Write a primitive transform that performs the operation
3. Write a grammar that recognizes where the transform should be applied, use the previously defined transform

Do you think this is reasonable? I mean, it is a lot of code to perform just an elementary op to a single kind of node. With contexts, it is possible to define several ops at once, discriminating on the node type. It is possible to do this with transforms also ? What is the general pattern to be used?

Answer 1

Your intuition is correct; you should be able to mutate the tree in-place. There seems to be some const weirdness with Proto's pass_through transform that I need to investigate, so the solution is a little non-obvious. First, I define some callables that I will use in the Proto algorithms. I prefer callables to primitive transforms because they are simpler to grok, more reusable, and result in easier-to-read Proto algorithms.

struct begin
  : proto::callable
{
    template<typename Sig>
    struct result;

    template<typename This, typename Rng>
    struct result<This(Rng)>
      : boost::range_iterator<Rng>
    {};

    template<typename This, typename Rng>
    struct result<This(Rng &)>
      : boost::range_iterator<Rng>
    {};

    template<typename Rng>
    typename boost::range_iterator<Rng>::type
    operator()(Rng &rng) const
    {
        return boost::begin(rng);
    }

    template<typename Rng>
    typename boost::range_iterator<Rng const>::type 
    operator()(Rng const &rng) const
    {
        return boost::begin(rng);
    }
};

struct advance
  : proto::callable
{
    typedef void result_type;

    template<typename Iter>
    void operator()(Iter &it, unsigned d) const
    {
        it += d;
    }
};

Now, I solve your brittleness problem with a simple iterator adaptor:

template<typename Iter>
struct vector_iterator
  : boost::iterator_adaptor<vector_iterator<Iter>, Iter>
{
    vector_iterator()
      : boost::iterator_adaptor<vector_iterator<Iter>, Iter>()
    {}

    explicit vector_iterator(Iter iter)
      : boost::iterator_adaptor<vector_iterator<Iter>, Iter>(iter)
    {}

    friend std::ostream &operator<<(std::ostream &sout, vector_iterator it)
    {
        return sout << "vector_iterator(value: " << *it << " )";
    }
};

Here's the algorithm to turn a tree containing vectors into a tree containing vector iterators.

// 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::nary_expr<_, proto::vararg<vector_begin_algo> >)
        >
    >
{};

The last proto::_byval shouldn't be needed. The pass_through transform used by proto::nary_expr shouldn't be creating const temporary nodes. Sorry about that.

And here is the algorithm to advance all the iterators in-place. When you can fully grok this, you will truly be a Proto master.

// Mutate in-place by advancing all vector iterators the amount
// in the state parameter
struct vector_advance_algo
  : proto::or_<
        proto::when<
            proto::terminal<vector_iterator<_> >
          , advance(proto::_value, proto::_state)
        >
      , proto::when<
            proto::terminal<_>
          , proto::_void
        >
      , proto::otherwise<
            proto::and_<
                proto::fold<
                    _
                  , proto::_state
                  , proto::and_<
                        vector_advance_algo
                      , proto::_state
                    >
                >
              , proto::_void
            >
        >
    >
{};

The trick to understanding the above is knowing:

1. proto::_void does nothing and returns void
2. proto::and_, when used as a transform like this, executes all the specified transforms and returns the result of the last.

After all that, you can now do what you had set out to do: Turn a tree containing vectors into a tree containing iterators, and then advance all the iterators in-place:

proto::literal<std::vector<int> > vec1;
proto::value(vec1).assign(
    boost::make_counting_iterator(0)
  , boost::make_counting_iterator(16)
);

auto beg = vector_begin_algo()(2 * vec1 + vec1);
proto::display_expr(beg);

vector_advance_algo()(beg, 1u);
proto::display_expr(beg);

vector_advance_algo()(beg, 1u);
proto::display_expr(beg);

I think your code would have worked had you not run into the const weirdness. Also, I think you might have an easier time of it if you write ordinary callables instead of primitive transforms.

Hope this helps.