James Pine Has A Blog

I don’t know anyone (though not doubt they exist) who debates the merits of natural languages and chooses which one to communicate with based on characteristics such as whether they’re fusional vs. agglutinative, but I know plenty of people who discuss the virtues of various computer programming languages and think one is better than the other for various reasons. One of the languages I find often lambasted, happens to be one that I’m required to use at my current job, Perl.

I skim through numerous computerish books, and one that I recently came across is Higher-Order Perl. I’ve read through the first three chapters and the third one touched on the inefficiencies of the recursive version of the Fibonacci sequence generating function. In order to improve its runtime, the author suggested caching and discussed a generic library for memoizing any function. Here’s the fib function in question:

sub fib {
  my ($n) = @_;
  return 1 if($n < 2);
  return fib($n-1) + fib($n-2);
};

Running this code to calculate the 30th Fibonacci number, 1346269, takes my Intel Atom based EeePC 8.7 seconds. The simplistic memoization function looks like this:

sub memoize {
  my ($func) = @_;
  my %cache = ();
  my $stub = sub {
    my $key = join(",", @_);
    $cache{$key} ||= $func->(@_);
    return $cache{$key};
  };
  return $stub;
};

The memoization function takes a function as a parameter and caches invocations of it so future invocations with the same parameters don't need to be recomputed. Of course this won't work with every type of function, but it works great for our fib function e.g. fib(30) calculates fib(29) + fib(28), and fib(29) calculates fib(28) + fib(27) etc. which results in a lot of duplicate operations. The caveat is that the fib function has to be replaced in Perl's symbol table with the memoized function, otherwise the recursive calls won't be using the cache:

*fib = memoize(\&fib);

It occured to me that there should be a way to get around mucking with Perl's symbol table and maybe a YCombinator could help. Here's a version of fib written as a YCombinator and a new version of memoize that works with it:

sub yComFib {
  my ($f,$n) = @_;
  return 1 if($n < 2);
  return $f->($f,$n-1) + $f->($f,$n-2);
};

sub memoizeYComF {
  my ($func) = @_;
  my %cache = ();
  my $stub = sub {
    my ($f, @args) = @_;
    my $key = join(",", @args);
    $cache{$key} ||= $func->($f, @args);
    return $cache{$key};
  };
  return $stub;
};

Now instead of altering Perl's symbol table, we can just store a function reference and call is with itself:

my $fastfib = memoizeYComF(\&yComFib);
$fastfib->($fastfib,30);

This version only take 0.0012 seconds to calculate the 30th Fibonacci number. The syntax may not be that pretty, but the idea expressed is quite powerful!