Given an expression template tree, I want to create a new optimized tree before processing it. Consider the following example of a multiplication operation:
a * b * c * d,
which produces, due to the left-to-right associativity of operator*, the expression tree:
(((a * b) * c) * d).
I would like to produce a transformed expression tree where multiplication occurs from right-to-left:
(a * (b * (c * d))).
Consider the binary expression type:
template<typename Left, typename Right>
struct BinaryTimesExpr
{
BinaryTimesExpr() = default;
BinaryTimesExpr(const BinaryTimesExpr&) = default;
BinaryTimesExpr(BinaryTimesExpr&&) = default;
BinaryTimesExpr(Left&& l, Right&& r) : left(forward<Left>(l)), right(forward<Right>(r)) {}
BinaryTimesExpr& operator=(const BinaryTimesExpr&) = default;
BinaryTimesExpr& operator=(BinaryTimesExpr&&) = default;
Left left;
Right right;
};
Define the multiplication operator operator*:
template<typename Left, typename Right>
BinaryTimesExpr<Constify<Left>, Constify<Right>> operator*(Left&& l, Right&& r)
{
return {forward<Left>(l), forward<Right>(r)};
}
where Constify is defined by:
template<typename T> struct HelperConstifyRef { using type = T; };
template<typename T> struct HelperConstifyRef<T&> { using type = const T&; };
template<typename T>
using ConstifyRef = typename HelperConstifyRef<T>::type;
and used to ensure sub-expressions with const lvalue-references when constructed from lvalues, and copies (by copy/move) of rvalues when constructed from rvalues.
Define the transformation function that creates a new expression template tree with the previous conditions:
template<typename Expr>
auto Transform(const Expr& expr) -> Expr
{
return expr;
}
template<typename Left, typename Right>
auto Transform(const BinaryTimesExpr<Left, Right>& expr) -> type(???)
{
return {(Transform(expr.left), Transform(expr.right))};
}
template<typename Left, typename Right>
auto Transform(const BinaryTimesExpr<BinaryTimesExpr<LeftLeft, LeftRight>, Right>& expr) -> type(???)
{
return Transform({Transform(expr.left.left), {Transform(expr.left.right), Transform(expr.right)}}); // this sintax is invalid...how can I write this?
}
My questions are:
1) How do I determine the return types of the Transform functions? I've tried using type traits like:
template<typename Expr>
struct HelperTransformedExpr
{
using type = Expr;
};
template<typename Left, typename Right>
struct HelperTransformedExpr<BinaryTimesExpr<Left, Right>>
{
using type = BinaryTimesExpr<typename HelperTransformedExpr<Left>::type, typename HelperTransformedExpr<Right>::type>;
};
template<typename LeftLeft, typename LeftRight, typename Right>
struct HelperTransformedExpr<BinaryTimesExpr<BinaryTimesExpr<LeftLeft, LeftRight>, Right>>
{
using type = BinaryTimesExpr<typename HelperTransformedExpr<LeftLeft>::type,
BinaryTimesExpr<typename HelperTransformedExpr<LeftRight>::type, typename HelperTransformedExpr<Right>::type>>;
};
template<typename Expr>
using TransformedExpr = typename HelperTransformedExpr<Expr>::type;
but don't know how to apply this to solve my question (2) below.
2) How do I write the recursion line:
return Transform({Transform(expr.left.left), {Transform(expr.left.right), Transform(expr.right)}});
3) Is there a cleaner solution for this problem?
Edit: DyP presents a partial solution to the above problem. Below is my full solution based on his answer:
template<typename Expr>
auto Transform(const Expr& expr) -> Expr
{
return expr;
}
template<typename Left, typename Right>
auto Transform(BinaryTimesExpr<Left, Right> const& expr)
-> decltype(BinaryTimesExpr<decltype(Transform(expr.left)), decltype(Transform(expr.right))>{Transform(expr.left), Transform(expr.right)})
{
return BinaryTimesExpr<decltype(Transform(expr.left)), decltype(Transform(expr.right))>{Transform(expr.left), Transform(expr.right)};
}
template<typename LeftLeft, typename LeftRight, typename Right>
auto Transform(BinaryTimesExpr<BinaryTimesExpr<LeftLeft, LeftRight>, Right> const& expr)
-> decltype(Transform(BinaryTimesExpr<decltype(Transform(expr.left.left)), BinaryTimesExpr<decltype(Transform(expr.left.right)), decltype(Transform(expr.right))>>{Transform(expr.left.left), {Transform(expr.left.right), Transform(expr.right)}}))
{
return Transform(BinaryTimesExpr<decltype(Transform(expr.left.left)), BinaryTimesExpr<decltype(Transform(expr.left.right)), decltype(Transform(expr.right))>>{Transform(expr.left.left), {Transform(expr.left.right), Transform(expr.right)}});
}
int main()
{
BinaryTimesExpr<int, int> beg{1,2};
auto res = beg*3*4*5*beg;
std::cout << res << std::endl;
std::cout << Transform(res) << std::endl;
}
Output:
(((((1*2)*3)*4)*5)*(1*2))
(1*(2*(3*(4*(5*(1*2))))))
Note that it was necessary to apply the Transform function on every sub-expression besides the most external Transform call (see the last Transform overload).
The full source code can be found here.
(((a * b) * c) * d)into(a * (b * (c * d)))or would it be sufficient to build the expression tree directly as(a * (b * (c * d)))? – Coequal((((a * b) * c) * d) * e)wich evaluates tobinary_exp<binary_exp<binary_exp<binary_exp<decltype(a),decltype(b)>,decltype(c)>,decltype(d)>,decltype(e)>, have to be evaluated asbinary_exp<decltype(a),binary_exp<decltype(b),binary_exp<decltype(c),binary_exp<decltype(d),decltype(e)>>>>right? Why you don't simply returns the expression in reverse order, in the operators overloads? – Flowingtemplate<typename Left ,typename Right> binary_exp<Right,Left> operator*(const Left& lhs , const Right& rhs) { return { std::forward<Right>( rhs ) , std::forward<Left>( lhs ) }; }– Flowinga*b->exp<B,A>. Second iteration:exp<B,A>*c->exp<C,exp<B,A>>. This doesn't help if eachexpshall perform one multiplication. – Coequaloperator *is allowed to use perfect forwarding, it'll create types likeBinaryTimesExpr<int&, int&>, and, consequently, alsoBinaryTimesExpr<BinaryTimesExpr<int,int>&, int>. This breaks the partial specialization used; maybe it could be fixed using a more generic approach restricted by SFINAE. N.B. rvalues don't profit from (perfect) forwarding here due to lifetime issues. – CoequalBinaryTimesExpr<BinaryTimesExpr<Left,Right>&, RightRight>will not happen ifBinaryTimesExpr<Left, Right>is a rvalue. See my new edit with theConstifytype trait. With this, the expressiona * b * C()becomesBinaryTimesExpr<BinaryTimesExpr<const A&, const B&>, C>, where the first two terms are lvalues and the third is a rvalue. In my application, the expression nodes should not be instantiated at runtime (they should exist only at compile time). – ActinismBinaryTimesExpr<BinaryTimesExpr<int,int>&, int>, or with yourConstify,BinaryTimesExpr<BinaryTimesExpr<int,int> const&, int>. The problem would be that this doesn't match the third overload ofTransform(which expects aBTE<BTE [non-ref], T>). However, this is solved by your second overload (in a way that a don't understand yet ;). – Coequal