C++ lazy evaluation with templates

Question

I have written a c++ program to implement lazy binary operations.

The program is supposed to work as follows: create a binary tree with operations, each time we use a tree in a binary operation with something else, we put both things as left and right children of the new operation. When I call operator T, it entails another operator T recursively of each child in case it is also an operator, or otherwise pass it to the function associated with the template parameter (F).

Code

#include <iostream>
#include <cassert>
#include <vector>

static const auto &add = [](auto a, auto b) {return a + b;};
static const auto &sub = [](auto a, auto b) {return a - b;};
static const auto &mul = [](auto a, auto b) {return a * b;};
static const auto &frac = [](auto a, auto b) {return a / b;};

template <class A, class B, class F> class BinaryOP;

template <class A, class B> using Addition = BinaryOP <A, B, decltype(add)>;
template <class A, class B> using Subtraction = BinaryOP <A, B, decltype(sub)>;
template <class A, class B> using Multiplication = BinaryOP <A, B, decltype(mul)>;
template <class A, class B> using Division = BinaryOP <A, B, decltype(frac)>;

static const auto make_binop = [](auto a, auto b, auto &F) { return BinaryOP<decltype(a), decltype(b), decltype(F)>(a, b, F); };
static const auto make_add = [](auto a, auto b) { return make_binop(a, b, add); };
static const auto make_sub = [](auto a, auto b) { return make_binop(a, b, sub); };
static const auto make_mul = [](auto a, auto b) { return make_binop(a, b, mul); };
static const auto make_div = [](auto a, auto b) { return make_binop(a, b, frac); };

template <class T>
struct is_recursable {
private:
  typedef char yes;
  typedef short no;
  template <typename C> static yes test(decltype(C::RECURSE_ME)*);
  template <typename C> static no test(...);
public:
  enum { value = sizeof(test<T>(0)) == sizeof(yes)  };
};

template <class A, class B, class F>
class BinaryOP {
protected:
  typedef BinaryOP <A, B, F> THIS_T;
  const A lhs;
  const B rhs;
  F func;
public:
  static const bool RECURSE_ME;

  constexpr BinaryOP(const A &lhs, const B &rhs, F &func):
    lhs(lhs), rhs(rhs), func(func)
  {}

  virtual ~BinaryOP()
  {}

  template <class T>
  constexpr operator T() const {
    auto a = is_recursable<A>::value ? T(lhs) : lhs;
    auto b = is_recursable<B>::value ? T(rhs) : rhs;
    return func(a, b);
  }

  template <class R>
  constexpr Addition <THIS_T, R> operator+(const R &b) {
    return make_add(*this, b);
  }

  template <class R>
  constexpr Subtraction <THIS_T, R> operator-(const R &b) {
    return make_sub(*this, b);
  }

  template <class R>
  constexpr Multiplication <THIS_T, R> operator*(const R &b) {
    return make_mul(*this, b);
  }

  template <class R>
  constexpr Division <THIS_T, R> operator/(const R &b) {
    return make_div(*this, b);
  }

  friend std::ostream &operator<<(std::ostream &os, const THIS_T &tree) {
    os << "{" << tree.lhs << ":" << is_recursable<A>::value << ", " << tree.rhs << ":" << is_recursable<B>::value << "}";
    return os;
  }

  void printrec() const {
    printf("1: {");
    if(is_recursable<A>::value == 1)
      /* printf("1 %s", typeid(B).name()); */
      lhs.printrec();
    else
      printf("0");
    printf(", ");
    if(is_recursable<B>::value == 1)
      /* printf("1 %s", typeid(B).name()); */
      rhs.printrec();
    else
      printf("0");
    printf("}");
  }
};

class Matrix {
  typedef std::vector <float> vec_t;
  typedef std::vector <std::vector <float> > mat_t;
  mat_t mat;
public:
  Matrix(mat_t mat):
    mat(mat)
  {}
  Matrix(size_t h, size_t w):
    mat(mat_t(h, vec_t(w)))
  {
    for(size_t i = 0; i < h; ++i)
      for(size_t j = 0; j < w; ++j)
        mat[i][j] = (i == j);
  }
  size_t height() const { return mat.size(); }
  size_t width() const { return (height() == 0) ? 0 : mat.front().size(); }
  Matrix operator*(const Matrix &other) {
    Matrix res(height(), other.width());
    assert(width() == other.height());
    for(size_t i = 0; i < height(); ++i) {
      for(size_t j = 0; j < other.width(); ++j) {
        float sum = 0.;
        for(size_t k = 0; k < width(); ++k) {
          sum += mat[i][k] * other.mat[k][j];
        }
        res.mat[i][j] = sum;
      }
    }
    return res;
  }
  Matrix operator*(const float &scalar) {
    Matrix res(height(), width());
    for(size_t i = 0; i < height(); ++i) for(size_t j = 0; j < width(); ++j) res.mat[i][j] = mat[i][j] * scalar;
    return res;
  }
  friend std::ostream &operator<<(std::ostream &os, const Matrix &m) {
    for(size_t i = 0; i < m.height(); ++i) {
      for(size_t j = 0; j < m.width(); ++j) {
        os << m.mat[i][j] << " ";
      }
      os << std::endl;
    }
    return os;
  }
};

int main() {
  auto tree = make_add(2, 3) + make_sub(5, 6) * make_add(3, 0) / 3; // = 4
  std::cout << tree << std::endl;
  std::cout << int(tree) << std::endl;
  Matrix m(10, 10), n(10, 10);
  auto mattree = make_mul(m, n) + 6;
  std::cout << mattree << std::endl;
  std::cout << "operator is recursable: " << is_recursable<Addition<float, Matrix> >::value << std::endl;
  std::cout << "matrix is recursable: " << is_recursable<Matrix>::value << std::endl;
  std::cout << "float is recursable: " << is_recursable<float>::value << std::endl;
  std::cout << "mattree is recursable: " << is_recursable<decltype(mattree)>::value << std::endl;
  mattree.printrec();
  /* std::cout << (mattree.operator Matrix()) << std::endl; */
}

Compiling

c++ -flto -O2 -std=c++1y binary_operator.cpp

clang

binary_operator.cpp:93:10: error: member reference base type 'const int' is not a structure or union
      rhs.printrec();
      ~~~^~~~~~~~~
binary_operator.cpp:158:11: note: in instantiation of member function 'BinaryOP<BinaryOP<Matrix, Matrix, const <lambda at binary_operator.cpp:7:26> &>, int, const <lambda at binary_operator.cpp:5:26> &>::printrec' requested here
  mattree.printrec();
          ^
binary_operator.cpp:87:11: error: no member named 'printrec' in 'Matrix'
      lhs.printrec();
      ~~~ ^
binary_operator.cpp:87:11: note: in instantiation of member function 'BinaryOP<Matrix, Matrix, const <lambda at binary_operator.cpp:7:26> &>::printrec' requested here
      lhs.printrec();
          ^
binary_operator.cpp:158:11: note: in instantiation of member function 'BinaryOP<BinaryOP<Matrix, Matrix, const <lambda at binary_operator.cpp:7:26> &>, int, const <lambda at binary_operator.cpp:5:26> &>::printrec' requested here
  mattree.printrec();
          ^
binary_operator.cpp:93:11: error: no member named 'printrec' in 'Matrix'
      rhs.printrec();
      ~~~ ^
3 errors generated.
make: *** [binary_operator] Error 1

gcc

binary_operator.cpp: In instantiation of 'void BinaryOP<A, B, F>::printrec() const [with A = BinaryOP<Matrix, Matrix, const<lambda(auto:5, auto:6)>&>; B = int; F = const<lambda(auto:1, auto:2)>&]':
binary_operator.cpp:158:20:   required from here
binary_operator.cpp:93:11: error: request for member 'printrec' in '((const BinaryOP<BinaryOP<Matrix, Matrix, const<lambda(auto:5, auto:6)>&>, int, const<lambda(auto:1, auto:2)>&>*)this)->BinaryOP<BinaryOP<Matrix, Matrix, const<lambda(auto:5, auto:6)>&>, int, const<lambda(auto:1, auto:2)>&>::rhs', which is of non-class type 'const int'
       rhs.printrec();
       ~~~~^~~~~~~~
binary_operator.cpp: In instantiation of 'void BinaryOP<A, B, F>::printrec() const [with A = Matrix; B = Matrix; F = const<lambda(auto:5, auto:6)>&]':
binary_operator.cpp:87:7:   required from 'void BinaryOP<A, B, F>::printrec() const [with A = BinaryOP<Matrix, Matrix, const<lambda(auto:5, auto:6)>&>; B = int; F = const<lambda(auto:1, auto:2)>&]'
binary_operator.cpp:158:20:   required from here
binary_operator.cpp:87:11: error: 'const class Matrix' has no member named 'printrec'
       lhs.printrec();
       ~~~~^~~~~~~~
binary_operator.cpp:93:11: error: 'const class Matrix' has no member named 'printrec'
       rhs.printrec();
       ~~~~^~~~~~~~

shell returned 1

But if I change printrec by changing comments (see the code), I will get:

{{2:0, 3:0}:1, {{{5:0, 6:0}:1, {3:0, 0:0}:1}:1, 3:0}:1}
4
{{1 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 1
:0, 1 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 1
:0}:1, 6:0}
operator is recursable: 1
matrix is recursable: 0
float is recursable: 0
mattree is recursable: 1
1: {1 i, 0}

Clearly, when I try to evaluate (or print) the tree recursively, it fails to compile with an error as it can't find the same method (e.g. printrec) in a leaf (non-operator) class, but it seems (see is_recursive) that it is aware of which types are there in compile-time.

Answer 1

if(is_recursable<A>::value == 1)
  /* printf("1 %s", typeid(B).name()); */
  lhs.printrec();
else
  printf("0");

Until constexpr if exists you cannot do this. Reason being is that the compiler must assume that both branches are possible even if one or the other is not reachable--yeah, seems like it should be able to tell, but it's not allowed to by the language. You need to use tag dispatching or some other compile time construct.

See this answer