Understanding a memoization decorator as a closure
<p>I'm trying to learn about Python decorators, and I'd like to understand in more detail exactly how closure applies, for example in this memoization context:</p>

<pre><code>def memoize(f):
    memo = {}
    def helper(x):                 
        if x not in memo:
            memo[x] = f(x)
        return memo[x]
    return helper   

@memoize  
def fib(n):
    if n in (0,1):
        return n
    return fib(n - 1) + fib(n - 2)
</code></pre>

<p>I understand that <code>memoize</code> returns functions that are bound to <code>memo</code> values in the enclosing scope of <code>helper</code>, even when the program flow is no longer in that enclosing scope. So, if <code>memoize</code> is called repeatedly it will return a varying sequence of functions depending upon the current values of <code>memo</code>. I also understand that <code>@memoize</code> is syntactic sugar that causes calls to <code>fib(n)</code> to be replaced with calls to <code>memoize(fib(n))</code>.</p>

<p>Where I am struggling is how the called value of <code>n</code> in <code>fib(n)</code> is effectively converted to the <code>x</code> in <code>helper(x)</code>. Most tutorials on closures don't seem to make this point explicit, or they rather vaguely say that one function âcloses overâ the other, which just makes it sound like magic. I can see how to use the syntax, but would like to have a better grasp of exactly what is happening here and what objects and data are being passed around as the code executes.</p>

<p>You've misunderstood what the <code>@memoize</code> decorator does. The decorator is not called each time you call <code>fib</code>. The decorator is called <em>just once</em> per function that is decorated.</p>

<p>The original <code>fib</code> function is <em>replaced</em> by the <code>helper()</code> function, with the original function object available as the <code>f</code> closure, together with the <code>memo</code> closure:</p>

<pre><code>&gt;&gt;&gt; def fib(n):
...     if n in (0,1):
...         return n
...     return fib(n - 1) + fib(n - 2)
...
&gt;&gt;&gt; fib
&lt;function fib at 0x1023398c0&gt;
&gt;&gt;&gt; memoize(fib)
&lt;function helper at 0x102339758&gt;
</code></pre>

<p>This gives the replacement <code>helper</code> function <em>one</em> closure, and each time you call that <code>helper()</code> function the same <code>memo</code> dictionary is used to look up already-produced results for the current value of <code>x</code>.</p>

<p>You can see this all work in the interpreter:</p>

<pre><code>&gt;&gt;&gt; @memoize
... def fib(n):
...     if n in (0,1):
...         return n
...     return fib(n - 1) + fib(n - 2)
...
&gt;&gt;&gt; fib
&lt;function helper at 0x10232ae60&gt;
</code></pre>

<p>Note the function name there! That's <code>helper</code>. It has a closure:</p>

<pre><code>&gt;&gt;&gt; fib.__closure__
(&lt;cell at 0x10232d9f0: function object at 0x10232ade8&gt;, &lt;cell at 0x10232da98: dict object at 0x102353050&gt;)
</code></pre>

<p>A function object and a dictionary, those are <code>f</code> and <code>memo</code>, respectively. Access the cell contents with <code>.cell_contents</code>:</p>

<pre><code>&gt;&gt;&gt; fib.__closure__[0].cell_contents
&lt;function fib at 0x10232ade8&gt;
&gt;&gt;&gt; fib.__closure__[1].cell_contents
{}
</code></pre>

<p>That's the original decorated function and the empty dictionary alright. Let's use this function:</p>

<pre><code>&gt;&gt;&gt; fib(0)
0
&gt;&gt;&gt; fib(1)
1
&gt;&gt;&gt; fib.__closure__[1].cell_contents
{0: 0, 1: 1}
</code></pre>

<p>That's the resulting values for <code>x</code> set to <code>0</code> and <code>1</code> being stored in the <code>memo</code> dictionary. Next time I call <code>fib</code> with either value, the memo is used. New <code>x</code> values are calculated and added:</p>

<pre><code>&gt;&gt;&gt; fib(2)
1
&gt;&gt;&gt; fib.__closure__[1].cell_contents
{0: 0, 1: 1, 2: 1}
</code></pre>

<p>You can see how well that works by timing how long a larger number takes to calculate:</p>

<pre><code>&gt;&gt;&gt; start = time.clock(); fib(500); print(format(time.clock() - start, '.10f'))
139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125L
0.0008390000
&gt;&gt;&gt; start = time.clock(); fib(500); print(format(time.clock() - start, '.10f'))
139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125L
0.0000220000

&gt;&gt;&gt; start = time.clock(); fib(500); print(format(time.clock() - start, '.10f'))
139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125L
0.0000190000
</code></pre>

<p>After the first call, looking up the memo is 40 times as fast as all the intermediate results have been memoized:</p>

<pre><code>&gt;&gt;&gt; len(fib.__closure__[1].cell_contents)
501
</code></pre>

python closures memoization python-decorators