How to make `short-circuit evaluation` also available in `fold expressions`?

Question

#include <type_traits>

#define FORWARD(arg)\
std::forward<decltype(arg)>(arg)

template<typename... Args>
constexpr bool AndL(Args&&... args)
{
    return (... && FORWARD(args));
}

template<typename... Args>
constexpr bool AndR(Args&&... args)
{
    return (FORWARD(args) && ...);
}

int main()
{
    bool* pb = nullptr;

    false && (*pb = true);       // ok at runtime.
    AndL(false, (*pb = true));  // error at runtime!
    AndR(false, (*pb = true));  // error at runtime!
}

The traditional && operator supports short-circuit evaluation, so false && (*pb = true) will be ok at runtime, but the following two cases are not.

How to make short-circuit evaluation also available in fold expressions?

Benil

The issue here is not the fold expression at all. Try it with constexpr bool AND(bool a, bool b) { return a && b; }. The issue is that all arguments must be evaluated before calling the function, and it's their result that is passed in. – Hyetograph

You never new pb, all the *pb = true is undefined behavior. – Hierogram

The reason for the run-time evaluation is because *pb = true is itself not a constexpr. – Crowbar

@appleapple that's the point: using short-circuiting to check for nullptr before dereferencing. – Hyetograph

@Hyetograph thanks, it is not that obvious to me. And it's seems like OP is confused because of this. If OP tried with other expression which don't depend on undefined behavior. It might be more clear it's not possible to do it like this. – Hierogram

@Quentin: that should be an answer. – Aide

@VittorioRomeo it's a step towards an answer, but doesn't tell how to have short-circuiting. – Hyetograph

@Quentin: good point. Lambdas? :) – Aide

Answer 1

The problem here is just a misconception of what's actually happening.

How to make short-circuit evaluation also available in fold expressions?

It is available in fold expressions. (args && ... ) follows the exactly the same rules as (a && b && c && d). That is, d will only be evaluated if a, b, and c all evaluate to truthy.

That's not the actual difference between your two cases.

false && (*pb = true);       // ok at runtime.
AndL(false, (*pb = true));   // error at runtime!

While fold expressions do exactly the same thing as their non-fold counterparts, there's one important difference between these two statements. The first is just a statement-expression, the second is a function call. And all function arguments must be evaluated before the start of the body begins.

So the second is equivalent to:

auto&& a = false;
auto&& b = (*pb = true);
(FORWARD(a) && FORWARD(b));

It's that ordering that is causing the problem, not the fold expression (note: b could be evaluated before a).

In order to make this transparent, what you really need are lazy arguments. This is a feature in several languages (e.g. Scala), but not in C++. If you need laziness, the best you could do is wrap everything in a lambda:

template<typename... Args>
constexpr bool AndL(Args&&... args)
{
    return (... && FORWARD(args)());
}

AndL([]{ return false; }, [&]{ return *pb = true; });

You could then make this arbitrarily complex - maybe only "unwrap" those types that are callable, otherwise assume that they're bool:

template <class T, std::enable_if_t<std::is_invocable<T>::value, int> = 0>
bool unwrap(T&& val) { return std::forward<T>(val)(); }

template <class T, std::enable_if_t<std::is_convertible<T, bool>::value, int> = 0>
bool unwrap(T&& val) { return std::forward<T>(val); }

template<typename... Args>
constexpr bool AndL(Args&&... args)
{
    return (... && unwrap(FORWARD(args)));
}

AndL(false, [&]{ return *pb = true; });

But really, the main point is that function argument evaluation precedes the function body, and the issue is not the fold expression itself.

Pierian

Function arguments evaluation is sequenced before the evaluation of statements in the function bodies. This is applicative evaluation, a sequenced form of strict evaluation which guarantees every argument to be evaluated in despite of the body. Note that arguments are not lazy by themselves. Calls of functions may use call-by-name strategy to implement the non-strict evaluation. OTOH, lazy evaluation (call-by-need), is the memoized form of the call-by-name strategy, and not necessarily required here (though there is no difference if everything is evaluated once). – Youngyoungblood

And interestingly, using the wrapped thunks proposed there is not the only way to distinguish strict and non-strict forms. The thunks here are like Lisp's quote'd forms, which convey the non-strictness in an additional indirection invocation. A more direct way is in the contrast: treating the applicative evaluation a wrapped form of the operative one, and this seems neater, because evaluation of arguments + evaluation of the body is more than evaluation of the body in the overall operational semantics. Sadly most languages do not fall in this favor. – Youngyoungblood

Actually the direct reason I find the question here is that I fail to find the map/reduce/fold/accumulate-like algorithm neutral to strict and non-strict forms of the binary function. Most are strict-only, and a few (e.g. in Haskell) rely totally on the laziness. Even Kernel, one of the first languages making the idea of the explicit evaluation style (against to quote) clear, requires its reduce only accept an applicative binary. Still looking for a more general one... – Youngyoungblood