Sunday, June 28, 2015

Fun with Lambdas: C++14 Style (part 4)

This is part 4 in the series of Fun with Lambdas: C++14 Style. The previous posts are part 3, part 2, and part 1.

C++14 has a number of features that support functional-style design. By "functional-style" I mean heavy use of higher-order functions (functions that take other functions as arguments). Quite often arguments to the higher-order functions are lambdas (closures, to be precise). With automatic return type deduction for normal functions, writing higher-order function becomes very easy and seamless in C++14.

This time, I have chosen a "text-book" example to show you the power of C++14: Composable Data Generators

What is a Generator?

A Generator<T> produces values of type T randomly. There is already a random number generator defined in the C library: random(). It produces long ints.

We can use this basic generator to create higher-level generators, such as bool, character, floating point numbers, etc. Even random sequence and structure generators are possible.

But first, lets add some structure around the C library function so that we can compose generators.

#include <cstdlib>

struct RootRandomGen
{
  long int operator () () const 
  {
    return random();
  }
};

RootRandomGen is a very simple function-object that when called produces a random number between 0 and RAND_MAX.

Let's create a Generator template from which we can create other generators.
template <class T, class GenFunc>
class Gen 
{
    GenFunc genfunc;

  public:
    explicit Gen(GenFunc func) 
      : genfunc(std::move(func)) 
    { } 
    
    T generate() 
    {   
      return genfunc();
    }   
};

The Gen class template allows us to pass any function-object or closure and a make a "generator" out of it. Of course, the function must not take any arguments and must produce a value.

To simplify creation of Generators from just lambdas, we create a helper factory function. This is where the power of C++14 starts becoming apparent.
template <class GenFunc>
auto make_gen_from(GenFunc&& func)
{
  return Gen<decltype(func()), GenFunc>(std::forward<GenFunc>(func));
}

make_gen_from is a higher-order function that takes a closure as an argument and creates a Gen<T> object. GenFunc is the type of the closure. The type T is deduced using decltype(func()), which is C++14 syntax to say whatever the type of the return value of func is. Rest of it is perfect-forwarding of the func argument to the Gen<T> object.

To create many more generators, such as for bool, char, string, etc, a function like make_gen<T> might be quite useful. So, let's add one.
template <class T>
auto make_gen();

template <>  
auto make_gen<long int>()
{
  return make_gen_from(RootRandomGen()); 
  //return make_gen_from([]() { return random(); }); 
}

The long int generator simply uses the "Root" generator. Alternatively, RootRandomGen can be defined in-place using a lambda as shown above. I.e., RootRandomGen is superfluous.

Let's test what we've so far.

void init_random() 
{
  time_t t;
  time(&t);
  srandom(t);
}

int main(void)
{
  init_random();
  auto gen = make_gen<long int>();
  std::cout << gen.generate(); // expect a random value.
}

We can create many more generators by explicitly specializing make_gen for a number of types. But before we do that let's observe the core properties of Gen<T>.

The Generator<T> Functor

In functional programming literature, Gen<T> is a functor, which means you can "map over it". I.e., you can write a function named map that takes a generator and a function and returns another generator that applies the function to the values generated by the argument generator. It's much easier to look at code.
template <class Gen, class Func>
auto map (Gen gt, Func func)
{
  return make_gen_from([gt, func]() { 
                          return func(gt.generate()); 
                      });
}

First, the lambda captures gt and func by value. When called, it first generates a value from gt and passes it to the function and simply returns the value produced by the function. We've already seen that make_gen_from converts any lambda (with right signature) to a generator. So we now have a very general-purpose facility to create arbitrarily many generators simply by passing functions to map.

Let's look at an example.
int main(void)
{
  init_random();
  auto gen = make_gen<long int>();
  auto boolgen = map(gen, [](long int i) { return bool(i % 2); });
  std::cout << std::boolalpha << boolgen.generate(); // expect a random boolean.
}

The only problem, however, is that it does not work.

The problem is that Gen<T> is designed to support stateful generators that might mutate state between two successive calls to generate. That's why the generate function is not const. But the lambda in the map function is by default const. Therefore, gt is also const, which prevents us from calling gt.generate() as Gen<T>::generate() is a non-const function.

The solution is to make the lambda in map function mutable. With that, the program compiles but there are more things that can be improved about map.

First, gt and func arguments are passed by value and the lambda captures them by value. That may be potentially quite wasteful. We can improve efficiency by using perfect forwarding. Adding perfect forwarding, however, adds a lot of noise to the otherwise simple map function. This noise has become my pet peeve regarding functional-style programming in C++14.
template <class Gen, class Func>
auto map (Gen&& gt, Func&& func)
{
  return make_gen_from([gt=std::forward<Gen>(gt), 
                        func=std::forward<Func>(func)]() mutable { 
                          return func(gt.generate()); 
                      });
}

I think this map function is a well-behaved citizen of the C++14 world. It's using the generalized lambda capture syntax and perfect-forwarding in combination.

Using this map function is slightly awkward because it's a free function. To support more fluent style of API, I would like to "upgrade" the map function to the Gen<T> class. As I said before, every generator supports mapping. So here's the new Get<T> template.
template <class T, class GenFunc>
class Gen 
{
    GenFunc genfunc;

  public:
    explicit Gen(GenFunc func) 
      : genfunc(std::move(func)) 
    { } 
    
    T generate() 
    {   
      return genfunc();
    }  
 
    template <class Func>
    auto map (Func&& func)
    {
      return make_gen_from([gt=*this, 
                            func=std::forward<Func>(func)]() mutable { 
                              return func(gt.generate()); 
                          });
    }
};

Note that map makes a full copy of this in the lambda so that every generator becomes self-sufficient.

We can create a number of other generators using the built-in map function. For instance, an consider Gen<int> below.
template <>  
auto make_gen<int>()
{
  return make_gen<long int>().map([](long int i) { return static_cast<int>(i); });
}

A range generator that produces a random value in the specified range may be created as follows. Like in the iterator semantics, hi is one past the desirable range.
template <class Integer>
auto make_range_gen(Integer lo, Integer hi) 
{
  return make_gen<long int>().map( 
          [lo, hi](long int x) { return static_cast<Integer>(lo + x % (hi - lo)); });
}

Using the range generator, a generator for uppercase characters is quite simple.
auto uppercase_gen = make_range_gen('A', 'Z'+1);
std::cout << uppercase_gen.generate(); // expect a random uppercase character.

Combinators

Many more helper functions can be added to the Gen<T> class that produce new generators from argument generators. In functional literature they are called combinators.

Here's the zip2 combinator: Zip works just like a zipper. It takes 2 generators and produces another generator that combines the values generated by the argument generators. To combine the values, it needs a function that accepts two arguments and return a value. The user must provide the function.

template <class T, class GenFunc>
class Gen 
{
    // ....

    template <class UGen, class Zipper2>
    auto zip2(UGen&& ugen, Zipper2&& func)
    {
      return this->map(
                [ugen=std::forward<UGen>(ugen),
                 func=std::forward<Zipper2>(func)](auto&& t) mutable {
                    return func(std::forward<decltype(t)>(t), ugen.generate());
                });
    }
};

auto uppergen = make_range_gen<char>('A', 'Z'+1);
auto lowergen = make_range_gen<char>('a', 'z'+1);
auto pairgen  = 
       uppergen.zip2(lowergen, 
                     [](char up, char low) { return std::make_pair(up, low); });

The example above shows how a pair of random characters can be produced by zipping an uppercase generator with a lowercase generator. The zipper function simply constructs the pair from two characters. Alternatively, &std::make_pair<char, char> would have been sufficient.

The zip2 function looks significantly more verbose than a comparable implementation in most other languages that support lambdas. A lot of code is devoted to perfect-forwarding of arguments, which is quite necessary for highly composable libraries such as this one. We'll see later that C++ compilers are smart enough to inline the call-chain completely.

Another example of zip is string generator. A string generator zips a bool generator and int generator where the bool value indicates whether string is empty or not and int generator determines the length of the string. Of course, string generator also needs a char generator to populate the string. Here's one way of doing it.
template <>
auto make_gen<std::string>()
{
  auto char_gen = make_range_gen(32, 127); // printable characters.
  auto length_gen = make_range_gen(1, 256);

  return make_gen<bool>().zip2(
                      length_gen,
                      [char_gen](bool empty, int length) mutable {
                        std::string str;
                        if(!empty)
                        {
                          str.reserve(length);
                          for(int i = 0; i < length; ++i)
                            str.push_back(char_gen.generate());
                        }
                        return str;
                      });
}

There are many more combinators. The single generator would always produce the same value. The oneOf generator selects one of the elements from a given array non-deterministically. Finally, the amb combinator will use of the two input combinators to produce value. Here's a couple of them.
template <class T>
auto make_single_gen(T&& t)
{
    return make_gen_from([t=std::forward<T>(t)]() { return t; });
}

template <class T>
auto make_oneof_gen(std::initializer_list<T> list)
{
    return make_range_gen(0ul, list.size()).map([list](int idx) { return *(list.begin()+idx); }); 
}

Stateful Generators

The examples we've seen so far are stateless generators. I.e., between two successive calls to generate, no state is updated. Let's look at a stateful generator: fibonacciGen. This generator must maintain at least two integers (a and b) for its computation.
auto fiboGen()
{
  int a = 0;
  int b = 1;
  return make_gen_from([a, b]() mutable {
                          int c = a;
                          a = b;
                          b = c+b;
                          return c;
                       });
}

The Cost of Functional Design

It is quite interesting how complex generators can be created from simple generators. But is there a cost to this high level of abstraction? Is the code as fast as it can be?

Here are two different algorithmically identical implementations of bool generator. The reason I chose this algorithm because I wanted make use of zip2, which in turn uses map. I wanted to include multiple levels of indirection.
extern "C" bool random_bool1()
{
  return (random()-random()) > 0;
}

extern "C" bool random_bool2()
{
  auto boolgen = 
    make_gen<long int>()
           .zip2(make_gen<long int>(),
                 [](long int i, long int j) { return (i-j) > 0; });

  return boolgen.generate();
}

The screenshot below shows the compiler's assembly output for both the functions. The amazing fact is that it is exactly identical! The compiler is able to see through the layers and layers of indirections (invocations of lambdas) and is able to produce optimal code for the random_bool functions. That's quite a remarkable feat achieved by g++ 5.1 in this case. Perhaps it is the same with other major C++ compilers.

Generator size

The performance story does not end here though. Note that producing a random boolean does not need any state. I.e., it is just a function. However, RootRandomGen take one byte because it's a class. Every object in C++ must have a unique identity. To ensure that's the case, C++ compiler gives minimal possible size to each object. As we compose higher-level generators from smaller generators, we are clearly creating objects, which have non-zero sizes. But how much memory do they need exactly? What is the size of boolgen in random_bool2?

The size of boolgen is 3 bytes on my machine. The reason for the state is lambda captures. Both map and zip combinators use lambdas with one or more captures. As higher-level generators are built from lower level generators, the state adds up. The problem is that in most generators we've seen so far, there is no real reason to maintain state between two successive calls to the generate function. I.e, the next value is completely unrelated to the previous values. In fact, as we saw before, the compiler did not refer to any state in the implementation of random_bool2. Of course, for truly stateful generators such as the the fibonacci generator, maintaining state from the prior computation is necessary.

The build-up of unnecessary state is quite fast though. For instance, the size of the string generator is whopping 28 bytes! The compiler maintains 28 bytes of state and does not serve any obvious purpose to the user! A generator of printable strings implemented as a simple function would require no persistent state at all. As the size of the generators get larger and larger, pretty soon they won't fit in the cache line and will start to degrade performance, especially if truly stateful generators are mixed with only accidently stateful generators. I hope compiler writers will figure something out about this problem.

This concludes the part 4 in the series of Fun with Lambdas: C++14 Style. I hope you enjoyed it. See Live Example.

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.

Tuesday, August 26, 2014

Fun with Lambdas: C++14 Style (part 3)

Now that we have C++14, it has opened up doors for truly mind-bending uses of lambdas--more specifically--generic lambdas. This blog post is the third installment in the series of "Fun with Lambdas: C++14 Style". Check out part 1 and part 2 if you have not already.

This post is about "monadic tuples".

Monad--a simple but powerful abstraction, however, considered quite difficult to understand in the imperative circles. We will look into what's know as the "continuation monad". As it turns out, in C++14, you need just a couple of lines of code to create an instance of a continuation monad.

I'm fairly new to the world of monads. So, things did not begin with great clarity for me. It all started with an intriguing question on Stackoverflow. As it turns out the same "trick" is also used in Boost.Hana and discussed on boost mailing list here.

What you see below is more or less how I came to understand the idiom as an instance of a monad. Some background in functional programming may be helpful in reading this post. A good understanding of nested generic lambdas is a must. If you are wondering if you should read the part 1 first, then you probably should.

Ok, lets cut to the chase.
auto List = [](auto ...xs) { 
    return [=](auto access) { return access(xs...); }; 
}; 

auto head = [](auto xs) { 
    return xs([](auto first, auto ...rest) { return first; }); 
}; 

auto tail = [](auto xs) { 
    return xs([](auto first, auto ...rest) { return list(rest...); }); 
}; 

auto length = [](auto xs) { 
    return xs([](auto ...z) { return sizeof...(z); }); 
}; 

int len = length(list(1, '2', "3"));  // 3

list is a generic lambda that accepts a variable number of arguments and returns a closure (an instance of the inner lambda) that captures the arguments by value. The inner lambda accepts a parameter (called access) that must be callable with an arbitrary number of arguments. The inner lambda simply expands the parameter pack while calling the callable. That way it provides "access" to the captured parameter pack.

If you squint a little, you will probably realize that list is like a constructor of a tuple. As a matter of fact, if you were to implement the inner lambda using a good old class template, you will most likely resort to using a std::tuple member.

head, tail, and length are examples of operations that you may perform on a list. head returns the first element, tail returns the list excluding the first element and length returns the size of the parameter pack. For example, a three element list is passed to the length lambda. As every list itself is a closure, it is called with an "accessor" function. The accessor simply does a sizeof... and returns the result, which propagates all the way out.

It is probably immediately apparent that this idiom adds life to otherwise drab variadic parameter packs. Don't get me wrong, variadic parameter packs are cool and we won't have other cool things like std::tuple without them. However, the point is that the language allows very few operations on a parameter pack. In general, you can't "store" them. Pretty much, you can expand a parameter pack, ask for its size, and unwind it using the car/cdr recursive style. And that's about it. Until now, To store a parameter pack you have to put it in a std::tuple.

But now there is an alternative. You can capture it using a lambda and provide access to it as done in the list lambda. As it turns out, this seemingly innocuous and perhaps needlessly convoluted approach to "accessing" parameter packs is phenomenally powerful.

WHY? ... the list lambda and the closure inside are special. Together, they form an implementation of a Continuation Monad.

A great introduction for continuation monad for C++ programmers is here. In essence, the list lambda above takes a value (a variadic parameter-pack) and returns a simple "continuator" (the inner closure). This continuator, when given a callable (called access), passes the parameter pack into it and returns whatever that callable returns.

Borrowing from the FPComplete blogpost, a continuator is more or less like the following.
template<class R, class A>
struct Continuator {
   virtual ~Continuator() {}
   virtual R andThen(std::function<R(A)> access) = 0;
};
The Continuator above is abstract--does not provide an implementation. So, here is a simple one.
template<class R, class A>
struct SimpleContinuator : Continuator<R, A> 
{
   SimpleContinuator(A x) : _x(x) {}
   R andThen(std::function<R(A)> access) {
       return access(_x);
   }
   A _x;
};
The SimpleContinuator accepts one value of type A and passes it on to access when andThen is called. The closure returned by the list lambda is conceptually the same. It is more general. Instead of a single value, the inner closure captures a parameter-pack and passes it to the access function. Neat!

Hopefully that explains what it means to be a continuator. but what does it mean to be a monad? Here is a good introduction using pictures.

The inner closure returned by the list lambda is also a list monad, which is implemented as a continuation monad. Note that continuation monad is the mother of all monads. I.e., you can implement any monad with a continuation monad. Of course, list monad is not out of reach.

As a parameter-pack is quite naturally a "list" (often of heterogeneous types), it makes sense for it to work like a list/sequence monad, where operations can be chained one after another. The list lambda above is a very interesting way of converting C++ parameter-packs to a monadic structure.

The head and length lambdas above, however, are a bit disappointing because they break the monad and the nested lambda inside simply returns a non-monadic value (something you can't chain more operations to). There is arguably a better way to write a chain of "processing" operations as shown below.

Functor

Before we can say that the list lambda is a monad constructor, we have to show that it is a functor. I.e., fmap must be written for the inner closure. Note that "functor" is a category theoretic term. It has no direct correlation with a C++ functor (i.e., a function object)

The list lambda above serves as the creator of the functor from a parameter pack---essentially it serves as the "return" in Haskell. That created functor keeps the parameter-pack with itself (capture) and it allows access to it provided you give a callable that accepts a variable number of arguments. Note that the callable is called EXACTLY-ONCE.

Lets write fmap for such a functor.
    
auto fmap = [](auto func) {
    return [func] (auto alist) {
        return alist([func](auto... xs) { return List(func(xs)...); });
    };
};
The type of the func must be (a -> b). I.e., in C++ speak,
    template <class a, class b>
    b func(a);
The type of fmap is "fmap: (a -> b) -> list[a] -> list[b]" I.e., in C++ speak,
    

    template <class Func, class a, class b>
    list<b> fmap(Func, list<a>);
I.e., when fmap is given a function from a to b, it simply returns another function that maps list-of-a to a list-of-b.
Now you can do
    
    auto twice = [](auto i) { return 2*i; };
    auto print = [](auto i) { std::cout << i << " "; return i; };
    auto l1 = List(1, 2, 3, 4);
    auto l2 = fmap(twice)(l1);
    auto l3 = fmap(print)(l2); // prints 2 4 6 8 on clang (g++ in reverse)
Therefore, it is a functor.

Monad

Now, lets try to write a flatmap (a.k.a. bind, selectmany)

Type of flatmap is "flatmap: (a -> list[b]) -> list[a] -> list[b]"

I.e., given a function that maps a to a list-of-b and a list-of-a, flatmap return a list-of-b. Essentially, it takes each element from list-of-a, calls func on it, receives (potentially empty) list-of-b one-by-one, then concatenates all the list-of-b, and finally returns the concatenated list-of-b.

Here's an implementation of flatmap for List.
 
    auto concat = [](auto l1, auto l2) {
        auto access1 = [=](auto... p) {
          auto access2 = [=](auto... q) {
            return List(p..., q...);
          };
          return l2(access2);
        };
        return l1(access1);
    };

    template <class Func>
    auto flatten(Func)
    {
      return List(); 
    }
    
    template <class Func, class A, class... B>
    auto flatten(Func f, A a, B... b)
    {
      return concat(f(a), flatten(f, b...));
    }
    
    auto flatmap = [](auto func) {
       return [func](auto alist) {
           return alist([func](auto... xs) { return flatten(func, xs...);  });
    };
Now you can do a lot of powerful things with a list. For example,
 
    auto pair     = [](auto i) { return list(-i, i); };
    auto count    = [](auto... a) { return list(sizeof...(a)); };
    
    auto l1 = List(1, 2, 3);
    auto l2 = flatmap(pair)(l1);
    auto l3 = fmap(print)(l2); // prints -1, 1, -2, 2, -3, 3 on clang (g++ in reverse)
    auto l4 = l3(count);    
    auto l5 = fmap(print)(l4); // prints 6.
The count function is a monad-perserving operation because it returns a List of single element. If you really want to get the length (not wrapped in a List) you have to terminate the monadic chain and get the value as follows.
 
    auto len = [](auto ...z) { return sizeof...(z); }; 

    auto l1 = List(10, 20, 30);
    auto l2 = flatmap(pair)(l1);
    std::cout << l2(len); // prints 6
If done right, the collection pipeline pattern (e.g., filter, reduce) can now be applied to C++ parameter-packs. So lets try to do that.

You might have noticed that we're doing only one operation per line and giving names to each intermediate result (i.e., l1, l2, l3 etc). Naming the intermediate results is unnecessary but if we don't, readability of code goes out the window.

Lets try to rewrite the previous program where we print 1, 1, -2, 2, -3, 3.
    
    auto l3 = 
      fmap(print)(flatmap(pair)(List(1, 2, 3))); 
    // prints -1, 1, -2, 2, -3, 3 on clang (g++ in reverse)
The above code is pretty much incomprehensible and at this point you probably want to click away. But bear with me for just one moment. There's a pattern here and we can factor that out. I'm going to use C++ operator overloading so that the code looks significantly more readable.
 
template <class LIST, class Func>
auto operator > (LIST l, Func f)
{
  return fmap(f)(l);   
}

template <class LIST, class Func>
auto operator >= (LIST l, Func f)
{
  return flatmap(f)(l);   
}
Operator > accepts our special list as the left hand side argument and a function from a->b as the right hand side argument. It uses fmap internally. The Operator >= is similar but it takes a function that goes from a->List[b] and uses flatmap internally. Remember, both functions return the special list (monadic tuple).

And now's the show time!
 
  auto l3 = 
     List(1, 2, 3) >= pair > print;  
  // prints -1, 1, -2, 2, -3, 3 on clang (g++ in reverse)
Suddenly, you can read the program from left to right and all the fmap/flatmap boilerplate is hidden inside the overloaded operators. You are looking at a tiny Domain-Specific Language (DSL) for piping operations on collections. The chain can be arbitrarily extended to the right.

Before we celebrate though, lets verify the monad laws.

Monad Laws

Let's make sure the list monad satisfies all three monad laws.
    
  template <class M1, class M2>
  void assert_equal(M1 m1, M2 m2)
  {
    auto to_vector = [](auto... a) { return std::vector<int> { a... }; };
    assert(m1(to_vector) == m2(to_vector));   
  }
  
  auto triplet(int i)  { return List(-i, 0, i); }

  {
    auto M = List(11);
    std::cout << "Monad law (left identity)\n";
    assert_equal(flatmap(pair)(M), pair(11));
    assert_equal(M >= pair, pair(11));
    
    std::cout << "Monad law (right identity)\n";
    assert_equal(flatmap(List)(M), M);
    assert_equal(M >= List, M);
     
    std::cout << "Monad law (associativity)\n";
    assert_equal(flatmap(triplet)(flatmap(pair)(M)),
                 flatmap([=](auto x) { return flatmap(triplet)(pair(x)); })(M));
    assert_equal(M >= pair >= triplet, 
                 M >= [=](auto x) { return pair(x) >= triplet; });
  }
All assertions are satisfied.

Collection Pipeline

Although the above list lambda is provably a monad and shares characteristics of the proverbial list-monad, it is quite unpleasant to work with as a collection pipeline. Especially because the behavior of a common collection pipeline combinator filter (a.k.a where) does not meet common expectations.

The reason is just how C++ lambdas work. Each lambda expression produces a function object of a unique type. Therefore, list(1,2,3) produces a type that has nothing to do with list(1) and an empty list, which in this case would be list().

The straight-forward implementation of `where` fails compilation because in C++ a function can not return two different types.
    
   auto where_broken = [](auto func) {
      return flatmap([func](auto i) { 
          return func(i)? list(i) : list(); // broken :-(
      }); 
    };
In the above implementation, func returns a boolean. It's a predicate that says true or false for each element. The ?: operator does not compile because the types of list(i) and list() (empty list) are different.

So, a different trick can be used to allow continuation of the collection pipeline. Instead of actually filtering the elements, they are simply flagged as such---and that's what makes it unpleasant.
    
  auto where_unpleasant = [](auto func) {
    return [=](auto i) { 
        return std::make_pair(func(i), i);
    }; 
  };
The where_unpleasant gets the job done but unpleasantly... For example, this is how you can filter negative elements.
    
    auto positive = [](auto i) { return i >= 0; };
    auto pair_print = [](auto pair) { 
      if(pair.first) 
         std::cout << pair.second << " "; 
      return pair; 
    };
    List(10, 20) >= pair > where_unpleasant(positive) > pair_print; 
    // prints 10 and 20 in some order


Heterogeneous Tuples

So far the discussion was about homogeneous tuples. Now lets generalize it to true tuples. Note that fmap, flatmap, where take only one callback lambda. To provide multiple lambdas each working on one type, we can overload them. For example,
    template <class A, class... B>
    struct overload : overload<A>, overload<B...> {
      overload(A a, B... b) 
          : overload<A>(a), overload<B...>(b...) 
      {}  
      using overload<A>::operator ();
      using overload<B...>::operator ();
    };
     
    template <class A>
    struct overload<A> : A {
      overload(A a) 
          : A(a) {} 
      using A::operator();
    };
    
    template <class... F>
    auto make_overload(F... f) {
      return overload<F...>(f...);   
    }
    
    auto test = 
       make_overload([](int i) { std::cout << "int = " << i << std::endl; },
                     [](double d) { std::cout << "double = " << d << std::endl; });
    test(10); // int 
    test(9.99); // double    
Let's use the overloaded lambda technique to process a heterogeneous tuple continuator.
    
        auto int_or_string = 
            make_overload([](int i) { return 5*i; },
                          [](std::string s) { return s+s; });
        List(10, "ab") > int_or_string >  print; // prints 50 and abab (gcc in reverse)

Finally, Here is the complete live example. For more relevant reading, also see the lambda-over-lambda.

P.S. Why is the order of output not the same across compilers? The order of variadic pack expansion is defined in the standard which corresponds to the original order of the pack. The order of evaluating function argument expressions is, however, not standardized. For example, checkout the implementation of fmap. func(z) is called as many time as there are arguments. However, the order in which multiple calls to func are evaluated is not guaranteed. As the calls to func print the values out to the console, the output is unpredictable across compilers. See more discussion on reddit/r/cpp.

Thursday, May 22, 2014

Using The Pigeonhole Principle in C++ Metaprogramming

The Pigeonhole Principle is one of the most obvious fundamentals in mathematics. It is so obvious that you may be surprised that there is even a name for it. It states that:

"If n items are put into m containers, with n > m, then at least one container must contain more than one item."

Alternatively,

"If there are n items and m containers, with n > m, and only one item can fit in a container, then at least one item must remain out."

For those who prefer visuals and really hate math:


Even though the principle is simple it has been used to prove many complex mathematical theorems and lemmas. Here is one I find quite interesting:

"Incompressible strings of every length exist."

Alternatively,

"There is a file of every size that your favorite zip program can't compress."

The solution is left to the reader as an exercise.

So, does the Pigeonhole Principle show up in programming. Of course it does. That's why std::vector must allocate memory when its capacity is full. OK, but does it manifest in more interesting ways? As it turns out, it has been used in compile-time meta-programming to achieve interesting results. It manifests in preprocessor meta-programming and in template meta-programming in two distinct flavors.

The Pigeonhole Principle in C++ Preprocessor Meta-programming

Check out the following example. Also available here. The original author of this trick is unknown to me.
#include <iostream>

#define COUNT_ARGS(...)     PP_NARG_IMPL(__VA_ARGS__,PP_RSEQ_N()) 
#define PP_NARG_IMPL(...)   PP_ARG_N(__VA_ARGS__) 
#define PP_ARG_N( _1, _2, _3, _4, _5, _6, _7, _8, _9, _10, N, ...) N 
#define PP_RSEQ_N() 10,9,8,7,6,5,4,3,2,1,0 

int main()
{
  std::cout << COUNT_ARGS(a,b,c,d); // prints 4
}
COUNT_ARGS is a "simple" macro that counts the number of variadic arguments it is called with. It does that by using a preprocessing programming trick based on the Pigeonhole principle. Here is how the macro expands:
  1. The COUNT_ARGS macro substitutes the arguments (a,b,c,d) in the __VA_ARGS__ part before calling PP_NARG_IMPL. The PP_RSEQ_N macro is a list of integers from 10 to 0, which is substituted in the PP_NARG_IMPL. Therefore, the PP_NARG_IMPL macro is "called" with actual arguments = a,b,c,d,10,9,8,7,6,5,4,3,2,1,0
  2. The PP_NARG_IMPL macro simply forwards its arguments to the PP_ARG_N macro.
  3. The PP_ARG_N macro is where the Pigeonhole Principle comes in to play. It has 11 named arguments: From _1, _2, _3, etc. and N. Note that _1, _2, etc. are not special. They are just macro arguments with an underscore at the beginning. You may want to rename them as one, two, three, four, etc. It won't make a difference. The PP_ARG_N always expands to its 11th argument because of N.
  4. The original argument list has 15 arguments but there are only 11 arguments to the PP_ARG_N macro. Obviously, not all are going to fit. The PP_ARG_N macro only "picks up" the first actual argument that does not get a slot (i.e., 11th)
  5. As N always coincides with the 11th actual argument, the PP_ARG_N results in that value producing the count.
Needless to say, that's clever! Now let's proceed with template meta-programming.

The Pigeonhole Principle in C++ Template Meta-programming

Check out the following example. Also available here.
int main()
{
 auto x = ::nth<7>(0,"1",'2',3,"4",'5',6,"7");
 std::cerr << x << std::endl;
}
The goal is to access the N-th element in a variadic function argument list. The output of the above program should be 7.

There are many ways to go about implementing it, most using recursion of some sort. However, there is one implementation I came across, which I find particularly interesting. Why? You guessed it ... It uses the Pigeonhole Principle to avoid recursion.

The code was originally written by Richard Smith. I found it through a post by Roland Bock on the boost developers mailing list. If you prefer more comments, please see the same example with comments by LJEvans.
#include <utility>
#include <iostream>

namespace detail
{
  struct any { template<typename T> any(T &&) {} };

  template<typename T, typename U> struct first { typedef T type; };

  template<typename ...Ts>
  struct select_impl 
  {
    template<typename U, typename ...Vs>
 static U &&select(typename first<any, Ts>::type..., U &&u, Vs &&...) 
    {
    return static_cast<U&&>(u);
    }
  };

  template<std::size_t... Idx, typename... Ts>
  static auto select(const std::index_sequence<Idx...>&, Ts&&... ts)
  {
     return select_impl<decltype(Idx)...>::select(static_cast<Ts&&>(ts)...);
  }
}

template<std::size_t N, typename ...Ts>
auto nth(Ts &&...ts)
{
  return detail::select(std::make_index_sequence<N>(), static_cast<Ts&&>(ts)...);
}

int main()
{
 auto x = ::nth<7>(0,"1",'2',3,"4",'5',6,"7"); // prints 7
 std::cerr << x << std::endl;
}
Here is how the nth<7>(...) function works in the example above.
  1. N is 7 and Ts is a variadic parameter pack of integers, character strings, and plain characters.
  2. The std::make_index_sequence is a new addition in C++14 that produces an instance of std::index_sequence given a compile-time integral constant. Here, it produces std::index_sequence<0,1,2,3,4,5,6>.
  3. The formal arguments to the nth function (captured in the parameter pack ts) are forwarded to detail::select using a static_cast. This function must return the nth argument among the forwarded arguments.
  4. In detail::select, the Idx parameter pack represents the indices from 0 to 6. Its deduced by the compiler looking at the type of the index_sequence instance.
  5. The select_impl class template is instantiated with the decltype of each member in the Idx parameter pack. decltype(ts)... expands in to a list of types for every member in Ids. In this case, it is just 'int, int, int,... 7 times. The remaining arguments to select_impl::select are just being forwarded as before.
  6. The select_impl::select has access to Ts parameter pack, which is at the class-template level. Recall that it is 'int,int,int,....'. The list of formal arguments to select_impl::select is broken down in to 3 parts: a variadic piece of N-1 arguments at the beginning, U&& in the middle, and everything else in Vs.
  7. The first N-1 arguments to select_impl::select are "absorbed" using the detail::any class. The detail::any has a single argument constructor that converts argument of any type to any. The first N-1 arguments are thus converted to any. In our example, all the arguments from 0 to 6 are converted to any. The conversion is achieved using an in place parameter pack expansion 'typename first::type...'. For every argument in the Ts parameter pack, the 'first' meta-function is applied, which results into the 'any' type every time.
  8. As the first N-1 arguments are out of the way, U&& necessarily fits the N-th argument. This is where the Pigeonhole Principle springs back in to action.
  9. The remaining argument after the N-th (if any) are left unused in the Vs parameter pack.

So, there it is: returning the N-th argument in a argument list without using recursion. In practice, however, std::make_index_sequence is implemented using recursion. So, the above code is not truly recursion-free.

OK ... So you read it all! I'm sure you found the use of the Pigeonhole Principle in processing variadics in C++ very interesting.

Wednesday, May 07, 2014

A tale of noexcept swap for user-defined classes in C++11

C++11 has taken another stab at function exception specifications for the masses. The shiny new ‘noexcept’ keyword is phasing out its zombie cousin ‘throw’. The well accepted guideline for the old exception specification is: "don’t use them!" That’s good for us because now we don’t have to bother (the reasons for not using throw specification aren’t for the faint hearted anyways.) The noexcept feature does not appear to be a walk in a park either. So hold on tight!

noexcept is meta-programmable! a.k.a conditional noexcept. It is possible to conditionally specify functions to throw any exceptions. The noexcept specification of functions can be inspected at compile-time and functions can derive their own noexcept specification based on exception specifications found elsewhere in the program. Meta-programs are not off-limits here. An excellent introduction of the noexcept feature and its history can be found in June’11 Overload Journal and on Andrzej's C++ blog. I won’t repeat that here but a quick motivation is in order.

Compile-time knowledge about a move-constructor that it does not throw (i.e., annotated with noexcept(true)) can be used for improved run-time performance. For example, std::vector<T>::resize, std::vector<T>::reserve automatically use T’s move-constructor instead of a copy-constructor if T's move-constructor does not throw. Moving of T objects instead of copying would likely achieve higher performance. The standard library provides std::move_if_noexcept function that does move only if it is guaranteed to not fail. Otherwise, it simply resorts to copy-construction. More on this can be found here. I'll return to the topic of writing noexcept move-ctor towards the end of this post.

But the post is about swapping, so lets talk about that. Here is how the std::pair::swap is declared in C++11.

void pair::swap(pair& p)
  noexcept(noexcept(swap(first, p.first)) &&
           noexcept(swap(second, p.second)));


It basically says that pair's swap will throw if either swapping of first or second member throws. The swapping of first and second possibly resolve to their own namespace-level swap via ADL or else they simply pick up std::swap (because pair::swap is declared in std namespace). This declaration seems to indicate a few things.

  1. For a user-defined type it is now much more preferable to have its own namespace-level swap overload instead of using vanilla std::swap. The namespace-level swap function, being an extension of the type’s interface, is vastly more efficient and often can be written in way that it does not throw. The std::swap function, on the other hand, may throw because it uses a copy-constructor and copy-assignment operator while swapping two objects. If you are like me, your member copy-assignment operator will use copy-and-swap idiom for strong exception safety. That means std::swap will create and destroy 3 copies. What a waste! Moreover, that increases the chance of throwing. Bottom line: If T has a member swap, a swap function should be added in the same namespace as of T.

  2. There are some assumptions buried in the above reasoning: (1) move-constructor is not available for a user-defined T, and (2) it is possible to implement member swap of T that does not throw and you can actually say so.

  3. As far as move-constructor being not available is concerned, I think, there are large number of C++03 libraries, which will acquire move-semantics slowly than you might desire. Till then std::swap will, unfortunately, use copy-ctor and copy-assign. A legacy class with a copy-ctor won’t get an automatic move-ctor because it would do wrong things.

  4. The noexcept specification of the user-defined swap better be accurate. Can we really write a nothrow member swap and say so confidently? Obviously, it depends on the members of the user-defined type that we’re swapping. To me, it’s all uphill from here.


Lets look at how standard library uses noexcept for some of its own classes. We already saw std::pair before. How about std::tuple, which is a generalization of a struct and that’s why may be user-defined classes should follow the same basic principle. Tuple’s member swap is declared as

void tuple::swap(tuple& rhs) noexcept(see below)
// The expression inside noexcept is equivalent to the
// logical AND of the following expressions:

noexcept(swap(declval<T&>(), declval<T&>()))
// where Ti is ith type in the variadic list of types.


Tuple’s member swap inspects the noexcept specifications of its members’ swap functions and derives its own specification from that. That makes sense. If swapping of any of the member throws, the tuple’s swap throws. The declval function belongs to same clique as std::move, std::forward, etc. It is a way to obtain rvalue reference of a type without using a constructor. It suffices to say that declval<T> returns "T&&" and declval<T&> returns "T & &&", which is the same as "T &."

Consider a typical C++03 user-defined legacy class that manages its own resources.

namespace L 
{
struct legacy 
{
  legacy();                             // Does not throw
  legacy(const legacy &);               // This may throw
  legacy & operator = (const legacy &); // This may throw (strong exception safe)
  ~legacy() throw();                    // Does not throw
  void swap(legacy &) throw();          // Does not throw
};
} // namespace L


The above legacy class is well-designed except for the fact that it does not have any namespace-level swap. To make it a better citizen in C++11, it needs a namespace-level swap. Interestingly enough, there is substantial code out there that has a specialization of the std::swap in the std namespace. Considering the popularity of this anti-pattern, it probably makes sense to add a swap in two places. It is not too much work in the first place and that may help people who always use a qualified swap (std::swap) habitually.

namespace L 
{
  void swap(legacy &, legacy &) noexcept;
}

namespace std 
{
  template <>
  void swap(L::legacy &, L::legacy &) noexcept;
}


Let’s try to use this modernized legacy class in our C++11 class: Modern.

namespace M 
{
struct Modern 
{
  int count;
  std::string str;
  std::array<L::legacy, 5> data;
  /// default-ctor, copy-ctor, copy-assign, move-ctor, move-assign are defined = default.
  void swap(Modern & p) 
    noexcept(noexcept(swap(std::declval<int &>(),
                           std::declval<int &>())) &&
             noexcept(swap(std::declval<std::string &>(),
                           std::declval<std::string &>())) &&
             noexcept(swap(std::declval<std::array<L::legacy, 5> &>(),
                           std::declval<std::array<L::legacy, 5> &>())));
};
} // namespace M


That’s one awful looking swap. My eyes bleed when I look at it.

It is doing exactly the same thing as std::tuple. It simply checks whether swapping two integers, two strings, and two arrays throw or not. If it does, then member swap of Modern throws. You can skip checks for integer swapping but what’s left is not pretty at all.

Note: The text in italics below is not accurate anymore as noted in the comment below. C++11 std::swap uses move-construction and move-assignment internally. As a result, std::swap in C++11 is generally very efficient IF the move-operations are defined and they are really more efficient than their copy counterparts. In such cases, there is little need to write a custom namespace-level swap. However, member swap may still be useful. See the "default-construct-and-swap" technique for implementing a move-constructor below.

Couple of important things to note here:
  1. Because we added namespace-level swap for the L::legacy class, we dodged several problems.If we did not have free swap, the compiler will instantiate std::swap if it is in the scope. Note, however, that vanilla std::swap may throw defeating the purpose of Modern::swap. If no swap is to be found, compiler issues an error.

  2. We hope that swap of std::string and std::array do not throw. As mentioned in [container.requirements.general], std::string::swap does not throw but std::array<T> swap may throw if an unqualified call to swap(T &, T &) throws. Once again, the namespace-level swap will be chosen here, if available. If that does not exist, a specialization of std::swap will be chosen. If none of them exist, std::swap will be instantiated giving our Modern::swap a nothrow(false) specification.

I like my strong exception safety in my little copy-assignment operator so I don’t want my swap to throw but I don’t want my program to std::terminate() if an exception is really thrown. With all that in mind, I would rewrite the swap as follows.

void Modern::swap(Modern &) noexcept 
{
  static_assert(noexcept(swap(std::declval<int &>(),
                              std::declval<int &>())) &&
                noexcept(swap(std::declval<std::string &>(),
                              std::declval<std::string &>())) &&
                noexcept(swap(std::declval<std::array<L::legacy, 5> &>(),
                              std::declval<std::array<L::legacy, 5> &>())), 
                "throwing swap");
  //.... remaining swap code
}


This is not unlike what’s proposed by others but there’s more. The static assert looks awful and looks redundant. There is already a standard library utility that does the same thing: std::tuple. As mentioned before, std::tuple’s swap throws if any member swap throws. We use it here to make our job a lot easier.

void Modern::swap(Modern & that) noexcept 
{
  typedef std::tuple<int, std::string, std::array <L::legacy, 5> > MemberTuple;
  static MemberTuple *t = 0;
  static_assert(noexcept(t->swap(*t)), "throwing swap");
  // .... remaining swap code
}


If you an enthusiastically paranoid C++ programmer, you may want to use conditional noexcept with a little meta-function (is_nothrow_swappable_all) to save typing.

template<typename... T>
struct is_nothrow_swappable_all
{
  static std::tuple<T...> *t = 0;
  enum { value = noexcept(t->swap(*t)) };
};

void Modern::swap(Modern & that) 
   noexcept(is_nothrow_swappable_all<int, std::string, std::array<L::legacy, 5> >::value);


The "remaining swap code" section above is also rather important. The recommended (by Dave and Howard) way to write it is to use unqualified swap but bring std::swap in the scope:

void Modern::swap(Modern & that) 
  noexcept(is_nothrow_swappable_all<int, std::string, std::array<L::legacy, 5> >::value);
{
  using std::swap;
  swap(this->count, that->count);
  swap(this->str, that->str);
  swap(this->data, that->data);
}


The appropriate swap (namespace-level via ADL or std::swap) will be chosen depending upon availability. That’s exactly what tuple’s swap noexcept checker is going to do for us.

Back to the move-constructor, as promised! As mentioned before, noexcept specification of a move-ctor may have performance implications. So you want to get it right. For the M::Modern class we could have defaulted the move-ctor (= default). That will give it a noexcept(false) specification automatically because internally it uses L::legacy’s copy constructor, which throws. As a consequence, std::vector::resize is not as fast as it can be. We can do better.

Implementing a move-ctor using the default-construct-and-swap idiom turns out be quite handy. Default-construct-and-swap does what it says by first delegating to a noexcept default constructor followed by a swap. To implement a noexcept move-ctor this way, you really need to make sure that swap does not throw. As always, you can rely on a conditional noexcept. I'm using std::is_nothrow_constructible type trait to test the obvious!

Modern::Modern(Modern && m) 
  noexcept(std::is_nothrow_constructible<Modern>::value &&
           noexcept(m.swap(m)))
  : Modern()           
{
  swap(m);
}


As long as Modern's default constructor and member swap are noexcept, the move-ctor is noexcept.

Finally, the move-assign operator can be simply implemented as a single swap operation but for some classes that may not be accurate.

Modern::operator = (Modern && m) noexcept
{
  swap(m);
}


Acknowledgements: I want to thank Howard Hinnant (former Library Working Group chair) for reviewing this article and providing me valuable feedback. Any inaccuracies and mistakes left in the article are strictly mine.

Sunday, May 04, 2014

Fun with Lambdas: C++14 Style (part 2)


Look at some interesting examples of C++11/14 lambdas and how they interact with other language features and libraries. I hope to find some time to add some explanations. See part 1 if you missed it.

  • Associative containers and lambdas
    std::set<int, std::function<bool(int, int)>> 
      numbers([](int i, int j) { return i < j; });
    
  • Recursive Lambdas (see Creating recursive lambdas and returning them too!)
    auto make_fibo() 
    {
      return [](int n) {
        std::function<int(int)> recurse;
        recurse = [&](int n){ 
           return (n<=2)? 1 : recurse(n-1) + recurse(n-2); 
        }; 
        return recurse(n);
      };
    }
    
  • Composable list manipulation (e.g., cpplinq, narl, LEESA)
    Box boxes[] = { ... };
    int sum_of_weights = 
         cpplinq::from_array(boxes)
      >> where([](const Box & box) { 
           return box.color == Color.RED;
         })
      >> select([](const Box & box) {
           return box.get_weight();
         })
      >> sum();
    
    
  • Overloaded Lambdas
    template <class... F>
    struct overload : F... {
      overload(F... f) : F(f)... {}  
    };
    
    template <class... F>
    auto make_overload(F... f) {
      return overload<F...>(f...);   
    }
    
    auto f = 
        make_overload([](int i) { /* print */ },
                      [](double d) { /* print */ });
    f(10); // int 
    f(9.99); // double
    
  • Type Switch (simple pattern matching) (see type_switch.cpp and this paper)
    struct Base { 
      virtual ~Base() {} 
    };
    struct Derived : Base {};
    
    template <class Poly>
    void test(Poly& p) {  
      match(p)(
        [](int i)             { cout << "int";       },
        [](std::string &)     { cout << "string";    },
        [](Derived &)         { cout << "Derived";   },     
        [](Base &)            { cout << "Base";      },    
        otherwise([](auto x)  { cout << "Otherwise"; })
      );  
    }
    Derived d;
    Base &b = d;
    std::string cpptruths = "C++ Truths";
    boost::any something = cpptruths;
    
    test(10);        // int
    test(cpptruths); // string
    test(something); // string
    test(b);         // Derived
    test(9.99);      // Otherwise
    
  • Converting shared_ptr between boost and std (see StackOverflow)
    template <typename T>
    boost::shared_ptr<T> 
    make_shared_ptr(std::shared_ptr<T> ptr) 
    {      
      return boost::shared_ptr<T>(ptr.get(), 
        [ptr](T*) mutable { ptr.reset(); });
    }
    
    template <typename T>
    std::shared_ptr<T> 
    make_shared_ptr(boost::shared_ptr<T> ptr)
    {      
      return std::shared_ptr<T>(ptr.get(), 
        [ptr](T*) mutable { ptr.reset(); });
    }
    
  • In-place parameter pack expansion 
    template <class... T>
    void foreach(T... args) 
    {  
      bool b[] = { [=](){ 
        std::cout << args << "\n"; 
        return true; 
      }()... }; 
    }
    
    foreach(10, 20.2, true);
    
  • Memoization (see original)
    template <typename ReturnType, 
              typename... Args>
    auto memoize(ReturnType (*func)(Args...))
    {
        std::map<std::tuple<Args...>, ReturnType> cache;
    
        return ([=](Args... args) mutable  
        {
            std::tuple<Args...> t(args...);
            if (cache.find(t) == cache.end())                
            {
              std::cout << "not found\n";
              cache[t] = func(args...);
            }
            return cache[t];
        });
    }
    
  • Finally, slides