Clang and Generic (Polymorphic) Lambdas.

Recently a Faisal Vali put forth an implementation of n3418, which he co-authored with Herb Stutter and Dave Abraham,  allowing generic lambdas using a fork of clang. It also includes auto type deduction, which I wrote about being implemented in gcc 4.8. There are a few caveats before continuing: This has not been merged into the mainline. It has a few bugs, but Vali is quick to fix them if you point one out. The implementation itself is a proof of concept (similar to automatic type deduction) and so it isn't unreasonable to assume some things might change. Section 2.4 of the proposal (named lambdas) has not yet been implemented. And while this doesn't allow us to do many things that were previously impossible, the possible used to be so verbose that no one would want to do it!

Generic lambdas are profound and may have a great impact on the style of code written in C++. Consider this a light (and lacking) overview of what is possible.

Before continuing, I want to note that I found evidence that some GCC developers had begun working on generic lambdas (from the mailing list: Latest experimental polymorphic lambda patches), however, I cannot find anything more recent than 2009 discussing this, and code using auto and lambdas does not compile.

Being terse.

This patch allows the writing of incredibly terse polymorphic functions, such as these:

auto add = [](auto x, auto y) x + y;
auto times = [](auto x, auto y) x * y; 
auto print_int = [](int x) void(std::cout << x);

No {}, no return, auto-deduced types, and void can even be used to throw away the value of state-full operations. x and y can be anything and the return type is entirely dependent on them. Why is this interesting? Say you want to find the product of a vector.

auto prod = std::accumulate ( 
    v.begin(), v.end(), 1,
    []( int x, int y ){ return x * y; }
);

Bit of a mouthful, right? v might store ints today, but tomorrow, maybe it will store long long ints to avoid overflow or just unsigned ints to avoid negatives. When the vector's declaration changes, the lambda's argument types need to change, which is a maintenance problem. I currently solve this by writing polymorphic function objects.

constexpr struct {
    template< class X, class Y >
    auto operator () ( X x, Y y )
        -> decltype(x*y)
    {
        return x * y;
    }
} timesObj{}; 

But the above and times are mostly equivalent. (A lambda can be thought of as an automatic function object. It even has a unique type. (see below: Overloading))

auto prod = std::accumulate ( 
    v.begin(), v.end(), 1,
    times
);

This never needs to change unless the underlying operation (multiplication) changes.

Sometimes, an underlying operation is consistent across types. Using zip_tuple as an example from my article "Zipping and Mapping Tuples", one could write:

std::tuple<int,std::string> a{1,"hello "}, 
                            b{2,"world!"};

// r = {3,"hello world"}
auto r = zipTuple( ([](auto x, auto y) x + y), a, b );

Because of the comma operator, we must put the lambda in parentheses to make clear where it ends. 

Up until now, things like composition could not be lambdas.

template< class F, class G > struct Composition {
    F f;
    G g;

    template< class ...X >
    auto operator () ( X&& ...x ) 
        -> decltype( f(g(std::forward<X>(x)...)) )
    {
        return f( g( std::forward<X>(x)... ) );
    }
};

template< class F, class G, class C = Composition<F,G> >
C compose( const F& f, const G& g ) {
    return C{f,g};
}

int main () {
    auto add1 = []( auto x ) x + 1;
    auto Char = []( auto c ) char(c);
    // Prints "a + 1 = b"
    std::cout << "a + 1 = " << compose(Char,add1)('a') << std::endl;
}

compose is generic and it returns a generic function object. Generic lambdas make the same possible by returning another generic lambda that captures f and g.

auto compose = [](auto f, auto g) 
    [=](auto x) f(g(x));

However, this version of compose only allows one argument. Luckily, generic lambdas can be fully templated, variadic, and perfect forwarding.

auto compose = 
    []( auto f, auto g )
        [=]<class ...X>( X&& ...x ) 
            f( g(std::forward<X>(x)...) );

However, the syntax for these lambdas is so convenient, one might as well drop the functional programming theory and write

auto f = [](char c) char(c+1);

For an example of the power of nested lambdas, consider currying:

auto curry3 = 
    []( auto f )
        [=](auto x) [=](auto y) [=](auto z) 
            f(x,y,z);

auto sum3 = [](auto x, auto y, auto z) x + y + z;
auto ten = curry3(sum3)(2)(3)(5)

Nested lambdas especially aid in the use of monads, as I have written about previously ("Monads in C++").

auto justThree = Just(1) >>= [](auto x)
                 Just(2) >>= [](auto y)
                 mreturn<std::unique_ptr>( x + y ); // Or Just(x+y).

This also takes care of the return mreturn problem I discussed in that article.

Overloading

Overloading functions is obviously useful, but impossible with lambdas alone. To fully take advantage of their brevity, we must have a way to overload them. In the proposal, Mathius Gaunard is attributed with the following:

template<class F1, class F2> struct overloaded : F1, F2
{
    overloaded(F1 x1, F2 x2) : F1(x1), F2(x2) {}
    using F1::operator();
    using F2::operator();
};

template<class F1, class F2>
overloaded<F1, F2> overload(F1 f1, F2 f2)
{ return overloaded<F1, F2>(f1, f2); } 

(See also: "Unifying Generic Functions and Function Objects")

This works because lambdas are function objects with a unique type, and can therefore act as the base class for overloaded. This is an unlikely solution because this fact is so rarely taken advantage of, however there is much advantage to take!

Unfortunately, one cannot inherit from function pointers, so, in order to overload lambdas and regular functions together requires a little more work. First, we must define a base type that can handle both function pointers and function objects. It's job is to just forward the arguments to its function.

template< class F > struct Forwarder : F {
    constexpr Forwarder( const F& f ) : F(f) { }
};

template< class R, class ...X > struct Forwarder<R(*)(X...)> {
    using type = R(*)(X...);
    type f;

    constexpr Forwarder( type f ) : f(f) { }

    constexpr R operator () ( X... x ) {
        return f(x...);
    }
};

template< class R, class ...X > 
struct Forwarder<R(X...)> : Forwarder<R(*)(X...)>
{
    using type = R(*)(X...);
    constexpr Forwarder( type f ) 
        : Forwarder<R(*)(X...)>(f)
    {
    }
};

Function pointers get two specializations because decltype(f)=R(X) and decltype(&f)=R(*)(X). It makes the most sense to specialize for pointers, but only doing so would require we take the address of our functions when we call overload.

Next, Overloaded inherits from two Forwarders.

template< class F, class G >
struct Overloaded : Forwarder<F>, Forwarder<G> {
    constexpr Overloaded( const F& f, const G& g )
        : Forwarder<F>(f), Forwarder<G>(g)
    {
    }
};

template< class F > F overload( F&& f ) {
    return std::forward<F>(f);
}

template< class F, class G, class ...H,
          class O1 = Overloaded<F,G> > 
auto overload( const F& f, const G& g, const H& ...h ) 
    -> decltype( overload(O1(f,g),h...) )
{
    return overload( O1(f,g), h... );
}

Overloads can be of arity and domain (or argument type). The simplest example, for demonstration purposes, is a printing function.

auto prnt = overload (
    // Anything cout is already defined for.
    []( const auto& x ) 
        -> decltype( void(std::cout << x) )
    { std::cout << x; },

    // Any STL sequence.
    []<class Sequence>( const Sequence& s )
        -> decltype( void(std::begin(s)) )
    {
        std::cout << "[ ";
        for( const auto& x : s ) 
            std::cout << x << ' ';
        std::cout << ']';
    },

    // These are both sequences for which cout is defined.
    // Specializing disambiguates this.
    []( const char* const s ) { std::cout << s; },
    []( const std::string& s ) { std::cout << s; }
);

// ...
prnt("abc"); // Prints abc.
prnt(std::vector<int>{1,2,3}); // Prints [ 1 2 3 ]. 

Although defining all overloads in a single statement is an annoyance, they are grouped together, they don't require a template<...> line, and the visual clutter is overall less than if prnt were defined as the equivalent (explicit) function object.

Perhaps a function must be overloaded, but decltype or std::enable_if is too accepting and specializing for each type is redundant. For example, one might be annoyed by the last two string specializations of prnt. One solution is to define yet another overload type.

template< class X, class F >
struct UnaryOverload {
    F f;
    UnaryOverload( const F& f ) : f(f) { }

    using result_type = typename std::result_of< F(X) >::type;

    result_type operator () ( X x ) const {
        return f(x);
    }
};

template< class ...X, class F >
auto unary_overload_set( const F& f ) 
    -> decltype( overload(UnaryOverload<X,F>(f)...) )
{
    return overload( UnaryOverload<X,F>(f)... );
}

auto prnt = overload (
    // ...

    unary_overload_set<const char* const,
                       const std::string&>(
        []( auto&& s ) { std::cout << s; }
    )
);

One might write an overloading class to specialize for specific types, or a category of types, or more generally, a class might be written to do type conversion before calling the inner function, to prepare the output, or whatever one's needs may be. An overloading type might even select one of two functions based on an enable_if.

    // Where pred is a templated type defining pred<X>::value.
    auto h = enable_when<pred>( f, g );

The downsides of overloading function objects include that each overload must be defined all at once and none can be added. That isn't too bad since the point of lambdas is to be brief, but one should be mindful of extensibility when writing generic functions. (In other words, if an overload must be added, is it OK to modify the function object, or must the user be able to add overloads later?)

Recursion.

Without generic lambdas, recursion is possible.

std::function<int(int)> fact = [&]( int x ) x * fact(x-1);

Or, with function pointers, which a lambda may implicitly convert to.

// In global scope:
using IntToInt = int(*)(int);
IntToInt fact = []( auto x ) not x ? 1 : x * fact(x-1);

With generic lambdas, we could write it like this:

auto fact1 = []( auto f, int n ) -> int 
    not n ? 1 : f(f,n-1) * n;
auto fact = []( int x ) -> int 
    fact1( fact1, x );

One might notice that the Fibonacci sequence could be implemented in a similar fashion. In researching recursive lambdas, I came across the fixed-point combinator. Haskell has fix, which can be implemented like this:

auto fix = []( auto f )
    [=]( auto x ) -> decltype(x) f( f, x );

auto fact = fix (
    []( auto f, int n ) -> int
    not n ? 1 : f(f,n-1) * n
);

auto fib = fix (
    []( int f, int n ) -> int
    n == 0 ? 0 :
    n == 1 ? 1 :
    f(f,n-1) + f(f,n-2)
); 

fix is a generalization of a certain type of recursion. For an idea of how one would implement fix without lambdas, see this Stack Overflow post.

Making prnt above variadic requires a different kind of recursion.

// Variadic void unary.
auto vvu_impl = overload (
    [] (auto,auto) {},
    []<class X, class ...Y>( const auto& self, const auto& u, 
                             X&& x, Y&& ...y ) 
    {
        u( std::forward<X>(x) );
        self( self, u, std::forward<Y>(y)... );
    }
);

auto vvu = []( const auto& u )
    [&]<class ...x>( const x& ...x )
        vvu_impl( vvu_impl, u, x... );

// Variadic print.
// vprint(x,y...) = prnt(x); prnt(y)...
auto vprint = vvu( prnt );

auto print_line = []<class ...X>( const X& ...x ) 
    vprint( x..., '\n' );
 
print_line( "abc ", 123, std::vector<int>{1} ); // prints "abc 123 [1]\n" 

We can generalize left-associativity as well.

auto chainl_impl = overload (
    []( auto self, auto b, auto r ) { return r; },
    []<class ...Z>( auto self, auto b, auto x, auto y, Z ...z ) 
        self( self, b, b(x,y), z... )
);

auto chainl = []( auto b )
    [=]<class ...X>( const X& ...x )
        chainl_impl( chainl_impl, b, x... );

auto sum = chainl(add);
auto three = sum(1,1,1);

// Variadic compose.
auto vcompose = chainl( compose );

auto inc = []( auto x ) ++x;
auto addThree = vcompose( inc, inc, inc );

A good exercise might be to (a) write a variadic version of fix and (b) use that version to reimplement chainl and vprint.

There are, of course, many types of recursion. Implementing recursive lambdas is more complicated than for regular functions, not by too much.

Conclusions.

Polymorphic (generic) lambdas are very powerful indeed, but it may take a while before GCC, MSVC, and others catch up, much yet before Faisal Vali's branch is merged back into Clang. Still they may have a strong impact on code written in C++ in the future. Some thought that templates relieved a sort of functional language in C++, and others thought the same of constexpr. Generic lambdas reveal another, but more flexible one.

Lambdas cannot be marked constexpr. In terms of efficiency, I do not think this matters. They are implicitly inlined, so the compiler may still take advantage of any compile-time information it can gather. However, the result of a lambda expression could never be used in a template parameter, for example, which means they don't replace generic constexpr function objects.

Also, explicitly specifying a type is more verbose because the rules are the same as for template member functions, so lambdas can't replace template functions that require explicit parameters.

    auto f = []<class X>() { return x(); }; 
    f.operator()<int>(); // bad

The proposal to add polymorphic lambdas to C++ is not finalized and a few things are up in the air. For example, can we elide auto and just write [](x) f(x)? Should we be allowed to elid the enclosing braces and return? Are the implemented parts of this proposal useful? Remember that the standardization process is open to the public and that we can make our voices heard about the features that impact us.

Personally, I like the proposal as implemented currently. (Requiring auto, but eliding { return ... }.) I would go a step further and say that auto should be extended to allow variadic parameters. (i.e. [](auto ...x) f(x...)) And named lambdas (section 2.4) will be a very nice addition.

What are your thoughts?




Source for this article: https://gist.github.com/4347130 and https://gist.github.com/4381376
Another (google translated) article on generic lambdas: http://translate.google.com/translate?hl=en&sl=ja&u=http://d.hatena.ne.jp/osyo-manga/20121225/1356368196&prev=/search%3Fq%3Dgeneric%2Blambda%2Bc%252B%252B%2Bclang%26start%3D10%26hl%3Den%26safe%3Doff%26client%3Dubuntu%26sa%3DN%26tbo%3Dd%26channel%3Dfs%26biw%3D1535%26bih%3D870&sa=X&ei=v-LbUOG5BOmQ2gXw7ICABg&ved=0CFsQ7gEwBjgK
A long and thoughou article on the fixed-point combinator: http://mvanier.livejournal.com/2897.html