Thursday, 24 January 2008

Single Dispatch, Multiple dispatch and the Visitor Pattern

Every now and then the question of the Visitor pattern comes up, and sometimes we forget why we need the visitor pattern in the first place! The Visitor pattern is a way to implement double dispatch in single dispatch languages like C++ and Java.

Single Dispatch

The best method that I've discovered for remembering what single dispatch is, is by relating it to compile time vs. runtime function resolution, or overloading vs. overriding.

When you do overloading, the function (or method) that will be executed within the calling context is determined at compile time. Overriding is the ability to choose the method to execute at runtime (it's called single dispatch since you can only use one parameter to the function to determine which one to execute, which is the implicit "this" parameter in curly bracket languages).

Example

I'll illustrate with an example. Let's say that you have application that manages you share portfolio. You have two types of shares, a normal share and a preference share, and you wish to generate a report on the value of your portfolio. The value of a preference share is calculated differently to that of a normal share.

In Java, we'll have something like this:

class Share {
}

class PreferenceShare extends Share {
}


class PortfolioWriter {

public void write(Share share) {
System.out.println("Share");
}

public void write(PreferenceShare preferenceShare) {
System.out.println("PreferenceShare");
}
}


public class SingleDispatch {

public static void main(String[] args) {

PortfolioWriter writer = new PortfolioWriter();

Share share = new Share();
writer.write(share);

PreferenceShare preferenceShare = new PreferenceShare();
writer.write(preferenceShare);

Share shareReferenceToPreferenceShare = new PreferenceShare();
writer.write(shareReferenceToPreferenceShare); // 1
}
}



And here's the output:

$ java SingleDispatch
Share
PreferenceShare
Share


Looking at line marked with "// 1" in the code:
The method that is called on the writer object is determined at compile time, and at compile time the parameter is a Share reference. It's not possible for the compiler to know that the reference actually point to an instance of PreferenceShare!

Lisp

In Lisp, you have multiple dispatch, so you can do something like this


(defgeneric write (generator instrument))

(defmethod write ((g portfolio-generator) (s share))
(format t "portfolio-generator: a share"))

(defmethod write((g portfolio-generator) (p preference-share))
(format t "portfolio-generator: a preference share"))


And when you call "(write ...)" with a report-generator instance and either a share or preference-share instance, you will get the expected result!


In fact, in Lisp, if you have two (or more) type hierarchies you can choose to specialize the method at any point in the hierarchy of any of the parameters. This is very powerful, and the C++/Java object model looks like Lisp's poor cousin in comparison.

Conclusion

You can imagine the limitation of single dispatch when you have a collection of objects that conform to some interface. If you want to do something on each instance (like generate a report), but you don't want to inject that logic into each class, you have to use a visitor pattern to get around the single dispatch limitation.


Wikipedia references

Visitor Pattern
Single Dispatch
Multiple Dispatch

No comments: