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

[Gregor Lingl]

Danny Yoo schrieb

>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.
>
>  
>
Thanks, Danny, for your thorough demonstrations and explanations. 
Nevertheless
I must admit, that I haven't got it fully until now. I'll have to think 
about it on some
quite weekend.

I observed, that - if the goal only were to have a factory for 
fib-functions - one can get around
with:

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)
    fib_helper = Memoize(fib_helper)
    return fib_helper

I understand, that this is not a satisfactory solution to the problem of 
Memoize.
However,
(a) could you give me a clue, why this works in contrast to Memoizing the
returned fib_helper.
(b) this gives raise to the question if an enhanced Memoize could, by 
some sort
of inspection of fn, determine if this nested_scope_problem will occur 
with fn?
(Even if your words suggest that there is no hope to solve it)

Thanks, Gregor

PS.: By the way, thanks also for your de- and enlightening implementation
of Peanos axioms for the natural numbers (except that probably there will
not be infinitely many of them in my computer ... ;-) ) along with your
accompanying explanations of those different types of their 
representations ...

They really create understanding!






>
>
>
>
>
>
>
>
>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!
>
>
>
>  
>