symbol_optimization

exp.hpp

#if !defined(AMT_EXP_HPP)
#define AMT_EXP_HPP

#include <tuple>
#include <type_traits>

namespace amt{
    
    template<typename... Ts>
    struct expr_list{
        using type_list = std::tuple<Ts...>;

        template<std::size_t I>
        struct nth_impl{
            using type = std::tuple_element_t<I,type_list>;
        };

        template<std::size_t I>
        using nth_t = typename nth_impl<I>::type;
        static constexpr auto const size = sizeof...(Ts);


    };

    template<typename T, typename... Es>
    constexpr auto push_front(expr_list<Es...>) -> expr_list<T,Es...>;

    template<typename T, typename... Es>
    constexpr auto push_back(expr_list<Es...>) -> expr_list<Es...,T>;

    template<std::size_t I, typename Exp>
    using expr_nth_t = typename Exp::template nth_t<I>;

    template<typename Oper, typename Op2> 
    struct unary_expr : expr_list<Oper,Op2>{};

    template<typename Op1, typename Oper, typename Op2> 
    struct binary_expr : expr_list<Op1,Oper,Op2>{};

    template<typename T>
    struct is_expr_list : std::false_type{};

    template<typename... T>
    struct is_expr_list<expr_list<T...>> : std::true_type{};
    
    template<typename T1, typename T2, typename T3>
    struct is_expr_list<binary_expr<T1,T2,T3>> : std::true_type{};
    
    template<typename T1, typename T2>
    struct is_expr_list<unary_expr<T1,T2>> : std::true_type{};

    template<typename T>
    inline static constexpr auto const is_expr_list_v = is_expr_list<T>::value;

} // namespace amt


#endif // AMT_EXP_HPP

main.cpp

#include <iostream>
#include <boost/core/demangle.hpp>
#include "rules.hpp"

template<typename T>
std::string type( T const& t ){
    return boost::core::demangle(typeid(t).name());
}

struct A{};
struct B{};
struct C{};

int main(){
    using exp1 = amt::binary_expr<
        amt::binary_expr<
            amt::binary_expr<
                A, amt::sym::mul, B
            >,
            amt::sym::add,
            amt::binary_expr<
                A, amt::sym::mul, C
            >
        >,
        amt::sym::add,
        amt::binary_expr<
            A, amt::sym::add, A
        >
    > ; // ( A * B + A * C ) + ( A + A ) => ( A * ( B + C ) ) + (2 * A)
    using exp2 = amt::binary_expr<
        A,
        amt::sym::add,
        amt::binary_expr<
            A, amt::sym::add, A
        >
    > ; // ( A + ( A + A ) ) => (3 * A)
    std::cout<<type(amt::optimize_expr<3 /*Max number of rules*/>(exp1{}))<<'\n'; // output: ( A * ( B + C ) ) + (2 * A)
    std::cout<<type(amt::optimize_expr<3 /*Max number of rules*/>(exp2{}))<<'\n'; // output: (3 * A)
    return 0;
}

rules.hpp

#if !defined(AMT_RULE_HPP)
#define AMT_RULE_HPP

#include "symbols.hpp"
#include "exp.hpp"

namespace amt{
    
    struct accept{};
    struct reject{};

    template<typename T>
    inline static constexpr auto const is_accepted_v = std::is_same_v<T,accept>;

    template<typename T>
    inline static constexpr auto const is_rejected_v = std::is_same_v<T,reject>;


    template<std::size_t N>
    struct rule;

    template<>
    struct rule<0>{
        
        static constexpr auto const total_sym_consumed = 3;
        // a * b + a * c
        using from_expr = expr_list< expr_list< sym::expr<0>, sym::mul, sym::expr<1> >, sym::add, expr_list< sym::expr<0>, sym::mul, sym::expr<2> > >;
        // a * ( b + c )
        using to_expr = expr_list< sym::expr<0>, sym::mul, expr_list< sym::expr<1>, sym::add, sym::expr<2> > >;

        template<typename Exp>
        inline constexpr auto operator()(Exp const&) const noexcept{
            if constexpr ( Exp::size != from_expr::size || !is_expr_list_v<Exp> ){
                return reject{};
            }else{
                using left_op = expr_nth_t<0,Exp>;
                using op = expr_nth_t<1,Exp>;
                using right_op = expr_nth_t<2,Exp>;
                if constexpr( sym::is_expr_v<left_op> && 
                    sym::is_operator_v<op> && std::is_same_v< expr_nth_t<1, from_expr>, op > &&
                    sym::is_expr_v<right_op>
                )
                {
                    if constexpr( is_accepted_v< decltype( check<left_op,right_op>() ) > ){
                        return expr_list<
                            expr_nth_t<0,left_op>,
                            sym::mul,
                            expr_list<
                                expr_nth_t<2,left_op>,
                                sym::add,
                                expr_nth_t<2,right_op>
                            >
                        >{};
                    }else{
                        return reject{};
                    }

                }else {
                    return reject{};
                }
            }
        }

    private:

        template<typename LExp, typename RExp>
        inline constexpr auto check() const noexcept{
            if constexpr( is_expr_list_v<LExp> && is_expr_list_v<RExp>  ){
                if constexpr(
                    sym::is_expr_v< expr_nth_t<0,LExp> > && sym::is_expr_v< expr_nth_t<0,RExp> > &&
                    sym::is_operator_v< expr_nth_t<1,LExp> > && sym::is_operator_v< expr_nth_t<1,RExp> > &&
                    sym::is_expr_v< expr_nth_t<2,LExp> > && sym::is_expr_v< expr_nth_t<2,RExp> > &&
                    std::is_same_v< expr_nth_t<1,LExp>, expr_nth_t<1,expr_nth_t<0,from_expr>> > &&
                    std::is_same_v< expr_nth_t<1,RExp>, expr_nth_t<1,expr_nth_t<0,from_expr>> >
                ){
                    return accept{};
                }else{
                    return reject{};
                }
            }else{
                return reject{};
            }
        }

    };

    template<>
    struct rule<1>{
        
        static constexpr auto const total_sym_consumed = 3;
        // a + a
        using from_expr = expr_list< sym::expr<0>, sym::add, sym::expr<0> >;
        // 2 * a
        using to_expr = expr_list< sym::integer<2>, sym::mul, sym::expr<0> >;

        template<typename Exp>
        inline constexpr auto operator()(Exp const&) const noexcept{
            if constexpr ( Exp::size != from_expr::size || !is_expr_list_v<Exp>  ){
                return reject{};
            }else{
                using left_op = expr_nth_t<0,Exp>;
                using op = expr_nth_t<1,Exp>;
                using right_op = expr_nth_t<2,Exp>;
                if constexpr( 
                    sym::is_expr_v<left_op> && std::is_same_v<left_op,right_op> &&
                    sym::is_operator_v<op> && std::is_same_v< expr_nth_t<1, from_expr>, op >
                )
                {
                    return expr_list<
                        sym::integer<2>,
                        sym::mul,
                        left_op
                    >{};

                }else {
                    return reject{};
                }
            }
        }

    };
    
    template<>
    struct rule<2>{
        
        static constexpr auto const total_sym_consumed = 3;
        // (N * a) + a
        using from_expr = expr_list< expr_list< sym::expr<1>, sym::mul, sym::expr<0> >, sym::add, sym::expr<0> >;
        // (N + 1)a
        using to_expr = expr_list< sym::expr<3>, sym::mul, sym::expr<0> >;

        template<typename Exp>
        inline constexpr auto operator()(Exp const&) const noexcept{
            if constexpr ( Exp::size != from_expr::size || !is_expr_list_v<Exp>  ){
                return reject{};
            }else{
                using left_op = expr_nth_t<0,Exp>;
                using op = expr_nth_t<1,Exp>;
                using right_op = expr_nth_t<2,Exp>;
                
                if constexpr( 
                    sym::is_expr_v<left_op> &&
                    sym::is_operator_v<op> && std::is_same_v< expr_nth_t<1, from_expr>, op >
                )
                {
                    if constexpr ( is_accepted_v< decltype(check<left_op,right_op>()) > ){
                        
                        if constexpr( sym::is_integer_v< expr_nth_t<0,left_op> > ){
                            return expr_list<
                                sym::integer< expr_nth_t<0,left_op>::value + 1 >,
                                sym::mul,
                                right_op
                            >{};
                        }else{
                            return expr_list<
                                sym::integer< expr_nth_t<2,left_op>::value + 1 >,
                                sym::mul,
                                right_op
                            >{};
                        }

                    }else if constexpr ( is_accepted_v< decltype(check<right_op,left_op>()) > ){
                        
                        if constexpr( sym::is_integer_v< expr_nth_t<0,right_op> > ){
                            return expr_list<
                                sym::integer< expr_nth_t<0,right_op>::value + 1 >,
                                sym::mul,
                                left_op
                            >{};
                        }else{
                            return expr_list<
                                sym::integer< expr_nth_t<2,right_op>::value + 1 >,
                                sym::mul,
                                left_op
                            >{};
                        }

                    }else{
                        return reject{};
                    }

                }else {
                    return reject{};
                }
            }
        }

    private:
        template<typename LExp, typename RExp>
        inline constexpr auto check() const noexcept{
            if constexpr( is_expr_list_v<LExp> ){
                using left_type = expr_nth_t<0,LExp>;
                using op = expr_nth_t<1,LExp>;
                using right_type = expr_nth_t<2,LExp>;

                if constexpr( ( std::is_same_v<left_type,RExp> || std::is_same_v<right_type,RExp> ) &&
                    ( sym::is_integer_v<left_type> || sym::is_integer_v<right_type> ) && 
                    sym::is_operator_v<op> && std::is_same_v< op, expr_nth_t<1, expr_nth_t<0,from_expr>> >
                )
                {
                    return accept{};
                }else{
                    return reject{};
                }
            }else{
                return reject{};
            }
        }

    };

} // namespace amt


namespace amt::detail{

    template<typename Op, typename... Ts>
    inline constexpr auto const_while(expr_list<Ts...> res = expr_list<>{}) noexcept{
        using res_type = decltype( Op{}(res) );

        if constexpr( !is_rejected_v< res_type > ){
            return const_while<Op>(res_type{});
        }else{
            return res;
        }

    }

    template<typename Exp, typename Op>
    inline constexpr auto optimize_helper() noexcept{
        if constexpr( is_expr_list_v<Exp> ){
            return const_while<Op>(Exp{});
        }else{
            return Exp{};
        }

    }

    template<std::size_t RuleN, typename Exp, typename... Ts >
    constexpr auto optimize_expr(expr_list<Ts...> res = expr_list<>{}) noexcept {
        
        if constexpr( is_expr_list_v<Exp> && !sym::is_operator_v<Exp>){
            static_assert( Exp::size <=3 && Exp::size > 0, "Invlaid expression" );
            if constexpr ( rule<RuleN>::total_sym_consumed == 3 && Exp::size == 3 ){

                using left_type = expr_nth_t<0,Exp>;
                using op_type = expr_nth_t<1,Exp>;
                using right_type = expr_nth_t<2,Exp>;
                using lreturn_type = decltype( optimize_expr<RuleN,left_type>(expr_list<>{}) );
                using rreturn_type = decltype( optimize_expr<RuleN,right_type>(expr_list<>{}) );
                using new_exp_type = expr_list< lreturn_type, op_type, rreturn_type >;

                using opt_exp = decltype( optimize_helper<new_exp_type,rule<RuleN> >() );

                return opt_exp{};

            }else{
                using expr_type = expr_nth_t< Exp::size == 1 ? 0 : 1 ,Exp>;
                using rexpr_type = decltype( optimize_expr<RuleN,expr_type>(expr_list<>{}) );
                using new_exp_type = expr_list< rexpr_type >;

                using opt_exp = decltype( optimize_helper<new_exp_type,rule<RuleN> >() );
                return opt_exp{};
            }

        }else{
            return Exp{};
        }
        
    }

}

namespace amt{

    template<std::size_t Max, std::size_t I = 0, typename Exp, typename... Ts >
    constexpr auto optimize_expr(Exp const& res) noexcept {
        
        if constexpr( I < Max ){

            using op_type = decltype(detail::optimize_expr<I,Exp>());
            return optimize_expr<Max,I + 1>(op_type{});
        }else{
            return res;
        }
        
    }

}

#endif // AMT_RULE_HPP

symbol.hpp

#if !defined(AMT_SYMBOLS_HPP)
#define AMT_SYMBOLS_HPP

#include <cstddef>
#include <type_traits>
#include "exp.hpp"

namespace amt::sym{
    
    struct op{};

    struct mul : op{};
    struct add : op{};
    struct sub : op{};
    struct div : op{};
    

    template<std::size_t N>
    struct expr
        : std::integral_constant<std::size_t,N>{};

    template<std::ptrdiff_t N>
    struct integer 
        : std::integral_constant<std::ptrdiff_t,N>{};

    template<typename T>
    struct is_operator : std::is_base_of<op,T>{};
    
    template<typename T>
    inline static constexpr auto const is_operator_v = is_operator<T>::value;

    template<typename T>
    struct is_integer : std::false_type{};

    template<std::ptrdiff_t N>
    struct is_integer< integer<N> > : std::true_type{};

    template<typename T>
    struct is_expr : 
        std::integral_constant<bool, !is_operator_v<T>> {};

    template<typename T>
    inline static constexpr auto const is_expr_v = is_expr<T>::value;

    template<typename T>
    inline static constexpr auto const is_integer_v = is_integer<T>::value;
    
} // namespace amt::sym


#endif // AMT_SYMBOLS_HPP