[Tutor] Memoizing ... [advanced topic: transparent memoization and nested scoping will conflict]

[Danny Yoo]

On Fri, 20 Jun 2003, Gregor Lingl wrote:

> Lloyd Kvam schrieb:
>
> > This is in the Python Cookbook in the Algorithms chapter (17.7).
>
> Thanks for this very valuable hint. My simplified version looks like
> this:
>
> class Memoize:
>     def __init__(self, fn):
>         self.fn = fn
>         self.memo = {}
>     def __call__(self, *args):
>         if args not in self.memo:
>             self.memo[args] = self.fn(*args)
>         return self.memo[args]
>
> It work's well for my purposes.


Hi everyone,



Unfortunately, there are some potential problems when we do memoization on
recursive functions when nested scope is involved.  Whew, that was a
mouthful.  *grin*


This is a very obscure issue --- most people will never ever run into
this problem --- so run away from this message when it starts looking
weird.










Ok, is the room empty now?  *grin* First, let's try out memoization on the
classic Fibonacci function:

###
>>> def fib(n):
...     if n < 2: return 1
...     return fib(n-1) + fib(n-2)
...
>>> class Memoize:
...     def __init__(self, fn):
...         self.fn = fn
...         self.memo = {}
...     def __call__(self, *args):
...         if args not in self.memo:
...             self.memo[args] = self.fn(*args)
...         else:
...             print "memoized lookup for %s" % args
...         return self.memo[args]
...
>>> fib = Memoize(fib)
>>> fib(5)
memoized lookup for 1
memoized lookup for 2
memoized lookup for 3
8
>>> fib(6)
memoized lookup for 5
memoized lookup for 4
13
###



Ok, this looks good so far.  Memoization is working perfectly at the
moment.  But what about this?

###
>>> def fib_maker(a, b):
...     def fib_helper(n):
...         if n == 0: return a
...         if n == 1: return b
...         return fib_helper(n-1) + fib_helper(n-2)
...     return fib_helper
...
>>> fib = fib_maker(1, 1)
>>> fib = Memoize(fib)
>>> fib(5)
8
>>> fib(5)
memoized lookup for 5
8
>>> fib(6)
13
>>> fib(6)
memoized lookup for 6
13
###


Big difference!  Here, we see that the recursive calls aren't going
through the same memoization route as the first example, so the
performance will inevitably suffer.  We do get a kind of memoization, but
only in a very shallow way.



This issue is known by the Lisp/Scheme community; it's briefly hinted in
SICP Exercise 3.27:

http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-22.html#%_thm_3.27


What's happening is that, within the internal fib_helper() function, those
recursive calls to fib_helper() are calls to itself.


When we do a memoization here:

>>> fib = f()
>>> fib = Memoize(fib)

those internal recursive calls still go through the unmemoized versions of
the function.  It's very diabolical.  The only reason we don't run into it
in the first example in Python is because Python apparently doesn't use
nested-scope rules at toplevel.


I'm not aware of a way to fix this without making fib() itself aware that
it's going to be memoized; if anyone can bring more enlightenment on this,
I'll be very happy.


The lesson, I guess, is to be aware that nested-scoped functions and
automatic memoization probably won't mix very well without some careful
work.  But for the most part, we'll seldom run into this issue.




On a related note: most Perl folks know about the 'Memoize' package,
written by Mark Jason Dominius.

    http://perl.plover.com/MiniMemoize/memoize.html

It's pretty cool.  In fact, it makes memoizing functions seem like magic,
and Mark's Memoize package can automatically memoize most functions.  But
for those who think Perl somehow has it any easier than Python, the
example below shows that it too has similar problems when nested scope and
memoization mix:


###
use strict;
use Memoize;


sub fib_maker {
    my ($a, $b) = @_;
    my $fib_helper = sub {
	my ($f, $n) = @_;
	print "Called on $n\n";
	if ($n == 0) { return $a;}
	if ($n == 1) { return $b;}
	return $f->($f, $n-1) + $f->($f, $n-2);
    };
    ## Some contortions seem necessary to get a nested-scope recursive
    ## function... *grin*
    return sub { $fib_helper->($fib_helper, @_[0]) };
}

{ no strict 'refs';
  *{fib} = fib_maker(1, 1);
}

memoize('fib');

print "call1", "\n";
print fib(5),  "\n";
print "call2", "\n";
print fib(6),  "\n";
print "call3", "\n";
print fib(6),  "\n";
###


The conflict between automatic memoization and nested scopes is a
language-indepdendent problem.



Anyway, hope this helps!