Open Multi-Methods for C++11: Part 1 - The Case for Open Multi-Methods

Introduction

This article is the first in a series about open multi-methods for C++11. In this installment, I will explain what they are, how they fit in the object-oriented paradigm, and make controversial statements.

Subsequent articles will present a new library that implements open multi-methods, using the facilities provided by C++11 (in particular, variadic templates). The library's salient features are: fast, constant time dispatch using compact tables; arbitrary number of virtual and non virtual arguments; access to the next most specific specialization; and support for shared libraries and dynamic loading. The series will conclude with an in-depth presentation of the internals of the library.

If you are impatient, you can grab the code from GitHub and read the documentation.

Polymorphism and Poly-polymorphism

Object-oriented programming (OOP) rests on three pillars: encapsulation, inheritance and polymorphism. The latter is what makes the difference between object-based programming and object-oriented programming.

I used to teach C++ classes when OOP was still a new thing. I explained polymorphism in this way: if you kick a dog, it barks; if you kick a cat, it meows. Each animal reacts according to its nature. Indeed, when you think about it, that's all there is to that big Greek sounding word: do the right thing.

From now on, I will use a language neutral notation to represent situations like the dog and cat example:

kick(dog) -> bow wow wow
kick(cat) -> meow

At this point, C++ programmers are possibly raising eyebrows; Java programmers may be snorting. You probably expected something like dog.kick(), didn't you? I will go back to this later (Lisp programmers see nothing strange happening here).

This sort of behavior is readily implemented in C++, Java or Smalltalk: we call a virtual function or a method on an object, or send a message to an object. What's in a name? It works nice and well: it selects the "right" behavior given the same "stimulus".

There are times, however, when "the right thing" to do depends on more than one object. To carry on with the zoological metaphor, consider the encounter of two animals:

encounter(animal, animal) -> ignore
encounter(cow, wolf)      -> run
encounter(wolf, cow)      -> hunt
encounter(wolf, wolf)     -> wag tail

If you find this example silly, here is a more serious one. Imagine that you are building a matrix library. Matrices fall into different categories: ordinary, square, symmetrical, diagonal, sparse... You will probably use different representations for each matrix subtype. Certainly, you want to use specialized algorithms for addition too. And which algorithm is the "right" one depends on the subtypes of both operands:

add(matrix, matrix)       -> add all elements one by one
add(diagonal, diagonal)   -> just add the two diagonals
add(matrix, diagonal)     -> no need to add all the zeroes

Now if you are programming in C++, the big question is: are the matrix subtypes known at compile time? If they are, you can use the wonderfully expressive C++ template mechanism. You define a template for the general case (addition of two plain matrices) and then create specializations to handle the more specific cases. Something in the spirit of:

template<class Matrix1, class Matrix2>
matrix operator +(const Matrix1& m1, const Matrix2& m2) {
// add elements one by one; return an ordinary matrix
}
  
template<>
diagonal_matrix operator +(const diagonal_matrix& m1, const diagonal_matrix& m2) {
// just add the two diagonals; return a diagonal matrix
}

template<class Matrix1>
matrix operator +(const Matrix1& m1, const diagonal_matrix& m2) {
// just add m2's diagonal; return an ordinary matrix
}

// etc

This pseudo-code is naive, but it is meant to illustrate the principle. Anyway, if you know the matrices' subtypes at compile time, you really should make use of the information. The result will be a matrix library that will give you speed that languages like Java, C# and others just can't deliver.

Note that what is happening here is polymorphism, even if no virtual function calls are involved: the "right thing" is done depending on the arguments' types. It happens at compile time, hence C++ template specialization is often described as "static polymorphism". C++ has another form of static polymorphism: overloaded functions, which obey pretty much the same rules as template specialization. Thus the idea of selecting a behavior depending on multiple arguments should already be familiar to C++ programmers.

What if the subtypes are not known at compile time? Say, you are implementing the next Matlab. You don't know in advance what the two operands will be, exactly. In this case, you can select the right behavior on the basis of one argument only. The only tool left in your C++ toolbox is the virtual function. Aaah, when you only have a hammer...

What is missing from C++, but not from languages like Lisp and its many derivatives (Dylan and Clojure being the two popular lispoids these days), is the capacity to perform the multi-polymorphism trick at run time.

In situations like those described above, the C++ programmer is not without resources. The most popular hacks are multiple dispatch and type switches. Either way, the solution will not look much like the approach based on templates, and by far it will not "feel" as natural. There are also more audacious ways that involve extensions to the language, like Cmm - C++ with multi-methods. Finally, it is not Bjarne Stroustrup's fault if C++ is still lacking native support for multi-methods, as he has been arguing for their inclusion in the language for years. In 2005, he co-authored a paper that outlines an implementation of C++ multi-methods.

If, however, you don't want to wait until Stroustrup convinces his fellow committee members, nor use some experimental compiler, nor go to through the hoops of multiple dispatch, nor the ugliness of type switches, here is the good news: it is possible to implement a solution, within C++11, that imposes a fairly light syntax burden and delivers performance, both in terms of speed and memory. It will be presented in following articles. I am not done with generalities just yet.

Are You Receiving Me?

Object-oriented programming is a fifty year old idea, even though most people don't realize it, but it was only at the end of the eighties that it was brought into mainstream. People of my generation (I am myself kicking 50) certainly remember the issue of Byte dedicated to OOP. The language through which the new paradigm was championed to the masses was Smalltalk. It is pretty much alive today. Smalltalk's model of object-oriented programming is that of objects sending and receiving messages, each object responding to a message according to its nature, sometimes returning values, sometimes altering its state. Smalltalk takes the metaphor of message passing to the extreme, and with great elegance in my opinion. Even control structures are implemented via messages. For example, the if-then-else construct looks like this (Smalltalk aficionados, please be kind, my Smalltalk is a bit rusty):

(a < b)
    ifTrue:  [ "do something" ]
    ifFalse: [ "then do something else"]

If you are curious enough to look at the implementation (easy if you are lucky and you own a copy of the original book Smalltalk 80: the language and its implementation), you are in for a surprise. It is essentially this:

"in class True, a subclass of Boolean"
  ifTrue: trueBlock ifFalse: falseBlock
    ^trueBlock value
  
"in class False, the other subclass of Boolean"
  ifTrue: trueBlock ifFalse: falseBlock
    ^falseBlock value

What is happening here?

The square brackets create instances of class Block, which contain code. Blocks respond to message #value by executing the code and returning the value of the last expression. Operator < (implemented itself as a message, what else?) returns either true, the single instance of class True, or false. true sends #value to the first block, false to the second. And if things don't happen exactly like that (the chit chat between booleans and blocks may be optimized away), that is what goes on, conceptually.

Ain't it brilliant? Nonetheless, I believe that message passing is the wrong metaphor, as I am going to argue in the next section.

Kick the Dog or Dog the Kick?

I will now go back, as promised, to my choice of writing kick(dog) instead of dog.kick(). The second option can be defended, to a point. It is in a dog's nature to bark, not meow, when kicked. That it is in its nature to be kicked, on the other hand, is questionable. What I mean here is that the "kicking" business may belong somewhere else than the Animal class and is subclasses. Alas, if we want any form of polymorphism on animals, C++ offers us little choice: it has to go in virtual functions, if we can modify the classes that is. And in that case, we have to recompile all the code that depends on them. The Animal class may soon suffer from the obese base class syndrome, doing too much and at the same time, always missing some bit of functionality.

There is another approach to polymorphism though.

During the eighties, the Lisp community was researching the topic of OOP too. Ultimately, their efforts resulted in the Common Lisp Object System (CLOS). Some of the early attempts used an approach similar to Smalltalk's, but soon another model prevailed, which is not message oriented but rule oriented.

CLOS has classes and objects. Objects have state. However, classes don't "have" methods, in the sense of a piece of code living inside a class definition. Instead, CLOS has the notion of generic functions. They have little to do with Java's generics - they are multi-methods as described above. Since they don't "belong" to any object, they are, more precisely, open multi-methods.

And, in case you wonder, it is perfectly legitimate, indeed frequent, for a CLOS generic function to select the right specialization depending on a single argument. This makes the term "multi-method" a bit of a misnomer when applied to CLOS generics.

In my opinion, Lisp got it right and Smalltalk got it wrong.

And all the languages that followed the Smalltalk path got it wrong too - especially Java, which bans any form of code or data that does not belong to a class and invents classes that are not the blueprint of any object - you cannot say new Math().

I will be kinder to C++. Although it has its strongest root in Simula, another message-oriented design, C++ acknowledges that there are things that just don't naturally belong in any class in particular. In C++, we have free functions and data and types, and namespaces to organize them in large programs. And this is good.

Let us examine one more example that makes the dog kicking example more relevant to software engineering. When building multi-tiered applications, stitching the tiers together is tricky. Consider a business tier and, just above it, a presentation tier - e.g. a GUI. The GUI will need to create windows, or frames, or dialogs, for the various underlying business objects:

make_dialog(natural_person) -> return new natural_person_dialog(natural_person)
make_dialog(legal_person)   -> return new legal_person_dialog(legal_person_dialog)...

How does one go about implementing this? One solution is to stick a virtual function in some base class or interface, maybe introduced just for that purpose. This is not right of course! It is not in the nature of a person to fabricate and return a dialog box. Yet I have done it, in several projects, while pinching my nose, because it was the simplest solution and my profession is about solving problems, keeping esthetical concerns as a secondary factor.

Other solutions do exist. Or Patterns of solutions - have you noticed that many patterns are mostly about working around language limitations? For example, the Abstract Factory pattern can be used here (oops - it doesn't handle inheritance well).

Insider Trading

There is something else. Something deeper. Remember, I said at the beginning of the article that OOP rests on three pillars: encapsulation, inheritance and polymorphism. You certainly agree with this. Also note that a member function need not be virtual. Typically, you are a member function if you have really good reasons to manipulate the content of the capsule.

Now, let me ask you this question: how do you make a virtual function that does not have access to an object's private parts?

In C++, Java, C# and others, you cannot. We have a weird situation here: we can get polymorphism if we want it, but at the cost of breaking encapsulation, maybe unnecessarily. Two of the three pillars are merged like Siamese twins.

Conclusion

C++ needs open and multi methods. They are very coherent with the rest of the language. They will make it more complete and orthogonal. The creator of the language wants them. They can be implemented in accordance to the design guidelines of C++: be fast and impose no cost if the feature is not used.

I hope that I have not angered too many people with this article. I have programmed in Smalltalk and in C# and enjoyed it. They are fine languages with some brilliant ideas. My aim is to trigger reflection about ideas that, in my opinion, are too often left unchallenged.

I also hope I have not bored you with my philosophical ravings too much. Next time it will be 100% code, I promise.

No animals were hurt while writing this article.