[Python-checkins] r43724 - sandbox/trunk/overload/overloading.py sandbox/trunk/overload/time_overloading.py

guido.van.rossum python-checkins at python.org
Sat Apr 8 00:16:31 CEST 2006


Author: guido.van.rossum
Date: Sat Apr  8 00:16:29 2006
New Revision: 43724

Modified:
   sandbox/trunk/overload/overloading.py
   sandbox/trunk/overload/time_overloading.py
Log:
Some restructuring.  Better testing.


Modified: sandbox/trunk/overload/overloading.py
==============================================================================
--- sandbox/trunk/overload/overloading.py	(original)
+++ sandbox/trunk/overload/overloading.py	Sat Apr  8 00:16:29 2006
@@ -1,41 +1,26 @@
 #!/usr/bin/env python2.5
 
-# overloading.py
-
-"""Here's another executable email.
+"""Dynamically overloaded functions.
 
 This is an implementation of (dynamically, or run-time) overloaded
-functions, formerly known as generic functions or multi-methods.
+functions; also known as generic functions or multi-methods.
 
-I actually blogged on Artima about multi-methods about a year ago; but
-at the time I hadn't figured out the trick of explicitly declaring the
-MM before registering the implementations (Phillip helpfully pointed
-that out in a comment); also, I was using a global registry then.
-
-This version is an improvement over my earlier attempts (both last
-year and at the start of this thread) because it supports subclasses
-in call signatures.  If an implementation is registered for a
-signature (T1, T2), then a call with a signature (S1, S2) is
-acceptable, assuming that S1 is a subclass of T1, S2 a subclass of T2,
-and there is no ambiguity in the match (see below).
-
-I came up with an algorithm for doing this that may or may not
-resemble the one in PEAK's RuleDispatch.  I kind of doubt that it's
-all that similar because RuleDispatch supports arbitrary predicates.
-In contrast, I'm just using the argument types for dispatch, similar
-to (compile-time) overloaded functions in C++ and methods in Java.  I
-do use a concept that I overheard Phillip mention: if there are
-multiple matches and one of those doesn't *dominate* the others, the
-match is deemed ambiguous and an exception is raised.  I added one
-refinement of my own: if, after removing the dominated matches, there
-are still multiple matches left, but they all map to the same
-function, then the match is not deemed ambiguous and that function is
-used.  Read the method find_func() below for details.
-
-The example is a bit lame; it's not a very good pretty-printer and it
-only dispatches on a single argument; but it does exercise the weeding
-out of dominant matches.  I'll try to post a complete unit test suite
-later.
+The dispatch algorithm uses the types of all argument for dispatch,
+similar to (compile-time) overloaded functions or methods in C++ and
+Java.
+
+Most of the complexity in the algorithm comes from the need to support
+subclasses in call signatures.  For example, if an function is
+registered for a signature (T1, T2), then a call with a signature (S1,
+S2) is acceptable, assuming that S1 is a subclass of T1, S2 a subclass
+of T2, and there are no other more specific matches (see below).
+
+If there are multiple matches and one of those doesn't *dominate* all
+others, the match is deemed ambiguous and an exception is raised.  A
+subtlety here: if, after removing the dominated matches, there are
+still multiple matches left, but they all map to the same function,
+then the match is not deemed ambiguous and that function is used.
+Read the method find_func() below for details.
 
 Python 2.5 is required due to the use of predicates any() and all().
 
@@ -47,7 +32,7 @@
 
 
 class overloaded:
-    # An implementation of overloaded functions.
+    """An implementation of overloaded functions."""
 
     def __init__(self, default_func):
         # Decorator to declare new overloaded function.
@@ -56,20 +41,23 @@
         self.default_func = default_func
 
     def register(self, *types):
-        # Decorator to register an implementation for a specific set of types.
-        # .register(t1, t2)(f) is equivalent to .register_func((t1, t2), f).
+        """Decorator to register an implementation for a specific set of types.
+
+        .register(t1, t2)(f) is equivalent to .register_func((t1, t2), f).
+
+        """
         def helper(func):
             self.register_func(types, func)
             return func
         return helper
 
     def register_func(self, types, func):
-        # Helper to register an implementation.
+        """Helper to register an implementation."""
         self.registry[tuple(types)] = func
         self.cache = {} # Clear the cache (later we can optimize this).
 
     def __call__(self, *args):
-        # Call the overloaded function.
+        """Call the overloaded function."""
         types = tuple(map(type, args))
         func = self.cache.get(types)
         if func is None:
@@ -77,12 +65,19 @@
         return func(*args)
 
     def find_func(self, types):
-        # Find the appropriate overloaded function; don't call it.
-        # NB. This won't work for old-style classes or classes without __mro__.
+        """Find the appropriate overloaded function; don't call it.
+        
+        This won't work for old-style classes or classes without __mro__.
+
+        """
         func = self.registry.get(types)
         if func is not None:
             # Easy case -- direct hit in registry.
             return func
+
+        # XXX Phillip Eby suggests to use issubclass() instead of __mro__.
+        # There are advantages and disadvantages.
+
         # I can't help myself -- this is going to be intense functional code.
         # Find all possible candidate signatures.
         mros = tuple(t.__mro__ for t in types)
@@ -96,7 +91,9 @@
         if len(candidates) == 1:
             # Unique match -- that's an easy case.
             return self.registry[candidates[0]]
+
         # More than one match -- weed out the subordinate ones.
+
         def dominates(dom, sub,
                       orders=tuple(dict((t, i) for i, t in enumerate(mro))
                                    for mro in mros)):
@@ -113,6 +110,7 @@
                 return False
             return all(order[d] <= order[s]
                        for d, s, order in zip(dom, sub, orders))
+
         # I suppose I could inline dominates() but it wouldn't get any clearer.
         candidates = [cand
                       for cand in candidates
@@ -120,10 +118,12 @@
         if len(candidates) == 1:
             # There's exactly one candidate left.
             return self.registry[candidates[0]]
+
         # Perhaps these multiple candidates all have the same implementation?
         funcs = set(self.registry[cand] for cand in candidates)
         if len(funcs) == 1:
             return funcs.pop()
+
         # No, the situation is irreducibly ambiguous.
         raise TypeError("ambigous call; types=%r; candidates=%r" %
                         (types, candidates))

Modified: sandbox/trunk/overload/time_overloading.py
==============================================================================
--- sandbox/trunk/overload/time_overloading.py	(original)
+++ sandbox/trunk/overload/time_overloading.py	Sat Apr  8 00:16:29 2006
@@ -6,66 +6,67 @@
 
 from overloading import overloaded
 
-__metaclass__ = type # New-style classes by default
+__metaclass__ = type # Use new-style classes by default
 
 class A: pass
 class B: pass
 class C(A, B): pass
-def defaultfoo(x, y): pass
+def default(x, y): return "default"
 @overloaded
-def foo(x, y): defaultfoo(x, y)
- at foo.register(A, B)
-def fooAB(x, y): pass
- at foo.register(A, C)
-def fooAC(A, C): pass
- at foo.register(B, A)
-def fooBA(x, y): pass
- at foo.register(C, B)
-def fooCB(x, y): pass
-foo(C(), B())
-foo(A(), C())
+def automatic(x, y): return default(x, y)
+automatic.__name__ = "automatic"
+ at automatic.register(A, B)
+def methodAB(x, y): return "AB"
+ at automatic.register(A, C)
+def methodAC(A, C): return "AC"
+ at automatic.register(B, A)
+def methodBA(x, y): return "BA"
+ at automatic.register(C, B)
+def methodCB(x, y): return "CB"
+
+# Quick test that it works correct
+assert automatic(C(), B()) == "CB"
+assert automatic(A(), C()) == "AC"
 try:
-    foo(C(), C())
+    automatic(C(), C())
 except TypeError:
     pass
 else:
     assert False
-timeit.test_func = foo
-timeit.test_arg1 = C()
-timeit.test_arg2 = B()
-t = timeit.Timer("test_func(test_arg1, test_arg2)")
-r = t.repeat(3, 10000)
-print "foo(C(), C())   %.3f" % min(r)
-def bar(x, y):
+
+def manual(x, y):
     if isinstance(x, C):
         if isinstance(y, B):
-            return fooCB(x, y)
+            return methodCB(x, y)
     if isinstance(x, B):
         if isinstance(y, A):
-            return fooBA(x, y)
+            return methodBA(x, y)
     if isinstance(x, A):
         if isinstance(y, C):
-            return fooAC(x, y)
+            return methodAC(x, y)
         if isinstance(y, B):
-            return fooAB(x, y)
-    return defaultfoo(x, y)
-timeit.test_func = bar
-r = t.repeat(3, 10000)
-print "bar(C(), C())   %.3f" % min(r)
-timeit.test_arg1 = A()
-timeit.test_arg2 = A()
-r = t.repeat(3, 10000)
-print "bar(A(), A())   %.3f" % min(r)
-class Bar:
-    def __init__(self):
-        self.cache = {}
-        for t1 in A, B, C:
-            for t2 in A, B, C:
-                self.cache[t1, t2] = defaultfoo
-    def __call__(self, x, y):
-        return defaultfoo(x, y)
-##        t = tuple(map(type, args))
-##        return self.cache[t](*args)
-timeit.test_func = Bar()
-r = t.repeat(3, 10000)
-print "Bar()(A(), A()) %.3f" % min(r)
+            return methodAB(x, y)
+    return default(x, y)
+
+def run(func, C1, C2):
+    timeit.test_func = func
+    timeit.test_arg1 = C1()
+    timeit.test_arg2 = C2()
+    t = timeit.Timer("test_func(test_arg1, test_arg2)")
+    result = int(round(min(t.repeat(3, 10000))*1000))
+    print "%s(%s(), %s()) - %3d msec" % (func.__name__,
+                                         C1.__name__,
+                                         C2.__name__,
+                                         result)
+
+print '-'*20
+run(manual, C, B)
+run(manual, A, A)
+run(manual, A, B)
+run(manual, A, C)
+
+print '-'*20
+run(automatic, C, B)
+run(automatic, A, A)
+run(automatic, A, B)
+run(automatic, A, C)


More information about the Python-checkins mailing list