Multi-function memoizator and multi-type container

Question

I'm trying to write a multiple functions memoizator, which I've talked about here. The main problem is creating a container containing different and heterogenous functions.

I found a working solution, but I don't know if it's safe, if there are limitations, if it's somehow inefficient or if there is a more elegant solution.

This is my solution:

template <typename ReturnType, typename... Args>
function<ReturnType(Args...)> memoize(function<ReturnType(Args...)> func)
{
    return ([=](Args... args) mutable {
        static map<tuple<Args...>, ReturnType> cache;
        tuple<Args...> t(args...);
        auto result = cache.insert(make_pair(t, ReturnType{}));
        if (result.second) {
            // insertion succeeded so the value wasn't cached already
            result.first->second = func(args...);
        }
        return result.first->second;
    });
}

struct MultiMemoizator
{
    map<string, boost::any> multiCache;
    template <typename ReturnType, typename... Args>
    void addFunction(string name, function < ReturnType(Args...)> func) {
        function < ReturnType(Args...)> cachedFunc = memoize(func);
        boost::any anyCachedFunc = cachedFunc;
        auto result = multiCache.insert(pair<string, boost::any>(name,anyCachedFunc));
        if (!result.second)
            cout << "ERROR: key " + name + " was already inserted" << endl;
    }
    template <typename ReturnType, typename... Args>
    ReturnType callFunction(string name, Args... args) {
        auto it = multiCache.find(name);
        if (it == multiCache.end())
            throw KeyNotFound(name);
        boost::any anyCachedFunc = it->second;
        function < ReturnType(Args...)> cachedFunc = boost::any_cast<function<ReturnType(Args...)>> (anyCachedFunc);
        return cachedFunc(args...);
    }
};

And this is a possible main:

int main()
{
    function<int(int)> intFun = [](int i) {return ++i; };
    function<string(string)> stringFun = [](string s) {
        return "Hello "+s;
    };
    MultiMemoizator mem;
    mem.addFunction("intFun",intFun);
    mem.addFunction("stringFun", stringFun);
    try
    {
        cout << mem.callFunction<int, int>("intFun", 1)<<endl;//print 2
        cout << mem.callFunction<string, string>("stringFun", " World!") << endl;//print Hello World!
        cout << mem.callFunction<string, string>("TrumpIsADickHead", " World!") << endl;//KeyNotFound thrown
    }
    catch (boost::bad_any_cast e)
    {
        cout << "Bad function calling: "<<e.what()<<endl;
        return 1;
    }
    catch (KeyNotFound e) 
    {
        cout << e.what()<<endl;
        return 1;
    }
}

Answer 1

To make this even compile, I needed to add several standard-library includes:

#include <any>
#include <functional>
#include <iostream>
#include <map>
#include <stdexcept>
#include <string>

I also needed to add the std:: namespace prefix in many places. (Don't be tempted to using namespace std - especially in your header files, where that would affect all your users!)

---

memoize()

This looks like a straightforward memoization function. It's probably worthwhile to constrain it to work only with functions with no internal state and which return copyable values.

It's a shame the caller needs to provide a std::function - I'd like to be able to accept any std::regular_invocable here, but we need something with a known argument list, which we can't deduce in the general case (I think).

It seems that we need the ReturnType to be default-constructible. We can avoid this by first looking for the key, and only inserting if not found.

We're copying the argument tuple more than is necessary, which could be expensive (e.g. for std::string arguments). We should use std::move when storing the tuple as map key.

We have a serious bug because the cache is a function-static variable, meaning that it's shared by all functions with the same signature. That's a fundamental flaw, and should have been discovered during testing. The fix is to make it a member of the closure, with a capture that copy-initialises.

Here's my rewritten memoize():

#include <concepts>

template <std::copyable ReturnType, typename... Args>
auto memoize(std::function<ReturnType(Args...)> func)
    -> decltype(func)
{
    return [func, cache = std::map<std::tuple<Args...>, ReturnType>{}](Args... args) mutable {
        typename decltype(cache)::key_type t(args...);
        auto it = cache.lower_bound(t);
        if (it == cache.end() || it->first != t) {
            it = cache.emplace_hint(it, std::move(t), func(args...));
        }
        return it->second;
    };
}

---

MultiMemoizator

This doesn't seem as useful to me. I can't see how calling functions by name (and having to specify their signatures every time) is any great advantage. And I don't see why this needs to be tied in to the memoization functionality - why not simply store any function, and just return that, to be called or manipulated however required? The call would look quite similar, just swapping a comma for some parens e.g. mem.callFunction<int, int>("intFun")(1).

When looking up a function by name, we don't need a copy of the name - pass a const reference instead.

It's interesting that we report "not found" by exception, but just ignore (with a warning message) attempts to add a function that's already present. Users would probably prefer consistency - I'd suggest throwing in both cases. And consider using std::out_of_range for a lookup failure, as std::map::at() does.

Avoid storing std::string in custom exceptions - the standard library exceptions all use const char* for the message. This reduces the likelihood of exception handlers throwing (e.g. by copying the string and getting std::bad_alloc), which as we all know is unhandleable and causes program termination.

There's a serious bug in callFunction() (that was masked by the static cache in memoize): std::any_cast(), like boost::any_cast(), returns a copy of the stored function. To keep the memoization, we need to return the function back to the map after we've called it.

Improved code:

class MultiMemoizator
{
    std::map<std::string, std::any> functions = {};

public:
    struct duplicate_key_error : public std::logic_error {
        duplicate_key_error(const char *msg) : std::logic_error{msg} {}
    };

    template <typename ReturnType, typename... Args>
    void addFunction(std::string name, std::function<ReturnType(Args...)> func)
    {
        auto result = functions.try_emplace(std::move(name), memoize(func));
        if (!result.second) {
            // N.B. name was not moved from if try_emplace failed
            throw duplicate_key_error(name.c_str());
        }
    }

    template <typename ReturnType, typename... Args>
    ReturnType callFunction(const std::string& name, Args... args)
    {
        auto it = functions.find(name);
        if (it == functions.end()) {
            throw std::out_of_range(name.c_str());
        }
        using function_type = std::function<ReturnType(Args...)>;
        auto cachedFunc = std::any_cast<function_type> (it->second);
        auto const result = cachedFunc(args...);
        it->second = cachedFunc; // we possibly modified our copy of the function
        return result;
    }
};

---

The main() function misses some key tests, as noted above. It doesn't even demonstrate that values are actually being stored and retrieved. We can easily do that by passing a function that produces output when it is called.

Note that nothing except programmer discipline stops us attempting to memoize functions which don't act like constexpr functions, such as this simple example:

std::function<int(int)> badFun = [](int i){ static int n = 0; return i + ++n; };

I don't see anything we can usefully do to avoid that.