Sunday, May 25, 2014

Composing Lambdas in C++14 -- and Functions, Too!

In my most recent post, I mentioned the interesting lambda changes coming in C++14 (aka C++1y). This post will follow up on that, and provides some methods for exploiting those new lambdas. The C++14 lambda functionality is already available in Clang 3.4; all the code in this post was tested with that compiler.

Last time, I gave a shout out to this blog post by Sumant Tambe, who listed a number of very interesting things enabled by the draft standard. There's one significant new usage that Sumant didn't remark on, though, and that is composition. The new feature that enables these usages is generic lambdas, which are declared with a type of auto. The compiler uses template argument deduction to build the actual type of a generic lambda; that actual type is an anonymous template.

For example, declares a generic lambda lambda_plus. That lambda holds the value of a function which applies operator+ to two arguments. Well, sort of. If I understand the standard correctly, that line does nothing more than declare a template named lambda_plus. The following line forces the instantiation of that template. In instantiating the template, all of the 'auto' types in the previous line are deduced to int, and + is determined to be the builtin integer operator+. Thus z is assigned the integer value 8.


Composing Two Lambdas

This template treatment enables a number of very interesting capabilities with lambdas. Sumant has identified many of them; I would recommend reading his post before continuing here. Additionally, generic lambdas also enable composition of lambdas.  The template below defines an operator* that will perform function composition on two lambdas: Note that the rightmost lambda function is applied first. (EDIT: this can be made more efficient by std::forward'ing the arguments). 

The example code below uses this operator to take three lambdas and compose them. The composition works like this: first you apply dbl(), then the result of that is fed to incr(), and the result of that is fed to output_decorate(). The value that output_decorate returns is the return value of dbl_incr_decor. As expected, the output of this code is "11 2 ". The lambda templates have all been instantiated twice: once for int and once for double.

We can also compose inline, like this:
This produces 33.


A Handy Map

We can make this a bit more interesting if we define some useful operations. We will start with map, an operation which builds a new container by repeatedly applying a function to the elements of the original container. The original container is left untouched by the operation.  There are no restrictions on the source container, other than that it must support range-basedd for loops. This version of map works only with destination container types that support the push_back() method.
This code takes as input the vector data, outputs "3 5 7 9 ", and constructs a new vector map_results with the values 3, 5, 7, 9, while leaving data unmodified. I'll leave it as an exercise for the reader to construct a lambda tmap which applies a function to a container, modifying its contents (or you can look at the example code on gitHub).

When I have some more time, I intend to look at the possibilities offered by Ranges in conjunction with composed lambdas (see Eric Niebler's blog posts for some more details on ranges).


But What About Plain Old Functions? 

This is nice and all, but it really won't be a lot of use unless there is a way to compose plain old functions (POFs) and lambdas. Unfortunately, it looks as though there's no way to seamlessly compose lambdas and functions. Fortunately, there is an alternative that's not too painful. The template below will convert any function to a lambda. With the ability to convert any function to a lambda, this means we can not only compose a lambda and a POF, but we can also compose two POFs. This produces "1,1". All of the examples so far have used functions of only one argument. This isn't needed in all cases; the rightmost function (only) will accept more than one argument. There are working examples in the code at GitHub (linked above) of composing functions with two arguments, and with zero arguments.

One more tool that is useful for this style of programming is the ability to bind arguments. Here's a template for that, and some examples: The template _L1 binds the first argument to the function, then allows the other arguments to be filled in at the call site. There are similar templates _L2 and _L3 that bind the first two or three arguments.


A Note About the API: A Work in Progress

There are a number of things I'd like to improve on here:
  • _L1, _L2, _L3 are less than elegant. But the template metaprogramming way will be something like _L<1>::close, which is even less elegant. 
  • Presently, only the first function in the chain of composition can have more than one argument. There's at least one way to alleviate this: make functions that return tuples, and provide an automated way of unpacking the tuples into the argument list of the next function. If you've never seen Haskell in action --- this is more useful than you might think. It should pair wonderfully with Ranges. 
  • I would love to find a way to directly compose plain old functions, without needing the _L template. 
  • As written, map will need to be written separately for many of the different container types. There's probably a better way. 
  • (edited) The Biggie:  operator * applies to anything in the global namespace.  Using a variadic function instead is probably the best alternative that doesn't, but I don't like it much.  Boost::Proto was my first choice, but I didn't see a way to offer a clean interface with it.  I suppose operator, rather than operator* might result in fewer conflicts. 
  • (edited again) Another comment on that last issue: If there were an is_lambda type trait, we could just restrict the operator* to working on lambdas and instances of std::function.  That would be a clean solution.  


  1. Very nice post! Just a little suggestion: you can easily forward parameters:

    template < typename Lambda1, typename Lambda2 >
    auto operator* (Lambda1 l1, Lambda2 l2)
    return [l1, l2](auto&& ... x) {
    return l1(l2(forward < decltype(x) > (x)...));

    The other copies will be elided automatically (or moved).


    1. Marco, thanks for the useful comment. I hadn't known that forward could be applied to the whole parameter pack of a variadic template. Good to know.