After working a little bit with Java proxy classes for my yet incomplete support library for xajavac, which introduces subtyping to annotations, I started to think about what else I could do with them.
Proxies are essentially a wrapper around another object. Instead of calling a method of the wrapped object, a single invoke method is called and provided the Method object of the method that was to be called, along with the parameters:
public class MyProxy implements java.lang.reflect.InvocationHandler {
public Object invoke(Object proxy, Method m, Object[] args) throws Throwable {
// ...
return result;
}
}
Inside this method, the programmer can now do string comparisons on the method name, for example, and dispatch different methods, or perform some kind of pre- and post-processing. I used this, together with a very simple @MultiMethod marker annotation, to create multi-methods in Java.
Java normally only performs static dispatch and single dispatch. In static dispatch, the class of the method is decided at compile time already; in single (dynamic) dispatch, the class containing the method depends on the run-time type of the object. Static dispatch applies to static methods. Single dispatch, on the other hand, works with non-static methods and is the foundation of polymorphism. To demonstrate single dispatch, let’s consider the classic example of polymorphism:
interface IAnimal {
public void speak();
}
class Cat implements IAnimal {
public void speak() { System.out.println("Meow"); }
}
class Dog implements IAnimal {
public void speak() { System.out.println("Woof"); }
}
// ...
IAnimal a = new Cat();
a.speak(); // prints "Meow"
a = new Dog();
a.speak(); // prints "Woof"
At the call site, we just have an IAnimal, and we call its speak() method. Depending on whether the run-time type is Cat or Dog, the appropriate method is called. The dispatch is based on the receiver, object whose method is called.
However, the dispatch only depends on the receiver; the run-time types of the arguments do not matter. For example, if we create a feed(IFood food) method in IAnimal and then provide a specialized feed(Catnip food) method in the Cat class, the general Cat.feed(IFood food) method will be called even when the argument is of type Catnip. It is single dispatch, not multiple dispatch:
interface IFood { }
public Catnip implements IFood { }
public PetFood implements IFood { }
interface IAnimal {
public void feed(IFood food);
}
class Cat implements IAnimal {
public void feed(IFood food) { System.out.println("Num num"); }
public void feed(Catnip food) { System.out.println("Meow, my favorite!"); }
}
class Dog implements IAnimal {
public void feed(IFood food) { System.out.println("Gobble gobble"); }
}
// ...
IAnimal a = new Cat();
a.feed(new PetFood()); // prints "Num num"
a.feed(new Catnip()); // also prints "Num num", not "Meow, my favorite!"
a = new Dog();
a.feed(new PetFood); // prints "Gobble gobble"
If Java were to call the most appropriate method, where the class is determined by the receiver run-time type, and the actual overloaded method by the best match of the argument run-time types, then Java would be performing multiple dispatch. This, however, is not part of the Java Language Specification.
Using proxies, however, it is possible to intercept the call to the feed(IFood food) methods, look through the overloaded methods and compare their parameter types to the provided argument run-time types, and then call the method that is the closest to the run-time types, i.e. where all argument types are supertypes of the argument run-time types, and where the types are most closely related (defined as the number of edges separating the nodes in the type hierarchy).
To get a behavior like the one above, Java programmers (and programmers of most languages) usually employ the Visitor design pattern. Multi-methods (methods with multiple dispatch) make this unnecessary. Here is a more useful example of an abstract syntax tree (AST) consisting of integer and variable leaves and addition and multiplication interior nodes. First the code using the Visitor pattern to achieve double dispatch:
interface IAST {
public Object execute(IASTVisitor v);
}
class Num implements IAST {
private int _num;
public Num(int n) {
_num = n;
}
public int getNum() { return _num; }
public String execute(IASTVisitor v) { return v.numCase(this); }
}
class Var implements IAST {
private String _var;
public Var(String v) {
_var = v;
}
public String getVar() { return _var; }
public String execute(IASTVisitor v) { return v.varCase(this); }
}
class Add implements IAST {
private IAST _left;
private IAST _right;
public Add(IAST l, IAST r) {
_left = l;
_right = r;
}
public IAST getLeft() { return _left; }
public IAST getRight() { return _right; }
public String execute(IASTVisitor v) { return v.addCase(this); }
}
class Mul implements IAST {
private IAST _left;
private IAST _right;
public Mul(IAST l, IAST r) {
_left = l;
_right = r;
}
public IAST getLeft() { return _left; }
public IAST getRight() { return _right; }
public String execute(IASTVisitor v) { return v.mulCase(this); }
}
interface IASTVisitor {
public String numCase(Num ast);
public String varCase(Var ast);
public String addCase(Add ast);
public String mulCase(Mul ast);
}
class ToStringVisitor implements IASTVisitor {
public String numCase(Num ast) {
return String.valueOf(ast.getNum());
}
public String varCase(Var ast) {
return ast.getVar();
}
public String addCase(Add ast) {
return "("+ast.getLeft().execute(this)+" + "+ast.getRight().execute(this)+")";
}
public String apply(Mul ast) {
return "("+ast.getLeft().execute(this)+" * "+ast.getRight().execute(this)+")";
}
}
//...
IAST a = new Mul(new Add(new Var("x"), new Num(5)), new Num(-2));
a.execute(new ToStringVisitor());
The interesting point here is that each subclass of IAST has to have an execute(IASTVisitor v) method that accepts the visitor. The method implementations in the subclasses then call the corresponding case method in the IASTVisitor. When we execute the visitor on the AST (the host), we achieve double dispatch because there are two instances of single dispatch, once depending on the run-time type of the host, a, and again inside the execute method depending on the run-time type of the visitor, v.
With multi-methods, we can now remove the execute methods in the IAST hierarchy. We now just have an overloaded apply method in IASTVisitor where the type of the parameter changes and also determines which method gets invoked:
interface IAST { }
class Num implements IAST {
private int _num;
public Num(int n) {
_num = n;
}
public int getNum() { return _num; }
}
class Var implements IAST {
private String _var;
public Var(String v) {
_var = v;
}
public String getVar() { return _var; }
}
class Add implements IAST {
private IAST _left;
private IAST _right;
public Add(IAST l, IAST r) {
_left = l;
_right = r;
}
public IAST getLeft() { return _left; }
public IAST getRight() { return _right; }
}
class Mul implements IAST {
private IAST _left;
private IAST _right;
public Mul(IAST l, IAST r) {
_left = l;
_right = r;
}
public IAST getLeft() { return _left; }
public IAST getRight() { return _right; }
}
@MultiMethod
public interface IASTVisitor {
public String apply(IAST ast);
public String apply(Num ast);
public String apply(Var ast);
public String apply(Add ast);
public String apply(Mul ast);
}
class ToStringVisitor implements IASTVisitor {
public static IASTVisitor create() {
IASTVisitor v = new ToStringVisitor();
v.proxy = MMProxy.newInstance(v);
return v.proxy;
}
private IASTVisitor proxy;
public String apply(IAST ast) {
throw new AssertionError("Should never happen.");
}
public String apply(Num ast) {
return String.valueOf(ast.getNum());
}
public String apply(Var ast) {
return ast.getVar();
}
public String apply(Add ast) {
return "("+proxy.apply(ast.getLeft())+" + "+proxy.apply(ast.getRight())+")";
}
public String apply(Mul ast) {
return "("+proxy.apply(ast.getLeft())+" * "+proxy.apply(ast.getRight())+")";
}
}
//...
IAST a = new Mul(new Add(new Var("x"), new Num(5)), new Num(-2));
ToStringVisitor().create().apply(a);
The @MultiMethod marker annotation states that all methods in the IASTVisitor interface and all its subclasses should use multiple dispatch. To minimize overhead, this annotation can also be placed just in front of individual methods, then only those methods will use multiple dispatch.
There needs to be a method that takes the supertype of the AST classes, IAST, even though that method should never be called, because there are no objects of that type (unless you create anonymous inner classes, or add another subclass, e.g. Sub, for which there is no overloaded method). We therefore throw an exception there. Then there are the method that handle the concrete subclasses. This time, they all have the same name and overload the general method above that accepts the supertype.
Since we need to create the proxy that wraps around the object with the multi-methods, i.e. around the visitor here, we cannot just create the visitor using the new keyword. Instead, we have a static create() method that creates a new object and creates the proxy around it, and then returns it typed as interface. This is important! It must be returned as an IASTVisitor, not as a ToStringVisitor, because as it turns out, the proxies can only simulate interfaces, not classes. The created proxy is an IASTVisitor, but it is not a ToStringVisitor, even though it wraps around one.
Another very important difference is apparent in the methods for the composites Add and Mul, where recursion is necessary. Using the visitor, we could recurse into the subtrees using ast.getLeft().execute(this), where this was the visitor itself. Since we want the multiple dispatch behavior in the recursion too, we need to use the proxy object for the recursion, not the visitor itself. That means we cannot use this, because this is the visitor, not the proxy. Instead, we use the proxy field, where the create() method stored the created proxy. This is really inelegant and can cause numerous problems: If we accidentally use this, we lose the multiple dispatch; we could also make a mistake and overwrite the proxy field, with null for example. But I haven’t found a better way.
Finally, there is a huge limitation: As stated, proxies can only simulate interfaces, not classes. That means that the classes around which we wrap a proxy can only implement interfaces, but not extend other classes. You can never use the extends keyword! That doesn’t for good code reuse. For example, even though pretty much every visitor needs the proxy field, I cannot hoist it into an abstract class. The following example will cause a ClassCastException:
@MultiMethod
public interface IASTVisitor {
public String apply(IAST ast);
public String apply(Num ast);
public String apply(Var ast);
public String apply(Add ast);
public String apply(Mul ast);
}
abstract class AASTVisitor implements IASTVisitor {
protected IASTVisitor proxy;
public String apply(IAST ast) {
throw new AssertionError("Should never happen.");
}
}
class ToStringVisitor extends AASTVisitor {
public static IASTVisitor create() {
IASTVisitor v = new ToStringVisitor();
v.proxy = MMProxy.newInstance(v);
return v.proxy;
}
public String apply(Num ast) {
return String.valueOf(ast.getNum());
}
public String apply(Var ast) {
return ast.getVar();
}
public String apply(Add ast) {
return "("+proxy.apply(ast.getLeft())+" + "+proxy.apply(ast.getRight())+")";
}
public String apply(Mul ast) {
return "("+proxy.apply(ast.getLeft())+" * "+proxy.apply(ast.getRight())+")";
}
}
That’s what we would ideally want to do, but we can’t. This is really a huge impediment, but right now, without heavier machinery such as a bytecode-rewriting class loader, I can’t find a way around it. Proxies are promising, but not as powerful as I would like them to be.
I’m nonetheless making the source code for Java multi-methods using proxies and annotations available, even though it’s definitely a work in progress.
and I thought maybe that was supposed to be the symbol for antisymmetry, but it wasn’t defined anywhere.
crossed out. Durrh.
