Proto for Boost mailing list page: Re: [proto] Manipulating an expression tree

Subject: Re: [proto] Manipulating an expression tree
From: Thomas Heller (thom.heller_at_[hidden])
Date: 2011-04-08 07:43:05

On Fri, Apr 8, 2011 at 10:56 AM, Karsten Ahnert
<karsten.ahnert_at_[hidden]> wrote:
>>>> If you need to compute intermediate values, you can use a transform to
>>>> build a parallel structure.
>>>
>>> Do you mean to build an entire new tree, or just to replace some nodes?
>>
>> If only some nodes have associated intermediate result, then you could
>> just replace some nodes.
>
> Ok, this is a clear hint.
>
>>> In my current algorithm I use callable contexts to do the work. I think
>>> this is more favorable since I have to evaluate the tree N times to
>>> obtain
>>> the result.
>>
>> Why does that matter? Transforms are almost always a better choice.
>>
>>> I think it would be nice to replace some nodes and customizing
>>> the evaluation context, such that these nodes can be used to store the
>>> intermediates.
>>
>> If you're doing calculation *and* tree transformation, then drop the
>> callable contexts. They can't do the job.
>
> First I do tree transformation and then calculation. A Callable context
> will not do the job, since one only gets the tag of the current node, but
> not the node itself. So I have to implement my own context.
>
> I am not sure if transforms can do that job. It is definitely not possible
> to obtain the full tree for 10th derivative. Maybe some other tricks are
> possible with transforms. At the moment I don't understand them in detail,
> but I will try to change this. Thanks for your advice.

Why not just write a transform that calculates one derivative and call
it N times to get the Nth derivative?

Something like:

struct derivative
    : proto::or_<
        proto::when<
            proto::plus<derivative, derivative>
          , proto::_make_plus<derivative(proto::_left),
derivative(proto::_right)>
       >
       proto::when<
           proto::multiplies<derivative, derivative>
         , proto::_make_plus<
                proto::_make_multiplies<derivative(proto::_left), proto::_right>
               ,proto::_make_multiplies<proto::_left, derivative(proto::_right)>
            >
        >
    >
   /* add more derivation rules*/
{};

template <int N>
struct derive_impl
{
    template <typename Sig>
    struct result;

    template <typename This, typename Expr>
    struct result<This(Expr)>
    {
        typedef typename boost::result_of<derivative(Expr)>::type
first_derivative;
        typedef typename
boost::result_of<derive_impl<N-1>(first_derivative)>::type type;
    };

    template <typename Expr>
    typename result<derive_impl(Expr const&)>::type
    operator()(Expr const & expr) const
    {
        return derive_impl<N-1>(derivative()(expr));
    }
};

template <>
struct derive_impl<0>
{
    template <typename Sig>
    struct result;

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

    template <typename This, typename Expr>
    struct result<This(Expr &)>
    { typedef Expr type; };

    template <typename Expr>
    typename result<derive_impl(Expr const&)>::type
    operator()(Expr const & expr) const
    {
        return expr;
    }
};

template <int N, typename Expr>
typename boost::result_of<derive_impl<N>(Expr const &)>::type
derive(Expr const & expr)
{
     return derive_impl()(expr);
}