c++0x autos, lambdas, and lambda recursion!

C++0x introduces some new features that will probably end up making C++0x code many-times more obfuscated and harder to read; however the features can be very useful and fun to code with as well.

The first interesting feature I'll talk about is the "auto" keyword. Essentially you can use the auto keyword to hold a type that will be automatically inferred.
For example:

int  a = 1;    // Type is explicitly int
auto b = 1;    // Type of 'int', which is inferred by the int literal
auto c = a;    // Type of 'int', which is inferred by the type of a
auto d = 1.4f; // Type of 'float', which is inferred by the float literal

The auto keyword will probably be abused by c++0x coders, making code harder to follow; I imagine people will start using this for a-lot of their variable declarations, making it difficult to know the true types of variables when browsing code.

The auto keyword has some great uses, but I will not explicitly talk about them here because it'll make this post too long...


The second feature I'll talk about are lambdas.
When I first saw the c++0x lambdas I thought it looked very confusing, but after playing around with them I found out they're pretty fun.

I'll use Microsoft's definition of lambda expression:
"A lambda expression is a function or subroutine without a name that can be used wherever a delegate is valid. Lambda expressions can be functions or subroutines and can be single-line or multi-line. You can pass values from the current scope to a lambda expression."

Basically a lambda allows you to create anonymous functions, and they can be defined within other c++ functions, so it also allows you to do nested functions.

They look like this:

// Foo is a function pointer to a lambda that has nothing in its body,
// so it does nothing...
auto foo = [](){};

// [] tells which variables in the current scope will be available to the lambda
// () is the parameter list to be passed to the lambda function
// {} is the lambda's body

// You can now call foo like so:
foo();

Okay I know this is confusing, so I'll give a concrete example:

int main() {
    auto foo = [](int x) { return x * x; };
    cout << foo(2) << endl;
    return 0;
}

That prints out '4' to console.
As you can see we have a parameter list of "int x", and then in the body of the lambda we are returning x*x.
Notice how you don't have to explicitly mention a return-type! That is also an interesting feature of c++0x.

Now the '[]' part of the lambda is a bit tricky to understand, basically it allows you to specify variables from the current scope that will be available to the lambda's body.

For example you can do this:

int main() {
    int x = 2;
    auto foo = [&x]() { return x * x; };
    cout << foo(2) << endl;
    return 0;
}

This will return '4'.
What its saying is that the lambda's body has access to the 'x' from the main() function.
If you modify 'x' in the lambda's body, the 'x' in the main() function will also be modified because we're passing the value by reference.
If you want to pass x by value, you can just omit the ampersand, and it will pass the variable by value.

If you want the lambda to have access to all local variables then you can do:

int main() {
    int x = 2;
    auto foo = [&]() { return x * x; };
    cout << foo(2) << endl;
    return 0;
}

Using the '[&]' means that you're passing all variables of the same scope by reference.
You can also use '[=]' which means you're passing them all by value.
You can even do something like, '[&, x]', which means you're passing all by reference, except for 'x' which will be passed by value.

Technically I've been assigning an identifier to the lambda 'foo', so I've not been using lambdas as anonymous functions here.

The way you would use lambdas as anonymous functions (a function without a name or identifier), is when another method takes a function object as an argument.
The typical example seen all over the web is with 'for_each'.
The arguments for for_each() are found here, but basically are:
param1 = A starting iterator
param2 = An ending iterator
param3 = A function Object

So you can either pass an already defined function as param3, or you can use lambdas to define the function in the current scope.

This example is on wikipedia, but I'll reuse it here.
Suppose you have a vector full of ints, and you want to add up all the ints together.
With for_each, you can specify a lambda as param3 which adds each int to a 'total' variable:

std::vector<int> someList;
int total = 0;
std::for_each(someList.begin(), someList.end(), [&](int x) {
    total += x;
});

I recommend reading the wikipedia link as it has more examples.


Finally the last thing I want to mention is lambda recursion.
When I originally tried using recursion with c++ lambdas, I got compiler errors. So I ended up concluding that recursive lambdas in c++ were not possible without using hacks.

I ended up coding a hack to support lambda recursion:

typedef int(*pFoo)(int, int);

int main() {

    pFoo foo = [](int x, int _f) -> int { 
        int*  _p = (int*)&_f;
        void*& p = (void*&)*_p;
        pFoo*  a = (pFoo*)_p;
        pFoo   f = *a;
        return (x<=1) ? 1 : x * f(x-1, _f);
    };

    int* _p = (int*)&foo;
    int   p = *_p;

    cout << foo(5, p) << endl; // Prints '120'
    return 0;
}

Yes I know its super ugly, I had to do a lot of ugly casts to get GCC to compile without warnings or errors.

The basic idea here is that you define the lambda taking two arguments, one being the integer we will perform the factorial function on, and the other being a function pointer to the lambda itself. The lambda can then use that function pointer to call itself. The function pointer in this case is disguised as an 'int', and then casted to the function pointer type.

I have recently figured out however that you don't need to resort to hacks for lambda recursion!

Here is the proper way to do lambda recursion:

int main() {
    function<int(int)> factorial = [&factorial](int n) -> int { 
        return n <= 1 ? 1 : n * factorial(n-1);
    };
    cout << factorial(5) << endl; // Prints '120'
    return 0;
}

Notice how we give the lambda access to the 'factorial' variable.

I had tried this before using 'auto' instead of 'function<int(int)>' and it didn't work with GCC, so I had assumed recursive lambdas were not supported (I had also read posts by people saying they weren't supported... guess they were wrong :p).

So the trick is to not use 'auto' when declaring the lambda type, but instead use function<int(int)> to explicitly show its a function.

And when you think about it, it makes sense that you can't use 'auto' when using lambda recursion, since you're using the identifier before its type has fully been defined.

Anyways, with the introduction of lambdas, c++0x has nice support for nested functions, recursive nested functions, and anonymous functions.

So get yourself a c++0x compiler and try it out!