<p>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:</p>
<pre><code>#include &lt;functional&gt;
#include &lt;map&gt;

template &lt;class R, class ...T&gt;
class CachedFunc {
private:
    std::function&lt;R(T...)&gt; func;
    mutable std::map&lt;std::tuple&lt;T...&gt;, R&gt; caches;
public:
    // ...
    R operator() (const T &amp;...args) const {
        auto key = std::make_tuple(args...);
        try {
            return caches.at(key);
        } catch (const std::out_of_range &amp;) {
            auto result = func(args...);
            caches.insert_or_assign(key, result);
            return result;
        }
    }
};
</code></pre>
<p>The dictionary <code>caches</code> stores the cached outputs. Upon when the function object is called, if there is no cache for the input, it is newly cached.</p>
<p>Yet, I see several issues with this idea:</p>
<ul>
<li><p>This function class is just a pointless overhead if the function itself has constant time complexity.</p>
</li>
<li><p>For imperative languages, this <code>CachedFunc</code> 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.</p>
</li>
</ul>
<p>In summary, if my (functional) programming language to incorporate the mechanism of <code>CachedFunc</code>, 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?</p>

<functions><optimization><functional-programming><memoization>
Which functions should a compiler cache outputs for?
CC BY-SA 4.0
2023-05-18T13:16:53.767Z
This is called [memoisation](https://en.wikipedia.org/wiki/Memoization). 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?
kaya3
CC BY-SA 4.0
2023-05-18T13:18:19.347Z
@kaya3 I thought it was my responsibility to build a compiler that does this. If the community can help, I'll be so glad.
Dannyu NDos
CC BY-SA 4.0
2023-05-18T13:43:36.153Z
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?
kaya3
CC BY-SA 4.0
2023-05-18T13:44:55.457Z
@kaya3 The latter. I'd gladly accept it.
Dannyu NDos
CC BY-SA 4.0
2023-05-18T13:50:55.227Z
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.
kaya3
<h1>A middle ground: CSE</h1>
<p>Swift — not even a functional language — has <a href="https://github.com/apple/swift/blob/main/docs/ReferenceGuides/UnderscoredAttributes.md#_effectseffectname" rel="nofollow noreferrer">the <code>@_effects</code> attribute</a>. 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 (<code>@_effects(readnone)</code>) or only reading from and not writing to external state (<code>@_effects(readonly)</code>). Methods marked with these attributes can be eliminated at the call site <strong>when the return value is known by the caller</strong>, such as when the caller has already used the function. This is known as <em>call-site elimination</em>, or CSE.</p>
<p>Since Swift is not a functional language, methods without the <code>@_effects</code> attribute are impure-by-default.</p>

CC BY-SA 4.0
2023-05-18T13:21:06.280Z
2023-05-18T13:21:06.280Z
Bbrk24
# Which functions should a compiler cache outputs for?
Posted by: username_0 on 2023-05-18
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 
#include 

template 
class CachedFunc {
private:
    std::function func;
    mutable std::map, 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?
**Tags:** functions optimization functional-programming memoization
> **Comments:**
> **username_1**: This is called [memoisation](https://en.wikipedia.org/wiki/Memoization). 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?  
> **username_0**: @kaya3 I thought it was my responsibility to build a compiler that does this. If the community can help, I'll be so glad.  
> **username_1**: 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?  
> **username_0**: @kaya3 The latter. I'd gladly accept it.  
> **username_1**: 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.  
---
## 1 answers
### Answer by username_2 on 2023-05-18. Score: 3
# A middle ground: CSE

Swift — not even a functional language — has [the `@_effects` attribute](https://github.com/apple/swift/blob/main/docs/ReferenceGuides/UnderscoredAttributes.md#_effectseffectname). 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.
---
