Multimethods considered harmful

(This article is partially a follower for the “Visitors unvisited!” article.)

0. Multimethods and “super hyper advanced object oriented programming”

Multimethods is one of buzzwords in today object oriented programming. It’s considered to be some “higher level” of object oriented method dispatch (which dispatches by multiple objects, in contrast to single dispatch).

My previous article, “Visitors unvisited!” stated in the beginning that bad things have happened to design patterns, as they are used more to torture students than in practical use. The practical use is “how to solve my problem” and the practical use of design patterns is “I can use this design pattern to solve this problem”. Unfortunately, the majority of descriptions of design patterns found on the net just describe what particular design pattern is, however there’s no examples of what kind of problems you can solve with it. And lack of such examples disqualify design patterns in full length: what worth is a pattern for which no practical use can be shown?

I have already written about this, as an example taking the Visitor pattern, for which it’s even rarely stated that this is a way to implement multimethods in languages that offer only single dispatch, but they provide also function overloading by static types.

That’s really bad that Visitor is more a way to torture students and job applicants than a tool to solve practical problems, that is, to implement multimethods.

Although, it’s much worse than that. Multiple dispatch is also a kind of tool, which is widely explained on the net about how it works. For this thing there’s also a big hole of lacking problems to be solved by this tool. In particular, there’s no practical example to show that in this particular case multimethod is the only or the best way to solve it.

I know it may sound astonishing for some people because it’s really obvious that Visitor pattern is a way to implement multiple dispatch (that is, to have a development replacement for multimethods). What can I do – “super educated master developers” creating better and better languages are also “exploring America” by “revelatory” statements that “multimethods make Visitor pattern useless“. Yeah, guys, visitors are useless because they are useless anyway.

These guys should be really treated as extremely well educated. Other guys seem to not even know that Visitor is only for multimethods and using them for anything else is useless even theoretically.

1. What are mutlimethods?

Multimethods generally base on a statement that, in contrast to single dispatch, where for an operation with one object being a “pivot”, and deciding how to perform requested operation, for multiple dispatch there are two or more objects that together decide about it. For example: we can have an operation “op” and would like that an object kept by reference do “op” and in response some function will be called – which one, it depends on the type of the object. For multiple dispatch, we do “op” passing two or more objects (plus maybe some additional arguments) and which function will be called in result, depends on the combination of types of these two objects.

It’s easy to imagine what it means in practice. As in case of single dispatch you had to provide an override for every class that derives some abstract class, for double dispatch you have to provide “a square more” (a cube more in case of triple dispatch and so on). For example, if we have first hierarchy, with class A and derivatives B, C, D, operation op( A ), requires op( B ), op( C ), and op( D ) overrides. If we have a second hierarchy, with class “W” and derivatives X, Y, Z, and operation op2( A, W ) (being a multimethod for A and W), then we need to provide the following overrides: op2( B, X ), op2( C, X ), op2( D, X ), op2( B, Y ), op2( C, Y ), op2( D, Y ), op2( B, Z ), op2( C, Z ), and op2( D, Z ). Total 9 of methods, which is the number of derived classes in both hierarchies multiplied by each other.

I’m not going to focus on implementations. As I have already mentioned, the Visitor pattern is one of the most famous implementation; there are also implementations for Python and Java. It’s not the most important for my article; I’d like to rather focus on finding any practical use of multimethods.

2. The basics of object-oriented programming

Yeah, funny. I know. But what can I do – I must start with reminding what really the object-oriented programming is if I want to explain, what I can see wrong in multimethods.

I have already used the word “pivot”. I am not sure whether this is the best word to describe it (English is not my first language), but as I know its explanation in mathematics and linguistics, the object for which the method is called, can be named with this word. Since generally when you call a function, you pass some arguments to the call and theoretically the object, for which the method is called, is also an argument of this call. (That’s why people who like functional languages would also say that this object is some very artificial and unnatural thing.) So it would be most safe for me to define this object as “pivot”.

This “pivot” is an object, which has one special meaning among other arguments passed to the call, that from this object there is read some characteristic information that allows it to retrieve the correct implementation of the defined operation.

This exceptional role of the pivot relies on the rule that the operation to be performed on an object is abstract. And the pivot is used to “instantiate” this operation, that is, state what “op” means in its particular case.

Note, however, that this too is a kind of a “design pattern”! And, by the same rule, people also are often confused about “well, should I use this pattern here, or not? And how?”. There is a famous confusion about the operation of sending data to the stream. Should a data print itself on the stream or the stream should print the data on itself? I’ll cover that later because this is also one of the most interesting cases in the topic of multimethods.

3. Multiple abstractions

Abstraction in object oriented programming is strictly bound to abstractions in the real world: abstractions base on terms. There is an abstract term and there can be some abstract treat or abstract operation that can be performed for a “live being”, matching this term.

Well, so: are the two types of objects so special that abstractions should be defined on the level “how both of these types would perform this operation together”? Let’s consider, for instance, an abstraction for “a man drives a car”. In abstraction it would be “a drives b”.

Does it make sense? Well, we can try to define it by many ways, but probably it will be most reasonable to have some limitations (base classes) on these two objects that would perform this operation. So we can do it the following way: “Driver drives Drivable”. So, does it make sense? That is, can we think about multiple cases of Driver and multiple cases of Drivable that can “intercommunicate” by various ways?

Well, it may make sense, but what for. We can define the “drive” as a set of operations that can be performed on “Drivable” and as long as the “Drivable” supports them, they can be used by “Driver” – while “Driver” may use these simple operations by various ways, as long as it makes sense for it.

Generally, you can define “drive” operation as set of appropriate accelerating, braking, and turning. If we can define these three operations – we can define the “drive” operation without having any least knowledge on the details of both Driver and Drivable! The “drive” operation can be defined by using only abstract operations of Drivable and Driver. And no matter if the Driver is a man sitting behind the gears or this is a built-in automaton, only the way the operation is being requested from Drivable differs – not the operation itself. So, both cases of Driver should define what they mean by controlling, and all cases of Drivable should define what they mean by accelerating, braking and turning. Now the “drive” operation needs only to cause “controlling” by Driver and cause accelerating, braking and turning by Drivable.

Of course, this can too be defined on the base of multimethods, but the most important question is: what’s the reason? The only difference is that the number of methods you have to cover is in a level of exponentiation more! Look: When you have two Drivers: Man and the Machine, and three Drivable-s: Car, Tank and Horse (no matter how funny sounds an automatic driver for a horse :), you need only to define: Man::control (using gears with hands and legs), Machine::control (access the lowest level control terminals by electronics or engines), Car::accelerate (engine), brake (brakes), turn (steering wheel), Tank::accelerate (engine), brake (engine plus brake support), turn (caterpillar engines differentiation), and Horse::accelerate (run faster), brake (run slower), turn (just turn :). Total number of overrides is 2*1 + 3*3, that is 11. For multimethods in the above equation you’ll have to change + to * in the above equation, so the result is 2*1*3*3 = 18. Note, however, that these method overrides are not equivalent – in case of multimethods one override does things of two methods in single override. It should be then multiplied by two. Even stating that the factor may be 1.5 because simplified information interchange methods can be used due to more direct access, it makes 27 required overrides, which is still more than twice comparing to 11 (plus one general method based only on abstractions) in single inheritance.

But it doesn’t even matter that so many methods you’d have to define. Much more important is that… what’s indeed the difference between “A man rolls the reins of the horse” and “A machine is turning the steering wheel”? If you describe them both as “A driver is using drivable’s means to make a turn”, the difference is none. There may be only a difference about what it means for the driver to use driveable’s means and what it means for the drivable to make a turn – but all these things can be defined on the driver and drivable abstraction levels. The only abstraction, which can be here, is how the data between these two objects are interchanged in this operation. The operation itself isn’t an abstraction at all – what is abstraction here is the information interchange. Do we really need abstraction to express this thing?

Now you can see now how reasonable can be abstractions based on multiple terms. Remember: unless you can define reasonably a term of “multiabstraction”, don’t try to state that multimethods are reasonable. Can you?

Of course, we may have not enough details defined in abstract types and we need them in this operation… bullshit! None of implementations of multimethods or their replacers states that private, inaccessible otherwise data should participate in this operation. This is just the reason, for which abstractions are needed for base classes: let’s state some general forms that must be provided by every derived class.

If you say that you need multimethods because your base class does not provide appropriate abstraction on which you can base your general operation, then maybe you just need to sit down and add them? If your crossing operation needs two concrete objects together, maybe by some reason it’s not enough to have them each other single as concrete class and both together as abstract class – and this “some reason” is “not present appropriate abstraction methods” and “not present appropriate abstract methods for intercommunication of objects”?

4. Multiple pivots?

The problem of pivot is indeed a very similar problem to the problem of inheritance. The object-oriented programming states that there can only be one base class, just similarly, as there can be only one object to decide about the operation’s implementation.

But we have also multiple inheritance. What is multiple inheritance in the terms of object-oriented programming? I describe this topic well enough in another article, I’ll try to be short here then.

First, you must reconsider that inheritance has two aspects: extending (adding new features towards the base class) and subclassing (changing or defining the behavior from the base class). While you can extend multiple classes without problems, it’s a strange thing to have a multiple subclassing.

This is an important difference between extending and subclassing: when B subclasses A, it means that if an operation cannot be defined by class A, it’s redirected to B (whatever it is); while when B extends A, it means that B defines an operation the same way as A unless an explicit override is provided. It means that while it’s normal that the extending B does operation “op” as defined in A, or whatever else derived class defines it, it’s strange what to say when “op” is performed for an object of class B, which subclasses A, X, Y: as B does not define it then the class redirects it to what? All of them? Only those that “understand” it? Only the first one?

The first one, well… a tempting offer. That’s how Smalltalk manages it: it does not offer multiple inheritance, but offers delegation. You can treat it as multiple inheritance, where the first class has special meaning. It can be even treated as a “pivot class”.

And that’s what this “pivot problem” is.

If you have one of the following cases in C++: only one polymorphic class in the hierarchy, two polymorphic classes with one common virtual base, or two polymorphic classes from two separate polymorphic hierarchies – you still have only one “pivot” base class (that is, the base class that defines what to do for particular operation if the derived class did not define it). In first two cases, this polymorphic base class is the pivot, and the last case is the “class composite”, where each composite member has its own pivot.

Only in the case when you have two polymorphic classes coming from the same root as base classes, may you have a kind of “two pivots”. But such a hierarchy is disallowed in object-oriented programming.

(By the way, note that in Java, C#, and many other languages, you always have a class that is a base for all classes, usually named “object”; also there are no “compact” classes or at least they cannot participate in inheritance. It means that the second case – two separate polymorphic hierarchies – is not possible to be done in these languages. In consequence, they do not allow for multiple inheritance.)

The term “method” comes from object-oriented programming and the core meaning of object-oriented programming is “I order object o to do operation p and let object o do this p the way it understands it”. If you are doing something else with the object, it’s not object-oriented programming. How would you then end the sentence “I order objects o and q to do operation p…” ?

What it means for the matter of pivot in case of calling a method, is that the situation of “two pivots” is something unnatural and illogical. Nonetheless, in whatever domain you’d understand the word “pivot”, the “two pivot” term is an oxymoron. So if you confirm that object oriented programming has been inspired by the logics of surrounding world, multimethods is just the point, where this logics ends.

Moreover, in the “multimethod” term the matter is not that objects o and q do operation p. The matter is that object o do operation p adjusted to object q. Or object q do operation p adjusted to object o. Or even “let’s do operation p adjusted to o and q together”. Maybe, then, the problem is with not having something important in the middle?

5. Which one is pivot?

So let’s go back to the problem: when we want to write an object to a stream, should the object print itself on the stream, or the stream should print the object on itself?

Some people say that this problem is unreal. Not exactly. The problem here is the level of information privacy.

However pay attention that this is a typical problem of two-kind polymorphism: there can be many various implementation of a stream, and there can be many types of objects to be printed on the stream. Actually both the stream and the object may implement the way it is being printed!

Isn’t it then the typical problem for which the multimethods have been developed?

So, if this is the typical problem to be solved by multimethods, why it’s never solved by multimethods or any replacement mechanism like visitors?

And how is it solved?

Well, usually the stream have defined methods for sending to it values of some basic types, including string. In other words, there’s something like stream::write(), which is then implemented in specific way. Then, if you want to print your type object to the stream, just convert it to some “printable” type (usually string) and use an existing stream::write(). You may also use several stream::write() methods for multiple parts of the contents of your object. In final effect, all versions are glued together with one common function (in C++ it’s operator<<).

What does this example teach to us?

If the operation requires access to vital data of two objects, there must be some way to convert them into some common (interchangeable) representation. Moreover, in practice every stream should only have the write method for string – for all other data types they are first converted to string and then redirected to the string version. So, it means in practice that this interchangeable representation is string. This way, all that particular stream class has to do in its write() method is to implement write( string ), while all that particular object class's implementor has to do to make it printable on a stream is to convert the contents to string value. That's all. And it really works – since a long time this interface has allowed that objects of various types may be dumped to various kind of streams.

There is also another interesting example, that may be implemented by multimethods: adding two numbers. We have an abstract Number class, and we have operation:

Number add( Number, Number )

where Number may be Integer, Float and Complex (let’s state Complex of Float). You’d have to provide adding Integer to Integer, Float to Float, Complex to Complex, Integer to Float, Integer to Complex, Float to Complex – total 6 of methods. If you add one more Number class, you’d have to add one for both types identical, then one per existing class (3 in this case), so additionally 4 methods. For next one, it will be 5 additional methods. And so on. As both arguments have the same base for the hierarchy, you only have to fill the upper to diagonal – lower to diagonal can be defined by inversion (however it’s the case when you create an operation for two objects of the same abstract class – if they are different abstract classes then usually whole matrix should be filled).

But, unfortunately, in today implementations this is not solved by using multimethods. And it’s not because multimethods are weakly supported. It is because using multimethods is stupid: in the case of Number, much better would be to define only adding for the same types and conversion between types. This uses, however, still some special case: number classes can be ordered from least significant (Integer) to most significant (Complex), that is, an object of less significant class can be converted to more significant class loselessly, however in opposite way only with narrowing (losing part of information). So the other object of the operation is “adjusted” to more significant class of them both and object of this class is returned.

However, whatever example you show to be a good for implementation with multimethods, each such example may have this “something special” that causes that this can be still implemented different way – much simpler in every case. In this case it’s the orderable treat, in case of streams it’s the common data representation. In other cases maybe there should be some specialized object that may have access to private data. Whatever. Implementing this by using multimethods, even in the form of visitor, will make this work always more effort consuming.

6. Are there any typical examples?

Is this a rule? Is there always a method for retrieving data for each object?

There is a faaaamous example of intersection of two shapes. Everyone gives this example as multimethods (including Bjarne Stroustrup in his “Design and Evolution of C++”) – but no-one shows how this intersection methods should be implemented. No-one has even tried. It’s not impossible that if I can see this implementation, I can quickly show, how to do the same, without multimethods or some their replacement, and simpler. Probably some of people who refer to this example, do not realize that this operation is really complicated, and using exactly stated types of two shapes for which we want to test intersection, is no help here.

I have tried to approach (just theoretically – this example really doesn’t look interresting for me and is not practical at all) to implement it. And my first idea was: why not define a method that will do something like “trace shape”, allowing to detect common points of two shapes? Why not having something like “return set of functions that describe parts of the shape”? When you have such methods, you are able to easily implement the intersection… without knowing concrete class of the shape. You can just encode it in the frames of the Shape class. Moreover, in this particular case you don’t have to expose the “functions” method to public because only the Shape class needs to know this information.

And if you say that you would have to reveal too much information to public, try to first verify how deep access to information you would have to ensure if you want to create implementations for all combinations of two (or more) classes. Because if you don’t need details of these classes, then why isn’t it enough for you to encode your operation just once, using abstract virtual methods?

I have tried “mutlimethods example” and “visitor example” in web search engines. The majority of them were explanations how the visitor pattern works or how multimethod works, given some simple examples, usually with – guess what? – and usually so stupid like those mentioned in the beginning. There was one site where the autor was tempted to spell up some really practical examples of multimethods, however the implementation isn’t shown, nor any discussion was provided to at least try to prove that this method seems to be best or that it at least makes sense.

7. Is there any “value added” from multimethods?

All available informations about multimethods make me think about them as about a kind-of scientific aberration, a curiosity, which shouldn’t ever reach the practical software engineering. They are cherished by Java programmers (especially those, who just discovered them), they are implemented in python (a language, for which 80-20 rule becomes 95-5), they are also implemented in many other languages, which for industrial software engineering are niches.

Actually, I cannot find an example, which is using multimethods, which cannot be translated into normal single-dispatch based code. Multimethods are just useless, and I would even make a statement that using them means that the need of using multimethods is simply a design flaw.

So?

To all developers who participate in creating and designing programming languages: guys, I really believe you have lots of much more important problems to solve. Forget multimethods and you’ll really stop wasting your time.

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s