c++ - 式テンプレートツリーの変換

Question

式テンプレートツリーが与えられた場合、処理する前に最適化された新しいツリーを作成したいと考えています。次の乗算演算の例を考えてみましょう。

a * b * c * d,

の左から右への結合性によりoperator*、次の式ツリーが生成されます。

(((a * b) * c) * d).

乗算が右から左に行われる変換された式ツリーを作成したいと思います。

(a * (b * (c * d))).

二項式の型を考えてみましょう:

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;
};

乗算演算子を定義しますoperator*。

template<typename Left, typename Right>
BinaryTimesExpr<Constify<Left>, Constify<Right>> operator*(Left&& l, Right&& r)
{
    return {forward<Left>(l), forward<Right>(r)};
}

は次のようConstifyに定義されます。

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;

左辺値から構築された場合は const 左辺値参照を使用し、右辺値から構築された場合は右辺値のコピー (コピー/移動による) を含む部分式を確保するために使用されます。

前の条件で新しい式テンプレートツリーを作成する変換関数を定義します。

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?
}

私の質問は次のとおりです。

1) 関数の戻り値の型を決定するにはどうすればよいTransformですか? 次のような型特性を使用してみました。

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;

以下の私の質問（2）を解決するためにこれを適用する方法がわかりません。

2) 再帰行の書き方:

return Transform({Transform(expr.left.left), {Transform(expr.left.right), Transform(expr.right)}});

3)この問題のよりクリーンな解決策はありますか?

編集: DyP は、上記の問題に対する部分的な解決策を提示します。以下は、彼の答えに基づく私の完全な解決策です。

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;
}

出力：

(((((1*2)*3)*4)*5)*(1*2))
(1*(2*(3*(4*(5*(1*2))))))

Transform最も外部の呼び出し以外のすべてのサブ式に関数を適用する必要があることに注意してTransformください (最後のTransformオーバーロードを参照)。

完全なソースコードはここにあります。

score 3 · Accepted Answer

OPはBoost.Protoを使用しないソリューションを望んでいましたが、他の人はそれを使用して（かなり簡単に）これを行う方法を知りたいと思うかもしれません：

#include <iostream>
#include <boost/type_traits/is_same.hpp>
#include <boost/proto/proto.hpp>

namespace proto = boost::proto;
using proto::_;

struct empty {};

struct transform
  : proto::reverse_fold_tree<
        _
      , empty()
      , proto::if_<
            boost::is_same<proto::_state, empty>()
          , _
          , proto::_make_multiplies(_, proto::_state)
        >
    >
{};

int main()
{
    proto::literal<int> a(1), b(2), c(3), d(4);
    proto::display_expr( a * b * c * d );
    proto::display_expr( transform()(a * b * c * d) );
}

上記のコードは次を表示します。

multiplies(
    multiplies(
        multiplies(
            terminal(1)
          , terminal(2)
        )
      , terminal(3)
    )
  , terminal(4)
)
multiplies(
    terminal(1)
  , multiplies(
        terminal(2)
      , multiplies(
            terminal(3)
          , terminal(4)
        )
    )
)

score 0 · Accepted Answer

完全転送を組み込まない場合:

#include <iostream>

// simplified by making it an aggregate
template<typename Left, typename Right>
struct BinaryTimesExpr
{
    Left left;
    Right right;
};

// "debug" / demo output
template<typename Left, typename Right>
std::ostream& operator<<(std::ostream& o, BinaryTimesExpr<Left, Right> const& p)
{
    o << "(" << p.left << "*" << p.right << ")";
    return o;
}

// NOTE: removed reference as universal-ref yields a reference type for lvalues!
template<typename Left, typename Right>
BinaryTimesExpr < typename std::remove_reference<Left>::type,
                  typename std::remove_reference<Right>::type >
operator*(Left&& l, Right&& r)
{
    return {std::forward<Left>(l), std::forward<Right>(r)};
}


// overload to end recursion (no-op)
template<typename Expr>
auto Transform(const Expr& expr) -> Expr
{
    return expr;
}

template<typename LeftLeft, typename LeftRight, typename Right>
auto Transform(BinaryTimesExpr < BinaryTimesExpr<LeftLeft, LeftRight>,
                                 Right > const& expr)
-> decltype(Transform(
     BinaryTimesExpr < LeftLeft,
                       BinaryTimesExpr<LeftRight, Right>
                     > {expr.left.left, {expr.left.right, expr.right}}
   ))
{
    return Transform(
        BinaryTimesExpr < LeftLeft,
                          BinaryTimesExpr<LeftRight, Right>
                        > {expr.left.left, {expr.left.right, expr.right}}
    );
}


int main()
{
    BinaryTimesExpr<int, int> beg{1,2};
    auto res = beg*3*4*5*6;
    std::cout << res << std::endl;
    std::cout << Transform(res) << std::endl;
}

出力：

(((((1*2)*3)*4)*5)*6)

(1*(2*(3*(4*(5*6)))))

score 0 · Accepted Answer

式は実際には二分木です。たとえば、式a * b * c * d * eは次のようなツリーとして評価され((((a * b) * c) * d) * e)ます (3 歳の子供のような図面については申し訳ありませんが、スタイラスのない iPad...):

ここに画像の説明を入力

ご覧のとおり、デフォルトの評価された式は、left-side-first inorder でツリーをトラバースして生成されます。

一方、逆評価された式 (OP が望むもの) は、right-side-first-inorder でツリーをトラバースして生成されます。

ここに画像の説明を入力

したがって、1 つの解決策は、生成された式ツリーをright-side-first-inorderで走査し、その過程で新しいツリーを作成することです。

c++ - 式テンプレート ツリーの変換

3 に答える 3

Related

Reference

c++ - 式テンプレートツリーの変換