{"id":4753,"date":"2008-11-18T14:14:00","date_gmt":"2008-11-18T14:14:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/vcblog\/2008\/11\/18\/stupid-lambda-tricks\/"},"modified":"2019-02-18T18:53:58","modified_gmt":"2019-02-18T18:53:58","slug":"stupid-lambda-tricks","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/cppblog\/stupid-lambda-tricks\/","title":{"rendered":"Stupid Lambda Tricks"},"content":{"rendered":"

Hi.  <\/span>I’m Arjun Bijanki, the test lead for the compiler front-end and Intellisense engine.  <\/span>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.  <\/span>My recollection is that Boris Jabes, whom some of you might have seen deliver the “<\/font>10 is the new 6<\/font><\/a>” talk at PDC last week, was trying to convince the other colleague that you could write an automatic <\/font>memoization<\/font><\/a> function for C++0x lambdas.<\/font><\/p>\n

I became intrigued.<\/font><\/p>\n

For those that haven’t used C++0x lambdas before, the feature provides a way to define unnamed function objects.  <\/span>VCBlogger STL wrote up a <\/font>great post<\/font><\/a> that describes lambdas and their syntax in more detail.<\/font><\/p>\n

Interestingly, lambdas can be recursive.  <\/span>For example, here’s a lambda that implements the fibonacci series using recursion: <\/font><\/p>\n

#include<\/span><iostream><\/p>\n

<\/span><\/p>\n

#include<\/span><functional><\/p>\n

<\/span><\/p>\n

using<\/span> namespace<\/span> std;<\/p>\n

<\/span><\/p>\n

using<\/span> namespace<\/span> tr1;<\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

int<\/span> main()<\/p>\n

<\/span><\/p>\n

{<\/p>\n

<\/span><\/p>\n

\/\/ implement fib using tr1::function<\/span><\/p>\n

<\/span><\/p>\n

      <\/span>function<int<\/span>(int<\/span>)> fib1 = [&fib1](int<\/span> n) -> int<\/p>\n

<\/span><\/span><\/p>\n

      <\/span>{<\/p>\n

<\/span><\/p>\n

            <\/span>if<\/span>(n <= 2)<\/p>\n

<\/span><\/p>\n

                  <\/span>return<\/span> 1;<\/p>\n

<\/span><\/p>\n

            <\/span>else<\/p>\n

<\/span><\/span><\/p>\n

                  <\/span>return<\/span> fib1(n-1) + fib1(n-2);<\/p>\n

<\/span><\/p>\n

      <\/span>};<\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

      <\/span>cout<<fib1(6);<\/p>\n

<\/span><\/p>\n

}<\/span> <\/p>\n

<\/span><\/font><\/font><\/p>\n

Note that we had to actually name<\/i> the lambda in order to implement the recursion.  <\/span>Without a name, how would you make the recursive call?  <\/span>This self-referencing places some restrictions on how a recursive lambda can be used; the lambda doesn&rsquo\n;t refer to itself<\/i>, it refers to <\/font>fib1<\/span>, which happens to be itself.  <\/span>The restriction is subtle, and shown by the following code: <\/font><\/p>\n

 <\/font><\/span>      <\/span>function<int<\/span>(int<\/span>)> fib1_copy = fib1; \/\/ copy fib1<\/p>\n

<\/span><\/span><\/p>\n

      <\/span>fib1 = [](int<\/span> n) { return<\/span> -1; };    <\/span>\/\/ fib1 now does something else<\/p>\n

<\/span><\/span><\/p>\n

      <\/span><\/span>cout<<fib1_copy(6);                 <\/span>\/\/ uh oh, doesn’t do what we expect<\/span><\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

Quiz: what would <\/font>fib1_copy(6)<\/span> return? <\/p>\n

<\/span><\/font><\/font><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

Anyway, <\/font>fib1 <\/span>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.  <\/span>By changing this function to cache values it has already computed, we can make it faster:<\/font><\/p>\n

function<int<\/span>(int<\/span>)> fib2 = [&fib2](int<\/span> n) -> int<\/p>\n

<\/span><\/span><\/p>\n

{<\/p>\n

<\/span><\/p>\n

      <\/span>static<\/span> map<int<\/span>,int<\/span>> cache;<\/p>\n

<\/span><\/p>\n

      <\/span>if<\/span>(n <= 2)<\/p>\n

<\/span><\/p>\n

            <\/span>return<\/span> 1;<\/p>\n

<\/span><\/p>\n

      <\/span>else<\/span> if<\/span>(cache.find(n) == cache.end())<\/p>\n

<\/span><\/p>\n

      <\/span>{<\/p>\n

<\/span><\/p>\n

            <\/span>cache[n] = fib2(n-1) + fib2(n-2);<\/p>\n

<\/span><\/p>\n

      <\/span>}<\/p>\n

<\/span><\/p>\n

      <\/span>return<\/span> cache[n];<\/p>\n

<\/span><\/p>\n

};<\/p>\n

<\/span><\/p>\n

(At this point, I should make the caveat that we’re really getting into parlor trick territory.  <\/span>A functor class is a far better bet for production code, and can do everything here, and more.) <\/font><\/p>\n

Now the function is really hard to read, and I may as well just implement it iteratively.  <\/span>This is where the automatic memoization function comes in.  <\/span>What we’d really like to write is something nice and clean like <\/font>fib1<\/span>, but allowing us to memoize it for the faster computation of <\/font>fib2<\/span>:<\/font><\/p>\n

      <\/span>\/\/ memoize the fib1 function and find fib(6)<\/p>\n

<\/span><\/span><\/p>\n

      <\/span>memoize(fib1)(6);<\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

The three of us tried for an hour or so to write the <\/font>memoize()<\/span>function, but intercepting <\/font>fib1<\/span>’s recursion to insert a cache proved difficult. <\/font><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

\/\/ what goes into the highlighted calls?  <\/span><\/p>\n

<\/span><\/p>\n

\/\/ we want to use a cache, not call fib directly.<\/span><\/p>\n

<\/span><\/p>\n

      <\/span>return<\/span> fib1<\/span>(n-1) + fib1<\/span>(n-2); <\/span><\/p>\n

<\/span><\/p>\n

\n

 <\/font><\/p>\n<\/p>\n

If we had a function to independently manage the cache, we make the recursive call this way:<\/font><\/p>\n

      <\/span>return<\/span> check_cache(fib1,n-1) + check_cache(fib1,n-2); <\/span><\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

This is much cleaner than <\/font>fib2<\/span>, but even so, I had to intentionally write <\/font>fib1 <\/span>to make use of the cache.  <\/span>It would be a nicer if I didn’t have to do that.  <\/span>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.  <\/span>That way, we can write <\/font>fib1<\/span> normally, and under the covers check the cache. <\/font>tr1::function<\/span> doesn’t seem to support this, so after a couple of tries, I coded up <\/font>adaptable_function <\/span>and<\/font> memoize_adapter<\/span> (Warning: Templates Ahead). <\/font><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

template<\/span><class<\/span> Arg><\/p>\n

<\/span><\/p>\n

struct<\/span> adaptable_function<\/p>\n

<\/span><\/p>\n

{<\/p>\n

<\/span><\/p>\n

      <\/span>tr1::function<Arg(Arg)> func;<\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

      <\/span>typedef<\/span> tr1::function<Arg(tr1::function<Arg(Arg)>,Arg)> adapter_type;<\/p>\n

<\/span><\/p>\n

      <\/span>adapter_type adapter;<\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

      <\/span>\/\/ binds a function<\/p>\n

<\/span><\/span><\/p>\n

      <\/span>adaptable_function(tr1::function<Arg(Arg)> const<\/span>& f) : func(f) <\/p>\n

<\/span><\/p>\n

      <\/span>{<\/p>\n

<\/span><\/p>\n

      <\/span>}<\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

      <\/span>\/\/ invokes the bound function through an adapter, if one exists<\/p>\n

<\/span><\/span><\/p>\n

      <\/span>Arg operator<\/span>()(Arg p) const<\/p>\n

<\/span><\/span><\/p>\n

      <\/span>{<\/p>\n

<\/span><\/p>\n

            <\/span>if<\/span>(adapter)<\/p>\n

<\/span><\/p>\n

                  <\/span>return<\/span> adapter(func, p);<\/p>\n

<\/span><\/p>\n

            <\/span>else<\/p>\n

<\/span><\/span><\/p>\n

                  <\/span>return<\/span> func(p);<\/p>\n

<\/span><\/p>\n

      <\/span>}<\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

      <\/span>void<\/span> set_adapter(adapter_type const<\/span>& a)<\/p>\n

<\/span><\/p>\n

      <\/span>{<\/p>\n

<\/span><\/p>\n

            <\/span>adapter = a;<\/p>\n

<\/span><\/p>\n

      <\/span>}<\/p>\n

<\/span><\/p>\n

      <\/span>void<\/span> clear_adapter()<\/p>\n

<\/span><\/p>\n

      <\/span>{<\/p>\n

<\/span><\/p>\n

            <\/span>adapter = adapter_type(); \/\/ better way to clear a tr1::function?<\/p>\n

<\/span><\/span><\/p>\n

      <\/span>}<\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

private<\/span>:<\/p>\n

<\/span><\/p>\n

      <\/span>\/\/relies on self-referential recursion, so the class is non-copyable<\/p>\n

<\/span><\/span><\/p>\n

      <\/span>adaptable_function(adaptable_function const<\/span>&);<\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

};<\/p>\n

<\/span><\/p>\n

\n

 <\/font><\/p>\n<\/p>\n

<\/span><\/p><\/p>\n","protected":false},"excerpt":{"rendered":"

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 […]<\/p>\n","protected":false},"author":289,"featured_media":35994,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[],"class_list":["post-4753","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-cplusplus"],"acf":[],"blog_post_summary":"

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 […]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/posts\/4753","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/users\/289"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/comments?post=4753"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/posts\/4753\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/media\/35994"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/media?parent=4753"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/categories?post=4753"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/tags?post=4753"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}