Is there actually a reason why overloaded && and || don't short circuit?

Question

The short circuiting behaviour of the operators && and || is an amazing tool for programmers.

But why do they lose this behaviour when overloaded? I understand that operators are merely syntactic sugar for functions but the operators for bool have this behaviour, why should it be restricted to this single type? Is there any technical reasoning behind this?

Solution 1

All design processes result in compromises between mutually incompatible goals. Unfortunately, the design process for the overloaded && operator in C++ produced a confusing end result: that the very feature you want from && -- its short-circuiting behavior -- is omitted.

The details of how that design process ended up in this unfortunate place, those I don't know. It is however relevant to see how a later design process took this unpleasant outcome into account. In C#, the overloaded && operator is short circuiting. How did the designers of C# achieve that?

One of the other answers suggests "lambda lifting". That is:

A && B

could be realized as something morally equivalent to:

operator_&& ( A, ()=> B )

where the second argument uses some mechanism for lazy evaluation so that when evaluated, the side effects and value of the expression are produced. The implementation of the overloaded operator would only do the lazy evaluation when necessary.

This is not what the C# design team did. (Aside: though lambda lifting is what I did when it came time to do expression tree representation of the ?? operator, which requires certain conversion operations to be performed lazily. Describing that in detail would however be a major digression. Suffice to say: lambda lifting works but is sufficiently heavyweight that we wished to avoid it.)

Rather, the C# solution breaks the problem down into two separate problems:

• should we evaluate the right-hand operand?
• if the answer to the above was "yes", then how do we combine the two operands?

Therefore the problem is solved by making it illegal to overload && directly. Rather, in C# you must overload two operators, each of which answers one of those two questions.

class C
{
    // Is this thing "false-ish"? If yes, we can skip computing the right
    // hand size of an &&
    public static bool operator false (C c) { whatever }

    // If we didn't skip the RHS, how do we combine them?
    public static C operator & (C left, C right) { whatever }
    ...

(Aside: actually, three. C# requires that if operator false is provided then operator true must also be provided, which answers the question: is this thing "true-ish?". Typically there would be no reason to provide only one such operator so C# requires both.)

Consider a statement of the form:

C cresult = cleft && cright;

The compiler generates code for this as thought you had written this pseudo-C#:

C cresult;
C tempLeft = cleft;
cresult = C.false(tempLeft) ? tempLeft : C.&(tempLeft, cright);

As you can see, the left hand side is always evaluated. If it is determined to be "false-ish" then it is the result. Otherwise, the right hand side is evaluated, and the eager user-defined operator & is invoked.

The || operator is defined in the analogous way, as an invocation of operator true and the eager | operator:

cresult = C.true(tempLeft) ? tempLeft : C.|(tempLeft , cright);

By defining all four operators -- true, false, & and | -- C# allows you to not only say cleft && cright but also non-short-circuiting cleft & cright, and also if (cleft) if (cright) ..., and c ? consequence : alternative and while(c), and so on.

Now, I said that all design processes are the result of compromise. Here the C# language designers managed to get short-circuiting && and || right, but doing so requires overloading four operators instead of two, which some people find confusing. The operator true/false feature is one of the least well understood features in C#. The goal of having a sensible and straightforward language that is familiar to C++ users was opposed by the desires to have short circuiting and the desire to not implement lambda lifting or other forms of lazy evaluation. I think that was a reasonable compromise position, but it is important to realize that it is a compromise position. Just a different compromise position than the designers of C++ landed on.

If the subject of language design for such operators interests you, consider reading my series on why C# does not define these operators on nullable Booleans:

http://ericlippert.com/2012/03/26/null-is-not-false-part-one/

Solution 2

The point is that (within the bounds of C++98) the right-hand operand would be passed to the overloaded operator function as argument. In doing so, it would already be evaluated. There is nothing the operator||() or operator&&() code could or could not do that would avoid this.

The original operator is different, because it's not a function, but implemented at a lower level of the language.

Additional language features could have made non-evaluation of the right-hand operand syntactically possible. However, they didn't bother because there are only a select few cases where this would be semantically useful. (Just like ? :, which is not available for overloading at all.

(It took them 16 years to get lambdas into the standard...)

As for the semantical use, consider:

objectA && objectB

This boils down to:

template< typename T >
ClassA.operator&&( T const & objectB )

Think about what exactly you'd like to do with objectB (of unknown type) here, other than calling a conversion operator to bool, and how you'd put that into words for the language definition.

And if you are calling conversion to bool, well...

objectA && obectB

does the same thing, now does it? So why overload in the first place?

Solution 3

A feature has to be thought of, designed, implemented, documented and shipped.

Now we thought of it, let's see why it might be easy now (and hard to do then). Also keep in mind that there's only a limited amount of resources, so adding it might have chopped something else (What would you like to forego for it?).

---

In theory, all operators could allow short-circuiting behavior with only one "minor" additional language-feature, as of C++11 (when lambdas were introduced, 32 years after "C with classes" started in 1979, a still respectable 16 after c++98):

C++ would just need a way to annotate an argument as lazy-evaluated - a hidden-lambda - to avoid the evaluation until neccessary and allowed (pre-conditions met).

---

What would that theoretical feature look like (Remember that any new features should be widely usable)?

An annotation lazy, which applied to a function-argument makes the function a template expecting a functor, and makes the compiler pack the expression into a functor:

A operator&&(B b, __lazy C c) {return c;}

// And be called like
exp_b && exp_c;
// or
operator&&(exp_b, exp_c);

It would look under the cover like:

template<class Func> A operator&&(B b, Func& f) {auto&& c = f(); return c;}
// With `f` restricted to no-argument functors returning a `C`.

// And the call:
operator&&(exp_b, [&]{return exp_c;});

Take special note that the lambda stays hidden, and will be called at most once.
There should be no performance-degradation due to this, aside from reduced chances of common-subexpression-elimination.

---

Beside implementation-complexity and conceptual complexity (every feature increases both, unless it sufficiently eases those complexities for some other features), let's look at another important consideration: Backwards-compatibility.

While this language-feature would not break any code, it would subtly change any API taking advantage of it, which means any use in existing libraries would be a silent breaking change.

BTW: This feature, while easier to use, is strictly stronger than the C# solution of splitting && and || into two functions each for separate definition.

Solution 4

With retrospective rationalization, mainly because

• in order to have guaranteed short-circuiting (without introducing new syntax) the operators would have to be restricted to results actual first argument convertible to bool, and

• short circuiting can be easily expressed in other ways, when needed.

---

For example, if a class T has associated && and || operators, then the expression

auto x = a && b || c;

where a, b and c are expressions of type T, can be expressed with short circuiting as

auto&& and_arg = a;
auto&& and_result = (and_arg? and_arg && b : and_arg);
auto x = (and_result? and_result : and_result || c);

or perhaps more clearly as

auto x = [&]() -> T_op_result
{
    auto&& and_arg = a;
    auto&& and_result = (and_arg? and_arg && b : and_arg);
    if( and_result ) { return and_result; } else { return and_result || b; }
}();

The apparent redundancy preserves any side-effects from the operator invocations.

---

While the lambda rewrite is more verbose, its better encapsulation allows one to define such operators.

I’m not entirely sure of the standard-conformance of all of the following (still a bit of influensa), but it compiles cleanly with Visual C++ 12.0 (2013) and MinGW g++ 4.8.2:

#include <iostream>
using namespace std;

void say( char const* s ) { cout << s; }

struct S
{
    using Op_result = S;

    bool value;
    auto is_true() const -> bool { say( "!! " ); return value; }

    friend
    auto operator&&( S const a, S const b )
        -> S
    { say( "&& " ); return a.value? b : a; }

    friend
    auto operator||( S const a, S const b )
        -> S
    { say( "|| " ); return a.value? a : b; }

    friend
    auto operator<<( ostream& stream, S const o )
        -> ostream&
    { return stream << o.value; }

};

template< class T >
auto is_true( T const& x ) -> bool { return !!x; }

template<>
auto is_true( S const& x ) -> bool { return x.is_true(); }

#define SHORTED_AND( a, b ) \
[&]() \
{ \
    auto&& and_arg = (a); \
    return (is_true( and_arg )? and_arg && (b) : and_arg); \
}()

#define SHORTED_OR( a, b ) \
[&]() \
{ \
    auto&& or_arg = (a); \
    return (is_true( or_arg )? or_arg : or_arg || (b)); \
}()

auto main()
    -> int
{
    cout << boolalpha;
    for( int a = 0; a <= 1; ++a )
    {
        for( int b = 0; b <= 1; ++b )
        {
            for( int c = 0; c <= 1; ++c )
            {
                S oa{!!a}, ob{!!b}, oc{!!c};
                cout << a << b << c << " -> ";
                auto x = SHORTED_OR( SHORTED_AND( oa, ob ), oc );
                cout << x << endl;
            }
        }
    }
}

Output:

000 -> !! !! || false
001 -> !! !! || true
010 -> !! !! || false
011 -> !! !! || true
100 -> !! && !! || false
101 -> !! && !! || true
110 -> !! && !! true
111 -> !! && !! true

Here each !! bang-bang shows a conversion to bool, i.e. an argument value check.

Since a compiler can easily do the same, and additionally optimize it, this is a demonstrated possible implementation and any claim of impossibility must be put in the same category as impossibility claims in general, namely, generally bollocks.

Solution 5

Short circuiting the logical operators is allowed because it is an "optimisation" in the evaluation of the associated truth tables. It is a function of the logic itself, and this logic is defined.

Is there actually a reason why overloaded && and || don't short circuit?

Custom overloaded logical operators are not obliged to follow the logic of these truth tables.

But why do they lose this behaviour when overloaded?

Hence the entire function needs to be evaluated as per normal. The compiler must treat it as a normal overloaded operator (or function) and it can still apply optimisations as it would with any other function.

People overload the logical operators for a variety of reasons. For example; they may have specific meaning in a specific domain that is not the "normal" logical ones people are accustomed to.

View more solutions

Comments

[Cheers and hth. - Alf]

well your logic error is to reason within the currently defined language about the effects of a differently defined language. in the old days a lot of newbies used to do that wrt. "virtual constructor". it took an inordinate amount of explanation to get them out of such box-thinking. anyway, with short-circuiting of built-in operators there are guarantees about argument non-evaluation. such guarantee would also be there for user-defined overloads, if short-circuiting was defined for them.

[iFreilicht]

@Alf I have to agree that he only explained why it doesn't work currently (and I know why that is), and not why there is no feature that makes it work.

[iFreilicht]

As mentioned in the comments and in @Deduplicators answer, it would be possible with an additional language feature. I know that it doesn't work now. My question was what the reasoning behind not there being such a feature is.

[nj-ath]

Well it certainly would be a complicated feature, considering we have to venture a guess about the user's definition of it!

[iFreilicht]

I like your short circuit substitutions, especially the ternary one, which is as close as you can probably get.

[DevSolar]

@iFreilicht: I basically said the same thing as Deduplicator or Piotr, just with different words. I elaborated a bit on the point in the edited answer. It was much more convenient this way, necessary language extensions (e.g. lambdas) didn't exist until recently, and the benefit would have been negligible anyway. The few times where the people responsible would have "liked" something that wasn't already done by compiler builders, back in 1998, it backfired. (See export.)

[iFreilicht]

What about : (<condition>) after the operator declaration to specify a condition at which the second argument is not evaluated?

[iFreilicht]

This edit certainly makes your answer better, but with an overloaded operator one would be able to use all member variables of both arguments to determine the output. I think it would have benefits, but the complexity of implementing that feature probably weighs those out. Also thanks for explaining the builtin operator thing a bit.

[DevSolar]

@iFreilicht: A bool conversion operator for either class has access to all member variables as well, and works fine with the builtin operator. Anything else but conversion-to-bool doesn't make semantic sense for short-circuit evaluation anyway! Try to approach this from a semantic standpoint, not a syntactical one: What would you be trying to achieve, not how you would go about it.

[iFreilicht]

I have to admit that I can't think of one. The only reason short circuiting exists is because it saves time for operations on Booleans and you can know the result of an expression prior to all arguments being evaluated. With other AND operations, that is not the case, and that is why & and && are not the same operator. Thanks for helping me realise that.

[Oliver Charlesworth]

@iFreilicht: Well, perhaps optimisations, and also for abbreviations like if (foo != NULL && foo->bar()). But yeah, I can't see a meaningful use for either of those in a non-bool context.

[iFreilicht]

@OliverCharlesworth I believe these abbreviations are a side effect of short circuit behaviour and not the reason why it was implemented in the first place. But yeah, those were what initially got me thinking about it.

[dyp]

Short circuiting can make sense for non-boolean types if it could delay evaluating the rhs expression under some condition. But I think this doesn't work well with the pass values to functions C++ uses (as opposed to, say pass expressions to functions). One could think of implementations like an operator&& getting only the lhs, then iff it returns true, the rhs is evaluated and passed on to another function.

[DevSolar]

@dys: That's what we've been talking about, yes: You'd need lambdas ("pass expressions to functions"), which only appeared with C++11. And as we found out, yes, that's how it syntactically could work, but it still wouldn't make sense semantically.

[dyp]

I don't think you need lambdas. You could define some pair<bool, result> operator&&(LHS lhs) that the compiler calls only evaluating the lhs; then, if the .first of the returned pair is true, the compiler calls another function result2 operator&&(result r, RHS rhs). But as you can see, this is rather complicated.

[dyp]

@DevSolar I do think it can make sense semantically. For example, if you want && to return something other than bool. E.g. combine two objects if the first one fulfils some condition; return either the combined object or some null-object.

[Arne Mertz]

You are missing the short-circuiting of the && - there would need to be an additional line like if (!a) { return some_false_ish_T(); } - and to your first bullet: short-circuiting is about the parameters convertible to bool, not the results.

[Cheers and hth. - Alf]

This appears to become Yet Another Highly Upvoted Incorrect SO Answer. But we do not need any more examples that the SO voting system doesn't work. Consequently I have now provided a counter example in my answer. Contrary to the claimed impossibility, the code there does what's claimed to be impossible. People, please redact your upvotes of this (incorrect) answer.

[Cheers and hth. - Alf]

@ArneMertz: your comment about "Missing" is apparently meaningless. the comment about what it's about, yes i'm aware of that. conversion to bool is necessary to do short-circuiting.

[BlackJack]

Is the cost really that high? The D programming language allows to declare parameters as lazy which turns the expression given as arguments implicitly into an anonymous function. This gives the called function the choice to call that argument, or not. So if the language already has lambdas the extra syntax needed is very tiny. ”Pseudocode”: X and(A a, lazy B b) { if (cond(a)) { return short(a); } else { actual(a, b()); }}

[Arne Mertz]

@Cheersandhth.-Alf the comment about missing was for the first revision of your answer where you did short-circuit the || but not the &&. The other comment was aimed at the "would have to be restricted to results convertible to bool" in your first bullet point - it should read "restricted to parameters convertible to bool" imo.

[Cheers and hth. - Alf]

@ArneMertz: OK, re versioning, sorry I'm slow editing. Re restricted, no it's the operator result that has to be restricted, because it has to be converted to bool in order to check for short circuting of further operators in the expression. Like, result of a && b has to be converted to bool to check for short-circuting of the logical OR in a && b || c.

[Arne Mertz]

@BlackJack that lazy parameter could be implemented by accepting a std::function<B()>, which would incur a certain overhead. Or if you are willing to inline it make it template <class F> X and(A a, F&& f){ ... actual(a,F()) ...}. And maybe overload it with the "normal" B parameter, so the caller can decide which version to choose. The lazy syntax may be more convenient but has a certain performance tradeoff.

[Cheers and hth. - Alf]

@ArneMetz: thinking about it, the least restrictive is probably to require any actual first argument to be convertible to bool.

[MSalters]

Retriction doesn't make sense. a && b can be short-circuited in theory if (1) a && b == f(a) whenever g(a)==true for arbitrary T f(A) and bool g(A). There is no fundamental reason to restrict g() to the identity function or A::operator bool.

[MSalters]

@iFreilicht: You'd still need an alternative unary function body.

[MSalters]

One of the problems with std::function versus lazy is that the first can be evaluated multiple times. A lazy parameter foo which is used as foo+foo is still only evaluated once.

[Deduplicator]

You know, your first point, that the operator would need to be restricted to actual first argument convertible to bool does not make sense. See, you are writing the operator, thus you can make whatever tests you deem sufficient on the first argument (including that conversion if you deem that the right test) to determine whether the second one should be evaluated, and then you have complete freedom in how they are combined for the final result (like e.g. returning the first if you didn't calculate the second, and otherwise returning the second one).

[Cheers and hth. - Alf]

@Deduplicator: if you're talking about some notation for explicit short-circuit condition, then maybe yes "you can make whatever tests". but within the body of an ordinary overload, with the syntax of the language preserved, you can't do short-circuiting because when execution reaches the body, the arguments have already been evaluated.

[Cheers and hth. - Alf]

@MSalters: Yes, but with an arbitrary short-circuit decision function g you need new syntax in order to specify g. So thanks, i should perhaps have mentioned that restriction is only needed for the limitation of redefining semantics for the existing syntax.

[Deduplicator]

@Cheers: I updated my answer to show how, with exactly one new (fairly minor) language-feature (as of C++11 though), one could implement short-circuiting operators, or generally lazy-evaluated function-arguments without explicit lambdas.

[Mooing Duck]

"the use of short-circuits would be restricted to cases where Y is convetible to X"... no, it's restricted to cases where X can be calculated based on Y alone. Very different. std::ostream& operator||(char* a, lazy char*b) {if (a) return std::cout<<a;return std::cout<<b;}. Unless you are using a very casual usage of "conversion".

[Eric Lippert]

As @deduplicator points out correctly, the first operand does not need to be convertible to bool; rather, what is required to know is whether the second operand must be computed or not, and that is a subtle but extremely important distinction. In the case of && we do not need to know whether the first operand is logically true or false, just whether or not it is "false-ish" enough to skip computing the second operand. See my answer for details.

[Eric Lippert]

@Deduplicator: You might also be interested to read this question and answers: stackoverflow.com/questions/5965968/…

[Eric Lippert]

@iFreilicht: You said "The only reason short circuiting exists is because it saves time for operations on Booleans and you can know the result of an expression prior to all arguments being evaluated" Your belief is false. First, && does not save time the vast majority of the time. Which is faster, result = foo.bar & foo.blah or if (foo.bar) result = foo.blah else result = foo.bar? The former is like a single machine instruction. The latter is several basic blocks, opportunities for the branch predictor to make a mistake, and so on. But the latter is the && operator!

[Eric Lippert]

@iFreilicht: Rather, the purpose of short circuiting is because the computation of the left hand side can establish the truth of a precondition of the right hand side. if (x != NULL && x->foo) requires short circuiting, not for speed, but for safety.

[Eric Lippert]

@iFreilicht: Any question of the form "why does feature X not exist?" has the same answer: to exist the feature must have been thought of, considered to be a good idea, designed, specified, implemented, tested, documented, and shipped to the end user. If any one of those things did not happen, no feature. One of those things did not happen with your proposed feature; finding out which one is a historical research problem; start talking to people on the design committee if you care which one of those things was never done.

[Cheers and hth. - Alf]

@ErikLippert: you can't evaluate "false-ish enough" within existing syntax.

[Deduplicator]

@EricLippert: And, depending on which reason it is, repeat until it is implemented: Perhaps it was thought too complicated, and noone thought to do a re-evaluation. Or the re-evaluation ended with different reasons to reject than earlier held. (btw: Added the gist of your comment)

[Cheers and hth. - Alf]

@ErikLippert: But with some means of defining false-ish and true-ish, that idea (first mentioned by MSalters, and I updated the answer in response to his comment) appears to be what's needed for e.g. set intersection and union expressed via && and ||. You need false-ish for intersection (corresponding to empty set) and true-ish for union (corresponding to complement of empty set).

[Cheers and hth. - Alf]

A slight reduction in generality brings some clarity in naming, namely "operator false" as is_min and "operator true" as is_max. This correspond to a view of boolean operations as minimum (for AND) and maximum (for OR), which works nicely also for tri-value logic. The conceptual view can't be applied for sets but is_min and is_max works nicely also there (empty set, set of all things), so it would be interesting to hear if you know of any example where this naming would not work well. If none such, then I think I'll use it. ;-)

[supercat]

I wonder if any consideration was given to the question of whether overloads of &&, ||, and , should be allowed? The fact that C++ has no mechanism to allow overloads to behave like anything other than function calls explains why the overloads of those functions can't do anything else, but it doesn't explain why those operators are overloadable in the first place. I suspect the real reason is simply that they got thrown in a list of operators without much thought.

[Cody Gray]

In this case, I think the compromise is more than justified. The complicated stuff is something that only the architect of a class library must be concerned with, and in exchange for this complication, it makes the consumption of the library easier and more intuitive.

[Sumant]

@Deduplicator With expression templates neither the lazy keyword nor lambdas are required.

[Sumant]

@Arne Expression templates can easily solve this problem. See my answer below if interested.

[Arne Mertz]

@MooingDuck "...or else there had to be additional info of how to actually do the short circuiting (i.e. compute the result from only the first parameter)" which is what your early return does.

[Arne Mertz]

@Sumant they can. But you also can write out the logic of a short-circuiting custom operator&& by hand. The question is not if it's possible, but why there is not a short convenient way.

[Marc van Leeuwen]

As a historical aside, note that the original Algol 68 language had a "proceduring" coercion (as well as deproceduring, which means implicitly calling a parameterless function when the context requires the result type rather than the function type). This means that an expression of type T in a position that requires a value of type "parameterless function returning T" (spelled "proc T" in Algol 68) would be implicitly transformed into function body returning the expression given (implicit lambda). The feature was removed (unlike deproceduring) in the 1973 revision of the language.

[Marc van Leeuwen]

...For C++ a similar approach could be to declare operators like && to take one argument of type "pointer to function returning T" and an additional conversion rule that allows an argument expression of type T to be implicitly converted into a lambda expression. Note that this is not an ordinary conversion, as it must be done at the syntactic level: turning at runtime a value of type T into a function would be of no use as evaluation would already have been done.

[Joshua Taylor]

People ask similar questions about "why can't I apply and to a list in Lisp?" E.g., Why (apply and '(1 2 3)) doesn't work while (and 1 2 3) works in R5RS?, and the answer is that "because functions don't get special argument evaluation." In the linked question there are answers about an "and" function that takes functions as arguments, which is essentially the lambda lifting you describe.

[WernerCD]

@EricLippert I believe Envision was stating that he saw this post and thought it was you... then saw he was right. He wasn't saying your post is irrelevant. His noticing your distinct writing style is irrelevant.

[asawyer]

@EnvisionAndDevelop You can get all of his posts right to your favorite rss reader!

[Eric Lippert]

@EnvisionAndDevelop: Ah, I apologize for my misunderstanding and withdraw my remark! Cheers.

[Voo]

I find the idea that you have to decide whether the first value is truish (or falsish) if you want to short-circuit rather logical. What I find not clear is why C# went with two explicit operators for it instead of just using a conversion to bool for it (which is what python does).

[Cheers and hth. - Alf]

@Voo: consider sets. && as intersection needs to know if first argument is empty set. || as union needs to know if first argument is set of everything. A conversion to two-valued boolean can't capture both cases. However, a conversion two tri-value boolean can.

[Deduplicator]

@MarcvanLeeuwen: It needs to be at least two pointers if you go that route: Function-pointer+Context-pointer.

[Marc van Leeuwen]

@Deduplicator: You're right, or rather, I should have realised that having local functions is just not a C++-like way to go (C++ functions never use a context pointer, though |this| in class methods plays a somewhat similar role). Instead the (implicit) argument type should be reference to some functor type returning T (for which an appropriate lambda would provide an instance).

[codenheim]

The Microsoft team does not get enough credit for (1) making a marked good effort to do the right thing in C# and (2) getting it right more times than not.

[Eric Lippert]

@Voo: If you choose to implement an implicit conversion to bool then you can use && and || without implementing operator true/false or operator &/| in C# no problem. The problem arises precisely in the situation where there is no conversion to bool possible, or where one is not desired.

[supercat]

@Cheersandhth.-Alf: Sets are also a nice example of why having separate operators may be better than a three-value one: determination of whether left-hand operand of || or && will compel evaluation of the right-hand operand can early-exit as soon as it finds anything indicating that it must do so.

[dshin]

@Cheersandhth.-Alf I encountered this problem and came up with essentially the same macro solution as you (allowing multiple arguments instead of just 2), along with a version for the ternary operator. It works, but I really pine for a c++ language solution that would allow me to define short-circuited &&, ||, and ?. I want the users of my library to write code that looks/feels/smells like it is dealing with primitives, but instead they have to write nasty expressions like TERNARY(AND(TERNARY(...)), which adds undesirable code-readability overhead.