Lazy Evaluation in C++

C : is there lazy evaluation when using && operator, as in C++?

Yes && is short circuited and you are using it correctly.
If next is NULL string compare will never happen.

How would one implement Lazy Evaluation in C?

You could try to encapsulate this in a struct:

typedef struct s_generator {
    int current;
    int (*func)(int);
} generator;

int next(generator* gen) {
    int result = gen->current;
    gen->current = (gen->func)(gen->current);
    return result;
}

Then you define you multiples with:

int next_multiple(int current) { return 2 + current; }
generator multiples_of_2 = {0, next_multiple};

You get the next multiple by calling

next(&multiples_of_2);

C++ lazy evaluation of boolean or in function call expression

In C/C++ the logical operators short-circuit. In a || b if a is true b is not evaluated and in a && b if a is false b is not evaluated.

Careful: this only happens with && and ||, not with | and &.

C++17 static template lazy evaluation

I am familiar with lazy evaluation in C++, and would expect that the second branch of the if statement the generic fibonacci template would not be evaluated, when an argument < 0 is passed.

It doesn't need to be evaluated. But we aren't dealing with evaluation here. We are dealing with template instantiation. You used fibonacci<n-1>::value, and that requires the complete object type fibonacci<n-1> to be instantiated. The type has to be checked, to see if it has a member value that can be used in such an expression.

Instantiating a class template causes the declarations of its members to be instantiated. The declaration of the static data member contains an initializer, which must therefore be instantiated as well. So we hit the need to instantiate the template recursively.

Simply naming fibonacci<n-1> won't cause it to be instantiated (think forward declarations). If you want to delay the instantiation, you must delay using those types in a way that requires their definition (such as accessing a member).

The old meta-programming trick for this (that is very in line with functional programming) involves helper templates.

template<class L, class R>
struct add {
    static constexpr auto value = L::value + R::value;
};

template<int n>
struct fibonacci {
    static const int value = std::conditional_t<(n < 0), fibonacci<0>, add<fibonacci<n-1>, fibonacci<n-2>>>::value;
};

std::conditional_t will choose a type based on the condition. Then, the ::value of that type (and only that type) is accessed. So nothing is fully instantiated until actually needed.

A way of achieving lazy evaluation in C++

• You may want to have thunk_type and reference to it as a separate objects. Right now copy of lazy<T> will gain nothing from evaluation of origin. But in that case you'll get additional indirect access.
• Sometimes you may get rid of wrapping into std::function by simply using templates.
• I'm not sure that value needs to be shared_ptr. Maybe caller should decide that.
• You are going to produce new closures on each access.

Consider next modification:

template<typename F>
lazy(const F& x) :
  thunk_ptr([&x,&this](){
    T val = (*x)();
    thunk_ptr = [val]() { return val; };
    return val;
  })
{}

Or alternative implementation might look like:

template<typename F>
auto memo(const F &x) -> std::function<const decltype(x()) &()> {
    typedef decltype(x()) return_type;
    typedef std::function<const return_type &()> thunk_type;
    auto thunk_ptr = std::make_shared<thunk_type>();
    auto *thunk_cptr = thunk_ptr.get();

    // note that this lambda is called only from scope which holds thunk_ptr
    *thunk_ptr = [thunk_cptr, &x]() {
        auto val = std::move(x());
        auto &thunk = *thunk_cptr;
        thunk = [val]() { return val; };
        // at this moment we can't refer to catched vars
        return thunk();
    };

    return [thunk_ptr]() { return (*thunk_ptr)(); };
};

Lazy arithmetic in C

In case of logical operators && and || order of evaluation bound to take place from left to right and short circuiting takes place.
There is a sequence point between evaluation of the left and right operands of the && (logical AND), || (logical OR) (as part of short-circuit evaluation). For example, in the expression *p++ != 0 && *q++ != 0, all side effects of the sub-expression *p++ != 0 are completed before any attempt to access q, but not in case of arithmetic operators .

What is short-circuit evaluation in C?

The && operator uses lazy evaluation. If either side of the && operator is false, then the whole expression is false.

C checks the truth value of the left hand side of the operator, which in your case is 0. Since 0 is false in c, then the right hand side expression of the operation, (a = b = 777), is never evaluated.

The second case is similar, except that || returns true if the left hand side expression returns true. Also remember that in c, anything that is not 0 is considered true.

Hope this helps.

What is the use case for not having lazy evaluation of value_or()?

It's not possible to design a function that does lazy evaluation. Function arguments are always evaluated if the function call itself is evaluated. The ONLY things that can short-circuit or evaluate in a lazy way are the built-in && and || and ?: operators.

Other related comments:

A few Standard library functions or features do things that would not be possible to implement in portable code, so they require some compiler "magic". But they try to keep those sorts of things limited.

Even an overloaded operator function operator&& or operator|| still must evaluate its operands, so that's a caution about overloading those: they'll never act just like the built-in versions.

Although the value_or function itself can't put off evaluating its argument, there are some tricks you could use to pass in a lazy placeholder that only does a computation if it's actually needed.

Lazy evaluation in C++

I'm wondering if it is possible to implement lazy evaluation in C++ in a reasonable manner. If yes, how would you do it?

Yes, this is possible and quite often done, e.g. for matrix calculations. The main mechanism to facilitate this is operator overloading. Consider the case of matrix addition. The signature of the function would usually look something like this:

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

Now, to make this function lazy, it's enough to return a 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 that needs to be done is to 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 method operator matrix() which is an implicit conversion operator from matrix_add to plain matrix. This way, you can chain multiple operations (by providing appropriate overloads of course). The evaluation takes place only when the final result is assigned to a matrix instance.

EDIT I should have been more explicit. As it is, the code makes no sense because although evaluation happens lazily, it still happens in the same expression. In particular, another addition will evaluate this code unless the matrix_add structure is changed to allow chained addition. C++0x greatly facilitates this by allowing variadic templates (i.e. template lists of variable length).

However, one very simple case where this code would actually have a real, direct benefit is the following:

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

Here, it is assumed that A and B are two-dimensional matrices and that dereferencing is done in Fortran notation, i.e. the above calculates one element out of a matrix sum. It's of course wasteful to add the whole 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've just remembered that I have implemented something related not long ago. Basically, I had to implement a string class that should adhere to a fixed, pre-defined interface. However, my particular string class dealt with huge strings that weren't actually stored in memory. Usually, the user would just access small substrings from the original string using a function infix. I overloaded this function for my string type to return a proxy that held a reference to my string, along with the desired start and end position. Only when this substring was actually used did it query a C API to retrieve this portion of the string.

---

Related Topics