Re: [boost] [yap] Re-announcing Yap

Subject: Re: [boost] [yap] Re-announcing Yap
From: Zach Laine (whatwasthataddress_at_[hidden])
Date: 2017-03-31 15:47:18

On Fri, Mar 31, 2017 at 2:20 AM, Oswin Krause via Boost <
boost_at_[hidden]> wrote:

> On 2017-03-31 03:02, Edward Diener via Boost wrote:
>
>> On 3/18/2017 6:55 PM, Zach Laine via Boost wrote:
>>
>>> I posted 2-3 months ago about Yap, an expression template library I've
>>> written that I intend to propose for Boost.
>>>
>>> This is just a reminder that the library exists, and where to find it.
>>>
>>> I'm giving a talk about it at C++Now 2017, and some time after that I
>>> intend to submit it to the queue.  Louis Dionne has offered to serve as
>>> review manager when the time comes.
>>>
>>> You can find the main repo on GitHub:
>>>
>>> https://github.com/tzlaine/yap
>>>
>>> And online docs are here:
>>>
>>> https://tzlaine.github.io/yap
>>>
>> I hope it is okay that i answer to this mail, I could not find the mail
> above in my inbox/trash/junk.
>
> I had a short glimpse over the tutorial and I like that you managed to
> solve the temporary argument problem. Still, a few of my "more advanced
> problems" seem not to be discussed in the documention.
>
>
> So, some questions:
>
> 1. You discussed transforming an expression into its arity. What about
> more complex expression transformations? my expression template code[1][2]
> is riddled with meta-expressions intended to bring the AST into some normal
> form so that i can apply optimizations like (M1*M2)*v = M1 * (M2 * v)
> (where M1 and M2 are matrices and v is a vector). In general I only
> consider transformations of the AST of the form
>
> transform(Node(Arg1,Arg2))= NewNode(transform1(Arg1),transform2(Arg2))
>
> Does yap come with support for such transformations?

Yes.  Transforms are free-form.  A transform can do anything you like.  The
matching used in transforms comes in two forms.  Using the more verbose but
more flexible ExpressionTransform form, I would write that something like:

struct transform
{
    template <yap::expr_kind Kind, typename Left, typename Right>
    decltype(auto) operator() (
        boost::yap::expression<
            Kind,
            boost::hana::tuple<Left, Right>
        > && expr
    ) {
        return yap::make_expression<Kind>(
            yap::transform(yap::left(std::move(expr)), transform1),
            yap::transform(yap::right(std::move(expr)), transform2)
        );
    }
};

... where transform, transform1, and transform2 mean the same thing as in
your original example.  You might need to repeat this overload 3 times,
once each for lvalue, const lvalue, and rvalue.  The other form,
TagTransform, makes this work a bit more gracefully.  I didn't use to here
because the mapping from expressions to matching transform call operators
takes a bit more explanation.

> How would such a transformation interact with captured rvalues?
>

Gracefully, I hope.  I have gone to great lengths to make sure that code
like the above forwards/moves appropriately all throughout Yap's call
stack.  In this example, the semantics are up to you -- what you write into
the transformation determines the interaction with captured rvalues.

> 2. is it hard to implement variable tagging? (e.g. for checking whether a
> specific variable occurs in the expression).
>

If a variable has a particular type or value, you can simply write a
transform that "converts" an expression into a count indicating how many
times that type/value appears in the expression, similar to how the arity
transform works.  "Converts" is in quotes, because of course such a
transform leaves the original expression unmodified, and simply returns the
count.

3. How does the library handle variable aliasing, i.e. a variable being on
> both sides of an assignment.
>

The same way that C++ always does.  All the builtin operators are used
unless you override them.  So, this:

my_type a_ = /*...*/;
auto a = yap::make_terminal(a);
yap::evaluate(a = a);

Generates the same object code as this:

my_type a_ = /*...*/;
a_ = a_;

Of course, if you decide to detect this case and do something different (in
a transform or via customization point -- there's more than one way to do
this in Yap), that's fine too.

> 4. if 1. and 2. work easily: How hard would you consider an implementation
> of auto-differentiation? e.g. given an expression and a tagged variable,
> transform the expression into its derivative? Bonus points for reverse
> accumulation [3]

Not very -- there's an auto-differentiation example in Yap already, though
it uses an existing toy auto-differentiation library to do the real work:

https://tzlaine.github.io/yap/doc/html/boost_yap__proposed_/manual/examples/autodiff.html

Zach