What is multiple dispatch? Read on.
STYPE obj = new RTYPE(); obj.foo((A)a, (B)b, (C)c)will call the foo method on the instance obj. While obj is declared to be of type STYPE, its actual run-time type is that of its constructor, namely RTYPE, which (in the above example) must be a subtype (extension) of STYPE. If both of these types define a method for foo with parameter signature A, B, C, then the method actually called is that of the more refined type, namely RTYPE's version.
In summary, the dispatch for foo is based solely on the actual run-time type of obj, and has nothing at all to do with the run-time type of the supplied parameters. Most compilers will search for an appropriate definition of foo based on the supplied parameters' declared types. But that is done at compile-time, when the parameters' actual types may be unknown. The parameters' run-time types may be more refined, but that fact will not affect the dispatch.
Multiple dispatch is a concept that allows method dispatch to be based not only on the receiving object but also on the parameters of the method's invocation.
Why should we care? Read on.
We also want to traverse an AST for many different purposes. We may want to print the AST, perform semantic analysis, or generate code. Each of these could be accomplished by refining the notion of tree traversal in extensions of some common superclass.
Thus, the actual work performed upon a node depends on two things: the node type and the traversal type. But without multiple dispatch, we cannot have both refinements participate in method dispatch simultaneously.
One solution is to sprinkle elements of a traversal in all of the nodes' classes. So, an IntegerNode would contain code to print itself out, to perform semantic analysis, and to generate code. The problem here is that the code for a given traversal is spread through all the classes, which makes both the traversal and the node-based classes more difficult to read and maintain.
public class PrintTraversal extends Visitor {
public void visitStringNode(StringNode n) {....}
public void visitIntNode (IntNode n) {....}
public void visitSymbolNode(SymbolNode n) {....}
}
Each of the above methods knows how to print out its own particular kind of node.
Each node in turn accepts a call from a particular visitor:
public class StringNode extends AbstractNode {
pubic void accept(Visitor v) { v.visitStringNode(this); }
}
Because the supplied visitor's actual type could be any subclass of Visitor, this
implies that the superclass Visitor must have (potentially abstract) methods.
public abstract class Visitor {
public abstract void visitStringNode(StringNode n) ;
public abstract void visitIntNode (IntNode n) ;
public abstract void visitSymbolNode(SymbolNode n) ;
}
Java offers a nice solution through reflection. Double-dispatch is achieved by having each node call the same method (dispatch), through a superclass to avoid duplication, and that method then causes the type-specific method to be called through reflection on the supplied object's type.
In other words, at the point where a StringNode would call-back its Visitor:
public class StringNode extends AbstractNode {
pubic void accept(Visitor v) { v.visitStringNode(this); }
}
the node instead inherits accept from its superclass:
public final void accept(NodeVisitor v) { v.dispatch(this); }
The v.dispatch(this) method is reflectively responsible for making it look
like the StrongNode actually executed
v.visitStringNode(this). In fact, since parameter names participate in the
signature of a method, all such methods can be named visitor and can be
distinguished by the type of their parameter. Thus, v.dispatch(this) is
really responsible for invoking v.visit(StringNode).
public class PrintTraversal extends ReflectiveVisitor {
public void visit(StringNode n) {....}
public void visit(IntNode n) {....}
public void visit(SymbolNode n) {....}
public void defaultVisit(Object o) {....}
}
The defaultVisit(Object) method is called if there is no better method matched
for a given AST node type.
The above scheme overcomes the disadvantages of the nonreflective visitor, as follows:
The getMethod method shown above searches for a method in the visitor that matches the supplied object's type, where the notion of type is widened to include any interfaces implemented by that object.
Thus, by arraninging for objects to implement a common interface, they can be offered common treatment by a visitor.
The code for dispatch is as follows:
public final void dispatch(Object o) {
Method m = getBestMethodFor(o);
try {
m.invoke(this, new Object[] { o });
} catch (IllegalAccessException e) {
e.printStackTrace(System.err);
throw new Error("Method " + m + " aborting, bad access: "+e);
} catch (InvocationTargetException e) {
// This exception is thrown if the reflectively called method
// throws anything for any reason
e.printStackTrace(System.err);
throw new Error("Method " + m + " aborting: "+e);
}
}
The code for getMethod, which figures out which method to
invoke is as follows:
/**
* Find the closest visit method that handles the supplied object
*/
protected Method getBestMethodFor(Object o) {
Class nodeClass = o.getClass();
Method ans = null;
// Try the superclasses
for (Class c = nodeClass;
c != objectClass && ans == null;
c = c.getSuperclass()) {
debugMsg("Looking for class match for " + c.getName());
try {
// Unlike GoF, all methods are "visit" and are
// distinguished by their param type
ans = getClass().getMethod("visit", new Class[] {c});
} catch (NoSuchMethodException e) { }
}
// Try the interfaces. The code below will find the last
// interface listed for
// which "this" visitor can handle the type
Class iClass = nodeClass;
while (ans == null && iClass != objectClass) {
debugMsg("Looking for interface match in " + iClass.getName());
Class[] interfaces = iClass.getInterfaces();
for (int i = 0; i < interfaces.length; i++) {
debugMsg(" trying interface " + interfaces[i]);
try {
ans = getClass().getMethod("visit", new Class[] {interfaces[i]});
} catch (NoSuchMethodException e) { }
}
iClass = iClass.getSuperclass();
}
if (ans == null) {
try {
debugMsg("Giving up");
ans = getClass().getMethod("defaultVisit",
new Class[] {(new Object()).getClass()});
} catch (NoSuchMethodException e) {
// Just stop, because throwing an exception will cascade upwards
debugMsg("Cannot happen -- could not find defaultVisit(Object)");
e.printStackTrace(System.err);
System.exit(-1);
}
}
debugMsg("Best method for " + o + " is " + ans);
return ans;
}