Statically Typed

because Hindley-Milner rocks

A memoizing decorator


I like decorators in Python as they take a fairly basic design pattern and turn it into a succinct way of expressing functionality within code.  I’ve also had to make use of memoization in a number of instances at work where performance mattered (C++ specifically.)  Inspired by an SO post, I got to thinking about how I might go about making a memoizing decorator in Python myself.  The primary goal of this decorator:  to assign to a function some dictionary-like object that handles result storage.

def memoize( myDict ):
    """Adds the ability to memoize the results of any function call.  Memoize is a decorator factory."""
    def output( func ):
        def lookUp( *args ):
            result = myDict.get( args )
            if( result == None ):
                result = func( *args )
                myDict[ args ] = result
            return result
        loopUp.__name__ = func.__name__
        loopUp.__doc__ = func.__doc__
        loopUp.__dic__ = func.__dic__
        loopUp.__module__ = func.__module__
        return lookUp
    return output

Unfortunately now that I’ve written it, I don’t like it.  Why?  Two reasons and both are about maintainability.  First, my own rule of thumb is that if you’re nesting more than three times, you’re doing it wrong.  The more nesting there is, the more difficult code is to understand.  I don’t want the next guy thinking hard about my code, I want him thinking hard about his code.

The second reason is that most people I’ve talked to and met in my professional career haven’t dealt with functions as first-class objects.  They see return and wonder what “value” is being returned without consideration that a function, itself, is a valid return type. What makes me sad is that this is true of both part-time and full-time Python developers; a story for another day.

I’ll jump back into coding mode by examining two Python libraries in my efforts to reduce code complexity.  The first comes packaged with Python 2.6 while the second has to be downloaded from the Python website.  Be forewarned that I’ve only used the first and not the second.

The first library is all about aiding the creation of partially applied function objects, i.e. currying.  The wraps decorator from functools creates a partially applied function while at the same time making itself invisible to the caller.

from functools import wraps
def memoize( myDict ):
    """Adds the ability to memoize the results of any function call.  Memoize is a decorator factory."""
    def output( func ):
        @wraps( func )
        def lookUp( *args ):
            result = myDict.get( args )
            if( result == None ):
                result = func( *args )
                myDict[ args ] = result
            return result
        return lookUp
    return output

All this does is remove four lines of code and replace it with a call to a decorator.  In my opinion this code is even less maintainable than it was before as someone would have to know what action @wraps accomplished.

In Python 2.6 and later someone came out with a decorator decorator.  Using it, the above code simplifies to

from decorator import decorator
def memoize( myDict ):
    """Adds the ability to memoize the results of any function call.  Memoize is a decorator factory."""
    @decorator
    def output( func, *args ):
        result = myDict.get( args )
        if( result == None ):
            result = func( *args )
            myDict[ args ] = result
        return result
    return output

which is arguably more concise and expressive to the original intent.  On the downside, it still leaves a level of indirection.  However, I’m certain that someone reading this and seeing an example could quickly figure out what was happening here.

expensive = {}

@memoize( expensive )
def reallyExpensiveFunction( x, y, z ):
    #code goes here

Now I’m happy.  Here are two other memoizing Python solutions to compare to mine: link 1 and link 2.  The first is a very good solution (better than mine.)

I don’t want the next guy to have to think hard about my code, I want him to think hard about his code.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Information

This entry was posted on June 13, 2010 by in Python.
%d bloggers like this: