mark++

Wow, Perl’s Memoize.pm is cool. Try this:

   use Memoize;
   sub fib {
      my $n = shift;
      print "called fib($n)\\n";
      return $n if $n < 2;
      fib($n-1) + fib($n-2);
   }
   print fib(5) . "\\n\\n";
   memoize( 'fib' );
   print fib(5) . "\\n\\n";

It does two different things:

1. It wraps the function with a caching version.
2. It replaces all calls to the function with calls to the memoized version. This includes the recursive calls inside the function itself.

It does all of this without requiring any source-level changes to the memoized function. This makes it easy to accelerate any referrentially-transparent function. Just don’t do something dumb like memoize print() or time().

With C++ I can mimic #1, but not #2. It’s a shame, because #2 is the cool part. With my C++ implementation, I only speed up identical repeated calls:

   fib(5);  // slow: makes 14, mostly-redundant, recursive calls
   fib(5);  // fast: purely a look up
   fib(4);  // slow
   fib(6);  // slow

Perl does much better:

   fib(5);  # fast: makes 5 recursive calls
   fib(5);  # fast: purely a look up
   fib(4);  # fast: purely a look up
   fib(6);  # fast: picks up where fib(5) left off

I’m somewhat bugged that I couldn’t duplicate this behavior with C++. Perl needn’t reach into it’s “dynamic language” bag of tricks to achieve this. It just provides access to the symbol table:

   sub a() { print "a\\n"; }
   sub b() { print "b\\n"; }
   *a = \\&b;
   a();     # prints b