Closures in Python

The problem is in your scoping, not in your closures. If you're up for some heavy reading, then you can try http://www.python.org/dev/peps/pep-3104/.

If that's not the case, here's the simple explanation:

The problem is in the statement global get . global refers to the outermost scope, and since there isn't any global function get, it throws.

What you need, is an access specifier for variables in the enclosing scope, and not the global scope.

In python 3.0, as I've tested, the nonlocal keyword is exactly what you need, in the place of global.

nonlocal get
...

In python 2.x, I just removed the global get and the oldget references and it works properly.

def memoize(fn):
  get = [lambda key: (False, None)]

  def vset(args):
    value = fn(*args)
    oldget = get[0]
    def newget(key):
      if args == key:
        return (True, value)
      return oldget(key)
    get[0] = newget
    return value

  def mfun(*args):
    found, value = get[0](args)
    if found:
      return value
    return vset(args)

  return mfun

CALLS = 0

def fib(x):
  global CALLS
  CALLS += 1
  if x<2: return x
  return fib(x-1)+fib(x-2)

@memoize
def fibm(x):
  global CALLS
  CALLS += 1
  if x<2: return x
  return fibm(x-1)+fibm(x-2)

CALLS = 0
print "fib(35) is", fib(35), "and took", CALLS, "calls"
CALLS = 0
print "fibm(35) is", fibm(35), "and took", CALLS, "calls"

Output is:

fib(35) is 9227465 and took 29860703 calls
fibm(35) is 9227465 and took 36 calls

Similar to other answers, however this one works. :)

The important change from the code in the question is assigning to a non-global non-local (get); however, I also made some improvements while trying to maintain your *cough*broken*cough* closure use. Usually the cache is a dict instead of a linked list of closures.