Automatic memoisation with recursive function support

Question

Blog post Automatic Memoization in C ++ 0x provides a function for creating a memoized version of an existing function. The blog post and its related code were discussed earlier in stackoverflow (for example, What does this C ++ 11 code do? ), However, none of these solutions can provide a fully universal memoizer that is capable of correctly remembering recursive functions.

Of course, there is a trick about changing a recursive call using something like this (assuming we have a memoizer, such as the one that was presented in a blog post called memoize already in place):

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

But this seems more like a workaround than a proper solution, because we still need access to the function we want to memoize. The correct solution should be able to completely memoize any function, including those defined in some library. However, creating such a solution is apparently not available (if possible), so I ask:

Is a truly universal memoise function possible? How can such success be achieved?

And if this is not possible, is there at least one way to generalize the above approach. Something line by line (not compiled and invalid C ++):

 int fib(int n){ if (n < 2) return n; return this_func(n-1) + this_func(n-2); } 

Where this_func is what looks like a this pointer for a class, but for a function. [ Edit:. There will probably still be a problem that this_func pointer will point to fib instead of memoized fib ]

Answer 1

Since the cache must be shared between function calls, you need to either pass it as an argument, or share it differently. One way to share it is to use a function object:

 struct fib { std::map<std::tuple<int>, int> cache; int operator()(int n) { if(n < 2) return n; auto memoize = [this](int p) { auto i = cache.find(p); if(i == cache.end()) i = cache.insert({p, (*this)(p)}).first; return i->second; }; return memoize(n-1) + memoize(n-2); } }; 

Where you can measure the memoize part.

There is also a trick with a temporary lifetime for passing memoized functions as an argument; something like that:

 struct recurse // possibly a class template { std::function<int(int, recurse const&)> f; // possibly `mutable` template<class T> recurse(T&& p) : f( memoize(decltype(f){p}) ) {} int operator()(int x) const { return f(x, *this); } }; int fib(int n, recurse const& f); int fib(int n, recurse const& f = {fib}) { if(n < 2) return n; return f(n-1) + f(n-2); // or `fib(n-1, f) + fib(n-2, f)` } 

However, this requires a change to memoize , because recurse const& cannot (and should not) be part of the internal map .

<sub> NB those const& can also be && to extend longevity, however, this can be confusing due to the semantics of movement

Answer 2

My guess is that this is not possible, staying within a certain behavior, because there is no way to abstract from a recursive call. In fact, I can't think of anything better than the global variable you provided.

One obvious idea to provide an abstraction point more robust than a global variable would be to add a function for recursion as the first argument:

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

Then you can change the memoize function to pass the memoized version into the first argument, and everything should work. This trick is often used to achieve the same goal in (single / untyped) functional languages ​​such as schema.

However, this trick relies on something called "Y combinator" , which I think cannot exist in C ++, because it is an infinite type.

Answer 3

After that it might help, but it's still a hack, and it's ugly ...:

 int fib(void* f, int n) { if (n < 2) return n; auto this_func = *reinterpret_cast<std::function<int (void*, int)>*>(f); return this_func(f, n - 1) + this_func(f, n - 2); } int main(int argc, char *argv[]) { std::function<int (void*, int n)> fib1 = &fib; std::cout << fib1(reinterpret_cast<void*>(&fib1), 5) << std::endl; auto f = memoize(fib1); std::cout << f(reinterpret_cast<void*>(&f), 5) << std::endl; return 0; } 

I am using void* as the correct signature is recursive: - /