Talk:Multiple dispatch
This is the talk page for discussing improvements to the Multiple dispatch article. This is not a forum for general discussion of the article's subject. |
Article policies
|
Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL |
![]() | This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
|
Let's divide the article into two articles: Multimethods and Multiple dispatch
editMultimethods != multiple dispatch. Multiple dispatch is a broader concept. Multimethods are just a syntax construct and just one way of implementing multiple dispatch. Other ways are chains of virtual methods (as in Visitor pattern) or instanceofs. Unnamed666 (talk) 12:42, 13 October 2014 (UTC)
Incorrect C++ Template example
editThe C++ example with templates does not implement double dispatch. It implements something akin to function overloading; but since all the arguments are dispatched upon statically, this is certainly not double-dispatch. In fact, the page for double dispatch explicitly points this out and describes how to implement double dispatch in C++ using the visitor pattern, and it also states explicitly why using function overloading does not achieve double dispatch. If I hear no objections, I will remove the C++ template example from the page in a while. 74.125.57.33 (talk) 10:17, 17 February 2010 (UTC)
A preposition seems to be missing in the first sentence of this article:
...a function or method can be specialized on run time the type of more than one of its arguments.
Specialized to or with regard to perhaps?
—Preceding unsigned comment added by 62.113.133.134 (talk) 15:49, 2 October 2008 (UTC)
Is the Java example poorly chosen, since the following would work just as well (via method overloading), and doesn't need anything as exotic as multi-dispatch?
/* Example using run time type comparison via Java's "instanceof" operator */ class Asteroid extends Thing { public void collide_with(Asteroid other) { } public void collide_with(Spaceship other) { } } class Spaceship extends Thing { public void collide_with(Asteroid other) { } public void collide_with(Spaceship other) { } }
What am I missing?
Hi You are right. That would work, but thats not really Multiple dispatch. It would be multiple dispatch if you had
/*Note:The following code is illegal in Java, however it would be legal if Java supported Multiple-dispatch*/ class Thing{ public void collide_with(Thing other){ //Thing-Thing collision code } } class Test{ void Main(){ Thing t1 = new Asteroid(); Thing t2 = new Spaceship(); t1.collide_with(t2); //Multiple Dispatch would call Asteroid.collide_with(Spaceship) } }
In Single-dispatch systems, subtype polymorphism is *ONLY* permitted on the receiver object of the method call, so the above code would be illegal in Java. If Java supported Multiple Dispatch, this call would work because polymorphism would be applied to the parameters aswell, when selecting the version of collide_with method to call. Think of Multiple-dispatch as an advanced form of polymorphism. It is not supported by c++/java because there it has some overhead and possibility of message ambiguity during run-time.
155.140.121.227 16:40, 22 January 2007 (UTC)Asim Sinha
I don't agree. We can use multiple dispatch in Java. Your code should be modified:
public abstract class Thing {
public abstract void collide(Thing thing);
protected abstract void collideWithAsteroid(Asteroid asteroid);
protected abstract void collideWithSpaceship(Spaceship spaceship);
}
public class Asteroid extends Thing {
@Override
public void collide(Thing thing) {
// Second dispatch
thing.collideWithAsteroid(this);
}
@Override
protected void collideWithAsteroid(Asteroid asteroid) {
// asteroid-asteroid collision code
}
@Override
protected void collideWithSpaceship(Spaceship spaceship) {
// spaceship-asteroid collision code
}
}
public class Spaceship extends Thing {
@Override
public void collide(Thing thing) {
// Second dispatch
thing.collideWithSpaceship(this);
}
@Override
protected void collideWithAsteroid(Asteroid asteroid) {
// asteroid-spaceship collision code
}
@Override
protected void collideWithSpaceship(Spaceship spaceship) {
// spaceship-spaceship collision code
}
}
public class Main {
public static void main(String[] args) {
Asteroid asteroid = new Asteroid();
Spaceship spaceship = new Spaceship();
asteroid.collide(spaceship);
spaceship.collide(spaceship);
}
}
This is a true dynamic double dispatch. You can extend this to triple or quaternary dispatch if you wish.
VB9 multimethods
editErik Meijer (one of VB9 designers) claims that Visual Basic 9 has support for multimethods, here and here. I don't know VB9 syntax, but it would be cool if someone should provide an example and clarify it. —The preceding unsigned comment was added by 161.53.243.217 (talk) 08:41, 22 February 2007 (UTC).
Critique?
editThis article contains a sore lack of critique of multiple dispatch as a technique. What are the pros and cons of it? RyanTMulligan 23:46, 9 June 2007 (UTC)
Re: Critique?
editMultiple dispatch is often essential in software engineering like Visitor pattern. When you have a very dynamic and potentially extensible system where user defined types need to interact with each other in a polymorphic way, multiple dispatch provides the most flexible and intuitive solutions. Even Bjarne Stroustrup admitted that he rejected multi-methods with regret because he couldn't find an acceptable way to implement it in c++. Cons of multiple dispatch are that its harder to prove type safety, incurs atleast some overhead at run-time (to determine the best method to dispatch) and possibility of message ambiguity at run-time. Considering that Java and .Net are providing more run-time type-checking capabilities with each new version, the small overhead in multiple dispatch should not be a limiting factor anymore. I truly think languages could benefit hugely by implementing multiple dispatch.
- It's incorrect that multiple dispatch inevitably incurs runtime overhead. If the types are known at compile time, then it is often possible to perform the dispatch entirely at compile time. e.g. the Julia language has dynamic multiple dispatch, which occurs at runtime in cases where the types aren't known, but often occurs at compile-time because typically the types are known to the compiler. (When a function is called with a given argument-type signature, Julia JIT-compiles a specialized version for those argument types, and this includes compile-time dispatch, and sometimes even inlining, of any functions called within that function if possible.) Because of this, Julia uses multiple dispatch even for something as basic as
+
(addition) on built-in numeric types (e.g. hardware integers), without incurring runtime overhead (attaining near-C performance for typical code). — Steven G. Johnson (talk) 15:33, 13 July 2017 (UTC)
Static types vs. dynamic types
editWould it be useful to note the difference between static types and dynamic types (and how multiple dispatch operates on the dynamic, aka run-time type) before the C++ section? Text such as
When working with languages that can discriminate data types at compile-time, selecting among the alternatives can occur at compile-time.
makes it unclear as to whether we are talking about static types or dynamic types. The above would seem to indicate that any statically typed language that allows function overloading would allow multiple dispatch, but this is not the case. In fact, is the above actually true? How could one always determine run-time data types at compile time?
Labreuer 15:41, 29 October 2007 (UTC)
The text as given is *not* true. Java can "discriminate data types at compile-time". It is not capable however (in the general case) of "selecting among the alternatives [that] can occur at compile-time" because of this. Consider the simple, hypothetical case of iterating a List<Shape> and calling the draw() method on a sequence of arbitrary Point, Line, Rectangle, Oval subclasses of the Shape abstract class/interface. The JVM *must* resolve which implementation of draw() to call *at run-time*; there is no way for the compiler to do this at compile-time. (Again, there is an implied assumption here of dispatch by type - but that is only one form of multiple dispatch.) Sounds, also, a bit like that section is (confusingly, again) bringing method *overloading* into consideration - even though method overloading (same name, different arity and/or args) has nothing to do with multi-methods/multiple dispatch. 185.55.60.122 (talk) 11:24, 16 April 2015 (UTC)
Java without multiple dispatch?
editIs the following code segment not multiple dispatch? I realize that Java is not selecting the method at runtime, but instead at compile time (which separates it from dynamic dispatch). Perhaps added clarification in the article would help:
public class Manipulator { public void manipulate(List list) { System.out.println("List"); } public void manipulate(Set set) { System.out.println("Set"); } public void manipulate(Queue queue) { System.out.println("Queue"); } } class UseMan { public static void main(String[] args) { new Manipulator().manipulate(new HashSet()); new Manipulator().manipulate(new ArrayList()); // new Manipulator().manipulate(new LinkedList()); // line above is a compiler error - ambiguous invocation } }
The Java code above prints:
'Set' 'List'
Looks and smells like multiple dispatch to me - certainly not dynamic dispatch. Is this not right? .digamma (talk) 22:04, 16 February 2008 (UTC)
- To me this is not multiple dispatch, however I may be wrong because I just looked at this technique :)
- What you are doing here is method overloading (same name, different arguments) and this can be achieved statically (at compilation). —Preceding unsigned comment added by 62.17.152.241 (talk) 17:21, 21 February 2008 (UTC)
- Yes, this is method overloading but method overloading is a key aspect of multiple dispatch (see article). .digamma (talk) 11:14, 2 March 2008 (UTC)
- yes it is method overloading, but what makes you think it is multiple dispatch? The choice what method to execute depends only on the (dynamic) type of the argument of maniplate(), that is: only on the type of ONE object, whereas in multiple dispatch it depends on the type of MORE THAN ONE objects. It doesn't matter how many Interfaces the type of this ONE object implements, it's still just one object. 84.74.154.33 (talk) 20:27, 22 May 2008 (UTC)
- The method could just as well have multiple arguments, in which case it would depend on the type of multiple objects. — Preceding unsigned comment added by 82.171.109.65 (talk) 21:34, 10 January 2013 (UTC)
- Re "The choice what method to execute depends only on the (dynamic) type of the argument". This is wrong. Which method is called depends (in Java) *only* on the statically declared type of the reference passed to the method. The compiler chooses, at compile time. There is neither multiple, nor single dispatch, involved here - only method overloading. (The article - in so much as it keeps confusing the two - is wrong.) 185.55.60.122 (talk) 11:43, 16 April 2015 (UTC)
- yes it is method overloading, but what makes you think it is multiple dispatch? The choice what method to execute depends only on the (dynamic) type of the argument of maniplate(), that is: only on the type of ONE object, whereas in multiple dispatch it depends on the type of MORE THAN ONE objects. It doesn't matter how many Interfaces the type of this ONE object implements, it's still just one object. 84.74.154.33 (talk) 20:27, 22 May 2008 (UTC)
- Note that when you say 'new HashSet()' the compiler already knows the type of the expression i.e HashSet so this is simlply overloading. —Preceding unsigned comment added by 155.140.133.254 (talk) 11:19, 3 February 2009 (UTC)
- Yes, this is method overloading but method overloading is a key aspect of multiple dispatch (see article). .digamma (talk) 11:14, 2 March 2008 (UTC)
This is absolutely NOT multiple dispatch, it is static overloading. This is a good point though, as it is a common point of confusion; perhaps the article could mention this. 71.199.114.80 (talk) 18:42, 3 August 2009 (UTC)Donna Malayeri
Agreed. Definitely NOT (any form of) multiple dispatch (or, in fact, even single dispatch). It is just method overloading (same name, different types). Which method is called is resolved by the compiler at compile-time, in this code. (Imagine, for example, the same code but with the methods being static - still method overloading, and with even less chance of being confused for multiple dispatch.) 185.55.60.122 (talk) 11:37, 16 April 2015 (UTC)
Object-capability security considerations
editThere seems be nothing that prevents multimethods from violating strong encapsulation of objects.
Strong encapsulation of objects plus unforgable references are the base assumption that all of object-capability based security rests on.
I am mostly in faviour of representing objects via message passing and closures (procedures with lexical scoping) as that shunts the whole dispatching desicions proplem to the called object. How that dispatch is resolved is then handled on object by object bases. (Interface and implementation inheritenche, polymorphism of methods and all that stuff) --Zarutian (talk) 19:17, 14 May 2009 (UTC)
Badly broken definition
editThe introductory paragraph currently says
- Multiple dispatch or multimethods is the feature of some object-oriented programming languages in which a function or method can be dynamically dispatched based on the run time (dynamic) type of more than one of its arguments. This is similar to function overloading, which is statically dispatched based on static types.
This is variously incorrect.
Multiple dispatch simply means there's dispatch, and it's not single dispatch.
In contrast to the definition given, multiple dispatch can be done in functional non-OO languages (eg), can occur at compile time, and can also depend on:
- the number of arguments,
- the static types of arguments,
- argument values rather than types (predicate dispatch),
- the names of arguments (in languages with named argument passing),
- the return type expected,
- or combinations of these.
Incidentally but similarly, function overloading can occur at runtime, and be based on dynamic type, and/or on expected return type.
The current introductory definition is quite misleading.
I propose the introductory paragraph be replaced by something like the following:
- In some programming languages, functions or methods can have several variants, and which variant is chosen to handle a call, depends on the call. Languages differ in what call characteristics determine which variant a call gets dispatched to. Multiple dispatch is when more than one characteristic affects the choice.
- A call has several characteristics. It has some number of arguments (its arity). Each argument counts as one characteristic, and has a value, potentially a type (static and/or a dynamic), and potentially a name. A method call (but not a function call) has an object. And a call potentially has an expected return type. In single dispatch, just one of these determines dispatch. For instance, when a single argument (the first one) determines function dispatch. Or when method dispatch is determined by the object alone. But when, for example, the type and/or value of two arguments affects function dispatch, that is multiple dispatch.
- There can be ambiguity. At an implementation level, the presence of runtime dispatch code, single or multiple, is unambiguous. But at a language level, it is less clear. Multiple dispatch can be viewed as single dispatch on a tuple of arguments. Some languages define arity as part of a function's name, so foo(x) and foo(x,y) are calls to different functions foo/1 and foo/2. And the relationship between language and implementation may not be simple. A language's compiler may, sometimes or always, be able to avoid creating runtime dispatch code. So what looks like multiple dispatch, may be compiled into runtime single dispatch, or statically resolved. Usually the ambiguity isn't a problem.
- Multiple dispatch is an aspect of, and sometimes refered to by the name of, multimethods, multi-methods, generic functions, function overloading, open methods, and several other things, depending on the programming language. Dispatch (single or multiple) which uses argument type, is type polymorphism. Using argument value is predicate dispatch. And using return type is return type polymorphism. Dispatch done generally at runtime is dynamic dispatch.
Comments? 98.216.110.149 (talk) 22:24, 6 July 2009 (UTC)
Absolutely agree with the above post. Function overloading, which often, but not always, gets dispatched statically, is different from multiple dispatch. 71.199.114.80 (talk) 18:30, 3 August 2009 (UTC) Donna Malayeri
I note single dispatch redirects to dynamic dispatch. Here would be better. And off topic, dynamic dispatch starts by defining itself as OO message passing.
I second. I was just writing a simple (Java, generics) multi-method implementation that dispatches on the result value of an *arbitrary* function (the dispatch function). This has nothing to do with the types of the arguments (unless the user *chooses* to use type (or types) as the result of the dispatch function). I was going to link to this article in the Javadoc, but as it stands the definition is more confusing than helpful. In particular:
- Multi-methods (in the general case) are much broader than just dispatch by one/many types: dispatch by arbitrary discrimination is both possible and useful. (In fact, I'd argue extending dispatch from one type to multiple - but nothing else - isn't much less limiting than type-discriminated single dispatch.)
- This technique isn't limited to OO-languages. In fact, it is probably more natural to FP-languages. Perhaps the slant of the current article derives from the fact that OO-languages generally either need a) built in support for MM, or b) some sort of design pattern, mini-framework to implement it.
- Multi-methods are not "an extension of single-dispatch polymorphism" IMHO. Rather, single-dispatch, type-discriminated polymorphism, is a (doubly) restricted subset of general MM capabilities (albeit one that is common to C++/Java-family OO languages). Aside: extension also implies (to me) that MM 'comes after' or 'was developed later' - they may or may not be true.
- It is note just the summary that is incorrect - "the selected method is simply the one whose arguments match the number and type of the function call". Again with the types. (Perhaps this is the case with CLOS, which is mentioned next - I'm not a CLOS user - though it would surprise me if so.)
- From the 'Data Types' section: "When working with languages that can discriminate data types at compile-time, selecting among the alternatives can occur at compile-time." This isn't necessarily true. It isn't normally the case in Java for example. Unless you confuse method name (same method name, different types) overloading, as the text goes on to do, with MM. (And, again - with the types.)
- The Common Lisp example appears to be a CLOS example, which is not stated.
- I don't think the example given in Java, of emulating multiple dispatch really counts: it is only one step up from doubly-nested 'if' blocks.86.140.232.102 (talk) 17:18, 15 April 2015 (UTC)
Missing language: Prolog implementations with objects
editVisual Prolog (www.pdc.dk) has both types and a variety of mechanisms comparable to compile-time overloading while other OOP Prolog implementions would fall under multimethods - yet this topic (so often associated with Common Lisp, or more recently, Clojure) has no mention of post-1974 Prolog implementations let alone post-1980. and we are now in 2010. One reason may be that some key Prolog vendors in recent years have tended to focus on writing applications for clients (especially after Prologia (Frane, home of Prolog IV) was sold. But Prolog-style method overloading for objects implementing clauses is as old as OOP in Prolog. Given that a principal family of non-procedural languages is not mentioned, could some CS PhD please correct this omission? G. Robert Shiplett 10:36, 7 October 2010 (UTC)
- I had the same thought, but it might be not that simple. I imagine an OOP to have reference type objects, term objects or both. Lets look at term objects first. Assume we can just use terms for term objects, such as point(1,2), coloredpoint(1,2,red), redpoint(1,2). But unification usally cannot decided sub class relationship. So if I do something allong:
- collide_with(asteroid(...), asteroid(...)) :- /* case 1 */
- collide_with(asteroid(...), spaceship(...)) :- /* case 2 */
- collide_with(spaceship(...), asteroid(...)) :- /* case 3 */
- collide_with(spaceship(...), spaceship(...)) :- /* case 4 */
- I might not capture that the first or second argument is instance of. Instead I might maybe be able by such code to check for an exact type. Currently I don't know what OO Prolog systems offer here. Changing the first argument into a receiver surely helps:
- :- class asteroid.
- collide_with(X) :- X instanceof asteroid, !, /* case 1 */
- collide_with(X) :- X instanceof spaceship, !, /* case 2 */
- :- end.
- :- class spaceship.
- collide_with(X) :- X instanceof asteroid, !, /* case 3 */
- collide_with(X) :- X instanceof spaceship, !, /* case 4 */
- :- end.
- But still the instanceof check is not anymore unification, so not sure whether some indexing can work here. Jan Burse (talk) 14:33, 23 January 2016 (UTC)
function overloading is not multiple dispatching
editThis article states:
Multiple dispatch or multimethods or function overloading is the feature of some object-oriented programming languages in which a function or method can be dynamically dispatched
But the double dispatch article explains why that is not true http://en.wikipedia.org/wiki/Double_dispatch#Double_dispatch_is_more_than_function_overloading —Preceding unsigned comment added by 188.108.97.59 (talk) 23:52, 16 March 2011 (UTC)
Let's remove the non-multiple dispatch examples.
editSince the topic is multiple dispatch, let's remove the confusing examples for languages which do not support multiple dispatch. We could replace them with a link to Double dispatch where appropriate, or perhaps link to external articles with coding tips how to hack together mechanisms similar to multiple dispatch in languages which do not support it.
To be more specific, since C, C++ and Java do not support multiple dispatch as a built-in language mechanism, let's remove those examples. They are also examples of bad code -- we'd be hard pressed to find Java, C, or C++ guidelines recommending such approaches. (The dynamic_cast/instanceof chain of if-else branches is somewhat infamous.)
If the goal is to illustrate how multiple dispatch might work, then maybe just one example would suffice. — Preceding unsigned comment added by 69.253.247.233 (talk) 00:37, 14 July 2011 (UTC)
Java and C++ do support multiple dispatch. Just because there is no special syntax for multiple dispatch, does not mean these languages do not support this mechanism. Multiple dispatch is simply dispatch on multiple types. It does not matter whether this dispatch is written via a special language construct, a chain of virtual methods or instanceofs. (Unnamed666 (talk) 12:19, 13 October 2014 (UTC))
- That's a bit like arguing you could do function programming in Java before is had support for lambdas, etc. Well, yes, you could - by dint of skill, effort and a lot of conventions (contortions?). Sort of. (Also, a long block of 'instanceof' if statements is not multiple dispatch; it is what you have to do if you don't *have* multiple dispatch in your language (or a library/framework to emulate it). 185.55.60.122 (talk) 11:57, 16 April 2015 (UTC)
Re: Let's remove the non-multiple dispatch examples.
editI entirely agree, I'll remove the C section. How did it get there anyway? C isn't even object-oriented, for goodness' sake. — Preceding unsigned comment added by 79.124.84.16 (talk) 22:04, 9 November 2011 (UTC)
Though I tend to agree (with removing the C example), don't presume OO is a prerequisite for multiple dispatch - it isn't. 185.55.60.122 (talk) 13:50, 16 April 2015 (UTC)
Multiple dispatch and C
editThe C example should be removed entirely. Since someone thinks it has certain educational value, I propose to add a short paragraph which: 1) says that C is not an object-oriented language and has nothing to do with multiple dispatch; 2) says that one way to emulate multiple dispatch is by means of a branch table and provide link to that article, which essentially makes the example pointless. This is what we have now, more or less, save for the link, which I'll add shortly. — Preceding unsigned comment added by 79.124.84.16 (talk) 19:47, 15 November 2011 (UTC)
- C (2011) has something similar to multiple dispatch, now that it has the _Generic keyword. This allows a single pseudo-function name to be called to invoked one of several actual functions, depending on the call parameter types. This is not, however, dynamic dispatch, since the target function is resolved at compile time. — Loadmaster (talk) 20:03, 18 April 2013 (UTC)
- Interesting. But presumably this is akin, more or less, to method overloading as in Java, where the compile-time type of the variable/pointer determines the called function? (So not really MD/MM?) 185.55.60.122 (talk) 13:54, 16 April 2015 (UTC)
Python Example. CLOS related.
editThe end of the Python example states:
"Functionally, this is very similar to the CLOS example, but the syntax is conventional Python."
That doesn't make any sense to me: you still use Common Lisp syntax while using CLOS. If it is making mention that CLOS is an addition to the language (which it technically isn't); then that line needs to be modified. It has nothing to do with the article at large. 2601:41:4104:ED70:D1BA:620B:FC89:F834 (talk) 05:29, 2 March 2016 (UTC) Elijah Beale
Java emulated implementation results in StackOverflowError
editUsing the implementation as provided on the prior version with calls against identifiers typed as Collideable result in a StackOverflowError
(in Java 7, Java 8, & Java 12) because the type of the parameter passed in is a Collideable which binds to the interface not to the instance. This is the same behavior as defining the interface instead as an abstract class with a concrete void collideWith(Collideable)
implementation in the abstract class (for support in Java 7). Both of these approaches are verified with calls as follows:
Collideable a = new Asteroid();
Collideable s = new Spaceship();
a.collideWith(s);
a.collideWith(a);
s.collideWith(s);
s.collideWith(a);
However, moving the implementation of the default method from the interface down into the concrete classes (of course, removing the default
keyword) allows the code to work with the above calls. If instead, the variables were typed as Asteroid a
, and Spaceship s
then the prior default implementation in the interface works but there's no abstraction in the identifier declarations (in the caller) - which having this abstraction in the caller is usually the desired approach.
Consequently, Java appears to do the right thing at runtime with the change to the interface. Alas, default
isn't doing what people think it will do (it doesn't actually place the default implementation into the implementing subclasses). .digamma (talk) 19:53, 19 November 2019 (UTC)