DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
Refcards Trend Reports Events Over 2 million developers have joined DZone. Join Today! Thanks for visiting DZone today,
Edit Profile Manage Email Subscriptions Moderation Admin Console How to Post to DZone Article Submission Guidelines
View Profile
Sign Out
Refcards
Trend Reports
Events
Zones
Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Partner Zones AWS Cloud
by AWS Developer Relations
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Partner Zones
AWS Cloud
by AWS Developer Relations
The Latest "Software Integration: The Intersection of APIs, Microservices, and Cloud-Based Systems" Trend Report
Get the report
  1. DZone
  2. Coding
  3. Languages
  4. Multiple Dispatch: A Fix for the Problems of Single Dispatch Languages

Multiple Dispatch: A Fix for the Problems of Single Dispatch Languages

Axel Rauschmayer user avatar by
Axel Rauschmayer
·
May. 05, 09 · Interview
Like (0)
Save
Tweet
Share
14.28K Views

Join the DZone community and get the full member experience.

Join For Free

Almost all well-known object oriented languages (Java, C#, JavaScript, Python, Ruby, ...) have single dispatch: Methods are chosen depending on the (single) receiver of a message. On the other hand, there is multiple dispatch which is an interesting mix of functional method selection with mutable state. It is used in less-known object-oriented languages such as Common Lisp.

In this article, we'll first look at Java's single dispatch and Java's overloading and then use what we have learned to understand multiple dispatch and how it solves some design dilemmas that can't be solved with single dispatch.

Let's start with dynamic dispatch:

    public class Empty extends Object {

@Override
public String toString() {
return "Empty";
}

public static void main(String[] args) {
Object empty = new Empty();
System.out.println(empty.toString());
}
}

What is the output of this program? It is “Empty”. If this seems obvious, it is because you are already very familiar with dynamic dispatch: Java determines at runtime what class an instance belongs to and chooses the appropriate, possibly overridden, method. For the example above, this means that we don't use the toString() method from class Object, but the toString() method from class Empty. In some languages, such as C++, you have to explicitly state that you want dynamic dispatch.

Now on to overloading, another way of picking a method implementation.

    public class Printer {
public void print(String str) {
System.out.println("String: "+str);
}
public void print(Object obj) {
System.out.println("Object: "+obj);
}
public static void main(String[] args) {
Object obj = "abc";
new Printer().print(obj);
}
}

Here the output is “Object: abc”. The method implementation is chosen statically, at compile time: Internally, the compiler uses the static types of the method arguments to disambiguate the method names. This time, the result is unexpected, even really good Java programmers that I've asked get it wrong. Due to dynamic dispatch feeling so natural for the receiver of a message (=“this”), we expect it to work the same for the arguments. There is a kind of asymmetry between the receiver and the arguments of a method and that asymmetry is reflected in the invocation syntax, too.

With multiple dispatch, methods become top-level constructs. This is similar to implementing a single dispatch method “foo” with two arguments as a static method:
    public static void foo(this, arg1, arg2) {
if (this instanceof A) {
...
} else if (this instanceof B) {
...
} ...
}

The message receiver “this” becomes just another argument and all variations of the method are united in a single place (having this kind of view on a method helps with understanding implementations that use polymorphism, but I digress). Instead of the myObj.foo(x,y) you now invoke foo as foo(myObj,x,y). This is still single dispatch. Multiple dispatch nests instance-of checks for arg1 and arg2 inside the checks for “this”. Only after checking the types of all arguments do we decide which variation of the method to use. Common Lisp calls foo a generic function and the code snippets inside it methods.

Note that the if statements were for illustration only, languages with multiple dispatch have efficient algorithms for performing the checks and selecting a method.


What advantages does this have?

A generic function can “belong” to several classes. This helps whenever method arguments are not true parameters (data), but rather collaborators (that offer services) for an algorithm. For example, if you have a method Database.export(Filesystem,UserFeedback), this method might contain as many Database invocations as Filesystem invocations. The special case of binary operators as methods exhibits the same difficulty: Should the operator “String + Integer” be considered part of class Integer or part of class String? It is for a reason that UML has special diagrams for collaborations and that these diagrams cross-cut classes.

Another example of collaborating objects is the visitor pattern: It is a clumsy simulation of multiple dispatch with single dispatch. What you have at its core is the object for the algorithm collaborating with the object for the data. With multiple dispatch, things are much simpler, there is less code to write and the data objects do not have to be prepared for visitors. Interestingly, even the explicit object for the algorithm disappears, because the generic function replaces it.

Another area where the asymmetry of single dispatch shows is with the null value. For example, "abc".equals(null) is OK while null.equals("abc") causes an exception (and is not even directly syntactically correct). If you introduce null checks as selection criterion for methods, then handling null values is simple with multiple dispatch.

Extending a class is trivial with multiple dispatch, just create a new generic function that accepts instances of that class as its argument. With Java, people often overlook external static methods that actually extend a given class, because they don't know where to look. For example, if you don't know Java well, you might be puzzled as to why List has no sort() method. If you do, you know that the class Collections has a static method sort(List) that you have to use. In languages with multiple dispatch, one already assumes that in general, a generic function is relevant for several classes. The development tools help one with finding all functions that apply to a given class, making sure that code is re-used instead of re-invented.

Having code tightly integrated with the data is less desirable in settings where you serialize objects. With generic functions, code and data are separate and it is easier to use the same data structures on the server and the client. The server can host a lot of code that generates or modifies data. The client only has to display the data and lets the server handle the more complicated stuff. This is a frequent scenario when doing client-server communication with the Google Web Toolkit. As Java does not have generic functions, the server-only functionality has to be moved to external static helper methods. Consequently, things are even less encapsulated, slightly messy and one loses polymorphism.


Predicate dispatch

A generalization of multiple dispatch is predicate dispatch. With multiple dispatch, the methods of a function are selected based on the types of the arguments. With predicate dispatch, more complex conditions can be specified. This simplifies changing the behavior of an instance depending on its state and obviates the need for the strategy pattern. For example: Let's assume that an instance of class Bar has to behave differently if an error flag is set to true. The relevant generic functions will contain one method that is invoked if the flag is true and another one if the flag is false. Attached to the first method is an explicit selection condition such as myBar.error. The second method has a condition such as !myBar.error. These selection conditions are additional ways of classifying instances. One could say that myBar changes its class depending on the value of its field error.

Conclusion


We have seen that multiple dispatch can do several things that single dispatch can't. But I think that both are complementary. Message passing is a nice and clean metaphor for method invocation that works well with distributed computing. It views objects as components that provide services. On the other hand, objects-as-data result in phenomena (binary operators etc.) that are best implemented with multiple dispatch.

Further reading

The basics in depth

  • “Multiple dispatch in practice” by Radu Muschevici, Alex Potanin, Ewan Tempero, James Noble.
  • “Expressive and Modular Predicate Dispatch for Java” by Todd Millstein, Christopher Frost, Jason Ryder, Alessandro Warth. A paper about extending Java with predicate dispatch.
  • “Visitor Pattern Versus Multimethods”. Explains how the two relate, via the Nice programming language.

Advanced topics

  • “Python 3000 - Adaptation or Generic Functions?” by Guido van van Rossum. Illustrates how generic functions subsume adaptation.
  • “The DCI Architecture: A New Vision of Object-Oriented Programming” by Trygve Reenskaug, James O. Coplien. Explains that objects-as-data are fairly stable whereas the algorithms that span several objects are not. I suspect that their solution could benefit from multiple dispatch.

Languages close to Java with multiple dispatch

  • “The MultiJava Project”. Extends Java with multiple dispatch. The papers on that site provide more information on multiple dispatch.
  • “JPred: Practical Predicate Dispatch for Java”. Extends Java with predicate dispatch.
  • “The Nice programming language”. A JVM-based language with multiple dispatch whose syntax stays relatively close to Java.

From http://2ality.blogspot.com/

Java (programming language) Object (computer science)

Opinions expressed by DZone contributors are their own.

Popular on DZone

  • Master Spring Boot 3 With GraalVM Native Image
  • 10 Most Popular Frameworks for Building RESTful APIs
  • Isolating Noisy Neighbors in Distributed Systems: The Power of Shuffle-Sharding
  • Scaling Your Testing Efforts With Cloud-Based Testing Tools

Comments

Partner Resources

X

ABOUT US

  • About DZone
  • Send feedback
  • Careers
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 600 Park Offices Drive
  • Suite 300
  • Durham, NC 27709
  • support@dzone.com
  • +1 (919) 678-0300

Let's be friends: