Sunday, September 28, 2014

Fun with C++14 Lambdas at Silicon Valley Code Camp

Believe it or not, but the 9th Silicon Valley Code Camp is less than 2 weeks away and I can't wait to be at the largest software technology conference setup by developers for developers---and here is the best part---at no cost to the attendees. So far, there are 234 registered sessions, 7 technical tracks, and over 3100 registrations. So mark your calendar--it's October 11th and 12th, Saturday and Sunday, as always.



C++ is hot again at SVCC and third year in a row there is a dedicated track for modern C++. There are 11 sessions covering a wide variety of topics related to modern C++ programming.

I wanna thank SVCC organizers who generously allowed me to present two sessions: The first one is titled: Fun with Lambdas: C++14 Style[video]. You may be following the Fun with Lambdas series on this blog and hopefully having some fun too! I'll present a sampling of the content discussed here with new insights. Check out part 1, part 2, and part 3 if you haven't already. Come see how functional programming techniques are going to change the face of C++ programming beyond recognition.

Fun with Lambdas: C++14 Style from Sumant Tambe on Vimeo.


The second sessions is about Reactive Programming with DDS and Rx[video]. It's about functional programming again but this time it's going to be C#. Reactive Extensions (Rx) is a fascinating new technique to compose asynchronous and event-based programs using observables and LINQ-style query operators. It fits extremely well with DDS--a data distribution technology for networked real-time systems. I'll demo commonly used Rx operators with real data coming off of a toy DDS example. More on that here.

Reactive Stream Processing Using DDS and Rx from Sumant Tambe on Vimeo.

All in all, I'm anticipating the SVCC'14 to be a pretty busy weekend once again with a lot of learning and sharing. If you are in the area and decide to attend, stop by and say hi!

Saturday, September 20, 2014

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.