How to memoize functions?

[Jeff Epler]

The argument tuple is only "materialized" for a moment (it disappears
after the called function returns, if it was taken by *args, or else
before the first line of the function if it was taken by named args).
It will disappear from a weakkeydict immediately as a result.  

The common memoize, written here using nested scopes, never trims old
values from the dictionary:
    def memoize(f):
        d = {}
        def g(*args):
            if not d.has_key(args):
                d[args] = f(*args)
            return d[args]
        return g
You could make d be a cache of limited size with code like
            if not d.has_key(args):
                if len(d) > 1000:
                    d.pop() # XXX
                d[args] = f(*args)
the XXX line removes "some key" from the dictionary.  The actual item is
not specified, but turns out to have some relationship to the hash value
of args.  This may or may not be acceptable to you.  Otherwise, you might
implement a true pseudorandom replacement algorithm, or the standard LRU,
or LFU.  These may require that you maintain a heap or other auxiliary
list (corresponding to the keys) to achieve O(1) for the "remove an old
memoized value" code.

I just think weakrefs are not the solution to this problem...

Jeff