MultiMethods are sets of methods that are polymorphic on more than one of their arguments. Implemented in languages such as CommonLispObjectSystem, CecilLanguage, DylanLanguage, S# (a superset of Smalltalk), NiceLanguage, and the upcoming Perl6.

The idea of MultiMethods has been used very early in CommonLoops (1986). CommonLoops was an extension to Common Lisp developed by Xerox researchers (based on Flavors and Loops). Later (1988), CommonLoops created the most important influence for the CommonLispObjectSystem (CLOS). With ANSI Common Lisp, CLOS is an integral part of the language.

----
''' Very simple explanation of what MultiMethods are '''

Smalltalk, C++ and Java have polymorphism based on single dispatch. That is, if you see something like:

p.read( a, b, c );

Then, in runtime, depending on the type of p, the appropriate method will be resolved and executed. Please notice that based on the types of a, b and c, there could be overloading besides overriding, but that just wouldn't work. Overloading and overriding do not match. Both achieve polymorphism, but overriding achieves polymorphism at runtime (LateBinding) while overloading achieves polymorphism at compile time (EarlyBinding or should it be called PrematureBinding instead?). Therefore overriding is considered superior to overloading, but overriding only depends on the type of the receiver, while overloading depends also on the type of the parameters.

Then MultiMethods was born. The idea of MultiMethods is that the same LateBinding idea can be applied on all parameters.

Reading the "See also:" pages on DoubleDispatch and MultipleDispatch may help with understanding MultiMethods.

----
'''Very complicated discussion on what MultiMethods are'''

How do multimethods differ from method overloading? 
For example, in C# I could do this

  class Pretty''''''Print{
	public void Print(Customer aCustomer){}
	public void Print(User aUser){}
	public void Print(Super''''''User aUser){}
  }

I know I'm missing something here, just not sure what.

  If you do this (assuming "Person" is the superclass of Customer, User, and Super''''''User):

     PrettyPrint pp = ...;
     Person p = new Customer(...);
     pp.Print(p);

  , then the C# compiler will complain because it doesn't know which of the three methods it should call.

  If C# had multi-methods, this would compile and run as expected, i.e. the first "Print" would be called.
  This is because, with multimethods, the *dynamic* (run-time) types of all arguments (not just the
  first one) are considered *at runtime* when deciding which method to call.   -- OlafKlischat

''What you are missing is that your example is single-dispatch, the method is owned by PrettyPrint, and dispatches on it's first argument.  A standard (trivial) example of multimethods would be something like this, in CLOS''

  (defclass rock ()())
  (defclass paper ()())
  (defclass scissors ()())
Above defines classes ROCK, PAPER and SCISSORS with no superclasses and no slots.

  (defgeneric r-p-s (a b))
Above defines a GenericFunction with two arguments A and B.

  (defmethod r-p-s ((r rock) (p paper)) 'paper)
  (defmethod r-p-s ((r rock) (s scissors)) 'rock)
  (defmethod r-p-s ((p paper) (s scissors)) 'scissors)
Above defines three methods for the generic function R-P-S.
These methods each take two arguments. Each argument
is specialized for a certain class. Each method
return just a single constant symbol.

  * (r-p-s (make-instance 'rock) (make-instance 'paper))
  PAPER
  * (r-p-s (make-instance 'rock) (make-instance 'scissors))
  ROCK
  * 
MAKE-INSTANCE takes the name of a class as an argument and returns
an instance of that class.
R-P-S is a function with two arguments - the objects created.

While methods in CLOS belong to an object, namely the GenericFunction, they do not 'belong' to a class of a special argument. So CLOS does not follow some message sending paradigm. CLOS is based on generic functions that are called on a number of arguments, where all arguments are taking part in dynamic message selection.
At runtime methods can be added to or removed from the generic function. Additionally the class lattice can be changed, so the methods to be called at runtime can not be statically predetermined at compile time.

----
OK, sticking with your example and my limited understanding of Lisp, let me try to translate to what I know..

  class rock{}
  class paper{}
  class scissors{}

  class game{
	public static object rps(rock r, paper p){return p;}
	public static object rps(rock r, scissors s){return r;}
	public static object rps(paper p, scissors s){return s;}
  }
  class Test''''''Console{
	[STAThread]
	static void Main(string[] args) {
	Console.Write''''''Line(game.rps(new rock(),new paper())); //prints paper
	Console.Write''''''Line(game.rps(new rock(),new scissors()));  //prints rock
	Console.Read''''''Line();
	}	
  }

Now, assuming my translation was correct, the only difference I can see is that C# doesn't have first class methods so I must define the methods in a class game, which I'd consider a method object.  But it still seems to me I can dispatch on any of the arguments.  Though I'd have to call game.rps rather than just rps.  Am I still missing something?  Is my translation wrong?	

'''Yes you are still missing the fact that the multimethod call uses the base type for the arguments, but still finds the appropriate implementations for the derived types'''
'''Thus your example might be (in theoretical multi-dispatching C#/C++ ish language) '''

  class shape {}

  class rock : public shape {}
  class paper : public shape {}
  class scissors : public shape {}

  class game{
	public static object rps(rock r, paper p){return p;}
	public static object rps(rock r, scissors s){return r;}
	public static object rps(paper p, scissors s){return s;}
  }
  class Test''''''Console{
	[STAThread]
	static void Main(string[] args) {
	shape rock_shape = new rock();
	shape paper_shape = new paper();
	shape scissors_shape = new scissors();
	Console.Write''''''Line(game.rps(rock_shape, paper_shape)); //prints paper
	Console.Write''''''Line(game.rps(rock_shape, scissors_shape));  //prints rock
	Console.Read''''''Line();
	}	
  }

'''The thing is that the multimethod mechanism has to translate the type of arguments from their static type (always shape) to the appropriate dynamic type, before calling the appropriate overload.  Like it does with the 'argument' (!) before the dot.  Its a very useful facility, and inevitably leads on to the other question about whether the functions really should be tied up with the classes in the first place. -- BillWeston'''

Thanks Bill, that totally makes sense now, and of course now I hate that I can't do that!  I already know of places I'd find this ability extremely useful.  

My goal is to learn to program in a more functional style in C#, since that's what I must use at the office.  With C# about to get lexical scope and anonymous functions in it's next release, I think this could greatly improve my programming abilities and expressiveness.  ExternalPolymorphism seems very interesting to me because of the ability to dispatch on many arguments, hence my interest in MultiMethods.  Truth is I'm just trying to find out what's out there that I don't know about yet.  I understand OO idioms, and I've been studying functional idioms such as Closures, Continuations, Co-Routines, HigherOrderFunction''''''s, LexicalScope, Blocks/Anonymous Functions and grok it pretty well.  So I'm wondering what's left, what other advanced concepts are out there?  I've studied Lisp a little, I'd love to have macro's, but know that won't happen.  I'm very intrigued by Lisp and Scheme's habit of solving problem by recursive descent, but I'm not sure how to think like this yet, but I'm always impressed by how little code it seems to take to solve problems in the functional style.

[So it sounds like the big difference is that multi-methods are selected based on all of the arguments' object types instead of the object type of the first argument and the variable type of subsequent arguments?]

''I've never totally groked multimethods, so I can't answer your question completely, but I think I can move us a little way towards an answer. Your C# example is in fact not dispatching on all the arguments. "game" is an argument, it is just given special status syntactically. Another (theoretically) possible syntax that might clarify the matter is "rps(game, new rock(), new scissors())". This statement would always look in the game class for a method whose parameters match the remaining parameters in this statement. Multimethods, I think, allow this to vary, sometimes looking in game, sometimes elsewhere, as appropriate.''

''I've included a lot of handwaving in that last statement, because this is where my understanding ends. I don't grok, on a practical level, why you would want to vary that first argument. I don't see what the lisp version buys us that the c# version doesn't.''

'''It makes any higher level shape handling code generic -- BillWeston''' 

----
This presentation goes through the issues using Java for the examples: [http://www.cis.ksu.edu/Department/Seminars/leavens-mm-talk.pdf ''BrokenLink'']

I'm not sure the Java example applies since Java doesn't overload like C#.

''Java has run-time polymorphism, which is what's relevant. Overloading is different; static, compile-time type information is used to select among overloaded variants of a function, versus run-time type information for polymorphism in class methods and multimethods. The C# example 'translated' from Lisp above uses overloading, which is why it doesn't do the same thing as multimethods. Don't confuse the two! They're fundamentally different, and many programmers ''do'' confuse them. -- AnonymousDonor''
----

Can't you do essentially the same thing in the hated JavaLanguage using something like AspectJay to add methods to existing classes (including parent classes in inheritance trees)?

No, since you'd never get it to compile due to the type system.  Aspects don't really have anything to do with multimethods anyway, so I'm curious why you'd ask that question?

----

One major issue with MultiMethods seemingly not discussed here:  If you have two multi-methods as such

 void do_something (Derived d, Base b);
 void do_something (Base b, Derived d);

and you call code like this

 Base d1 = new Derived;
 Base d2 = new Derived;

 do_something (d1,d2);

The call to do_something is ambiguous.  Either you have to a) disallow it, unless disambiguated by the programmer, or  b) impose an ordering on the arguments.  Neither alternative seems satisfactory.

Similar issues arise, of course, with FunctionOverloading (where selection is based on the annotated type of the reference rather than the dynamic type of the object, as C++ does) and with multiple inheritance (when a feature with the same name is inherited from two different bases).

''Every language with multimethods imposes an ordering on them.  It's usually left-to-right in the parameter list.  This is no more (or less) arbitrary than dispatching dynamically on only the first argument, like SingleDispatch languages do.  And it's certainly more convenient than disallowing PolyMorphism entirely, which is what you'd have to do to eliminate the ambiguity entirely in a non-arbitrary way.''

[But eliminating the ambiguity in an arbitrary way might not be so bad, as a practical matter. Given that the two methods implement the same generic function/interface, they presumably serve the same purpose, so the ambiguity should mean that either one would do what's intended. In fact, a sophisticated compiler could perhaps pick the one that's likely to run fastest, if it was able to estimate this.]

[[If you have a MOP, you can change all of this as well (at runtime, depending on your system)]]

The solution is to provide a third method which accepts the most specific combination; indeed, this is what is implicitly done.  Myself, I'd give some sort of compiler/interpreter warning given the definition of those methods without the disambiguating method.  --WilliamUnderwood

[What is being discussed here is how languages that implement multimethods deal with such a potential ambiguity, not whether the programmer can manually eliminate the ambiguity.]

And I'm replying that a language should notify the programmer of that ambiguity and not make a guess based on heuristics, or anything resembling "Hmm, we could just do this...".  Kinda like dispatching to a method which takes one parameter just because we can't find one that takes the two parameters provided.

[Ah. So, you're in the camp that says all parameters should be given equal importance, thus the situation described above is in fact ambiguous. Others think that it is also perfectly OK for a language to define a precedence for the parameters (usually left-to-right), in which case there is in fact no ambiguity, there is a simple, easily-understood rule to follow, and there is no problem to be solved. In both schemes, creating a more specific third multimethod implementation is of course possible.

Now, I was the one that posted the comment about using speed heuristics, and you haven't said what you didn't like about it, but just told us the obvious way that a programmer could explicitly control the situation. I'd be interested to know what the objection is; my suggestion was not an original thought, but is based on a speculative idea from another source. I'm not entirely comfortable with it myself, but it is an interesting idea; if one assumes that two multimethod implementations are both applicable according to their specific signatures, would it not be reasonable for the compiler to assume that either one would produce correct results? And if the compiler has special information that's not easily accessible to the programmer that could be used to disambiguate, why not take advantage of it? Likely you'd want to give a programmer the means to exercise more exact control, perhaps requiring them to explicitly flag multimethods for which such behavior is allowed.]

Yay for talking out of my ass;  it's amazing what sleep deprivation will do for one's 'clarity' of thought.  I don't recant the general sense of "The programmer should ''probably'' be told", but do admit that there's some potential.  If it can be shown with some rigor that the ''semantics'' of the ''implementation'' will be equivalent (short of programmer errors) in two methods with such a setup, then by all means it is correct, even desirable to have the compiler / runtime decide which one to call.  --WilliamUnderwood

[LOL -- that was the most funny and honest retraction I've seen in a long time. I invite you to refactor/summarize/remove this exchange.]

If the compiler can decide that the semantics will be equivalent, it ought to just eliminate the code for the less efficient one and always call the more efficient one.  It tends to be fairly difficult for a compiler to tell that semantics are equivalent; that's what compiler optimizations are, and those're often limited to a fairly specific set of circumstances.  Doing it in the general case would probably run up against the HaltingProblem.  

As for the "should the programmer be told?", I haven't had many problems with the really limited CLOS/Dylan programming I've done.  I tend to lean towards the "order left-to-right for disambiguation" scheme, if only because it's used in CLOS, Dylan, and most PatternMatching languages (which also order top-to-bottom).  CecilLanguage has the "method ambiguous" error message, and also allows much more involved PredicateDispatching.  I'm curious if anyone has experience with Cecil or has had problems where the CLOS/Dylan ordering led to hard-to-find bugs.  -- JonathanTang

[The compile shouldn't eliminate one, because in the example given, either might be a ''better'' signature match for a given set of arguments. This sort of begs the question of why, if the semantics are equivalent, the programmer would supply both.

FWIW, which might not be much since I haven't had the opportunity to do any real work with a language that supports multimethods, the left-to-right precedence scheme sounds just fine to me.]

I've changed my mind about left-to-right ordering, because of KeywordParameterPassing.  With keyword args, the order of arguments at the call site may not match the ordering at the function declaration, or any other ordering.  A left-to-right argument ordering would mean that the calls
  do-something to: receiver with: implement
  do-something with: implement to: receiver
could call completely different methods.  Occasionally this is what you want, but in general, you choose keyword parameters because the order ''shouldn't'' matter.  

It also means that the dispatch code and tables have to be replicated at every call site, instead of having just one per GenericFunction.  Existing ways of efficiently ImplementingMultipleDispatch already take a large amount of space; multiplying that by potentially hundreds of calls isn't feasible.  It works in CL/Dylan because keyword parameters are typically not dispatched upon and the languages often don't use the latest dispatch algorithms, but it wouldn't work for a new language that relies heavily upon keyword parameters.

-- JonathanTang

Interesting point. I actually kind of like the idea that by using keywords, you could change the matching precedence for a specific call. The compiler wouldn't need a dispatch order per call, merely one per unique ordering encountered, which could be a lot less.

-- DanMuller

-----

Are MultiMethods simply ''static'' PrologLanguage-like things? My interpreter/dynamic-favoring ways lead me to think this way. Another way of saying the same thing is that it seems like compile-time QueryByExample, or "static QBE", and a candidate GreencoddsTenthRuleOfProgramming sighting. -- top

''No, not at all. See "How do multimethods differ from method overloading?" above.''

----

What I don't get is why you're calling them multi-''methods''. Methods are functions associated with a particular object or class. They are so associated by being callable only with that object or class, having direct access to that object or class' variables, and having special access to pseudo-variables holding that object or class.

In languages that have hidden variables in objects, only methods belonging to those objects can access these variables. Smalltalk is that way while C++ doesn't have methods.

In languages that don't have hidden variables, a method call keeps its original binding to self no matter how often it's delegated up the chain. Smalltalk and Self are both like that.

And I sincerely doubt that multi-"methods" are like that.

What variables of the objects passed as arguments is a multimethod able to access directly? All of them? None of them?

If a multimethod delegates a message, does the ... oh wait, CAN a multimethod delegate a message higher up the hierarchy? Is there even a hierarchy? And do you call a multimethod on first match or best match? And if there ''is'' and if you ''can'' and if it ''does'', does the more generic multimethod have the same arguments as the original?

Funny thing is, I can't help thinking of multimethods as intrinsically OO. You dispatch on an object and then you dispatch ''within'' that object on the second argument's type, and so on and so forth. But I really doubt that functional languages have this nesting pattern since, and this shouldn't come as a surprise, they aren't OO.

Note, it'd be difficult not to possess this nesting pattern if you dispatch in a sane way. But having this pattern and ruthlessly exploiting it are two very different things. More than anything, that's what I doubt. -- rk

There are several terms that are very closely related (sometimes synonymous): multimethods, generic functions, and polymorphic functions.

If someone says "multimethod", then yes, the "method" part of that tends to mean they're talking about OO, whether there's an implied object parameter or not (there is not in CLOS, but it's still OO) -- that's a mere syntactic matter. But if not, then the object is explicitly specified. The method belongs to the object, whether implicit or explicit.

"Generic" seems to have become widely used (I think) in the context of STL, which was first developed for Ada and then for C++, and usually means OO methods '''or''' non-OO functions which have polymorphic parameters, and unlike "multimethod", implies that multiple versions of the method/function are instantiated at compilation time (one per parameter type combination). The point in STL is that the polymorphism mechanism is handled at compile time, and specialized code is generated, so everything is fast.

"Polymorphic" is the oldest of the three terms. I'd like to say it's the most generic of the 3, but I guess that would be unwise.

The other stuff you're asking about, concerning details of the polymorphic dispatching, scope/access to instance variables, delegation, first match/best match, and such, are completely language dependent, and as such are independent of the terms multimethod/generic/polymorphic.

So to get particular answers, you'd have to specify the language you're asking about. Any of the possibilities that you mentioned has been done by some language or another.

But more importantly, don't be '''too''' concerned about terminology, such as what someone means by "multimethod"; it doesn't mean '''anything''' beyond the basic "polymorphic on more than one of their arguments" that it said at top of page (equivalently, "dispatches on more than one of their arguments"). Purists from certain camps claim they're not OO, others feel they're a variant on OO.

Oh, and as to pure functional languages like the ML family, they're all '''heavily''' polymorphic (on more than one parameter), but many are not OO. -- dm

See, I really don't care about terminology for its own sake. But I care about whether or not a system is OO. And it's OO if and only if a method belongs to a well-defined object. And it only does that if the language makes very specific choices about dispatch, scope/access, delegation, first/best match. There's only one correct OO answer for all of these. And if a language chooses the wrong one then they're simply not methods.

''And it's OO if and only if a method belongs to a well-defined object.'' [Actually, this is hardly uncontroversial; your stating it as bald fact is simply incorrect.]

A multimethod can't dispatch arbitrarily. It has to dispatch in a predefined order such as left to right. That rules out having both multimethods and keyword parameter passing in an OO language.

A multimethod has to do best match, not first match. And 'resend' sends the exact same message using the next best match.

A multimethod has to have pseudo-variables named after all of the formal parameters it takes in.

If the language has hidden variables in objects, then a multimethod can access either none of its parameters' hidden variables or only the first. Preferably none.

As long as you've made these choices then methods clearly belong to objects or classes and you've got yourself a pure OO language. Nothing else makes any kind of sense from an OO point of view. Actually, nothing else makes sense ''at all'' to me so I have difficulty imagining the other choices. The only alternative that I can imagine is with keyword parameter passing, and those are definitely not OO outside of single dispatch. And caller determined dispatch is not OO at all. -- RK

Here's another interpretation of what ''multimethod'' means: A ''method'' that belongs to ''multi''ple objects. Aside from the more complex dispatching rules, they're really as simple as that.

As long as objects are the primary determinants of dispatching, I think that the details can vary by language without saying "that's not OO". Quibble if you like; everyone's entitled to their own definition of OO these days.

I'm not sure what "best match" versus "first match" means. "First" according to what ordering? I'm also not sure why you mention pseudo-variables named after formal parameters; that's pretty standard for functions and methods. Did you have some different expectation in mind with respect to multimethods?

Regarding "hidden variables" (by which I assume you mean "hidden (data?) members"): If you do not give multimethods access, this implies that you ''must'' also have regular (single) methods, and that multimethods are second-class compared to them. Since multimethods can (without this restriction) do everything that traditional methods can, and just as conveniently, it's cleaner to only have multimethods (as in CommonLisp). I could imagine distinguishing "privileged" and "unprivileged" multimethods, I suppose.

-- DanMuller

Or that you not have hidden variables.

I mentioned pseudo-variables named after formal parameters because something I had read about Slate made me think it was otherwise. It isn't, but it left open the possibility in my mind.

Let's say you have:
* (convert automobile plane)
* (convert truck plane)
* (convert truck jet-fighter)

then calling (convert Ford F15) under best match would result in execution of (convert truck jet-fighter). resending would result in execution of (convert truck plane) and only resending within that method would result in execution of (convert automobile plane).

Now, that might seem obvious but it's not.

If you've got three or more arguments then you have to ask which is more generic (more of a best match) between:
* (convert truck plane liquid-fuel)
* (convert truck jet-fighter fuel)

If you have left to right, then the best match is the second. If you don't have left to right then it's ambiguous and there is no best match. -- RK

Right, but you didn't explain what you meant by "first". Did you mean "first, using a left-to-right matching order"? Or "first according to textual order of definitions that has matching arguments (without regard for how closely they match)"?

"Best" necessarily means "best according to the matching rules of your multimethod implementation". Whether that can produce ambiguities or not is up to those rules, and you can come up with many. Rules can take into account lexical order of parameters, "matching distance" (inheritance steps between a parameter's declared type and the actual run-time type) (I made that term up), alphabetical order, or any other darn thing you can think up. (Although I think I have an intuitive idea of what ''you'' meant by "best" -- probably involving a summing of inheritance distances, if it were to be formally stated.)

CommonLisp's CLOS avoids ambiguity using a combination of left-to-right matching preference, and an unambiguous total ordering of base classes, even in the presence of multiple inheritance. (I can go into more detail on this if desired.) This seems to be a reasonably understandable and unambiguous dispatching method. This is better than (what I think is your notion of) "best match", because it is unambiguous, and makes it straightforward for the programmer to get exactly the dispatching wanted. (Although I can imagine complex cases where competing concerns might make it a bit difficult.)

Of course, it's also possible to have situations where some combination of arguments doesn't match ''any'' method implementation, in which case you get a run-time error. Similar to some OO languages' "no such method" error, which however can't (easily) occur in some other OO languages.

-- DanMuller

I don't define 'first' because I don't care about it. And I do not define 'best' as a summing up of inheritance distances. Not unless you use transfinite arithmetic. That's because I believe in left-to-right argument precedence. It provides a nesting of the methods' signatures that's perfectly natural (and OO) to me.

For me, a perfect match on the first 2 arguments to a method trumps a discrepancy on the first parameter and a perfect match on the other 364 arguments. The former is the best fit because the first parameter matters infinitely more than the second which matters infinitely more than the third and so on.

But in this scheme, a method isn't owned by more than one object. It's owned by the first object which subleases it to the second which subleases it to the third, and so on. This is the mimimal multi-dispatching extension to an OO language like Smalltalk that would let it retain ''pure'' OO status.

And since single dispatch provides 90% of the bang for the buck, and the "arbitrary" kind of multi-dispatch I describe provides 90% of what's missing, I've yet to see a compelling argument for a perfectly uniform non-arbitrary multiple dispatching method. For that matter, I've yet to see a demonstration that it would be possible.

Now, onto matters you raised. A total ordering of classes is unnecessary, arbitrary and screwed up. I haven't the slightest clue how it could be maintained. I also haven't the slightest clue how it could be used if CLOS has left to right argument precedence. A ''partial'' ordering of classes is a very different thing.

Also, it seems to me that unless you're misspecifying the types of the other arguments, you wouldn't get any more "no such method" errors than in a single dispatch language. You'd just get the error earlier, when you call the method instead of when you try to do something with the wrong argument types within that method. Actually, that makes it look more like a statically typed language. -- RK

Not sure where you stand on multiple inheritance, but although it's a HolyWar issue, it sure makes it a lot easier to solve certain kinds of problems -- and interestingly, raises the same dispatching issues as multimethods. This makes the two subjects look more similar to me than they might if that weren't the case.

Multiple inheritance dispatching has usually been done sort of ad hoc in most languages. Dylan was the first to really think it out carefully and pick an arguably "correct" solution, which was then copied by Python 2.3.

Python apparently went through some trials on the way, first going by depth first, then in 2.2 stripping duplicates and going "left to right", then finally discovering the Dylan "C3 resolution order".

 http://www.python.org/2.3/mro.html
 http://www.webcom.com/haahr/dylan/linearization-oopsla96.html
 Guido van Rossum's essay, Unifying types and classes in Python 2.2:
      http://www.python.org/2.2.2/descrintro.html
 http://starship.python.net/crew/timehorse/BFS_vs_MRO.html

The point here is not about Python per se, it's about the fact that they tried it several unsatisfactory ways before embracing the Dylan approach. -- dm


''"I don't define 'first' because I don't care about it."'' RK, please reread what you wrote. I only harped on the definitions of "best" and "first" because ''you'' used the terms. Please slow down, and define your terms more carefully.

A left-to-right precedence works fine for me, too, as I explained. I wouldn't claim it's "more natural" or "more OO" than all other possible schemes, but it does seem comfortable. Be assured that other schemes ''are'' possible -- if nothing else, you could go right-to-left, or in alphabetical order of parameter identifiers. Even more schemes are possible if you're willing to tolerate ambiguity as a run-time error.

In the presence of multiple inheritance, as dm pointed out, even ''single'' dispatch can cause ambiguous calls, and that's certainly also true for multimethods. The partial ordering of classes implied by the inheritance hierarchy doesn't help you disambiguate; CLOS converts this to a ''full'' ordering in a relatively intuitive matter, and uses this ordering to disambiguate. I haven't read dm's references yet, but I suspect that Dylan does something similar.

Finally, regarding "no such method", how easy it is to get this really depends on the language. With C++'s single-dispatch, if you avoid constructs with undefined behavior, it's very hard. Any concrete class has to define any virtual functions, so you a real (fully-constructed) object can't exist that doesn't define an implementation for every declared method -- and the compiler only lets you call declared methods. I'm not sure how this works in languages like Smalltalk. In CLOS, it's quite easy to declare a generic function (which is, essentially, the most general interface of a multimethod) with a corresponding implementation, but then fail to provide methods (aka multimethod implementations) that cover every possible combination of more concrete arguments. Given that there are more arguments involved, it certainly does seem to me that it would be easier to create situations that don't cover all the calls that could occur. I imagine this is usually easily defended against by providing a "most general" implementation.  -- DanMuller

That would be the way I'd do it.

In Smalltalk, when the VM can't resolve a method call, it calls #doesNotUnderstand: aMessage on the receiver. Typically that pops up a debugger. Screwing with #doesNotUnderstand is a very, very dangerous thing to do. Since Smalltalk doesn't have true delegation, redefining DNU in a class that inherits from nil (ie, nothing) is the standard way to implement proxies.

Right to left and left to right makes no difference at all. Alphabetical would be a pain. As long as you've got a predefined total ordering of the parameters, it's all the same thing and the trivial differences between them are just syntax.

Slate has ''dynamic'' argument dispatch. The caller of a method can designate what arguments it will dispatch on. And there is no predefined order of precedence among the parameters since it's got keyword parameter passing. But then again, with KPP the caller could designate what argument to dispatch on by placing it on the left. Slate's scheme is more than just a different pretty syntax, it's something fundamentally different. And its equivalent in the multiple inheritance world is Self's targeted resends.

But anyways, RalphJohnson once mentioned that he was trying to collect examples of multiple inheritance because he was looking for a single case where it was necessary, where forwarding didn't simplify the code and make it more elegant. I wouldn't know but I'm pretty sure he never did find his example.

Thanks for the refs, Doug. Gonna check them out in a bit. -- rk

I would be extremely interested in anything RalphJohnson came up with, whether positive or negative, on that topic.

Re: total ordering -- that is in fact the point. It should be a predictable total ordering, and surprisingly often, turns out not to be reasonably predictable by the programmer in a variety of languages. -- dm

Email him.

I meant something a bit more stringent than what I think you have in mind.

Assume you have tvo disjoint types A and B; neither is a subclass of the other. You have the same method defined in both classes. What does it take to determine which method you'll execute when you call (method a b) and (method b a)?

If you can determine the precedence of the arguments by a simple inspection of the message, then that's one thing. It doesn't matter whether it's left to right, right to left, alphabetical or whatever because it's all fundamentally the same thing. Smalltalk fits here. The scheme I have in mind fits here as well.

If you need to check out how the class hierarchy is laid out then that's something else.

If you need to check out how the methods are implemented or their signatures, then that's something else yet again.

And if you can't determine it until the method is actually called, then that's completely different. Slate fits here.

Oh man, I'm gonna have to find out how Self does dispatch. And find out everything about mirrors. And look up spin and knots and the ref you gave me above, and there's a book I'm supposed to read. And I was supposed to write some unit tests today. <whimper>

Okay, I started reading the C3 MRO paper, and right off the bat I'm strongly against the algorithm. I don't believe in monoticity. I think it's an absurdly artificial criterion that has no relation to the real world. The real world isn't monotonic in too many significant respects. (People concerned with public choice theory think that voting ought to be monotonic. I think they're idiots who don't know anything about choices even in the singular case.)

Further, the paper says that it's okay for some class hierarchies to be invalid because they can't be resolved monotonically; well it bloody damned well isn't! First they call subclassing a trivial operation (which it is). Then they say that such a simple operation shouldn't break monoticity (which is false). Then they make subclassing INVALID in order to preserve monoticity. WTF?

I think a concrete example of monotonicity-breaking in the real world is needed in order to demonstrate how unreasonable it is to try to preserve it.

'''Example1.''' Let's say you have the choice to invest in some technology or to hold off investing and just save the money. Let's say you're leaning towards investing because the payoff's gonna be worth while. So far so good. Now let's say you suddenly discover a third choice. You find out that researchers have just discovered this new effect which should lead to a completely different but vastly superior technology in just two year's time. Do you still invest in the old technology or do you hold off? You hold off! So not only did the introduction of a third choice change the preference ordering of the pre-existing choices, but this third choice that was introduced is a SUBCLASS of one of the existing choices. This shows that subclassing ''should'' change preference order in certain cases.

'''Example2.''' Let's say that you're looking to buy a computer. You have a choice between a high end computer and a low end computer. You don't need all that horsepower so you pick the low end computer. But before you can get out of the store, the salesman shows you this ridiculously overpowered computer for people with money to burn. What do you pick? The high end computer! Why? Because it's been built into you by evolution that you always pick the middle choice. Birds do it, humans do it, everyone does it. Given three choices on a linear scale, the middle one always seems most reasonable.

I think that C3 linearization is simply wrong. I'd rather have to deal with Slate's method dispatch. And I think multiple inheritance has nothing to do with multiple dispatch. In the case of multiple inheritance, it might be possible to create a class that's a subclass of every class, and then to ask what's its linearization. Okay, fine. In the case of multiple dispatch, there is no equivalent. Even if you implemented a multimethod for every possible permutation of types, any particular call of that method would only hit a subset of those implementations through resends. -- rk

Just a minor clarification: CLOS doesn't define a total order of ''all'' classes. It defines a total order of ''base classes'' with respect to a particular derived class. In effect, this defines an unambiguous order of preference for treating an object as being of base class type for purposes of matching the object to parameter types. For instance, if class C derives immediately from A and from B, the base class order ''for the class C'' might be (C, A, B) -- in which case a match of an object of type C to a parameter of type A will be preferred over a match to a parameter of type B. The programmer controls the precedence list by manipulating the order in which base classes are specified in the declaration of class C. The programmer could thus choose to arrange things so that the precedence order is (C, B, A). -- DanMuller

Oh, is ''that'' what it is? Well, that's a major clarification for me. Corrected the above in that light. -- rk
----
Here is an example how you can get multimethods in pure Java using the reflection API and double dispatch.

There are some areas for improvement. E.g. you can use some aspect system to inject the plumbing code into the processor; you can also pass arguments using the varargs feature introduced in Java 1.5 or just pass the args in array (like the Reflection API). These enhancements would make Java+aspects code approximately the same length as LISP and the code would be arguably clearer for the ocasional reader.

    class DataA { }
    class DataB { }
    class DataC { }

    public class Multi''''''Method''''''Processor {
        public void process(Object data) { 
                Method method = this.getClass().getMethod("processSpecialized", new Class[]{data.getClass()});
                method.invoke(this, new Object[]{data});
        }
        private void processSpecialized(Object data) { System.out.println(data.getClass().getName()); }
        private void processSpecialized(DataA data) { System.out.println("A"); }
        private void processSpecialized(DataB data) { System.out.println("B"); }

        public static void main(String[] args) {
            Processable[] data = {
                new DataA(), new DataB(), new DataC(), new Processable(){}
            };
            Multi''''''Method''''''Processor mmp = new Multi''''''Method''''''Processor();
            for (int i = 0; i < data.length; i++) {
                mmp.process(data[i]);
            }
        }
    }


The same approach in Python gives even shorter/clearer code if we don't count that we're using method names to keep the type info (since the Python variables and function parameters are typeless.) Again, we could declare 'process'  as free
function and attach it to the class object at runtime.


    class X: pass
    class Y: pass
        
    class Multi''''''Method''''''Processor:
        def process(self, data):
            try:
                method = getattr(self, "_process%s" % data.__class__.__name__)
                method(data)
            except Attribute''''''Error:
                self._process__generic__(data)

        def _processX(self, data): print "X"
        def _processY(self, data): print "Y"
        def _processZ(self, data): print "Z"

        def _process__generic__(self, data): 
            print "Processing generic %s with value of %s" % (data.__class__.__name__, data)
        
    mmp = Multi''''''Method''''''Processor()

    for datum in (X(), Y(), 1, "string"): 
        mmp.process(datum)


-- DimitarDimitrov

----
Earlier on this page I wrote, in reference to CommonLisp's multimethods and access to class data members: "If you do not give multimethods access, this implies that you must also have regular (single) methods, and that multimethods are second-class compared to them. ... I could imagine distinguishing "privileged" and "unprivileged" multimethods, I suppose."

In the meantime, I've learned that you can use the package system in CommonLisp to manage such things. You can't ''completely'' hide symbols, but you can make it clear which are intended to be exported from the package, thus public, and which are not. A user of a package must use special syntax to access unexported symbols. Since access to most things revolves around symbols -- functions, classes, data members, you name it -- this effectively gives you a way to control access to the internals of a class, and to make some multimethods privileged by defining them in the same package as the class. In many OO languages, the packaging functionality is intertwined with class definitions. I like the separation of these concepts in CommonLisp, since they're actually orthogonal. (C++ gives a nod in this direction by providing namespaces as a separate packaging mechanism from classes.)

-- DanMuller

----
Couldn't multimethods be implemented using a switch-like behaviour on the class type?  Imagine in C#/Java we have a switch/cast statement for easier reuse, where switching on the type also converts the variable into the given type.

That is

 Hand myHand = getHand();
 CastSwitch(myHand)
 {
   case Rock:
     //dosomethingwithmyHandasRock
   break;
   case Paper:
     //dosomethingwithmyHandasPaper
   break;
   case Scissors:
     //dosomethingwithmyHandasScissors
   break;
   default: //myHand's type is not derived from nor is any of the above subclasses of Hand - in this case, it is treated as type Hand.
     throw new UnknownHandException()
   break;
 }

Doesn't this provide all of the power of multimethods without turning the calling syntax on it's side?  Either way, shouldn't multimethods be avoided?  After all, they break encapsulation - external polymorphism is a DesignSmell (although often a necessary one).  Of course, this would be much better in a language that allows custom blocks, so my theoretical "CastSwitch" construct could be implemented (a statically-typed RubyLanguage?).
* You can define different versions of multimethods in different places, and make new versions for your own types. You can't do that with a central TypeCase.

----
See also: ExternalPolymorphism, GenericFunction''''''s, MultipleDispatch, DoubleDispatch, ImplementingMultipleDispatch, PredicateDispatching
----
CategoryLanguageFeature CategoryPolymorphism