[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