Advanced OOP: Multimethods

by David Mertz
05/29/2003

Introduction

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.

With my multimethods module, Python can be extended to allow multiple dispatch. In Perl, Class::Multimethods serves 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.

Related Reading Python in a Nutshell By Alex Martelli

For example, there are many functions that operate on "file-like" objects, where file-like is defined simply by supporting a few methods: read(), readlines(), and maybe seek(). A function like read_app_data() might 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 function call src.read(). Each object type is interchangeable from the point of view of how it functions within read_app_data().

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 src.

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 protocol-compatible classes Foo and Bar as follows (in pseudo-Python):

Example 2: Foo and Bar implement the meth() method

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 x and 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 x a Foo or a Bar?) and, second, by procedural switch. Moreover, the switches within the definitions of Foo.meth() and Bar.meth() are largely equivalent. Polymorphism--of the single-dispatch variety--only goes half way.

Completing Polymorphism

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 Foo and Bar

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 multimethods. To enable multiple dispatch, simply include the following line in your application:

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 rule, a TypeError is raised. The initialization of x_with_y() with a fallback (object, object) pattern is not necessary if you simply want undefined cases to raise an exception.

Each (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 equivalent:

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 x and 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.

Improving Inheritance

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