Stupid Lambda Tricks
Hi. I’m Arjun Bijanki, the test lead for the compiler front-end and Intellisense engine. One afternoon a few months ago, I was sitting in my office in building 41 thinking about test passes, when an animated discussion between a couple of colleagues spilled into the hallway and grabbed my attention. My recollection is that Boris Jabes, whom some of you might have seen deliver the “10 is the new 6” talk at PDC last week, was trying to convince the other colleague that you could write an automatic memoization function for C++0x lambdas.
I became intrigued.
For those that haven’t used C++0x lambdas before, the feature provides a way to define unnamed function objects. VCBlogger STL wrote up a great post that describes lambdas and their syntax in more detail.
Interestingly, lambdas can be recursive. For example, here’s a lambda that implements the fibonacci series using recursion:
#include<iostream>
#include<functional>
using namespace std;
using namespace tr1;
int main()
{
// implement fib using tr1::function
function<int(int)> fib1 = [&fib1](int n) -> int
{
if(n <= 2)
return 1;
else
return fib1(n-1) + fib1(n-2);
};
cout<<fib1(6);
}
Note that we had to actually name the lambda in order to implement the recursion. Without a name, how would you make the recursive call? This self-referencing places some restrictions on how a recursive lambda can be used; the lambda doesn’t refer to itself, it refers to fib1, which happens to be itself. The restriction is subtle, and shown by the following code:
function<int(int)> fib1_copy = fib1; // copy fib1
fib1 = [](int n) { return -1; }; // fib1 now does something else
cout<<fib1_copy(6); // uh oh, doesn't do what we expect
Quiz: what would fib1_copy(6) return?
Anyway, fib1 isn’t a particularly efficient implementation of the algorithm, but, even though I don’t come from a functional programming background, I find the recursive solution has a certain elegance. By changing this function to cache values it has already computed, we can make it faster:
function<int(int)> fib2 = [&fib2](int n) -> int
{
static map<int,int> cache;
if(n <= 2)
return 1;
else if(cache.find(n) == cache.end())
{
cache[n] = fib2(n-1) + fib2(n-2);
}
return cache[n];
};
(At this point, I should make the caveat that we’re really getting into parlor trick territory. A functor class is a far better bet for production code, and can do everything here, and more.)
Now the function is really hard to read, and I may as well just implement it iteratively. This is where the automatic memoization function comes in. What we’d really like to write is something nice and clean like fib1, but allowing us to memoize it for the faster computation of fib2:
// memoize the fib1 function and find fib(6)
memoize(fib1)(6);
The three of us tried for an hour or so to write the memoize()function, but intercepting fib1’s recursion to insert a cache proved difficult.
// what goes into the highlighted calls?
// we want to use a cache, not call fib directly.
return fib1(n-1) + fib1(n-2);
If we had a function to independently manage the cache, we make the recursive call this way:
return check_cache(fib1,n-1) + check_cache(fib1,n-2);
This is much cleaner than fib2, but even so, I had to intentionally write fib1 to make use of the cache. It would be a nicer if I didn’t have to do that. Eventually, we figured out that we needed a way to hook the recursion and insert our own adapter that checks the cache before making the recursive call. That way, we can write fib1 normally, and under the covers check the cache. tr1::function doesn’t seem to support this, so after a couple of tries, I coded up adaptable_function and memoize_adapter (Warning: Templates Ahead).
template<class Arg>
struct adaptable_function
{
tr1::function<Arg(Arg)> func;
typedef tr1::function<Arg(tr1::function<Arg(Arg)>,Arg)> adapter_type;
adapter_type adapter;
// binds a function
adaptable_function(tr1::function<Arg(Arg)> const& f) : func(f)
{
}
// invokes the bound function through an adapter, if one exists
Arg operator()(Arg p) const
{
if(adapter)
return adapter(func, p);
else
return func(p);
}
void set_adapter(adapter_type const& a)
{
adapter = a;
}
void clear_adapter()
{
adapter = adapter_type(); // better way to clear a tr1::function?
}
private:
//relies on self-referential recursion, so the class is non-copyable
adaptable_function(adaptable_function const&);
};
template<class Arg>
struct memoize_adapter
{
map<Arg,Arg> cache;
Arg operator()(adaptable_function<Arg> func, Arg arg)
{
if(cache.find(arg) == cache.end())
{
cache[arg] = func(arg);
}
return cache[arg];
};
};
template<class Arg>
adaptable_function<Arg>& memoize(adaptable_function<Arg>& f)
{
f.set_adapter(memoize_adapter<Arg>());
return f;
};
Now, I can implement fib:
· Using the elegant recursive algorithm
· Using a cache without having to build a cache into the function
Here’s the calling code:
int main()
{
adaptable_function<int> fib = [&] (int n) -> int {
cout<<"fib("<<n<<")"<<endl; // to show calls
if(n <= 2)
return 1;
else
return fib(n-1) + fib(n-2);
};
cout<<"normal result = "<<fib(6)<<endl<<endl;
fib.set_adapter(memoize_adapter<int>());
cout<<"memoized result = "<<fib(6)<<endl<<endl;
fib.clear_adapter();
cout<<"normal result = "<<fib(6)<<endl<<endl;
cout<<"memoized result = "<<memoize(fib)(6)<<endl<<endl;
}
This does the trick!
There are several things I don’t really like about this code. First and foremost is that memoizing fib changes its state. memoize(fib) doesn’t just return a memoized version of fib, it changes fib’s recursive call. I think this is a limitation of recursive lambdas, since they have to be named. Or do they…?
Can anyone make this more elegant in C++? (Note that Bart De Smet recently wrote on this topic from a C# perspective. It’s a great post, and worth the read!)
- Arjun
