generic functions in python

[Howard Stearns]

Howard Stearns wrote:
> Funny you should mention this today -- I was just sitting down to 
> implement generic functions myself. ...
> When I finish (who knows when?), I'll try to remember to post here and 
> cc you, Jim.
> ...
> Jim Newton wrote:
>> ...
>> perhaps there is a standard
>> mult-method-dispatch package available for use?

Try this. It's only 55 lines of code plus about that many in comments. Python's pretty cool, no?

"""
Generic Functions and Methods

 >>> foo = Generic_Function()
 >>> foo[object, object, object] = lambda _, x, y, z: 'default'
 >>> foo[int, int, int] = lambda call_next, x, y, z: ['all ints'] + [call_next(x, y, z)]
 >>> foo[object, object] = lambda _, x, y: 'just two'
 >>> foo(1, 2, 3)
['all ints', 'default']
 >>> foo(1, 2, 'three')
'default'
 >>> foo(1, 'two')
'just two'
 >>> foo('oops')
Traceback (most recent call last):
   ...
NoNextMethod: oops
"""
_AUTHOR=["Howard Stearns (stearns at alum.mit.edu)",]
_COPYRIGHT="""
Use this for anything you want, at your own risk.
Mistakes here are Howard's fault and no one elses.
copyright 2004
As a Python newbie, I do welcome comments on style & performance, as
well as on functionality.
"""
"""
There are several simplifications here compared with, say,
http://www.lisp.org/table/references.htm#mop
- FIXME: Currently, no support for **key args.
- No method or class metaobjects or mop.
- No support for method combination, or for before/after methods:
   But there is a call-next-method mechanism, so you can assemble your own
   results as you like.
- No real support for subclassing new kinds of generic functions with their
   own mechanisms.
And there is one extension:
+ Instead of dispatching only on the classes of a fixed number of positional
   arguments, dispatch is on both the number and type of arguments.

Class precence order is as defined by Python getmro().

David Mertz has a nice package at
http://www-106.ibm.com/developerworks/linux/library/l-pydisp.html
* This one differs in that there is only a single (powerful?) mechanism for
   method combination (call-next-method) instead of a built-in list option.
* Generic_Function() instances here are also dict objects, and you add/replace
   method by setting them using the signature as a key.
* This implementation builds a cache of effective methods instead of computing
   dispatches again for each call, so this is a lot faster.
"""

from UserDict import UserDict
from inspect import getmro

class NoNextMethod(Exception): pass

def raise_NoNextMethod(*args):
     raise NoNextMethod, args

class Generic_Function(UserDict, object):
     """A function that can have different method bodies separately defined.
     """
     def __init__(self):
         self.data = {} # All raw methods that have been defined.
         self.reset()
     def reset(self):
         self.cache = {}  # Combined methods that have actually been called.
     # Being a dict, my_func[typeA, typeB, ...] gives the method for those types.
     def __setitem__(self, signature, method_function):
         """Add or replace a method.

         e.g., my_func[Type1, Type2, ...] = lambda call_next, arg1, arg2, ...: body
         Within the body of the method, call_next is a function with the same
         signature as the whole generic function. It executes the next more general
         method that applies to the given arguments.
         """
         self.reset()  # Whenever we add a method, it invalidates the cache.
         UserDict.__setitem__(self, signature, method_function)
     def __call__(self, *dispatch_args):
         actual_types = tuple(map(type, dispatch_args))
         effective_method = self.cache.get(actual_types)
         if effective_method == None:
             effective_method = self.compute_effective_method(actual_types)
             self.cache[actual_types] = effective_method
         return effective_method(*dispatch_args)
     # The next two could reasonably be changed in subclasses to provide different behavior.
     def compute_effective_method(self, classes):
         """Uses the applicable method function to produce a single effective method.

         A method function takes a call_next argument. See __setitem___.
         An effective method has the same signature as the generic function, and is
         suitable as a call_next argument to a method function.
         """
         applicable_methods = self.compute_applicable_methods(classes)
         if applicable_methods == []:
             return raise_NoNextMethod
         else:
             return self.compute_effective_method_from_list(applicable_methods)
     def compute_applicable_methods(self, classes):
         pairs = []
         for signature, method in self.data.iteritems():
             if self.sig_applies_p(signature, classes):
                 pairs.append((signature, method))
         pairs.sort(lambda a, b: self.cmp_sigs_relative_to_arg_types(a[0], b[0], classes))
         methods = []
         return [pair[1] for pair in pairs]
     # Utilities ...
     def sig_applies_p(self, method_sig, arg_types):
         """True if each of method_sig is subclass of each of arg_types, for all of arg_types."""
         return reduce((lambda r, (a, b): r and (a!=None) and (b!=None) and issubclass(a, b)),
                       map(None, arg_types, method_sig),
                       True)
     def cmp_sigs_relative_to_arg_types(self, sig_a, sig_b, arg_types):
         """At the first place where sig_a and sig_b differ, which comes first
         in the full class precedence list of the corresponding type in arg_types."""
         as, bs = list(sig_a), list(sig_b)
         for arg_type in arg_types:
             a = as.pop(0)
             b = bs.pop(0)
             if a != b:
                 class_precedence_list = list(getmro(arg_type))
                 return class_precedence_list.index(a) - class_precedence_list.index(b)
     def compute_effective_method_from_list(self, method_functions):
         """Converts a sequence of supplied method functions to a single effective method function."""
         rest = method_functions[1:]
         if rest == []:
             call_next = raise_NoNextMethod
         else:
             more = self.compute_effective_method_from_list(rest)
             call_next = lambda *args: more(*args)
         return lambda *args: method_functions[0](call_next, *args)

def _test():
     import doctest, Generic_Function
     return doctest.testmod(Generic_Function)

if __name__ == "__main__":
     _test()