What does this C++11 code (memoize) do?

Question

I found an article that contains this code:

template <typename ReturnType, typename... Args>
std::function<ReturnType (Args...)>
memoize(std::function<ReturnType (Args...)> func)
{
    std::map<std::tuple<Args...>, ReturnType> cache;
    return ([=](Args... args) mutable {
            std::tuple<Args...> t(args...);
            if (cache.find(t) == cache.end())                
                cache[t] = func(args...);
            return cache[t];
    });
}

Can you explain this please? I can't understand many things here, but the weirdest thing is that cache is local and not static, but maybe I'm wrong and...

Answer 1

"This simple piece of code" can memoize recursive functions too, provided it is properly invoked. Here I give a complete example:

#include <functional>
#include <iostream>
#include <tuple>
#include <map>

template <typename ReturnType, typename... Args>
std::function<ReturnType (Args...)> memoize(std::function<ReturnType (Args...)> func) {
  std::map<std::tuple<Args...>, ReturnType> cache;
  return ([=](Args... args) mutable {
          std::tuple<Args...> t(args...);
          if (cache.find(t) == cache.end())
             cache[t] = func(args...);
          return cache[t];
  });
}

std::function<int (int)> f;
int fib(int n) {
  if  (n < 2) return n;
  return f(n-1) + f(n-2);
}

std::function<int (int, int)> b;
int binomial(int n, int k) {
  if (k == 0 || n == k) return 1;
  return b(n-1, k) + b(n-1, k-1);
}

int main(void) {
  f = memoize(std::function<int (int)>(fib));
  std::cout << f(20) << std::endl;
  b = memoize(std::function<int (int, int)>(binomial));
  std::cout << b(34,15) << std::endl;
}

Answer 2

The cache is embedded into the lambda itself, and local to it.

Therefore, if you create two lambdas, each will have a cache of its own.

It's a great way to implement a simple cache, since this way the memory used is purged as soon as the lambda goes out of scope, and you don't have an explosion of memory.

Answer 3

Welcome to the wonderful world of lexical scoping. It can be used to create entire types with public and private members. In functional languages, it's often the only way to do that.

I suggest you read http://mark-story.com/posts/view/picking-up-javascript-closures-and-lexical-scoping, which is about Javascript, but C++0x adds the same concepts and (almost the same) behavior to C++.

Answer 4

To quote from the blog where you found this, just below the code:

... the equals sign in [=] means “capture local variables in the surrounding scope by value”, which is needed because we are returning the lambda function, and the local variable will disappear at that moment.

So, cache is copied into the returned function object as if it were a member.

(Note that this simple piece of code will fail to memoize a recursive function. Implementing a fixed-point combinator in C++0x is left as an exercise to the reader.)

Answer 5

This is simple C++1x implementation of memoization.

The memoize function returns a closure. The return value is a function that has state other than what is passed through the arguments (in this case, the cache variable).

The [=] bit in the anonymous function indicates that the returned function should take a copy of all local variables. The cache variable is not static because it is meant to be shared across invocations of the returned function.

Thus, each call to memoize will return a different function with it's own cache. Subsequent calls to a specific closure returned by memoize will insert/fetch values from that closure's cache.

You can think of this as a somewhat equivalent to the more old-school OOP version:

template <typename ReturnType, typename... Args>
class Memoize
{
    std::map<std::tuple<Args...>, ReturnType> cache;
public:
    ReturnType operator() (Args... args)
    {
        std::tuple<Args...> t(args...);
        if (cache.find(t) == cache.end())                
            cache[t] = func(args...);
        return cache[t];
    }
};