Skip to main content

Short-circuiting overloaded && and || using expression templates

This blog post is just a quick note that C++ offers (at least) two distinct ways to represent lazy computation that is lexically in the same scope but may execute lazily at a later time. In doing so, the computation must capture the local context (i.e., variables) so that it can be used later when needed. Clearly, lambda expressions are a direct language supported mechanism for that. Closures that come out of a lambda expression often capture the context and of course some behavior to be run later. The second mechanism is about 20 years old (as of this writing): Expression Templates.

Lets take an example of short-circuiting overloaded && and || operators. Regular overloaded && and || do not short circuit in C++. The reason is that before calling the overloaded operator &&, both the left-hand-side and the right-hand-side arguments of the overloaded function are evaluated. A function call is a sequence-point and therefore all the computations and the side-effects are complete before making the function call. This is eager strategy.

Expression Templates is a library-only approach to defer computation at a later time while keeping the context of the original expression around. Sounds a lot like lambda expressions.

Consider the struct S below. I would like to implement short-circuiting && and || for this type.

struct S
{
  bool val;
  explicit S(bool b) : val(b) {}

  bool is_true () const 
  {
    return val;
  }
};

S operator && (const S & s1, const S & s2)
{
  return s1.is_true()? S{s1.val && s2.val} : s1;
}

int main(void)
{
  S s1{false}, s2{true}, s3{true};
  S s4 = s1 && s2 && s3; // false
}
There is hardly any optimization at all. The overloaded && operator is called twice no matter what. Although the result of the expression s1 && s2 && s3 is known just by looking at s1. An opportunity for optimization is wasted (if you ever wanted to optimize that way!).

So let's use expression templates. The trick is to convert the expression into a tree of recursively nested instantiations of the Expr template. The tree is evaluated separately after construction.

The following code implements short-circuited && and || operators for S as long as it provides logical_and and logical_or free functions and it is convertible to bool. The code is in C++14 but the idea is applicable in C++98 also.

#include <iostream>

struct S
{
  bool val;

  explicit S(int i) : val(i) {}  
  explicit S(bool b) : val(b) {}

  template <class Expr>
  S (const Expr & expr)
   : val(evaluate(expr).val)
  { }

  template <class Expr>
  S & operator = (const Expr & expr)
  {
    val = evaluate(expr).val;
    return *this;
  }

  bool is_true () const 
  {
    return val;
  }
};

S logical_and (const S & lhs, const S & rhs)
{
    std::cout << "&& ";
    return S{lhs.val && rhs.val};
}

S logical_or (const S & lhs, const S & rhs)
{
    std::cout << "|| ";
    return S{lhs.val || rhs.val};
}


const S & evaluate(const S &s) 
{
  return s;
}

template <class Expr>
S evaluate(const Expr & expr) 
{
  return expr.eval();
}

struct LazyAnd 
{
  template <class LExpr, class RExpr>
  auto operator ()(const LExpr & l, const RExpr & r) const
  {
    const auto & temp = evaluate(l);
    return temp.is_true()? logical_and(temp, evaluate(r)) : temp;
  }
};

struct LazyOr 
{
  template <class LExpr, class RExpr>
  auto operator ()(const LExpr & l, const RExpr & r) const
  {
    const auto & temp = evaluate(l);
    return temp.is_true()? temp : logical_or(temp, evaluate(r));
  }
};


template <class Op, class LExpr, class RExpr>
struct Expr
{
  Op op;
  const LExpr &lhs;
  const RExpr &rhs;

  Expr(const LExpr& l, const RExpr & r)
   : lhs(l),
     rhs(r)
  {}

  auto eval() const 
  {
    return op(lhs, rhs);
  }
};

template <class LExpr>
auto operator && (const LExpr & lhs, const S & rhs)
{
  return Expr<LazyAnd, LExpr, S> (lhs, rhs);
}

template <class LExpr, class Op, class L, class R>
auto operator && (const LExpr & lhs, const Expr<Op,L,R> & rhs)
{
  return Expr<LazyAnd, LExpr, Expr<Op,L,R>> (lhs, rhs);
}

template <class LExpr>
auto operator || (const LExpr & lhs, const S & rhs)
{
  return Expr<LazyOr, LExpr, S> (lhs, rhs);
}

template <class LExpr, class Op, class L, class R>
auto operator || (const LExpr & lhs, const Expr<Op,L,R> & rhs)
{
  return Expr<LazyOr, LExpr, Expr<Op,L,R>> (lhs, rhs);
}

std::ostream & operator << (std::ostream & o, const S & s)
{
  o << s.val;
  return o;
}

S and_result(S s1, S s2, S s3)
{
  return s1 && s2 && s3;
}

S or_result(S s1, S s2, S s3)
{
  return s1 || s2 || s3;
}

int main(void) 
{
  for(int i=0; i<= 1; ++i)
    for(int j=0; j<= 1; ++j)
      for(int k=0; k<= 1; ++k)
        std::cout << i << j << k << " " << and_result(S{i}, S{j}, S{k}) << std::endl;

  for(int i=0; i<= 1; ++i)
    for(int j=0; j<= 1; ++j)
      for(int k=0; k<= 1; ++k)
        std::cout << i << j << k << " " << or_result(S{i}, S{j}, S{k}) << std::endl;

  return 0;
}
Let's break it apart piece by piece.

Type S has new conversion and assignment operators that convert a generic Expr argument that is convertible to S. The expression is not evaluated until it is actually assigned to another S. We just call evaluate on the expression to begin execution of the computation wrapped inside Expr. logical_and and logical_or are free functions that perform the non-short-circuiting logical operations because we're going to hijack the overloaded && and || for short-circuiting.

The evaluate free functions take care of the trivial base case when Expr happens to just another S and all other cases when Expr is a compound expression.

struct LazyAnd and LazyOr are the short-circuiting && and ||. They always evaluate the left-hand-side but may not evaluate the right-hand-side if it is not required.

Expr template enables construction of so called expression templates. It is meant to be instantiated recursively. for example, an expression template for (s1 && s2) looks like Expr<LazyAnd, S, S> whereas for (s1 && s2 && s3) it is Expr<LazyAnd, Expr<LazyAnd, S , S>, S>. One last example: (s1 && (s2 && s3)) becomes Expr<LazyAnd, S, Expr<LazyAnd, S , S>>.

Of course, creating the nested Expr instantiations manually is berserk. So we use overloaded && and || operators that instead of computing the result eagerly, produce and expression that we can evaluate later. I've avoided writing overly generic && and || operator by using the second argument that is either S or and Expr. So the operator does not match with types outside those. Take a look at the examples above. It is fairly straightforward to see how an expressions turns into a tree. Note that construction of tree does not involve calling logical_and and logical_or functions

Finally, the assignment operator and copy-ctor of S take care of executing the expression. LazyAnd and LazyOr do the least possible work while ensuring that left-hand-side is always evaluated. Here is the output of the program. Checkout the live example here.
000 0
001 0
010 0
011 0
100 && 0
101 && 0
110 && && 0
111 && && 1
000 || || 0
001 || || 1
010 || 1
011 || 1
100 1
101 1
110 1
111 1
Bottom line: Expression templates and lambdas are both suitable for passing lazy computations to functions. They both can capture local context (variables) and don't extend the life-cycle of the captured argument. Their type is not meant to be observed (it is often unpronounceable). Expression templates, however, are very specific because they appear only in the context of overloaded operators and as a result they may be lot more expressive.

This blog post is motivate by this question on Stackoverflow. Also see comments on reddit/r/cpp.

Comments

Thanks for your ideas. You can also find the details on Affity Solutions, at the C Developers. The main object of the Affity Solutions is to provide quality web services and is among the few software development company in Nagpur.
Jawad Jamal said…
Your way of making things clear is really awesome. Thank you for sharing this post. I am also working for the betterment of student through C++ Urdu Tutorial
cpp hub said…
The presentation of the topics are really good.

url=http://www.cpphub.com/]cpp hub[/url] | [url=http://www.cpphub.com/search/label/Operator%20Overloading/]Operator Overlaoading[/url]
pavuluri santhi said…
Operator overloading explained well here.

Operator Overloading
manho valentine said…

Hello!
I think that Keep posting more informative articles like these one.
These are very good articles to visit...
golden slot mobile
gclub

Popular posts from this blog

Multi-dimensional arrays in C++11

What new can be said about multi-dimensional arrays in C++? As it turns out, quite a bit! With the advent of C++11, we get new standard library class std::array. We also get new language features, such as template aliases and variadic templates. So I'll talk about interesting ways in which they come together.

It all started with a simple question of how to define a multi-dimensional std::array. It is a great example of deceptively simple things. Are the following the two arrays identical except that one is native and the other one is std::array?

int native[3][4];
std::array<std::array<int, 3>, 4> arr;

No! They are not. In fact, arr is more like an int[4][3]. Note the difference in the array subscripts. The native array is an array of 3 elements where every element is itself an array of 4 integers. 3 rows and 4 columns. If you want a std::array with the same layout, what you really need is:

std::array<std::array<int, 4>, 3> arr;

That's quite annoying for two r…

Folding Monadic Functions

In the previous two blog posts (Understanding Fold Expressions and Folding Functions) we looked at the basic usage of C++17 fold expressions and how simple functions can be folded to create a composite one. We’ll continue our stride and see how "embellished" functions may be composed in fold expressions.

First, let me define what I mean by embellished functions. Instead of just returning a simple value, these functions are going to return a generic container of the desired value. The choice of container is very broad but not arbitrary. There are some constraints on the container and once you select a generic container, all functions must return values of the same container. Let's begin with std::vector.
// Hide the allocator template argument of std::vector. // It causes problems and is irrelevant here. template <class T> struct Vector : std::vector<T> {}; struct Continent { }; struct Country { }; struct State { }; struct City { }; auto get_countries…

Covariance and Contravariance in C++ Standard Library

Covariance and Contravariance are concepts that come up often as you go deeper into generic programming. While designing a language that supports parametric polymorphism (e.g., templates in C++, generics in Java, C#), the language designer has a choice between Invariance, Covariance, and Contravariance when dealing with generic types. C++'s choice is "invariance". Let's look at an example.
struct Vehicle {}; struct Car : Vehicle {}; std::vector<Vehicle *> vehicles; std::vector<Car *> cars; vehicles = cars; // Does not compile The above program does not compile because C++ templates are invariant. Of course, each time a C++ template is instantiated, the compiler creates a brand new type that uniquely represents that instantiation. Any other type to the same template creates another unique type that has nothing to do with the earlier one. Any two unrelated user-defined types in C++ can't be assigned to each-other by default. You have to provide a c…