[yap] Re-announcing Yap

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

[yap] Re-announcing Yap

Boost - Dev mailing list
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

Zach

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [yap] Re-announcing Yap

Boost - Dev mailing list
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

You might want to mention here what the purpose of the library is and
when it might be used by developers, in order to interest others.

>
> Zach



_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [yap] Re-announcing Yap

Boost - Dev mailing list
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? How would such a
transformation interact with captured rvalues?

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

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

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]


[1]transformations:
https://github.com/Shark-ML/Remora/blob/master/include/remora/detail/expression_optimizers.hpp
[2] operators example:
https://github.com/Shark-ML/Remora/blob/master/include/remora/vector_proxy.hpp#L48
[3]
https://en.wikipedia.org/wiki/Automatic_differentiation#Reverse_accumulation

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [yap] Re-announcing Yap

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
Thanks, Edward.  I keep mistakenly thinking that "expression template
library" is a sufficient explanation on the Boost list, even though I know
that this is not the case.

Yap allows you to capture a C++ expression as an expression tree that can
be subsequently transformed and/or evaluated.  For instance, here is some
end-user code using lazy vectors.  The lazy_vector type and the associated
operations are defined using the Yap library.  This is mostly a copy-paste
from one of the Yap examples, here:

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

int main ()
{
    // A lazy vector contains a std::vector<double> value
    lazy_vector v1{std::vector<double>(4, 1.0)};
    lazy_vector v2{std::vector<double>(4, 2.0)};
    lazy_vector v3{std::vector<double>(4, 3.0)};

    // This statement does not create a temporary vector, and
    // only uses the elements v2[2] and v3[2].  It also generates
    // the exact same object code as "x2[2] + x3[2]", where x2
    // and x3 are non-lazy, plain old std::vector<double>s.
    double d1 = (v2 + v3)[2];
    std::cout << d1 << "\n";

    // This statement does an element-wise operation, creating
    // no temporaries.
    v1 += v2 - v3;
    std::cout << '{' << v1[0] << ',' << v1[1]
              << ',' << v1[2] << ',' << v1[3] << '}' << "\n";

    // This expression is disallowed because it does not conform to the
    // implicit grammar.  operator+= is only defined on terminals, not
    // arbitrary expressions.
    // (v2 + v3) += v1;

    return 0;
}

The Yap code that you must write in order to make this end-user code work
is fairly small:

// This transform turns a terminal of std::vector<double> into a terminal
// containing the nth double in that vector.  Think of it as turning our
// expression of vectors into an expression of scalars.
struct take_nth
{
    boost::yap::terminal<lazy_vector_expr, double>
    operator() (boost::yap::terminal<lazy_vector_expr, std::vector<double>>
const & expr);

    std::size_t n;
};

// A custom expression template that defines lazy + and - operators that
// produce expressions, and an eager [] operator that returns the nth
element
// of the expression.
template <boost::yap::expr_kind Kind, typename Tuple>
struct lazy_vector_expr
{
    using this_type = lazy_vector_expr<Kind, Tuple>;

    static const boost::yap::expr_kind kind = Kind;

    Tuple elements;

    BOOST_YAP_USER_BINARY_OPERATOR_MEMBER(plus, this_type,
::lazy_vector_expr)
    BOOST_YAP_USER_BINARY_OPERATOR_MEMBER(minus, this_type,
::lazy_vector_expr)

    // Note that this does not return an expression; it is greedily
evaluated.
    auto operator[] (std::size_t n) const;
};

template <boost::yap::expr_kind Kind, typename Tuple>
auto lazy_vector_expr<Kind, Tuple>::operator[] (std::size_t n) const
{ return boost::yap::evaluate(boost::yap::transform(*this, take_nth{n})); }

boost::yap::terminal<lazy_vector_expr, double>
take_nth::operator() (boost::yap::terminal<lazy_vector_expr,
std::vector<double>> const & expr)
{
    double x = boost::yap::value(expr)[n];
    return boost::yap::make_terminal<lazy_vector_expr,
double>(std::move(x));
}

// In order to define the += operator with the semantics we want, it's
// convenient to derive a terminal type from a terminal instantiation of
// lazy_vector_expr.  note that we could have written a template
// specialization here instead -- either one would work.  That would of
course
// have required more typing.
struct lazy_vector :
    lazy_vector_expr<
        boost::yap::expr_kind::terminal,
        boost::hana::tuple<std::vector<double>>
    >
{
    lazy_vector () {}

    explicit lazy_vector (std::vector<double> && vec)
    { elements = boost::hana::tuple<std::vector<double>>(std::move(vec)); }

    template <boost::yap::expr_kind Kind, typename Tuple>
    lazy_vector & operator+= (lazy_vector_expr<Kind, Tuple> const & rhs)
    {
        std::vector<double> & this_vec = boost::yap::value(*this);
        for (int i = 0, size = (int)this_vec.size(); i < size; ++i) {
            this_vec[i] += rhs[i];
        }
        return *this;
    }
};

More details and way more examples can be found at:

https://tzlaine.github.io/yap

Zach

On Thu, Mar 30, 2017 at 8:02 PM, Edward Diener via Boost <
[hidden email]> 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
>>
>
> You might want to mention here what the purpose of the library is and when
> it might be used by developers, in order to interest others.
>
>
>> Zach
>>
>
>
>
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman
> /listinfo.cgi/boost
>

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [yap] Re-announcing Yap

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
On Fri, Mar 31, 2017 at 2:20 AM, Oswin Krause via Boost <
[hidden email]> 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

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Loading...