Re: Multi-methods

Tim Peters (tim@ksr.com)
Sat, 11 Jun 94 16:42:39 -0400

Attached is an extension of the "Overload" class that resolves MM
dispatch using Cecil-like rules. The _type notion got extended to
include an "anytype" (Cecil's "top", I guess); function cmp_types
compares two _types and returns one of {less, equal, greater, unordered},
where anytype is equal to itself & less than all other types, built-in
types are unordered, and class instances compare based on the inheritance
relation applied to their classes; function cmp_sigs does much the same
for _type signature tuples; MM dispatch finds the "greatest" registered
signature <= the argument signature, and complains if that's not well-
defined. The tests reproduce the examples in Chambers. Coercions aren't
addressed here.

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