Advanced OOP: Multimethodsby David Mertz
This article continues a review of advanced object-oriented programming concepts. In this installment I examine multiple dispatch, which is also called multimethods. Most object oriented languages--including Python, Perl, Ruby, C++, and Java--are intellectually descended from Smalltalk's idea of message passing, albeit with syntax and semantics only loosely related to this source. Another option, however, is to implement polymorphism in terms of generic functions; this has the advantage of enabling code dispatch based on the types of multiple objects. In contrast, the native method calling style of common OOP languages only uses a single object for dispatch switching. Don't fear: this article will explain what all this means and why you should care.
multimethods module, Python can be extended to
allow multiple dispatch. In Perl,
the same purpose. Several other languages, including Java, Ruby, etc.,
have libraries or extensions to enable multiple dispatch. Common Lisp
Object System (CLOS) and Dylan contain multiple dispatch at their heart.
This article focuses on my Python implementation, but the concepts
themselves are language neutral.
Polymorphism as a Dispatch Mechanism
Object oriented programming gains much of its versatility through polymorphism. Objects of different kinds can behave in similar ways, given the right contexts. Perhaps the most common application of polymorphism is in creating a family of objects that follow a common protocol. In Python, this is usually a matter of ad hoc polymorphism. In other languages, formal interfaces might be declared or these families might share a common ancestor.
For example, there are many functions that operate on "file-like"
objects, where file-like is defined simply by supporting a few methods:
readlines(), and maybe
seek(). A function like
take an argument
src. When we call this function, we can
pass it a local file, a
urllib object, a
cStringIO object, or some custom object that lets the
src.read(). Each object type is interchangeable
from the point of view of how it functions within
Let us step back a bit to think about what is really happening here. At heart, what we are concerned about is choosing the right code path to execute within a context. Old-fashioned procedural code can make equivalent decisions; OOP merely adds some elegance. For example, a fragment of procedural (pseudo-)code might look like:
Example 1: procedural choice of code paths on object type
...bind 'src' in some manner... if <<src is a file object>>: read_from_file(src) elif <<src is a urllib object>>: read_from_url(src) elif <<src is a stringio object>>: read_from_stringio(src) ...etc...
By arranging for objects of different types to implement common
methods, we move the dispatch decision into the objects and out
of an explicit conditional block. A given
src object knows
what block of code it needs to call by looking through its inheritance
tree. There is still an implicit switch going on, but it is on the type
of the object
However, even though the type of
src directs the choice
of a relevant method code block, procedural switching is often simply
pushed into the method bodies of classes. For example we might implement
follows (in pseudo-Python):
Bar implement the
class Foo: def meth(self, arg): if <<arg is a Foo>>: ...FooFoo code block... elif <<arg is a Bar>>: ...FooBar code block... class Bar: def meth(self, arg): if <<arg is a Foo>>: ...BarFoo code block... elif <<arg is a Bar>>: ...BarBar code block... # Function to use Foo/Bar single-dispatch polymorphism def x_with_y(x, y): if <<x is Foo or Bar>> and <<y is Foo or Bar>>: x.meth(y) else: raise TypeError,"x, y must be either Foo's or Bar's"
There are five distinct code paths/blocks that might get executed when
x_with_y() is called. If the types of
y are not suitable, an exception is raised (you could also do
something different, of course). Otherwise, the code path is chosen,
first, by a polymorphic dispatch (is
Foo or a
Bar?) and, second, by
procedural switch. Moreover, the switches within the definitions of
Bar.meth() are largely
equivalent. Polymorphism--of the single-dispatch variety--only goes half
In single-dispatch polymorphism, the object that "owns" a method is singled out. Syntactically, it is singled out in Python by being named before the dot--everything following the dot, method name, and left parenthesis is just an argument. Semantically, the object is also special in using an inheritance tree for method resolution.
What if we did not treat just one object in a special fashion, but allowed every object involved in a code block to help choose the correct code path? For example, we might express our five-way switch in a more symmetric fashion:
Example 3: multiple dispatch on
x_with_y = Dispatch([((object, object), <<exception block>>)]) x_with_y.add_rule((Foo,Foo), <<FooFoo block>>) x_with_y.add_rule((Foo,Bar), <<FooBar block>>) x_with_y.add_rule((Bar,Foo), <<BarFoo block>>) x_with_y.add_rule((Bar,Bar), <<BarBar block>>) #...call the function x_with_y() using some arguments... x_with_y(something, otherthing)
I think this symmetry in polymorphic dispatch on multiple arguments is much more elegant than the prior style. As well, the style helps document the equal role of the two objects involved in determining the appropriate code path to take.
Standard Python does not let you configure this type of multiple
dispatch; but fortunately, you can do so using the module
To enable multiple dispatch, simply include the following line in your
from multimethods import Dispatch
An instance of
Dispatch is a callable object and can be
configured with as many rules as you wish. The method
Dispatch.remove_rule() can be used to delete rules as well,
which makes multiple dispatch using
multimethods a bit more
dynamic than in a static class hierarchy. Note also that a
Dispatch instance can accept a variable number of arguments.
Matching is done first on number of arguments, then on their types. If a
Dispatch instance is called with any pattern not defined in a
TypeError is raised. The initialization of
x_with_y() with a fallback
pattern is not necessary if you simply want undefined cases to raise an
(pattern, function) tuple that is listed in the
initialization call to
Dispatch is simply passed on to the
add_rule() method. When a function is called from the
dispatcher, it is passed the arguments used in the call to the dispatcher;
you need to make sure the function you use can accept the number of
arguments it is matched against. For example, the following are
Example 4 – explicit and dispatched function call
# Define function, classes, objects def func(a,b): print "The X is", a, "the Y is", b class X(object): pass class Y(object): pass x, y = X(), Y() # Explicit call to func with args func(x,y) # Dispatched call to func on args from multimethods import Dispatch dispatch = Dispatch() dispatch.add_rule((X,Y), func) dispatch(x,y) # resolves to 'func(x,y)'
Obviously, if you already know the types of
y at design time, the machinery of setting up a dispatcher is
just overhead. But the same limitation is true of polymorphism: it is
only helpful when you cannot constrain an object to a single type for
every execution path.
Multiple dispatch does not merely generalize polymorphism, it also provides a more flexible alternative to inheritance in some contexts. An example is illustrative here. Suppose you are programming a drawing or CAD program that deals with a variety of shapes. In particular, you want to be able to combine two shapes in a way that depends on both of the shapes involved. Moreover, the collection of shapes to consider will be extended by derived applications or plugins. Extending a collection of shape classes provides a clumsy technique for enhancement, e.g.:
Example 5: inheritance for capability extension
#-- Base classes class Circle(Shape): def combine_with_circle(self, circle): ... def combine_with_square(self, square): ... class Square(Shape): def combine_with_circle(self, circle): ... def combine_with_square(self, square): ... #-- (later) Enhancing base with triangle shape class Triangle(Shape): def combine_with_circle(self, circle): ... def combine_with_square(self, square): ... def combine_with_triangle(self, triangle): ... class NewCircle(Circle): def combine_with_triangle(self, triangle): ... class NewSquare(Square): def combine_with_triangle(self, triangle): ... #-- Can optionally use original class names in new context Circle, Square = NewCircle, NewSquare #-- Use the classes in application c, t, s = Circle(...), Triangle(...), Square(...) newshape = s.combine_with_circle(c) # combine 'x' of unknown type with 't' if isinstance(x, Triangle): new2 = t.combine_with_triangle(x) elif isinstance(x, Square): new2 = t.combine_with_square(x) elif isinstance(x, Circle): new2 = t.combine_with_circle(x)
Each existing shape class has to add capabilities in a descendant, which runs into combinatorial complexities, and maintenance difficulties. A multiple dispatch technique is more straightforward:
Example 6: multimethods for capability extension
#-- Base rules (stipulate combination is order independent) class Circle(Shape): pass class Square(Shape): pass def circle_w_square(circle, square): ... def circle_w_circle(circle, circle): ... def square_w_square(square, square): ... combine = Dispatch() combine.add_rule((Circle, Square), circle_w_square) combine.add_rule((Circle, Circle), circle_w_circle) combine.add_rule((Square, Square), square_w_square) combine.add_rule((Square, Circle), lambda s,c: circle_w_square(c,s)) #-- Enhancing base with triangle shape class Triangle(Shape): pass def triangle_with_circle(triangle, circle): ... def triangle_with_square(triangle, square): ... combine.add_rule((Triangle,Circle), triangle_w_circle) combine.add_rule((Triangle,Square), triangle_w_square) combine.add_rule((Circle,Triangle), lambda c,t: triangle_w_circle(t,c)) combine.add_rule((Square,Triangle), lambda s,t: triangle_w_square(t,s)) #-- Use the rules in application c, t, s = Circle(...), Triangle(...), Square(...) newshape = combine(c, t) # combine 'x' of unknown type with 't' new2 = combine(t, x)
The advantage here of the multiple dispatch style is in the
seamlessness with which you can combine shapes of unknown types. Rather
than revert back to explicit (and lengthy) conditional blocks, the rule
definitions take care of matters automatically. Even better, all
combining is done with a single
combine() callable, rather
than with a menagerie of distinct combinations methods.
David Mertz , being a sort of Foucauldian Berkeley, believes, esse est denunte.
Return to the Python DevCenter
Showing messages 1 through 5 of 5.
Languages and matching rules
2003-07-08 09:38:58 cbthiess [View]
2003-07-08 09:35:03 cbthiess [View]
Not sure where one would use this?
2003-06-17 23:24:30 anonymous2 [View]
2003-06-05 07:26:25 larsga [View]
for which reason?
2003-06-03 04:10:45 anonymous2 [View]