5
$\begingroup$

Because a bare function object might not have constant time complexity, and because the function object might be called with the same argument repeatedly, I thought it might be good to cache its outputs. This is possible if the function has equality-comparable domain. Let me illustrate by a C++ code snippet:

#include <functional>
#include <map>

template <class R, class ...T>
class CachedFunc {
private:
    std::function<R(T...)> func;
    mutable std::map<std::tuple<T...>, R> caches;
public:
    // ...
    R operator() (const T &...args) const {
        auto key = std::make_tuple(args...);
        try {
            return caches.at(key);
        } catch (const std::out_of_range &) {
            auto result = func(args...);
            caches.insert_or_assign(key, result);
            return result;
        }
    }
};

The dictionary caches stores the cached outputs. Upon when the function object is called, if there is no cache for the input, it is newly cached.

Yet, I see several issues with this idea:

  • This function class is just a pointless overhead if the function itself has constant time complexity.

  • For imperative languages, this CachedFunc can be a convenient function class on its own. However, because it inevitably involves a mutable state, I don't see how this class would go well with functional languages.

In summary, if my (functional) programming language to incorporate the mechanism of CachedFunc, it would be the compiler's responsibility whether to actually use it. What techniques can a compiler use to determine which functions will benefit from having their results cached?

$\endgroup$
5
  • 1
    $\begingroup$ This is called memoisation. Yes, it is a good idea in a functional language where functions generally don't have side-effects, but as you say it is not necessarily easy to know which functions will benefit from it. Is that what you're looking for as an answer, or do you want strategies for deciding which functions should be memoised? $\endgroup$
    – kaya3
    May 18, 2023 at 13:16
  • $\begingroup$ @kaya3 I thought it was my responsibility to build a compiler that does this. If the community can help, I'll be so glad. $\endgroup$ May 18, 2023 at 13:18
  • 1
    $\begingroup$ I think you may have misunderstood me ─ I'm not proposing to help you write your compiler, I'm trying to clarify what you're looking for from an answer to this question. Are you just looking for confirmation that memoisation can be a good idea, or are you looking for more detailed advice about how your compiler should decide which functions to memoise? $\endgroup$
    – kaya3
    May 18, 2023 at 13:43
  • $\begingroup$ @kaya3 The latter. I'd gladly accept it. $\endgroup$ May 18, 2023 at 13:44
  • $\begingroup$ Thanks for clarifying ─ I've edited your question to make clear what you're asking. Compiling functional languages isn't really my expertise, but I'm sure you will be able to get helpful answers from other users here. $\endgroup$
    – kaya3
    May 18, 2023 at 13:50

1 Answer 1

3
$\begingroup$

A middle ground: CSE

Swift — not even a functional language — has the @_effects attribute. While this only works inside the standard library at the time of writing, you can use it to mark a function as being completely pure (@_effects(readnone)) or only reading from and not writing to external state (@_effects(readonly)). Methods marked with these attributes can be eliminated at the call site when the return value is known by the caller, such as when the caller has already used the function. This is known as call-site elimination, or CSE.

Since Swift is not a functional language, methods without the @_effects attribute are impure-by-default.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .