Dispatch marches over registered signatures just once, so dispatch
runtime is proportional to the number of registered signatures, times the
length of the argument list, times some fuzzy function of the depth of
the inheritance DAG (since a recursive search _may_ be needed to figure
out whether a class inherits from another).
Ways to speed that up are more-or-less clear, although for simple cases
of MM dispatch they may cost more cycles than they save; putting back the
old class's test for an exact match would probably pay.
Whatever, I'm much more interested in seeing whether this style of
programming can be written readably in Python. Also wonder whether this
style can be written readably in Cecil <wink>: despite the formal
simplicity of Cecil's resolution rules as opposed to CLOS's, the rules
remain a puzzle for non-simple cases (e.g., try to guess what the grand
triply-nested loop at the end will print before running it <0.9 grin>).
complexity-is-in-the-nose-of-the-besniffer-ly y'rs - tim
Tim Peters tim@ksr.com
not speaking for Kendall Square Research Corp
class C: pass
class_type = type(C)
instance_type = type(C())
del C
tuple_type = type(())
anytype = 'any type'
def _type(x):
if x is anytype:
t = x
else:
t = type(x)
if t is instance_type:
t = x.__class__
return t
def sig( *values ):
return list2tuple( map(_type, values) )
def list2tuple(list):
tup = ()
for x in list: tup = tup + (x,)
return tup
LT, EQ, GT, UN = 'LT', 'EQ', 'GT', 'UN'
def cmp_types(t1, t2):
if t1 is t2: return EQ
if t1 is anytype: return LT
if t2 is anytype: return GT
if type(t1) is class_type is type(t2):
if isbase(t1, t2):
return LT
elif isbase(t2, t1):
return GT
return UN
def isbase(class1, class2):
# true iff class2 dervives at least in part from class1
bases = class2.__bases__
if class1 in bases: return 1
for base in bases:
if isbase(class1, base): return 1
return 0
def cmp_sigs(sig1, sig2):
if len(sig1) != len(sig2): return UN
guess = EQ
for i in range(len(sig1)):
t1, t2 = sig1[i], sig2[i]
compare = cmp_types(t1, t2)
if compare is UN:
return UN
if compare is not EQ:
# compare is LT or GT
if guess is EQ:
guess = compare
elif guess is not compare:
return UN
return guess
class Overload:
def __init__(self):
self.sig2func = {}
def register(self, func, sig_or_sig_list):
if type(sig_or_sig_list) is tuple_type:
sig_or_sig_list = [sig_or_sig_list]
for sig in sig_or_sig_list:
self.sig2func[sig] = func
def call(self, *args):
signature = apply(sig, args)
winner = None
for msig in self.sig2func.keys():
if cmp_sigs(msig, signature) in (LT, EQ):
if winner is None:
winner = msig
else:
compare = cmp_sigs(msig, winner)
if compare is LT:
pass
elif compare is GT:
winner = msig
elif compare is EQ:
raise TypeError, \
('surprise!', signature, msig, winner)
else: # UN
raise TypeError, \
('Ambiguous dispatch',
('sig', signature),
('method1', msig),
('method2', winner) )
if winner is None:
raise TypeError, 'no method known for ' + `signature`
func = self.sig2func[winner]
return apply(func, args)
class A: pass
class AB(A): pass
class AC(A): pass
class ABC(AB,AC): pass
a = A()
ab = AB()
ac = AC()
abc = ABC()
m1 = Overload()
m2 = Overload()
m3 = Overload()
m1.register(lambda x: 'm1@A', sig(a))
m1.register(lambda x: 'm1@ABC', sig(abc))
print m1.call(a) # m1@A
print m1.call(ab) # m1@A
print m1.call(ac) # m1@A
print m1.call(abc) # m1@ABC
m2.register(lambda x: 'm2@A', sig(a))
m2.register(lambda x: 'm2@AC', sig(ac))
print m2.call(a) # m2@A
print m2.call(ab) # m2@A
print m2.call(ac) # m2@AC
print m2.call(abc) # m2@AC
m3.register(lambda x: 'm3@AB', sig(ab))
m3.register(lambda x: 'm3@AC', sig(ac))
import sys
try: print m3.call(a) # unknown
except: print sys.exc_type, sys.exc_value
print m3.call(ab) # m3@AB
print m3.call(ac) # m3@AC
try: print m3.call(abc) # ambiguous
except: print sys.exc_type, sys.exc_value
class X: pass
class XY(X): pass
class XZ(X): pass
class XYZ(XY,XZ): pass
x = X()
xy = XY()
xz = XZ()
xyz = XYZ()
m1.register(lambda x,y: 'm1@A@X', sig(a,x))
m1.register(lambda x,y: 'm1@A@XZ', sig(a,xz))
print m1.call(abc,xyz) # m1@A@XZ
m2.register(lambda x,y: 'm2@A@any', sig(a,anytype))
m2.register(lambda x,y: 'm2@AB@any', sig(ab,anytype))
print m2.call(abc,xyz) # m2@AB@any
m3.register(lambda x,y: 'm3@AB@any', sig(ab,anytype))
m3.register(lambda x,y: 'm3@AB@XY', sig(ab,xy))
print m3.call(abc,xyz) # m3@AB@XY
m4 = Overload()
m4.register(lambda x,y: 'm4@ABC@X', sig(abc,x))
try: print m4.call(ab,xy) # unknown
except: print sys.exc_type, sys.exc_value
m5 = Overload()
m5.register(lambda x,y: 'm5@A@XZ', sig(a,xz))
m5.register(lambda x,y: 'm5@AB@X', sig(ab,x))
try: print m5.call(abc,xyz) # ambiguous
except: print sys.exc_type, sys.exc_value
m6 = Overload()
m6.register(lambda x,y: 'm6@AC@any', sig(ac,anytype))
m6.register(lambda x,y: 'm6@any@XYZ', sig(anytype,xyz))
try: print m6.call(abc,xyz) # ambiguous
except: print sys.exc_type, sys.exc_value
for m in 'm1', 'm2', 'm3', 'm4', 'm5', 'm6':
for arg1 in 'a', 'ab', 'ac', 'abc':
for arg2 in 'x', 'xy', 'xz', 'xyz':
print '%s(%s,%s) ->' % (m,arg1,arg2),
try:
print eval( '%s.call(%s,%s)' % (m,arg1,arg2) )
except:
print sys.exc_type, sys.exc_value
# end of module