Depth-first Polymorphism (or Customised Polyseme)

Consider the following class:

public class Polyseme {
 public static class Top {
   public void f(Object o) {
     System.out.println("Top.f(Object)");
   }
   public void f(String s) {
     System.out.println("Top.f(String)");
   }
 }
 public static void main(String[] args) {
   Top top = new Top();
   top.f(new java.util.Vector());
   top.f("hello");
   top.f((Object)"bye");
 }
}

Java looks for the method with the "narrowest" matching class for the parameter objects. Therefore, the output from running this class is:

Top.f(Object)
Top.f(String)
Top.f(Object)

In Java, the virtual machine tries to find a matching method for your parameters, starting at the top of the hierarchy and moving down. Say we have the following classes:

public class BreadthFirst {
 public static class Top {
   public void f(Object o) {
     System.out.println("Top.f(Object)");
   }
 }
 public static class Middle extends Top {
   public void f(String s) {
     System.out.println("Middle.f(String)");
   }
 }
 public static void main(String[] args) {
   Top top = new Middle();
   top.f(new java.util.Vector());
   top.f("hello");
   top.f((Object)"bye");
 }
}

The virtual machine will thus start at Top and check if there are any methods which would accept String.class or Object.class, and indeed, Top.f(Object) would handle all those parameters. The output is therefore the following:

Top.f(Object)
Top.f(Object)
Top.f(Object)

We could "fix" this by overriding f(Object) and using instanceof to call the correct f() method (brrr - I'd rather get stuck on the N2 than do that [for those not living in Cape Town, the N2 is notoriously dangerous, you either get shot at or in or with if your car breaks down])

public class BreadthFirstFix {
 public static class Top {
   public void f(Object o) {
     System.out.println("Top.f(Object)");
   }
 }
 public static class Middle extends Top {
   public void f(Object o) {
     if (o instanceof String)
       f((String)o);
     else
       super.f(o);
   }
   public void f(String s) {
     System.out.println("Middle.f(String)");
   }
 }
 public static void main(String[] args) {
   Top top = new Middle();
   top.f(new java.util.Vector());
   top.f("hello");
   top.f((Object)"bye");
 }
}

The output would now look as we would expect:

Top.f(Object)
Middle.f(String)
Middle.f(String)

This might have the correct effect, but it does mean that we have to have such a silly "instanceof" in all the subclasses. If we are designing a OO framework we want to have our clients subclass our classes without having to do acrobatics to achieve this.

Christoph Jung mentioned this problem with Java to me a few weeks ago and we thought of some code you could put at the highest level class that uses reflection to start at the lowest class and then tries to match the method to the type before moving up the hierarchy. I call this "depth-first-polymorphism".

import java.lang.reflect.*;
public class DepthFirst {
 public static class Top {
   private Method getPolymorphicMethod(Object param) {
     try {
       Class cl = getClass();  // the bottom-most class
       // we start at the bottom and work our way up
       Class[] paramTypes = {param.getClass()};
       while(!cl.equals(Top.class)) {
         try {
           // this way we find the actual method
           return cl.getDeclaredMethod("f", paramTypes);
         } catch(NoSuchMethodException ex) {}
         cl = cl.getSuperclass();
       }
       return null;
     }
     catch(RuntimeException ex) { throw ex; }
     catch(Exception ex) { return null; }
   }
   public void f(Object object) {
     Method downPolymorphic = getPolymorphicMethod(object);
     if (downPolymorphic == null) {
       System.out.println("Top.f(Object)");
     } else {
       try {
         downPolymorphic.invoke(this, new Object[] {object});
       }
       catch(RuntimeException ex) { throw ex; }
       catch(Exception ex) {
         throw new RuntimeException(ex.toString());
       }
     }
   }
 }
 public static class Middle extends Top {
   public void f(String s) {
     System.out.println("Middle.f(String)");
   }
 }
 public static class Bottom extends Middle {
   public void f(Integer i) {
     System.out.println("Bottom.f(Integer)");
   }
 }
 public static class RockBottom extends Bottom {
   public void f(String s) {
     System.out.println("RockBottom.f(String)");
   }
 }
 public static void main(String[] args) {
   Top top = new RockBottom();
   top.f(new java.util.Vector());
   top.f("hello");
   top.f(new Integer(42));
   top = new Bottom();
   top.f(new java.util.Vector());
   top.f("hello");
   top.f(new Integer(42));
 }
}

The answer is this time:

Top.f(Object)
RockBottom.f(String
Bottom.f(Integer)
Top.f(Object)
Middle.f(String)
Bottom.f(Integer)

When should you use this technique? Only if you have a lot of specific type handlers as subclasses of a common superclass where it would make sense to add such a depth-first invoker. You can probably extract this functionality and put it in a separate class. If you use this commercially please do the exception handling correctly, I didn't bother in my example, in preparation for when I change my logo to "The C# Specialists".

Thanks for your comments, I always appreciate your feedback.