Python closure

Question

I am trying to learn Python, and although I am enthusiastic about closing in Python, I am having trouble getting the code to work correctly:

def memoize(fn): def get(key): return (False,) def vset(key, value): global get oldget = get def newget(ky): if key==ky: return (True, value) return oldget(ky) get = newget def mfun(*args): cache = get(args) if (cache[0]): return cache[1] val = apply(fn, args) vset(args, val) return val return mfun def fib(x): if x<2: return x return fib(x-1)+fib(x-2) def fibm(x): if x<2: return x return fibm(x-1)+fibm(x-2) fibm = memoize(fibm) 

Basically, what this should do is use closure to maintain the function state stored in memory. I understand that it is probably much faster, easier to read, and generally more “Putin's” ways to realize this; however, my goal is to understand how Python closures work and how they differ from Lisp, so I'm not interested in alternative solutions, just why my code does not work and what I can do (if anything) to fix it.

The problem I am facing is when I try to use fibm - Python insists that get not defined:

 Python 2.6.1 (r261:67515, Feb 1 2009, 11:39:55) [GCC 4.0.1 (Apple Inc. build 5488)] on darwin Type "help", "copyright", "credits" or "license" for more information. >>> import memoize >>> memoize.fibm(35) Traceback (most recent call last): File "<stdin>", line 1, in <module> File "memoize.py", line 14, in mfun cache = get(args) NameError: global name 'get' is not defined >>> 

Seeing that I'm new to Python, I don’t know if I did something wrong or is it just a language restriction. I hope this is the first. :-)

Answer 1

The problem is your area, not your closures. If you need some heavy reading, you can try http://www.python.org/dev/peps/pep-3104/ .

If it is not, here is a simple explanation:

The problem is the global get statement. global refers to the look itself, and since there is no global get function, it throws.

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

In python 3.0, as I already tested, the nonlocal keyword is exactly what you need, instead of global .

 nonlocal get ... 

In python 2.x, I just deleted the global get and oldget and it works correctly.

Answer 2

 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" 

Exit:

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

Like other answers, however this works. :)

An important change from the code in the question is the assignment to non-global non-local (get); however, I also made some improvements trying to keep your * cough * broken * cough * using closure. Usually the cache is a dict, not a linked closure list.

Answer 3

Get not global, but local to the surrounding function, so the global declaration is not executed.

If you delete global , it still does not work, because you cannot assign a name to the captured variable. To get around this, you can use the object as a variable captured by your closures, and not just change the properties of this object:

 class Memo(object): pass def memoize(fn): def defaultget(key): return (False,) memo = Memo() memo.get = defaultget def vset(key, value): oldget = memo.get def newget(ky): if key==ky: return (True, value) return oldget(ky) memo.get = newget def mfun(*args): cache = memo.get(args) if cache[0]: return cache[1] val = apply(fn, args) vset(args, val) return val return mfun 

This way you don't have to assign the names of the captured variables, but still get what you wanted.

Answer 4

You want to put global get at the beginning of each function (except get ).

def get is the naming of get , so you want it to be declared global before then.

Putting global get into mfun and vset makes them work. I can not point out the rules for determining the area that make this necessary, but it works; -)

Your creations are also quite lazy ... :)

Answer 5

Probably because you want the global value to happen until it is global? By the way, apply is deprecated, use fn (* args) instead.

 def memoize(fn): def get(key): return (False,) def vset(key, value): def newget(ky): if key==ky: return (True, value) return get(ky) get = newget def mfun(*args): cache = get(args) if (cache[0]): return cache[1] val = fn(*args) vset(args, val) return val return mfun def fib(x): if x<2: return x return fib(x-1)+fib(x-2) def fibm(x): if x<2: return x return fibm(x-1)+fibm(x-2) fibm = memoize(fibm) 

Answer 6

I think the best way:

 class Memoized(object): def __init__(self,func): self.cache = {} self.func = func def __call__(self,*args): if args in self.cache: return cache[args] else: self.cache[args] = self.func(*args) return self.cache[args]