jmultimethod: Multimethods and value dispatch with Java annotations in 140 LoC

In single-dispatch object-oriented languages like Java, complex method dispatch is traditionaly solved structurally using Visitor Design Pattern because it is not supported at the language/syntactic level. Even though Java does not allow for syntactic abstraction, Java annotations can be used to implement multimethods. The following code requires Java 6.

Quoting from Wikipedia:

Multiple dispatch or multimethods is the feature of some object-oriented programming languages in which a function or method can be dynamically dispatched based on the run time (dynamic) type of more than one of its arguments.

Peter Norvig's presentation about Design Patterns in Dynamic Languages gives a brief insight into multimethods, especially slides The Type/Operation Matrix and Multimethods.

Multimethods are huge step forward on the path towards the ultimate extensibility and "clean" code structure.

jmultimethod implements multiple displatch in a similar way I have implemented multimethods in PicoLisp recently.

The problem

Java's ability to dispatch/find the right method is limited as can be seen from the following example (based on the Multiple dispatch example from Wikipedia):

package jmultimethod;

public class DispatchTest {
    static class Asteroid {
        String id;
        public Asteroid(String id) {this.id = id;}
        public String id() {return id;}
    }
    static class Spaceship {
        String name;
        public Spaceship(String name) {this.name = name;}
        public String name() {return name;}
    }
    static class Static {
        static void colide(Asteroid x, Asteroid y) {
            System.out.println("AA colide " + x.id() + " with " + y.id());
        }
        static void colide(Asteroid x, Spaceship y) {
            System.out.println("AS colide " + x.id() + " with " + y.name());
        }
        static void colide(Spaceship x, Asteroid y) {
            System.out.println("SA colide " + x.name() + " with " + y.id());
        }
        static void colide(Spaceship x, Spaceship y) {
            System.out.println("SS colide " + x.name() + " with " + y.name());
        }
        static void colide(Object x, Object y) {
            System.out.println("OO colide " + x + " with " + y);
        }
        static void run() {
            run1();
            run2();
        }
        static void run1() {
            System.out.println("-- Static: explicitly typed");
            Asteroid a1 = new Asteroid("A1");
            Asteroid a2 = new Asteroid("A2");
            Spaceship s1 = new Spaceship("S1");
            Spaceship s2 = new Spaceship("S2");
            colide(a1, a2);
            colide(a1, s1);
            colide(s1, a1);
            colide(s1, s2);
        }
        static void run2() {
            System.out.println("-- Static: superclass typed");
            // here is the problem: the declared variable type is used
            // but it should be infered by the compiler instead
            Object a1 = new Asteroid("A1");
            Object a2 = new Asteroid("A2");
            Object s1 = new Spaceship("S1");
            Object s2 = new Spaceship("S2");
            colide(a1, a2);
            colide(a1, s1);
            colide(s1, a1);
            colide(s1, s2);
        }
    }
    static class Dynamic {
        void colide(Asteroid x, Asteroid y) {
            System.out.println("AA colide " + x.id() + " with " + y.id());
        }
        void colide(Asteroid x, Spaceship y) {
            System.out.println("AS colide " + x.id() + " with " + y.name());
        }
        void colide(Spaceship x, Asteroid y) {
            System.out.println("SA colide " + x.name() + " with " + y.id());
        }
        void colide(Spaceship x, Spaceship y) {
            System.out.println("SS colide " + x.name() + " with " + y.name());
        }
        void colide(Object x, Object y) {
            System.out.println("OO colide " + x + " with " + y);
        }
        void run() {
            run1();
            run2();
        }
        void run1() {
            System.out.println("-- Dynamic: explicitly typed");
            Asteroid a1 = new Asteroid("A1");
            Asteroid a2 = new Asteroid("A2");
            Spaceship s1 = new Spaceship("S1");
            Spaceship s2 = new Spaceship("S2");
            colide(a1, a2);
            colide(a1, s1);
            colide(s1, a1);
            colide(s1, s2);
        }
        void run2() {
            System.out.println("-- Dynamic: superclass typed");
            // here is the problem: dispatch is on the declared
            // variable type instead of the run-time value type
            Object a1 = new Asteroid("A1");
            Object a2 = new Asteroid("A2");
            Object s1 = new Spaceship("S1");
            Object s2 = new Spaceship("S2");
            colide(a1, a2);
            colide(a1, s1);
            colide(s1, a1);
            colide(s1, s2);
        }
    }
    public static void main(String args[]) {
        Static.run();
        new Dynamic().run();
    }
}

The program output (partially edited to fit on the screen) is:

-- Static: explicitly typed
AA colide A1 with A2
AS colide A1 with S1
SA colide S1 with A1
SS colide S1 with S2
-- Static: superclass typed
OO colide Asteroid@7150bd4d with Asteroid@6bbc4459
OO colide Asteroid@7150bd4d with Spaceship@152b6651
OO colide Spaceship@152b6651 with Asteroid@7150bd4d
OO colide Spaceship@152b6651 with Spaceship@544a5ab2
-- Dynamic: explicitly typed
AA colide A1 with A2
AS colide A1 with S1
SA colide S1 with A1
SS colide S1 with S2
-- Dynamic: superclass typed
OO colide Asteroid@2e6e1408 with Asteroid@3ce53108
OO colide Asteroid@2e6e1408 with Spaceship@6af62373
OO colide Spaceship@6af62373 with Asteroid@2e6e1408
OO colide Spaceship@6af62373 with Spaceship@459189e1

When finding the right method, Java does not take into account the run-time type of the method's arguments. Java simply reasons about types of variables instead of values.

Idea

Java 6 annotations can be used to annotate methods and implement multimethods and value dispatch. All this can be done at runtime without the need for any special compilation or preprocessing and the usage can still be reasonably user-friendly.

We need to introduce two "simple" annotations to annotate:

  • methods: What multimethod this method implements?
  • parameters: What value should we dispatch on?

We can then process the annotations and build a list of methods that implement a particular multimethod. This list needs to be sorted so that the most specific methods come first. "Most specific" means that for each method parameter (from left to right), the parameter type/value is more specialized (e.g. it is a subclass or it is matched agains the specified value). Calling a multimethod means invoking the most specific applicable method. "Applicable" means that the method prototype matches the actual runtime arguments and "the most specific" means that we can simply search through the sorted list and find the first one which is applicable.

Annotation processing can be wrapped up in a class which can then be used in a user defined method that will simply invoke the multimethod dispatch code with the actual runtime arguments.

Implementation

The interface Multi implements a runtime method annotation used to mark multimethods:

package jmultimethod;

import java.lang.annotation.RetentionPolicy;
import java.lang.annotation.Retention;
import java.lang.annotation.ElementType;
import java.lang.annotation.Target;

@Target(ElementType.METHOD)
@Retention(RetentionPolicy.RUNTIME)
public @interface Multi {

    public String value();
}

The interface V implements a runtime parameter annotation used to specify dispatch values:

package jmultimethod;

import java.lang.annotation.ElementType;
import java.lang.annotation.Retention;
import java.lang.annotation.RetentionPolicy;
import java.lang.annotation.Target;

@Target(ElementType.PARAMETER)
@Retention(RetentionPolicy.RUNTIME)
public @interface V {

    public String value();
}

The Multimethod code follows:

package jmultimethod;

import java.lang.annotation.Annotation;
import java.lang.reflect.Method;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

public class Multimethod {

    protected String name;
    protected final ArrayList<Method> methods = new ArrayList<Method>();
    protected final MethodComparator methodComparator = new MethodComparator();

    public Multimethod(String name, Class... classes) {
        this.name = name;
        for(Class c: classes) {
            add(c);
        }
    }
    
    public void add(Class c) {
        for(Method m: c.getMethods()) {
            for(Annotation ma: m.getAnnotations()) {
                if(ma instanceof Multi) {
                    Multi g = (Multi) ma;
                    if(this.name.equals(g.value())) {
                        methods.add(m);
                    }
                }
            }
        }
        sort();
    }
              
    protected void sort() {
        Method[] a = new Method[methods.size()];
        methods.toArray(a);
        Arrays.sort(a, methodComparator);
        methods.clear();
        for(Method m: a) {
            methods.add(m);
        }
    }
    
    protected class MethodComparator implements Comparator<Method> {
        @Override
        public int compare(Method l, Method r) {
            // most specific methods first 
            Class[] lc = l.getParameterTypes();
            Class[] rc = r.getParameterTypes();
            for(int i = 0; i < lc.length; i++) {
                String lv = value(l, i);
                String rv = value(r, i);
                if(lv == null) {
                    if(rv != null) {
                        return 1;
                    }
                }
                if(lc[i].isAssignableFrom(rc[i])) {
                    return 1;
                }
            }
            return -1;
        }
    }

    protected String value(Method method, int arg) {
        Annotation[] a = method.getParameterAnnotations()[arg];
        for(Annotation p: a) {
            if(p instanceof V) {
                V v = (V) p;
                return v.value();
            }
        }
        return null;
    }
    
    protected boolean isApplicable(Method method, Object... args) {
        Class[] c = method.getParameterTypes();
        for(int i = 0; i < c.length; i++) {
            // must be instanceof and equal to annotated value if present 
            if(c[i].isInstance(args[i])) {
                String v = value(method, i);
                if(v != null && !v.equals(args[i])) {
                    return false;
                }
            } else {
                if(args[i] != null || !Object.class.equals(c[i])) {
                    return false;
                }
            }
        }
        return true;
    }
    
    public Object invoke(Object self, Object... args) {
        Method m = null; // first applicable method (most specific)
        for(Method method: methods) {
            if(isApplicable(method, args)) {
                m = method;
                break;
            }
        }
        if(m == null) {
            throw new RuntimeException("No applicable method '" + name + "'.");
        }
        try {
            return m.invoke(self, args);
        } catch (Exception e) {
            throw new RuntimeException("Method invocation failed '" + name + "'.");
        }
    }
}

To use multimethods, user code must:

  1. Annotate methods with the multimethod name, e.g.
    @Multi("myMultimethod")
    

    The name of the annotated methods can be anything Java is happy with. It is most likely going to be different from the multimethod name because some methods can have prototype similar enough to cause name clashes for the Java compiler (and maybe because the compiler could have problems with the null value). Also, the method should be visible (e.g. public) to the Multimethod class.

  2. Process the annotations by creating the Multimethod object, e.g.
    protected Multimethod mm = new Multimethod("myMultimethod", getClass());
    
  3. Define multimethod "entry point" method with parameters as general as necessary. This method dispatches using the Multimethod object created above, e.g.
    public void myMultimethod(Object X, Object Y) {
       mm.invoke(this, X, Y);
    }
    
  4. And then, the multimethod can be called as any normal Java method, e.g.
    myMultimethod(1, null);
    

Limitations:

  • Value dispatch works only with values supported by Java annotations, e.g. values of type String.

Asteroid Example

The following code is based on the Multiple dispatch example from Wikipedia.

package jmultimethod;

public class AsteroidTest {
    
    class Asteroid {}
    
    class Spaceship {}

    @Multi("collide")
    public void collideOO(Object X, Object Y) {
       log("?? Bang, what happened? ", X, Y);
    }

    @Multi("collide")
    public void collideAA(Asteroid X, Asteroid Y) {
        log("AA Look at the beautiful fireworks! ", X, Y);
    }

    @Multi("collide")
    public void collideAS(Asteroid X, Spaceship Y) {
        log("AS Is it fatal? ", X, Y);
    }

    @Multi("collide")
    public void collideSA(Spaceship X, Asteroid Y) {
        log("SA Is it fatal? ", X, Y);
    }

    @Multi("collide")
    public void collideSS(Spaceship X, Spaceship Y) {
        log("SS Who's fault was it? ", X, Y);
    }

    @Multi("collide")
    public void collide1S(String X, Spaceship Y) {
        log("1S any string? ", X, Y);
    }

    @Multi("collide")
    public void collide2S(@V("hi") String X, Spaceship Y) {
        log("2S 'hi' value? ", X, Y);
    }

    protected Multimethod mm = new Multimethod("collide", getClass());
    
    public void collide(Object X, Object Y) {
        mm.invoke(this, X, Y);
    }

    public void run() {
        Object A = new Asteroid();
        Object S = new Spaceship();
        collide(A, A);
        collide(A, S);
        collide(S, A);
        collide(S, S);
        collide(A, 1);
        collide(2, A);
        collide(S, 3);
        collide(4, S);
        collide(5, null);
        collide(null, null);
        collide("hi", S);
        collide("hello", S);
    }

    public void log(Object... args) {
        for(Object o: args) {
            if(o instanceof String) {
                System.out.print(" " + (String) o);
            } else {
                System.out.print(" " + o);
            }
        }
        System.out.println();
    }
    
    public static void main(String[] args) throws Exception {
        AsteroidTest t = new AsteroidTest();
        t.run();
    }
}

The program output (partially edited to fit on the screen) is:

AA Look at the beautiful fireworks!  Asteroid@1f24bbbf Asteroid@1f24bbbf
AS Is it fatal?  Asteroid@1f24bbbf Spaceship@24a20892
SA Is it fatal?  Spaceship@24a20892 Asteroid@1f24bbbf
SS Who's fault was it?  Spaceship@24a20892 Spaceship@24a20892
?? Bang, what happened?  Asteroid@1f24bbbf 1
?? Bang, what happened?  2 Asteroid@1f24bbbf
?? Bang, what happened?  Spaceship@24a20892 3
?? Bang, what happened?  4 Spaceship@24a20892
?? Bang, what happened?  5 null
?? Bang, what happened?  null null
2S 'hi' value?  hi Spaceship@24a20892
1S any string?  hello Spaceship@24a20892

Car Example

The following code is based on the Visitor pattern example from Wikipedia.

package jmultimethod;

public class CarTest {

    interface CarElement {}
    
    class Wheel implements CarElement {
        private String name;
        Wheel(String name) {
            this.name = name;
        }
        String getName() {
            return this.name;
        }
    }
     
    class Engine implements CarElement {}
     
    class Body implements CarElement {}
     
    class Car {
        CarElement[] elements;
        public CarElement [] getElements() {
            return elements.clone();
        }
        public Car() {
            this.elements = new CarElement[]
              { new Wheel("front left"), new Wheel("front right"),
                new Wheel("back left") , new Wheel("back right"),
                new Body(), new Engine()};
        }
    }

    @Multi("visit")
    public void visitP(Wheel wheel, @V("print") String mode) {     
        System.out.println("Visiting "+ wheel.getName() + " wheel");
    }
    
    @Multi("visit")
    public void visitP(Engine engine, @V("print") String mode) {
        System.out.println("Visiting engine");
    }
    
    @Multi("visit")
    public void visitP(Body body, @V("print") String mode) {
        System.out.println("Visiting body");
    }
    
    @Multi("visit")
    public void visitP(Car car, @V("print") String mode) {
        System.out.println("\nVisiting car");
        for(CarElement element : car.getElements()) {
            visit(element, mode);
        }
        System.out.println("Visited car");
    }
     
    @Multi("visit")
    public void visitD(Wheel wheel, @V("do") String mode) {
        System.out.println("Kicking my "+ wheel.getName());
    }
    
    @Multi("visit")
    public void visitD(Engine engine, @V("do") String mode) {
        System.out.println("Starting my engine");
    }
    
    @Multi("visit")
    public void visitD(Body body, @V("do") String mode) {
        System.out.println("Moving my body");
    }
    
    @Multi("visit")
    public void visitD(Car car, @V("do") String mode) {
        System.out.println("\nStarting my car");
        for(CarElement element : car.getElements()) {
            visit(element, mode);
        }
        System.out.println("Started car");
    }
     
    protected Multimethod mm = new Multimethod("visit", getClass());
    
    public void visit(Object any, String mode) {
        mm.invoke(this, any, mode);
    }

    public void run() {
        Car car = new Car();
        visit(car, "print");
        visit(car, "do");
    }
    
    static public void main(String[] args){
        CarTest t = new CarTest();
        t.run();
    }
}

The program output is:

Visiting car
Visiting front left wheel
Visiting front right wheel
Visiting back left wheel
Visiting back right wheel
Visiting body
Visiting engine
Visited car

Starting my car
Kicking my front left
Kicking my front right
Kicking my back left
Kicking my back right
Moving my body
Starting my engine
Started car

For this example, it would probably be even better to remove the mode parameter and have two independent multimethods for each mode as the parameter space is not sparse but completely covered by specific methods.

Other ideas

One useful thing missing in this implementation is possibility of calling next applicable method, i.e. call-next-method or something like super() in the multimethod context. However, the question is whether an implementation of such feature would be simple and usable enough, due to lack of syntactic abstraction and dynamic scope in Java.

Other things like around, before and after methods or custom method combinations as implemented in the Common Lisp Object System are out of scope here and are better addressed by Aspect-oriented programming frameworks which step away from standard Java.

More References

The ultimate object system to learn is the Common Lisp Object System. The Art of the Metaobject Protocol offers interesting reading about it.

A nice programming language Nice has some interesting points about multimethods and the Visitor pattern.

mm4j is another minimalistic implementation of multimethods in Java. It relies purely on Java reflection and does not have value dispatch so the resulting implementation and usage is rather different from the one described here.

Download

The latest jmultimethod version can be downloaded here.

Licence

jmultimethod is open source software, made available under a BSD license:

Copyright (c) 2009, Tomas Hlavaty All rights reserved.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

Neither the name of jmultimethod nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Feedback

Please send me an email. See also discussion on reddit.