Stupid Lambda Tricks

Stupid Lambda Tricks

  • Comments 26

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

  • "so return type is the type of the expression in the return statement."

    I hope there is a compiler option "force explicit lambda return type" which is on by default. Or at least a W4 warning for implicit return types.

  • Why does

    function<int(int)> fib1 = [fib1](int n) -> int

    crash if I capture fib1 by value?

  • hi, how do i ask you a question? do you have an email address?

  • @Andre

    function<int(int)> fib1 = [fib1](int n) -> int

    crashes because fib1 is not yet constructed when the lambda is being built, so you're copying a not-yet-constructed value, which is undefined behaviour => crash.

  • @Stephan:

    Thanks for the named functor examples.  I note you had to write the functors in a special way to allow for memoization.  In practice, certainly a good idea.  But can you think of a way to write this without needing to allow for memoization up front?

    @Andre:

    >> Also why does

    >>

    >> fib1 = [](int n) -> double { return -1; };

    >>

    >> compile? So function<> isn't type safe?

    Well, this is really the same issue as:

    double foo() { return -1; }

    tr1::function<> is indeed type safe, but converting the return expression to the return type will invoke implicit conversions.

    @Dimitris and Mike,

    I agree with you.  The code I wrote is needlessly complex, and I would be horrified if anyone introduced it into production code!  However, this parlor trick aside, I personally find there are real world cases where lambdas make code clearer than named functors (STL's lambdas post, which I link to, contains some good examples).

    Mike, have you read the posts about the Intellisense improvements we're working on?

    http://blogs.msdn.com/vcblog/archive/2008/02/29/intellisense-part-2-the-future.aspx

    @Craig

    A Y-combinator example would be neat...I was trying to come up with one a few weeks ago, but I ran into some problems expressing some of the types, and had to resort to boost::any (kind of an ugly hack).  Specifically, I needed a function that took a reference to its own type as a parameter.  Let me know if you are able to build one!

    @swigger

    Yep, my email address is arjun dot bijanki at microsoft.com.

  • Yes I have read about Intellisense. While this  is certainly welcome, there are MANY MANY igssues as well as the lags due to intellisense that people including me are upset about.

    Examples as before:

    1) Poor compilation times.

    2) Help integration for C++ is not as good as it was with 6. Now you often get help on c# not C++

    3) Why are new projects STILL created at warning level 3 by default.

    I could go on and on.

    4) Poor level of ongoing support. You made 6 SP's available for VC++6, and one for each of 2003, 2005 and 2008. This doesn't represent much ongoing support. Instead customers are blindly expected to pay for the next version in the often vain hope that problems get resolved.

    I am happy to talk more in depth if you wish to email me.

    Remove the spaces:

    mike_diack @ hotmail.com

    Mike

  • @Mike Diack,

    I think you would find that http://blogs.msdn.com/somasegar/archive/2007/08/08/visual-c-futures.aspx is a very interesting reading.

    I believe all of your questions have been asked there.

  • Sorry Raphael. I don't want this to generate into a flame war. I've been reading this blog for months including the posts in August that you've mentioned

    I'm less convinced than ever, based on what I'm seeing now that Microsoft are really fulfilling users needs.

    Maybe I need to get out more, but not one C++ developer I know of is screaming out for more state of the art C++ language features, but almost without exception they are begging for improvements to their IDE and toolset.

    I'm not having huge problems with Intellisense at the moment, I know some people are, and I've seen their problems, but a number of them have only got themselves to blame since against my advice they've not installed the service packs and hotfixes that changed the intellisense priority and reworked the algorithm. Besides which Whole Tomato's tool does a much better job anyway - and I've just begun using that.

    But all of the other issues remain and some of them are so fundamental and have been issues for 6+ years, left unresolved.

    You want to make reference to the August blog posting?

    Have a look at Larry's comments on it.

    "Wednesday, August 08, 2007 10:21 PM by Larry  "

    These are the real kind of issues I'm alluding to.

    Likewise Stephen Kelletts comments and my friend Anna-Jayne Metcalfe's or Brians or Gordons....

    I could go on.

    Seriously - this shows I'm not the only one who is not all that bothered about bleeding edge C++ standard stuff, but instead wants a productive, efficient toolset.

    The recent videos demoing VS10, have shown us that very little notice actually appears to have been taken of these requests - with the possible exception of intellisense.

    Mike

  • >> Well, this is really the same issue as:

    >> double foo() { return -1; }

    No, it's not.

    int    x() { return 1; }

    double y() { return 1; }

    int _tmain(int argc, _TCHAR* argv[])

    {

       typedef int(*pfn)(void);

       pfn fn = x; // ok

       fn = y; // error

       function<int(void)> func = x; // ok

       func = y; // ok

       return 0;

    }

  • Thanks for the interesting article. I'd love to see more like this.

  • Many recursive algorithms have initial parameters. For example, Fibonacci Number is defined as: Fn =

Page 2 of 2 (26 items) 12