Memoizer revisited – Python

A conversation with a coworker entertained the idea of giving a talk on dynamic typed programming language patterns to a group of C++ developers — not that we’re experts, but as part of my team’s initiative for continued education for our engineers, individuals go out and research different ideas, techniques, technologies and present the results to the group so we can, in theory, learn more than each of us could learn in isolation.

Of course, if I want to have any chance of saying anything intelligent, I would need to have more working experience than ‘having tinkered with Perl 5 at one point’. 

So, I’m learning Python.

Starting at the beginning

The first thing I did is go out and download IronPython and CPython, and install both.  Start up the runtime and:

>>>

Ooo, interactive console.  I remember this from Matlab and Maple in college.  Okay, okay, my experience is out of date, but I’m learning.  I wasted like a week on one C++ project last fighting with the limitations of a hand-rolled interactive shell.  Having one out of the box is already a major win, and I’m forgetting how I lived without one for so long. 

After half an hour with O’Reilly’s Python pocket reference, I had our friendly naive Fibonacci sequence generator:

>>> def fib(x):
...   if x < 2:
...     return 1
...   else:
...     return fib(x-1) + fib(x-2)
...
>>>

And we can invoke it with a range of integers 0 thru 9 with the built in map() function and range() functions

>>> map( fib, range(10) )
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
>>>

To the code

So, moving to a source file "memoize.py", memoize becomes some special magic.  This is short and sweet, and I like it even better than when I tinkered with JavaScript closures:

 

def memoize(f):
  "single argument memoization for results of 'f'"
  store = {}
  def anon(x):
    if store.has_key(x):
      return store[x]
    else:
      y = f(x)
      store[x] = y
      return y
  return anon

This is hardly complete, but works to illustrate.  How this works: when memoize is invoked with a function, ‘f’, it sets up a new hash table named ‘store’.  It then on the fly defines a new function ‘anon’ that uses both the original function ‘f’ and the new hash table.  This not-anonymous function is then returned from memoize.

You can now replace fib with the statement

fib = memoize(fib)

This new function object, returned from the call, is assigned to the ‘fib’ variable.  This function object will in turn sometimes invokes the original function, which calls ‘fib’, which now points to the memoizer function object, and not the original function.  Function names are just variables, and can be assigned.

As far as I know, there is no syntax for a function to call itself — it can only call through a variable, and that variable can be reassigned if you choose to.

Decorators

I would be done, but before finishing up this article, I luckily stumbled across decorator syntax — which is exactly this, a shorthand for saying ‘f = g(f)’.  So after defining memoize, we can skip a set and define ‘fib’ pre memoized:

@memoize
def fib(x):
  "computes fibonacci numbers"
  if x < 2:
    return 1
  else:
    return fib(x-1) + fib(x-2)

Paste both of these into "memoize.py", and at the interactive console:

>>> from memoize import fib
>>> fib(100)
573147844013817084101L
>>>

And that’s it.  In all, less than half the size of the C++ example. 

 

And don’t forget to try out the interative console at http://play1.pypy.org/console/.  The code samples above work, and on my machine (Asus eee 901, Win 7, Opera 9.6), it takes less  than a second to compute fib(800).

EDIT ADD: After this posting, I came across documentation for a decorator module in python.  This module apparently provides a set of helper functions for defining decorators.  Among the examples listed is a function named ‘memoize’ that is almost line-for-line identical with my definition above, except that it supports multiple arguments, and uses diifferent dictionary lookup.

In practice, you will want to scope the lifetime of the dictionary — one way to do this is to only use the memoize decorator on nested functions which have definite or bounded scope.