SICP exercise 3.27 discusses memoization in Scheme (get a large piece of paper if you want to draw the full environment diagram!). We make a couple of definitions

(define (fib n)
  (if (<= n 1)
    n
    (+ (fib (- n 1)
       (fib (- n 2))))))

and

(define (memoize f)
  (lambda (n)
    (cond ((in? n memo) (get n memo))
          (else
            (let ((result (f n)))
              (add-kv! n result)
              result)))))

(I’m simplifying the book’s code here - assume that we’ve made some kind of empty dictionary device called memo which has membership testing with in?, element access with get, and add-kv! to add a new key-value pair).

Of course, (define memo-fib (memoize fib)) is not the correctly memoized function we want. ‘Recursive’ calls it makes will actually be to the unmemoized fib function, so after (memo-fib 10) for example the memo will contain an entry for 10 but no other entries. The memoized version memo-fib used in 3.27 is a function which is defined to be memoize applied to a lambda function that calls memo-fib. This doesn’t let us memoize functions we’ve already defined - we had to re-write the definition entirely.

To do that, we have to change the binding of the name fib. Scheme lets us do this with (set! fib (memoize fib)) which works correctly. Imagine the environment diagram: after the set!, there will be an environment E used for the evaluation of (memoize fib) in which the parameter f is bound to the original definition of fib (whose environment part is the global environment) and a return value which is an unnamed function whose definition is the body of (memoize f) (and whose environment part is E). In the global environment, fib now points to this new function, so when we call (fib 3) it refers to the new memoized code, which uses a function f bound to the old definition of fib, but the recursive calls in this old code use the name fib which resolves to the new memoized function and thus the memoization works correctly.

This rebinding is exactly what happens with Python decorators:

@decorator
def f(x):
  <body>

is equivalent to

def f(x):
  <body>
f = decorator(f)

and indeed there is a memoizing decorator called cache in functools.

It’s more interesting to do the Python memoization by hand. Defining

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

memo = {}

def memoize(func):
    def memoized_func(x):
        if x in memo:
            return memo[x]
        value = func(x)
        memo[x] = value
        return value
    return memoized_func

fib = memoize(fib)

is equivalent to what we did with set! in Scheme, and pythontutor.com will draw you a beautiful frame diagram and step through the evaluation of fib(3). But we can now take the lid off and see what’s inside. Python functions have their closures accessible as dunder attributes: fib.__closure__[0] is a cell object containing bindings for the free variable func in memoized_func when fib was redefined, and we can get hold of this binding with

closure_fib = fib.__closure__[0].cell_contents

Self test: what will memo look like after closure_fib(10) is evaluated?

…

…

…

…

…

…

Answer: clo_fib references the original fib definition, so memo[10] will not be set. Recursive calls will use the name fib referring to the memoized code, so all of memo[0] to memo[9] will be set.