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
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:
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
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/express... [2] operators example: https://github.com/Shark-ML/Remora/blob/master/include/remora/vector_proxy.h... [3] https://en.wikipedia.org/wiki/Automatic_differentiation#Reverse_accumulation
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/... 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 < boost@lists.boost.org> 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:
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
On Fri, Mar 31, 2017 at 2:20 AM, Oswin Krause via Boost < boost@lists.boost.org> 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:
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/... Zach
Zack, I have been lurking on this topic, and have interested because I use muparserx (and before that exprtk) in a commercial application. I am curious about 2 things: 1) Is it possible to evaluate a large number of expressions at run-time, where each expression is provided dynamically as a std::string (assuming all functions used are already available)? 2) What is the performance compared to other expression evaluation libraries, as compared here: [1]https://github.com/ArashPartow/math-parser-benchmark-project/blob/ma ster/readme.md Thanks, Jeff References 1. https://github.com/ArashPartow/math-parser-benchmark-project/blob/master/rea...
On Fri, Feb 23, 2018 at 11:14 AM, Jeffrey Graham via Boost < boost@lists.boost.org> wrote:
Zack,
I have been lurking on this topic, and have interested because I use muparserx (and before that exprtk) in a commercial application.
I am curious about 2 things:
1) Is it possible to evaluate a large number of expressions at run-time, where each expression is provided dynamically as a std::string (assuming all functions used are already available)?
No. Yap is an expression *template* library, so the expressions you write and evaluate with Yap are always in your source code, not runtime-parsable.
2) What is the performance compared to other expression evaluation libraries, as compared here:
As I said before, it's a totally different problem domain. But, if you're still curious about Yap's performance, transformed and evaluated expressions end up being identical to the equivalent hand-written code for "reasonable" sizes of expressions. In my experiments on Clang, expressions of 35 terminals or less were "reasonable". Zach
participants (4)
-
Edward Diener -
Jeffrey Graham -
Oswin Krause -
Zach Laine