Caching in python using *args and lambda functions
<p>I recently attempted Googles <a href="http://www.ibtimes.co.uk/google-foobar-how-searching-web-earned-software-graduate-job-google-1517284" rel="nofollow"> foo.bar challenge</a>. After my time was up I decided to try find a solution to the problem I couldn't do and found a solution <a href="https://github.com/rtheunissen/foobar/blob/master/line_up_the_captives.py" rel="nofollow">here </a> (includes the problem statement if you're interested). I'd previously been making a dictionary for every function I wanted to cache but it looks like in this solution any function/input can be cached using the same syntax. </p>

<p>Firstly I'm confused on how the code is even working, the *args variable isn't inputted as an argument (and prints to nothing). Heres an modified minimal example to illustrate my confusion:</p>

<pre><code>mem = {}

def memoize(key, func, *args):
    """
    Helper to memoize the output of a function
    """

    print(args)

    if key not in mem:
        # store the output of the function in memory
        mem[key] = func(*args)

    return mem[key]

def example(n):
    return memoize(
        n,
        lambda: longrun(n),
    )

def example2(n):
     return memoize(
        n,
        longrun(n),
     )

def longrun(n):
    for i in range(10000):
        for j in range(100000):
            2**10
    return n
</code></pre>

<p>Here I use the same <strong>memoize</strong> function but with a print. The function <strong>example</strong> returns <strong>memoize(n, a lambda function,)</strong>. The function <strong>longrun</strong> is just an identity function with lots of useless computation so it's easy to see if the cache is working (<strong>example(2)</strong> will take ~5 seconds the first time and be almost instant after). </p>

<p>Here are my confusions:</p>

<ul>
<li>Why is the third argument of memoize empty? When args is printed in <strong>memoize</strong> it prints (). Yet somehow mem[key] stores func(*args) as func(key)?</li>
<li>Why does this behavior only work when using the lambda function (<strong>example</strong> will cache but <strong>example2</strong> won't)? I thought lambda: longrun(n) is just a short way of giving as input a function which returns longrun(n).</li>
</ul>

<p>As a bonus, does anyone know how you could memoize functions using a decorator?</p>

<p>Also I couldn't think of a more descriptive title, edits welcome. Thanks.</p>

<p>The notation <a href="https://docs.python.org/3/tutorial/controlflow.html#arbitrary-argument-lists" rel="nofollow"><code>*args</code></a> stands for a variable number of positional arguments. For example, <code>print</code> can be used as <code>print(1)</code>, <code>print(1, 2)</code>, <code>print(1, 2, 3)</code> and so on. Similarly, <code>**kwargs</code> stands for a variable number of keyword arguments.</p>

<p>Note that the names <code>args</code> and <code>kwargs</code> are just a convention - it's the <code>*</code> and <code>**</code> symbols that make them variadic.</p>

<p>Anyways, <code>memoize</code> uses this to accept basically <em>any</em> input to <em>func</em>. If the result of <em>func</em> isn't cached, it's called with the arguments. In a function call, <code>*args</code> is basically the reverse of <code>*args</code> in a function definition. For example, the following are equivalent:</p>

<pre><code># provide *args explicitly
print(1, 2, 3)
# unpack iterable to *args
arguments = 1, 2, 3
print(*arguments)
</code></pre>

<p>If <code>args</code> is empty, then calling <code>print(*args)</code> is the same as calling <code>print()</code> - no arguments are passed to it.</p>

<hr>

<p>Functions and lambda functions are <em>the same</em> in python. It's simply a different notation for creating a function object.</p>

<p>The problem is that in <code>example2</code>, you are not passing a function. You <em>call</em> a function, then pass on its result. Instead, you have to pass on the function and its argument separately.</p>

<pre><code>def example2(n):
    return memoize(
        n,
        longrun,  # no () means no call, just the function object
        # all following parameters are put into *args
        n
    )
</code></pre>

<hr>

<p>Now, some implementation details: why is <code>args</code> empty and why is there a separate key?</p>

<ul>
<li><p>The empty <code>args</code> comes from your definition of the lambda. Let's write that as a function for clarity:</p>

<pre><code>def example3(n):
    def nonlambda():
        return longrun(n)
    return memoize(n, nonlambda)
</code></pre>

<p>Note how <code>nonlambda</code> takes <em>no arguments</em>. The parameter <code>n</code> is bound from the containing scope as a closure, <a href="https://docs.python.org/3/tutorial/controlflow.html#defining-functions" rel="nofollow">bound from the containing scope</a>. As such, you don't have to pass it to memoize - it is already bound inside the <code>nonlambda</code>. Thus, <code>args</code> is empty in memoize, even though <code>longrun</code> does receive a parameter, because the two don't interact directly.</p></li>
<li><p>Now, why is it <code>mem[key] = f(*args)</code>, not <code>mem[key] = f(key)</code>? That's actually slightly the wrong question; the right question is "why isn't it <code>mem[f, args] = f(*args)</code>?".</p>

<p>Memoization works because the same input to the same function leads to the same output. That is, <code>f, args</code> <em>identifies</em> your output. Ideally, your <code>key</code> would be <code>f, args</code> as that's the only relevant information.</p>

<p>The problem is you need a way to look up <code>f</code> and <code>args</code> inside <code>mem</code>. If you ever tried putting a <code>list</code> inside a <code>dict</code>, you know there are some types which don't work in mappings (or any other suitable lookup structure, for that matter). So if you define <code>key = f, args</code>, you cannot memoize functions taking mutable/unhashable types. Python's <code>functools.lru_cache</code> actually has this limitation.</p>

<p>Defining an explicit <code>key</code> is one way of solving this problem. It has the advantage that the caller can select an appropriate key, for example taking <code>n</code> without any modifications. This offers the best optimization potential. However, it breaks easily - using just <code>n</code> misses out the actual function called. Memoizing a second function with the same input would break your cache.</p>

<p>There are alternative approaches, each with pros and cons. Common is the explicit conversion of types: <code>list</code> to <code>tuple</code>, <code>set</code> to <code>frozenset</code>, and so on. This is slow, but the most precise. Another approach is to just call <code>str</code> or <code>repr</code> as in <code>key = repr((f, args, sorted(kwargs.items())))</code>, but it relies on every value having a proper <code>repr</code>.</p></li>
</ul>

python caching lambda