A polyglot's guide to multiple dispatch - part 3

This is part 3 in the series of articles on multiple dispatch. Part 1 introduced the problem and discussed the issues surrounding it, along with a couple of possible solutions in C++. Part 2 revisited multiple dispatch in Python, implementing a couple of variations. In this part, I'm going back to the roots of multiple dispatch - Common Lisp - one of the first mainstream programming languages to introduce multi-methods and an OOP system based on multiple dispatch at its core.

It's strange to leave the language where multiple dispatch is actually built-in to the third article in the series; however, as Common Lisp is not exactly the most widely used language these days, I wanted to start with languages folks are more familiar with. Besides, my hope is that by now readers of the series have a much better understanding and appreciation of multiple dispatch, and it should be interesting to see a very powerful and feature-full version of it directly supported by a language.

The lessons from Common Lisp weren't lost on some modern language designers, and you can find variations of its multi-methods in 21st-century languages. In the next part of the series I'll show how multiple dispatch works in Clojure - a modern Lisp dialect [1].

A bit of history

Young programmers getting started in the 2010s can be forgiven to think that object-oriented programming (OOP) the way it's done in C++, Java and Ruby is how it was always done. But in fact, while C++ appeared in the early 80s and Java in 1995, OOP first appeared in the 1960s in specialized languages like Simula, and then Smalltalk in 1972. Smalltalk itself was influenced by Lisp in many aspects, and Lisp hackers didn't wait long to borrow back OOP ideas from Smalltalk; the first beginnings of OOP libraries in Lisp [2] started popping up in the mid 70s, years before a PhD student from Denmark started tinkering with bolting classes on top of C. That was Bjarne Stroustrup, of course, and C++ saw first light in 1982. Meanwhile, the OOP features in Lisp already started to fragment into multiple competing approaches (everything in the Lisp world fragments, it's an unwritten law). It was then (before 1980) when the initial ideas of what we now know as CLOS - the Common Lisp Object System - started appearing, with multi-methods, custom method combinations, the meta-object protocol [3] and so on.

There's a lesson in this long historical preamble. OOP as it manifests itself in Common Lisp may seem foreign if all you're familiar with is languages like C++ and Java. However, don't let that fool you. OOP is not a single recipe on how to do things - it's a concept, which was realized in many different ways in the past, in different languages. In fact, if you spend a bit of time learning it - you'll quickly realize that CLOS's OOP is a superset of the single-dispatch OOP in C++ and Java, and is much more powerful and general overall.

Common Lisp and CLOS

Common Lisp is the result of a Babelian consolidation of multiple Lisp implementations that happened in the 1980s, with an ANSI standard that appeared in the early 1990s. From the start, CLOS (the Common Lisp Object System) was part of the Common Lisp standard, itself consolidating two earlier attempts at OOP in Lisp - Flavors and LOOPS.

All in all, CLOS is a very powerful OOP system with many advanced features that don't exist in today's mainstream languages. It's well worth learning about - in this humble article I only provide a small taste. I listed some links and references to materials about CLOS I personally liked at the end of the post.

Polymorphic dispatch in CLOS

From the very start CLOS's idea of runtime polymorphism was based on multiple, rather than single dispatch. Let's see why this made sense.

Here's a sample method in C++:

class Person {
public:
    void Frobnicate(Record* r, Spreadsheet* s) {
        // 'this' points to a Person.
        // 'r' points to a Record, 's' to a Spreadsheet.
    }
};

And this is how we may call it:

Person person;
Record record;
Spreadsheet spreadsheet;
// ...
person.Frobnicate(&record, &spreadsheet)     // CALL

The call line marked with CALL is the most interesting here. Note how there are two distinct roles in this call: a special position is reserved to person, which is the object the method is invoked on. It goes before the dot. Method arguments go inside the function call syntax. Within the implementation of Frobnicate, the Person instance is known as this; the arguments are declared with the usual function parameter bindings. This is frequently called "message passing" - we're sending a Frobnicate message to a Person object with Record and Spreadsheet arguments.

In Python this would be very similar, except that the method implementation has a self parameter as a more explicit reference to the object the method is invoked on. Thus most of the widespread OOP languages these days have this special slot for one of the arguments - the object we invoke the method on. Note that this is distinct syntax from regular function calls.

In Lisp, such an approach goes against the philosophy of the language, where uniform syntax is paramount. In Lisp, all the main abstraction techniques have the same syntax, called "a form":

(foo bar baz)

The first position in the form defines the meaning of the form. It may be a function call, a macro invocation, or a special form (such as if); whatever it is, the syntax is uniform. This is one of the greatest strengths of Lisp.

Back to dispatch, though. Since Lisp wants to preserve its uniform invocation syntax, a special syntax for calling methods on symbols won't do. Therefore, what CLOS has is:

(defclass Person () ())

(defmethod frobnicate ((p Person) record spreadsheet)
  (format t "~a ~a ~a~&" (type-of p) (type-of record) (type-of spreadsheet)))

The syntax is different from what we're used to. The method frobnicate is defined outside the class Person. However, the special parameter form (p Person) in the definition of frobnicate makes sure that this method is only called when the first argument is indeed a Person. If we had another type with a frobnicate method, we'd define that method as:

(defclass Asteroid () ())

(defmethod frobnicate ((a Asteroid) velocity size)
  ; do stuff
  )

Then, at runtime:

(frobnicate a-person his-record big-spreadsheet)

Would be routed to the former method, while:

(frobnicate an-asteroid very-fast pretty-small)

Would be routed to the latter. As you can see, this is your standard single-dispatch runtime polymoprhism (the dispatch indeed happens at runtime - Common Lisp is dynamically typed, like Python), but based on a uniform Lisp-y syntax where the first parameter (the actual class instance) doesn't have a special position; besides being the first, of course.

It shouldn't be a huge leap of imagination to go from this to multi-methods. Because, you see, if the class instance has no special syntax dedicated to it, who says it's special at all. Can't we dispatch upon the second argument instead? Something like:

(defmethod interplex (solution (p Person))
  (format t "~a ~a~&" (type-of solution) (type-of p)))

Here, the dispatch happens upon the runtime type of the second argument, so even the position in the call is not special. What is special about Person as far as these methods are concerned? Well, nothing really.

This is where CLOS turns OOP on its head, at least to some degree. In C++, Java and kin, methods are properties of classes; each class has its set of methods. In CLOS, this works differently. Classes and methods are orthogonal. Methods do not belong to classes (as you may have guessed by now, if only from the fact that methods are defined outside of classes entirely, rather than being nested in them). Classes do not belong to methods. Methods are simply functions that are invoked when one or more of their argument matches some runtime criteria - most often type.

So what prevents methods to dispatch based on the types of more than one parameter? Nothing indeed.

CLOS and multi-methods

Without further ado, here is a Common Lisp implementation of the shape intersection problem we've been using throughout the series:

(defclass Shape () ())
(defclass Rectangle (Shape) ())
(defclass Ellipse (Shape) ())
(defclass Triangle (Shape) ())

; Having a defgeneric is not strictly necessary in CLOS. The code would
; work without this definition. However, this is good practice as it gives
; us a natural place to document the generic interface methods are expected
; to implement. It also lets us add a default handler with a meaningful
; error message, if no suitable method was found in some case.
(defgeneric intersect (x y)
  (:documentation "Shape intersection")
  (:method (x y)
    (error "Cannot interesect these shapes")))

(defmethod intersect ((r Rectangle) (e Ellipse))
  (format t "Rectangle x Ellipse [names r=~a, e=~a]~&"
          (type-of r) (type-of e)))

(defmethod intersect ((r1 Rectangle) (r2 Rectangle))
  (format t "Rectangle x Rectangle [names r1=~a, r2=~a]~&"
          (type-of r1) (type-of r2)))

(defmethod intersect ((r Rectangle) (s Shape))
  (format t "Rectangle x Shape [names r=~a, s=~a]~&"
          (type-of r) (type-of s)))

A few things to note here:

  • Most importantly: intersect is specialized by the types of both its parameters, and a different method is invoked based on the actual combination of runtime types passed in. We'll see this in action soon.
  • Inheritance is used. defclass lets us list the superclasses of any class after its name, and here Rectangle, Ellipse, and Triangle are all set to inherit from Shape.

Let's create some objects and do some intersect calls:

;; Create some objects
(setf r1 (make-instance 'Rectangle))
(setf r2 (make-instance 'Rectangle))
(setf e1 (make-instance 'Ellipse))
(setf t1 (make-instance 'Triangle))

;; Do intersects
(intersect r1 e1)
(intersect r1 r2)
(intersect r1 t1)

We get:

Rectangle x Ellipse [names r=RECTANGLE, e=ELLIPSE]
Rectangle x Rectangle [names r1=RECTANGLE, r2=RECTANGLE]
Rectangle x Shape [names r=RECTANGLE, s=TRIANGLE]

The dispatch works as expected. Moreover, base-class defaults work out of the box - we didn't define a method for Rectangle x Triangle, so the method for Rectangle x Shape was invoked in the last call to intersect [4].

Multiple dispatch is supported natively in CLOS. Moreover, as the earlier discussion hopefully highlights, multiple dispatch is not just a variation bolted onto the system (like our @multi decorators in part 2), but it is the way polymorphic dispatch works in the language. Single dispatch is just a special case of multiple dispatch.

CLOS methods are just functions

As I've mentioned before, CLOS methods are just functions. They are not special in the same way C++ methods are special (bound to objects). This means we can use them just as we use any other function.

For example, we can map them onto objects, and it will work as expected:

(mapcar #'intersect (list r1 r2 e1) (list r2 e1 t1))

Had intersect been special as it is in C++, it wouldn't be as easy. We'd need something like std::bind to "bind" it to an object instance first. In CLOS, we don't care. We can have a higher-order function that takes a function and applies it to pairs of objects:

(defun domap (func lst1 lst2)
  (mapcar func lst1 lst2))

We can now invoke domap with either a "regular" function or a method, using the same syntax:

;; invoke cons on pairs of objects
(domap #'cons (list r1 r2 e1) (list r2 e1 t1))

;; invoke intersect on pairs of objects
(domap #'intersect (list r1 r2 e1) (list r2 e1 t1))

I'm showing this example to stress that CLOS methods are just functions. Decoupling class declarations from methods that act upon these classes lets us be much more flexible in the usage of these methods. Since Lisp is all about uniform syntax and functional programming, the result is an object-oriented system elegantly blended into the whole.

Variations on a theme

The sample above demonstrates how CLOS gives us powerful multiple-dispatch capabilities right out of the box. As it turns out, this is just the tip of the iceberg, as CLOS supports many more features. I want to give a short taste of a few here - for more information I recommend doing some reading on CLOS.

Let's start with value-based dispatch. So far we've seen how a method can speficy which type of argument it specializes on. We can also specialize methods by the value of an argument. Here's a silly example based on the same world of shapes:

(defgeneric scale (shape factor)
  (:documentation "Scale a shape by a factor"))

(defmethod scale ((shape Shape) factor)
  (format t "Scale shape by ~a~&" factor))

(defmethod scale ((shape Shape) (factor (eql 0)))
  (format t "Scale shape by a zero~&"))

Now given some s - an instance of Shape, the call (scale s 42) will dispatch to the first method, while the call (scale s 0) will dispatch to the second method. Sure, we could have achieved the same by having an if condition in the beginning of scale, and sometimes that's what we need. But eql-based dispatch lets us decouple such code and express our intent more directly. An ad-hoc if-based solution would bury the special case somewhere in the method body, while the approach shown above makes it explicit and visible that a 0 gets special treatment.

CLOS also has the concept of method combinations, which manifects in several ways. For example, with each method we can have a variation marked with :before that can serve as a pre-processor:

(defclass Shape () ())
(defclass Rectangle (Shape) ())
(defclass Ellipse (Shape) ())
(defclass Triangle (Shape) ())

(defgeneric scale (shape factor)
  (:documentation "Scale a shape by a factor"))

(defmethod scale ((r Rectangle) factor)
  (format t "Scale Rectangle by ~a~&" factor))

(defmethod scale ((e Ellipse) factor)
  (format t "Scale Ellipse by ~a~&" factor))

(defmethod scale :before ((s Shape) factor)
  (format t ":before preprocessor on ~a scaled by ~a~&" (type-of s) factor))

Now if we create a couple of shapes and scale them:

(setf r (make-instance 'Rectangle))
(setf e (make-instance 'Ellipse))

(scale r 20)
(scale e 30)

We get:

:before preprocessor on RECTANGLE scaled by 20
Scale Rectangle by 20
:before preprocessor on ELLIPSE scaled by 30
Scale Ellipse by 30

The dispatches of scale happened as we expect by now; additionally, the scale method marked with :before was invoked in both cases before the actual method.

CLOS has :before, :after and :around markings; moreover, we can specify an arbitrary number of preprocessors, postprocessors or "around"-processors and even control their exact invocation order if we're so inclined. There's a huge amount of flexibility here.

But there's more. As we've seen so far, the most specific dispatch method is used it it exists; if it doesn't, the base class's dispatch is tried, and so on. This plays well with our intuition from other OOP languages. But in CLOS, there are powerful ways to customize this flow. What really happens when a method is called is that a list of functions to call is built, including all the :before (and others) methods, as well as the actual primary methods [5], from most to least specific. We can actually control how these invocations happen.

Here's an example:

(defgeneric scale (shape factor)
  (:documentation "Scale a shape by a factor"))

(defmethod scale ((s Shape) factor)
  (format t "Scale Shape by ~a~&" factor))

(defmethod scale ((r Rectangle) factor)
  (format t "Scale Rectangle by ~a~&" factor)
  (call-next-method))

(setf r (make-instance 'Rectangle))

(scale r 20)

Now (scale r 20) prints:

Scale Rectangle by 20
Scale Shape by 20

This is not unlike super calls in Python, or base-class method calls in C++. But in CLOS, the very nature of how multiple viable methods are combined can be customized.

The default combination of primary methods is, as we've seen above, the familiar approach of OOP languages with inheritance support: dispatch to the most specific method and if it doesn't exist try to dispatch with the base class, and so on. Method combinations is a CLOS concept that lets us do it differently. There are a number of standard method combinations supported by CLOS, and custom ones can be defined with define-method-combination. Let's see a standard one for an example.

We'll start with a simple demonstration of the regular dispatch again:

(defgeneric getstuff (shape))

(defmethod getstuff ((s Shape))
  '(shape stuff))

(defmethod getstuff ((r Rectangle))
  '(rectangle stuff))

If we call (getstuff (make-instance 'Rectangle)) we get (rectangle stuff). If we call (getstuff (make-instance 'Shape)) we get (shape stuff); so far so good. But now, let's use the list method combination instead:

(defgeneric getstuff (shape)
  (:method-combination list))

(defmethod getstuff list ((s Shape))
  '(shape stuff))

(defmethod getstuff list ((r Rectangle))
  '(rectangle stuff))

What this means is that when getstuff is invoked and CLOS finds all the viable methods, instead of calling the most specific one (and letting it call the others with call-next-method if it desires), it calls all of them, combining their results with the list function.

Now, calling (getstuff (make-instance 'Rectangle)) produces the list ((rectangle stuff) (shape stuff)). Bizarre? Maybe. Useful? Maybe.

If you're now thinking "this is crazy, those Lisp people have completely jumped the shark", I can't say I entirely disagree. If you're thinking "wow, this is immensely cool" I can't say I disagree either :-) These features are as power as you can get - all implemented as a library - as a set of macros and functions in standard Common Lisp. This is the power of Lisp, friends, and herein lies its beauty... and its biggest pitfall.

IMHO these features are too advanced to be useful in 99% of the cases. It's way too easy to produce write-only code with them. Besides, even though Lisp is a multi-paradigm language and can do OOP when OOP is due, it's not idiomatic to write OOP code in Lisp since the other paradigms it provides are often better suited for the task. For the few applications where OOP really shines, the capabilities are there - but even then, I'd stick to the basics - at least in realistic multi-person code bases, leaving the power-sauce to pet projects and exploratory blog posts.

This is a good place for a quote from Paul Graham's "On Lisp":

With the addition of CLOS, Common Lisp has become the most powerful object-oriented language in widespread use. Ironically, it is also the language in which object-oriented programming is least necessary.

CLOS - yay or nay?

Let's not forget the goal of this series - explore multiple dispatch and its use and implementation in different languages. In this aspect, Common Lisp and CLOS truly shine, I think. Leaving all the crazy features aside, the basic form of OOP in CLOS relies on multiple dispatch at its very core, and lets us write object-oriented code while still remaining fairly Lisp-y.

It's not impossible to reproduce CLOS-like features in languages like Python, but it takes effort. Moreover, Python and other non-Lisp languages miss the biggest trait that makes CLOS possible - uniform syntax.

As for the power-features of CLOS, while I think they provide a sobering perspective to judge the OOP capabilities of C++, Java and Python by, I personally would be wary about using them. The Lisp ideal is growing your language towards the problem you're solving; in other words, construct an embedded DSL on top of Lisp for solving the problem. CLOS is just another example of that, where extremely powerful - to the point of obscurity - features let us really custom-tailor the language to a specific problem when necessary.

Looking forward

Common Lisp is an interesting and, in many ways, inspiring language. However, I'll admit it's not very popular or well known nowadays, and it doesn't feel right ending the series with a language "from the past". Therefore, the upcoming part 4 in the series will focus on Clojure - a modern dialect of Lisp that's become fairly popular in the last few years.

For comments, please send me an email.