Memoizing decorator

[Bengt Richter]

On 5 Dec 2005 16:15:38 -0800, "Daishi  Harada" <daishi at gmail.com> wrote:

>Hi,
>
>I'm trying to find/write a memoizing decorator
>that works both for functions and methods.
ISTM you can't do that without defining exactly what
the instance that a method is bound to (i.e., the self argument)
contributes to the function/method result. It could be anything,
and it could guarantee that results are no more cacheable than random.random()
results. If you are saying (from the look of your test_memoize) that you want
to ignore the instance (self) entirely, you are effectively saying the method
might as well be a staticmethod.

>I've been looking at the following two samples:
>
>http://wiki.python.org/moin/PythonDecoratorLibrary#head-11870a08b0fa59a8622201abfac735ea47ffade5
>http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/325205
>
>AFAICT, both of these seem to be targetting bare
>functions (the second seems to break with:
>    unbound methods must have non-NULL im_class
>).
>
>I'm using the following code to test the decorators:
>
>---
>def test_memoize(memoize_fn):
>    @memoize_fn
>    def fn(x):
>        print '(eval %s)' % str(x),
>        return x
>    print 'fn', fn(1)
>    print 'fn', fn(1)
>
>    class A(object):
>        @memoize_fn
>        def fn(self, x):
>            print '(eval %s)' % str(x),
>            return x
>    a = A()
>    print 'meth', a.fn(1)
>    print 'meth', a.fn(1)
>---
>
>In the method test, I get:
>    fn() takes exactly 2 arguments (1 given)
>
>As I understand things the difficulty here
>is due to the way Python resolves between
>functions, unbound methods, and bound
>methods, which I have a basic sense of,
>and how user-defined callables fits into
>this picture, which I'm not very clear on.
>I *think* the reason this exception comes
>up is because user-defined callables don't
>automagically get a 'self' prepended to
>the argument list.
No, users can define callables that will get a "self' prepended" --
it's a matter of defining it so it has a __get__ method, which
functions do (whether bound to names in class variable name space or not,
it just the attribute lookup via instance finding it in the class that
triggers the __get__ method-binding)


>
>So I've managed to get these working for both
>functions and methods by wrapping them in
>yet another function (the following is for the
>cookbook example, replacing 'cachedmethod'):
>
>---
>def memoize(function):
>    im = Memoize(function)
>    def fn(*args, **kwargs):
>        return im(*args, **kwargs)
>    return fn
>---
>
>However, this seems wasteful in that there
>are now 2 "wrapper" function invocations
>before one gets to the underlying function.
>
>I would appreciate any advice on how to
>proceed/clean this up.
>
First, I would suggest thinking about the exact semantics of method
memoization. E.g. suppose you write

    class Oops(object):
        def __init__(self, factor): self.factor = factor
        @memoize_fn
        def mul(self, x):
            return self.factor * x

You would need a separate cache for every instance to use x as a cache lookup key,
or look up with say (x, id(self)), either way assuming that self.factor can't change.

But if you wanted something just to pass the test, and you really wanted to use
the same decorator for both, then you could wrap the decorated function/method
in a custom descriptor that would do what you want whether called as a function
or as a bound method. Here's a hack, caching just on the basis of non-self args,
tested only as far as you see. 

 >>> def test_memoize(memoize_fn):
 ...     @memoize_fn
 ...     def fn(x):
 ...         print '(eval %s)' % str(x),
 ...         return x
 ...     print 'fn', fn(1)
 ...     print 'fn', fn(1)
 ...     class A(object):
 ...         @memoize_fn
 ...         def fn(self, x):
 ...             print '(eval %s)' % str(x),
 ...             return x
 ...     a = A()
 ...     print 'meth', a.fn(1)
 ...     print 'meth', a.fn(1)
 ...
 >>> def memoize_FM(f):
 ...     _cache = {}
 ...     # define closure-seeing (f & _cache)  __call__ for method use
 ...     def __call__(self, *args, **kw):
 ...         try: return _cache[args]
 ...         except KeyError:
 ...             if self.inst is not None:
 ...                 retval = _cache[args] = f(self.inst, *args, **kw)
 ...             else:
 ...                 retval = _cache[args] = f(*args, **kw)
 ...             return retval
 ...     class FunMethod(object):
 ...         def __init__(self): self.inst=None
 ...         def __get__(self, inst, cls=None):
 ...             self.inst = inst
 ...             return self
 ...     FunMethod.__call__ = __call__   # to get access to f & _cache
 ...     return FunMethod()
 ...
 >>> test_memoize(memoize_FM)
 fn (eval 1) 1
 fn 1
 meth (eval 1) 1
 meth 1
  

Regards,
Bengt Richter