One of the interesting issues in
implementing dynamic dispatch for
Java is that the basic C3 linearization algorithm isn’t a very good
fit for the complexities of Java’s subtyping. (Note: the following
paragraphs rely on the reader having a basic understanding of the
details of C3 linearization.)
Java lists a class’s implemented interfaces separately from its
superclass. C3 requires, for each class, a list of direct superclasses
as input - so to adapt it for use with Java, we have to choose how to
combine each class’s superclass with its implemented interface list:
for instance, the superclass could be placed at the beginning or at
the end of the interface list.
In Java any interface is assignable to Object. So for C3 to make
sense, all interfaces which have no super-types have Object as a
super-type. If Object is in the super-type list of a type, it must be
the last thing - otherwise linearization will always be impossible. So
the most obvious thing to do is to include the super-class last in the
list of super-types.
This mostly works, but for the way collections from
java.util are implemented: The various abstract
collections implement their corresponding interface, but the actual
implementations don’t directly implement the corresponding interface,
so for example AbstractSet implements Set,
and HashSet extends AbstractSet, but does
not implement Set directly. This is a common pattern.
If, then, you always choose to put the super-class at the end of the
list of super-types while performing linearization for C3, this
results in an inconsistent linearization for all of Java’s built in
collections.
So I ended up doing the following by default: For any super-class
other than Object, the super-class goes first in the list of
super-types. If the super-class is Object, it gets pushed to the
end. This works in an intuitive way in lots of cases, and the
implementation supports pluggable ordering, should you need to do
something different.
June 23rd, 2006
david
Dynamic dispatch is a mechanism for selecting a method based on the
runtime types of the parameters supplied. Java dispatches instance
methods dynamically, using the runtime type of the receiver to choose
the code to invoke and ignoring the types of the other parameters
(just like Python and many other object-oriented languages). This is
called single dispatch. Unfortunately, Java’s dispatching is limited
in two important ways: it doesn’t allow class extensions, and
it doesn’t support multiple dispatch, as implemented in many
other object-oriented languages.
I have written some code which uses reflection and proxy generation to
conveniently implement dynamic multiple dispatch for Java. It uses C3
linearization to determine the method to invoke. This algorithm
was originally devised for Dylan. You can get the distribution here.
This implementation supports subtyping of both arrays and primitive
Java types such as int, byte,
char, but does not yet support Java 1.5’s generics. The
subtyping relation for arrays and primitive types is based on Java’s
notion of assignability - see the documentation for details.
Here’s a trivial example of using the dynamic dispatch library:
import net.lshift.java.dispatch.DynamicDispatch;
// define an interface
public interface NumberPredicate {
public boolean evaluate(Number n);
}
// implement it for some argument types
public class Exact {
public boolean evaluate(Float f) { return false; }
public boolean evaluate(Double f) { return false; }
public boolean evaluate(Number n) { return true; }
}
// create a dynamic dispatcher
NumberPredicate exact = (NumberPredicate)
DynamicDispatch.proxy(NumberPredicate.class, new Exact());
Now, code making use of exact can call the
evaluate method with a Number instance, and
the DynamicDispatch proxy that is backing the
NumberPredicate interface will find the most appropriate
method on Exact to invoke based on the runtime type of
the argument to evaluate. So, for instance:
exact.evaluate(new Float(12.3)); // returns false.
exact.evaluate(new Integer(34)); // returns true.
There are several reasons having dynamic dispatch (and multiple
dispatch) is useful when programming for Java:
If you want to extend an existing set of classes (for instance, to
add an aspect - see below), normally you’d create an interface
encapsulating your new feature, and make all the classes in the set
implement it. If you are not able to modify the classes, one
approach is to create wrapper classes for each, and somehow choose a
wrapper class at runtime based on the type of the object you’re
working with. You might implement this by
myObject.getWrapperClass() - but wait! This makes
getWrapperClass a new method that needs to be added:
precisely the problem you set out originally to solve.
Dynamic (single) dispatch helps you out here by conveniently
automating the required wrapping and method selection.
You might also want to use multiple dispatch, dispatching on the
types of multiple arguments. Neither the Java language nor the Java
virtual machine supports multiple dispatch. In some cases
overloading suffices, but in many it does not.
Dynamic multiple dispatch reinterprets Java’s notion overloading as
actual multimethod dispatch. Syntactically, you’re writing
overloaded methods - but using DynamicDispatch, the semantics are
those of full multiple-dispatched generic functions.
Dynamic dispatch is useful for adding aspects. For example, you might
use dynamic dispatch to write a Java object pretty printer, or custom
serializer. I’ve employed it for writing a general equality function
which is independent of the object’s own implementation of equals,
which I find useful in unit tests. I’ll write about that in a later
post.
If this kind of thing interests you, MultiJava, a compiler for a multiply-dispatched variant of Java, might be worth a look.
June 23rd, 2006
david