Lazy evaluation in C ++

Question

C ++ does not have built-in support for lazy evaluation (as Haskell does).

I am wondering if lazy evaluation in C ++ can be implemented in a reasonable way. If so, how would you do it?

EDIT: I like Conrad Rudolph's answer.

I am wondering if it is possible to implement it in a more general way, for example, using the parameterized class lazy, which essentially works for T, how the_add matrix works for the matrix.

Any operation on T will return instead of laziness. The only problem is storing the arguments and operation code inside the laziest one. Can anyone see how to improve this?

Answer 1

I am wondering if lazy evaluation in C ++ can be implemented in a reasonable way. If so, how would you do it?

Yes, this is possible and often done, for example. for matrix calculations. The main mechanism for this is operator overload. Consider the case of matrix addition. A function signature usually looks something like this:

matrix operator +(matrix const& a, matrix const& b); 

Now, to make this function lazy, it is enough to return the proxy instead of the actual result:

 struct matrix_add; matrix_add operator +(matrix const& a, matrix const& b) { return matrix_add(a, b); } 

Now all you need to do is write this proxy:

 struct matrix_add { matrix_add(matrix const& a, matrix const& b) : a(a), b(b) { } operator matrix() const { matrix result; // Do the addition. return result; } private: matrix const& a, b; }; 

The magic lies in the operator matrix() method, which is an implicit conversion operator from matrix_add to a simple matrix . Thus, you can combine several operations (of course, providing the appropriate overload). Evaluation is only performed when the end result is assigned to the matrix instance.

EDIT I should have been more explicit. Be that as it may, the code does not make sense, because although the evaluation is lazy, it still happens in one expression. In particular, another add-on will evaluate this code if the matrix_add structure matrix_add not changed to ensure that it is added to the chain. C ++ 0x greatly facilitates this by allowing variational patterns (i.e. lists of variable-length patterns).

However, one very simple case where this code really has real direct benefit is as follows:

 int value = (A + B)(2, 3); 

It is assumed here that A and B are two-dimensional matrices and that dereferencing occurs in Fortran notation, i.e. the above calculates one element from the sum of the matrix. Of course, it is wasteful to add all matrices. matrix_add to the rescue:

 struct matrix_add { // … yadda, yadda, yadda … int operator ()(unsigned int x, unsigned int y) { // Calculate *just one* element: return a(x, y) + b(x, y); } }; 

Other examples abound. I just remembered that I recently implemented something that was connected. Basically, I had to implement a string class that should stick to a fixed, predefined interface. However, my particular class of strings concerned huge strings that were not actually stored in memory. Typically, the user simply accesses the small substrings from the source string using the infix function. I overloaded this function for my string type in order to return a proxy server containing a link to my string, as well as the desired start and end position. Only when this substring was actually used did it request the C API to retrieve this part of the string.

Answer 2

Boost.Lambda is very nice, but Boost.Proto is exactly what you are looking for. It already has overloads of all C ++ operators, which by default perform their normal function when proto::eval() called, but can be changed.

Answer 3

What Conrad has already explained can be added to support nested operator calls that are executed lazily. In the Conrad example, he has an expression object that can store exactly two arguments, for exactly two operands of one operation. The problem is that it will perform only one subexpression lazily, which perfectly explains the concept in a lazy evaluation, a simple formulation, but does not significantly improve performance. Another example also shows how operator() can be applied to add only certain elements using this expression object. But to evaluate arbitrary complex expressions, we need some mechanism that can also preserve the structure of this. We cannot get around patterns to do this. And the name for this is expression templates . The idea is that one template expression object can recursively preserve the structure of an arbitrary subexpression, for example, a tree, where the operations are nodes and the operands are child nodes. For a very good explanation that I just found today (a few days after I wrote the code below), see here .

 template<typename Lhs, typename Rhs> struct AddOp { Lhs const& lhs; Rhs const& rhs; AddOp(Lhs const& lhs, Rhs const& rhs):lhs(lhs), rhs(rhs) { // empty body } Lhs const& get_lhs() const { return lhs; } Rhs const& get_rhs() const { return rhs; } }; 

This will store any add operation, even nested, as can be seen from the following definition of the + operator for a simple point type:

 struct Point { int x, y; }; // add expression template with point at the right template<typename Lhs, typename Rhs> AddOp<AddOp<Lhs, Rhs>, Point> operator+(AddOp<Lhs, Rhs> const& lhs, Point const& p) { return AddOp<AddOp<Lhs, Rhs>, Point>(lhs, p); } // add expression template with point at the left template<typename Lhs, typename Rhs> AddOp< Point, AddOp<Lhs, Rhs> > operator+(Point const& p, AddOp<Lhs, Rhs> const& rhs) { return AddOp< Point, AddOp<Lhs, Rhs> >(p, rhs); } // add two points, yield a expression template AddOp< Point, Point > operator+(Point const& lhs, Point const& rhs) { return AddOp<Point, Point>(lhs, rhs); } 

Now if you have

 Point p1 = { 1, 2 }, p2 = { 3, 4 }, p3 = { 5, 6 }; p1 + (p2 + p3); // returns AddOp< Point, AddOp<Point, Point> > 

Now you just need to overload operator = and add a suitable constructor for the Point type and accept AddOp. Change its definition to:

 struct Point { int x, y; Point(int x = 0, int y = 0):x(x), y(y) { } template<typename Lhs, typename Rhs> Point(AddOp<Lhs, Rhs> const& op) { x = op.get_x(); y = op.get_y(); } template<typename Lhs, typename Rhs> Point& operator=(AddOp<Lhs, Rhs> const& op) { x = op.get_x(); y = op.get_y(); return *this; } int get_x() const { return x; } int get_y() const { return y; } }; 

And add the corresponding get_x and get_y functions to AddOp as member functions:

 int get_x() const { return lhs.get_x() + rhs.get_x(); } int get_y() const { return lhs.get_y() + rhs.get_y(); } 

Note that we did not create temporary types of type Point. It could be a large matrix with many fields. But at a time when the result is needed, we calculate it lazily.

Answer 4

I have nothing to add to Konrad's post, but you can look at Eigen for an example of lazy evaluation done correctly in a real-world application. This is an impressive fear.

Answer 5

C ++ 0x is nice and that's it .... but for those of us who live in the present, you have the Boomb lambda and Boost Phoenix library. And in order to bring a lot of functional programming to C ++.

Answer 6

I am thinking of implementing a template class that uses std::function . A class should, more or less, look like this:

 template <typename Value> class Lazy { public: Lazy(std::function<Value()> function) : _function(function), _evaluated(false) {} Value &operator*() { Evaluate(); return _value; } Value *operator->() { Evaluate(); return &_value; } private: void Evaluate() { if (!_evaluated) { _value = _function(); _evaluated = true; } } std::function<Value()> _function; Value _value; bool _evaluated; }; 

For example, use:

 class Noisy { public: Noisy(int i = 0) : _i(i) { std::cout << "Noisy(" << _i << ")" << std::endl; } Noisy(const Noisy &that) : _i(that._i) { std::cout << "Noisy(const Noisy &)" << std::endl; } ~Noisy() { std::cout << "~Noisy(" << _i << ")" << std::endl; } void MakeNoise() { std::cout << "MakeNoise(" << _i << ")" << std::endl; } private: int _i; }; int main() { Lazy<Noisy> n = [] () { return Noisy(10); }; std::cout << "about to make noise" << std::endl; n->MakeNoise(); (*n).MakeNoise(); auto &nn = *n; nn.MakeNoise(); } 

Above the code should output the following message to the console:

 Noisy(0) about to make noise Noisy(10) ~Noisy(10) MakeNoise(10) MakeNoise(10) MakeNoise(10) ~Noisy(10) 

Note that the Noisy(10) constructor print will not be called until a variable is available.

This class is far from perfect. The first step is to use the default constructor Value , which must be called when the member is initialized (in this case, printing Noisy(0) ). Instead, we can use a pointer for _value , but I'm not sure if this will affect performance.

Answer 7

Everything is possible.

It depends on what you mean:

 class X { public: static X& getObjectA() { static X instanceA; return instanceA; } }; 

Here we have the influence of a global variable that is lazily evaluated at the point of first use.

As recently requested in the question.
And steal the design of Conrad Rudolph and expand it.

Lazy Object:

 template<typename O,typename T1,typename T2> struct Lazy { Lazy(T1 const& l,T2 const& r) :lhs(l),rhs(r) {} typedef typename O::Result Result; operator Result() const { O op; return op(lhs,rhs); } private: T1 const& lhs; T2 const& rhs; }; 

How to use it:

 namespace M { class Matrix { }; struct MatrixAdd { typedef Matrix Result; Result operator()(Matrix const& lhs,Matrix const& rhs) const { Result r; return r; } }; struct MatrixSub { typedef Matrix Result; Result operator()(Matrix const& lhs,Matrix const& rhs) const { Result r; return r; } }; template<typename T1,typename T2> Lazy<MatrixAdd,T1,T2> operator+(T1 const& lhs,T2 const& rhs) { return Lazy<MatrixAdd,T1,T2>(lhs,rhs); } template<typename T1,typename T2> Lazy<MatrixSub,T1,T2> operator-(T1 const& lhs,T2 const& rhs) { return Lazy<MatrixSub,T1,T2>(lhs,rhs); } } 

Answer 8

Johannes answers. But when it comes to more brackets, it doesn't work like a wish. Here is an example.

 Point p1 = { 1, 2 }, p2 = { 3, 4 }, p3 = { 5, 6 }, p4 = { 7, 8 }; (p1 + p2) + (p3+p4)// it works ,but not lazy enough 

Since the three overloaded + operators did not cover the case

 AddOp<Llhs,Lrhs>+AddOp<Rlhs,Rrhs> 

Thus, the compiler must convert either (p1 + p2) or (p3 + p4) to Point, which is not lazy enough. And when the compiler decides what to convert, it complains. Because no one is better than the other. Here is my extension: add another overloaded operator +

  template <typename LLhs, typename LRhs, typename RLhs, typename RRhs> AddOp<AddOp<LLhs, LRhs>, AddOp<RLhs, RRhs>> operator+(const AddOp<LLhs, LRhs> & leftOperandconst, const AddOp<RLhs, RRhs> & rightOperand) { return AddOp<AddOp<LLhs, LRhs>, AddOp<RLhs, RRhs>>(leftOperandconst, rightOperand); } 

Now the compiler can correctly handle this case and not imply a conversion, volia!

Answer 9

How this will be done in C ++ 0x , according to lambda expressions.

Answer 10

In C ++ 11, a lazy score like hiapay can be achieved with std :: shared_future. You still need to encapsulate the calculations in lambdas, but memoization takes care:

 std::shared_future<int> a = std::async(std::launch::deferred, [](){ return 1+1; }); 

Here is a complete example:

 #include <iostream> #include <future> #define LAZY(EXPR, ...) std::async(std::launch::deferred, [__VA_ARGS__](){ std::cout << "evaluating "#EXPR << std::endl; return EXPR; }) int main() { std::shared_future<int> f1 = LAZY(8); std::shared_future<int> f2 = LAZY(2); std::shared_future<int> f3 = LAZY(f1.get() * f2.get(), f1, f2); std::cout << "f3 = " << f3.get() << std::endl; std::cout << "f2 = " << f2.get() << std::endl; std::cout << "f1 = " << f1.get() << std::endl; return 0; } 

Answer 11

Simply create your own “container” class, which takes an object of the generating function and provides iterators.