11: Multiple dispatching

When dealing with multiple types which are interacting, a program can get particularly messy. For example, consider a system that parses and executes mathematical expressions. You want to be able to say Number + Number, Number * Number, etc., where Number is the base class for a family of numerical objects. But when you say a + b, and you don’t know the exact type of either a or b, so how can you get them to interact properly?
The answer starts with something you probably don’t think about: Java performs only single dispatching. That is, if you are performing an operation on more than one object whose type is unknown, Java can invoke the dynamic binding mechanism on only one of those types. This doesn’t solve the problem, so you end up detecting some types manually and effectively producing your own dynamic binding behavior.
The solution is called multiple dispatching. Remember that polymorphism can occur only via member function calls, so if you want double dispatching to occur, there must be two member function calls: the first to determine the first unknown type, and the second to determine the second unknown type. With multiple dispatching, you must have a polymorphic method call to determine each of the types. Generally, you’ll set up a configuration such that a single member function call produces more than one dynamic member function call and thus determines more than one type in the process. To get this effect, you need to work with more than one polymorphic method call: you’ll need one call for each dispatch. The methods in the following example are called compete( ) and eval( ), and are both members of the same type. (In this case there will be only two dispatches, which is referred to as double dispatching). If you are working with two different type hierarchies that are interacting, then you’ll have to have a polymorphic method call in each hierarchy.
Here’s an example of multiple dispatching:
//: c11:PaperScissorsRock.java
// Demonstration of multiple dispatching.
import java.util.*;
import com.bruceeckel.test.*;

// An enumeration type:
class Outcome {
  private int value;
  private String name;
  private Outcome(int val, String nm) { 
    value = val;
    name = nm;
  }
  public final static Outcome
    WIN = new Outcome(0, "win"), 
    LOSE = new Outcome(1, "lose"), 
    DRAW = new Outcome(2, "draw");
  public String toString() { return name; }
  public boolean equals(Object o) {
    return (o instanceof Outcome)
      && (value == ((Outcome)o).value);
  }
}

interface Item {
  Outcome compete(Item it);
  Outcome eval(Paper p);
  Outcome eval(Scissors s);
  Outcome eval(Rock r);
}

class Paper implements Item {
  public Outcome compete(Item it) {
    return it.eval(this);
  }
  public Outcome eval(Paper p) {
    return Outcome.DRAW;
  }
  public Outcome eval(Scissors s) {
    return Outcome.WIN;
  }
  public Outcome eval(Rock r) {
    return Outcome.LOSE;
  }
  public String toString() { return "Paper"; }
}

class Scissors implements Item {
  public Outcome compete(Item it) {
    return it.eval(this);
  }
  public Outcome eval(Paper p) {
    return Outcome.LOSE;
  }
  public Outcome eval(Scissors s) {
    return Outcome.DRAW;
  }
  public Outcome eval(Rock r) {
    return Outcome.WIN;
  }
  public String toString() { return "Scissors"; }
}

class Rock implements Item {
  public Outcome compete(Item it) {
    return it.eval(this);
  }
  public Outcome eval(Paper p) {
    return Outcome.WIN;
  }
  public Outcome eval(Scissors s) {
    return Outcome.LOSE;
  }
  public Outcome eval(Rock r) {
    return Outcome.DRAW;
  }
  public String toString() { return "Rock"; }
}

class ItemGenerator {
  public static Item newItem() {
    switch((int)(Math.random() * 3)) {
      default:
      case 0:
        return new Scissors();
      case 1:
        return new Paper();
      case 2:
        return new Rock();
    }
  }
}

class Compete {
  public static Outcome match(Item a, Item b) {
    System.out.print(a + " <--> " + b + " : ");
    return a.compete(b);
  }
}

public class PaperScissorsRock extends UnitTest {
  List 
    items1 = new ArrayList(),
    items2 = new ArrayList();
  static int SIZE = 20;
  public PaperScissorsRock() {
    for(int i = 0; i < SIZE; i++) {
      items1.add(ItemGenerator.newItem());
      items2.add(ItemGenerator.newItem());
    }
  }
  public void test() {
    for(int i = 0; i < SIZE; i++)
      System.out.println(
        Compete.match(
          (Item)items1.get(i), 
          (Item)items2.get(i)));
  }
  public static void main(String args[]) {
    new PaperScissorsRock().test();
  }
} ///:~

Visitor, a type of multiple dispatching

The assumption is that you have a primary class hierarchy that is fixed; perhaps it’s from another vendor and you can’t make changes to that hierarchy. However, you’d like to add new polymorphic methods to that hierarchy, which means that normally you’d have to add something to the base class interface. So the dilemma is that you need to add methods to the base class, but you can’t touch the base class. How do you get around this?
The design pattern that solves this kind of problem is called a “visitor” (the final one in the Design Patterns book), and it builds on the double dispatching scheme shown in the last section.
The visitor pattern allows you to extend the interface of the primary type by creating a separate class hierarchy of type Visitor to virtualize the operations performed upon the primary type. The objects of the primary type simply “accept” the visitor, then call the visitor’s dynamically-bound member function.
//: c11:BeeAndFlowers.java
// Demonstration of "visitor" pattern.
import java.util.*;
import com.bruceeckel.test.*;

interface Visitor {  
  void visit(Gladiolus g);
  void visit(Renuculus r);
  void visit(Chrysanthemum c);
}

// The Flower hierarchy cannot be changed:
interface Flower {  
  void accept(Visitor v);
}

class Gladiolus implements Flower {  
  public void accept(Visitor v) { v.visit(this);}
}

class Renuculus implements Flower {  
  public void accept(Visitor v) { v.visit(this);}
}

class Chrysanthemum implements Flower {  
  public void accept(Visitor v) { v.visit(this);}
}

// Add the ability to produce a string:
class StringVal implements Visitor {
  String s;  
  public String toString() { return s; }
  public void visit(Gladiolus g) { 
    s = "Gladiolus"; 
  }
  public void visit(Renuculus r) { 
    s = "Renuculus"; 
  }
  public void visit(Chrysanthemum c) { 
    s = "Chrysanthemum"; 
  }
}

// Add the ability to do "Bee" activities:
class Bee implements Visitor {  
  public void visit(Gladiolus g) {
    System.out.println("Bee and Gladiolus");
  }
  public void visit(Renuculus r) {
    System.out.println("Bee and Renuculus");
  }
  public void visit(Chrysanthemum c) {
    System.out.println("Bee and Chrysanthemum");
  }
}

class FlowerGenerator {
  public static Flower newFlower() {
    switch((int)(Math.random() * 3)) {
      default:
      case 0: return new Gladiolus();
      case 1: return new Renuculus();
      case 2: return new Chrysanthemum();
    }
  }
}

public class BeeAndFlowers extends UnitTest {
  List flowers = new ArrayList();
  public BeeAndFlowers() {
    for(int i = 0; i < 10; i++)
      flowers.add(FlowerGenerator.newFlower());
  }
  public void test() {
    // It's almost as if I had a function to
    // produce a Flower string representation:
    StringVal sval = new StringVal();
    Iterator it = flowers.iterator();
    while(it.hasNext()) {
      ((Flower)it.next()).accept(sval);
      System.out.println(sval);
    }
    // Perform "Bee" operation on all Flowers:
    Bee bee = new Bee();
    it = flowers.iterator();
    while(it.hasNext())
      ((Flower)it.next()).accept(bee);
  }
  public static void main(String args[]) {
    new BeeAndFlowers().test();
  }
} ///:~

Exercises

  1. Create a business-modeling environment with three types of Inhabitant: Dwarf (for engineers), Elf (for marketers) and Troll (for managers). Now create a class called Project that creates the different inhabitants and causes them to interact( ) with each other using multiple dispatching.
  2. Modify the above example to make the interactions more detailed. Each Inhabitant can randomly produce a Weapon using getWeapon( ): a Dwarf uses Jargon or Play, an Elf uses InventFeature or SellImaginaryProduct, and a Troll uses Edict and Schedule. You must decide which weapons “win” and “lose” in each interaction (as in PaperScissorsRock.java). Add a battle( ) member function to Project that takes two Inhabitants and matches them against each other. Now create a meeting( ) member function for Project that creates groups of Dwarf, Elf and Manager and battles the groups against each other until only members of one group are left standing. These are the “winners.”
  3. Modify PaperScissorsRock.java to replace the double dispatching with a table lookup. The easiest way to do this is to create a Map of Maps, with the key of each Map the class of each object. Then you can do the lookup by saying:
    ((Map)map.get(o1.getClass())).get(o2.getClass())
    Notice how much easier it is to reconfigure the system. When is it more appropriate to use this approach vs. hard-coding the dynamic dispatches? Can you create a system that has the syntactic simplicity of use of the dynamic dispatch but uses a table lookup?
  4. Modify Exercise 2 to use the table lookup technique described in Exercise 3.


chris@sunpack.com Last Update:09/08/2001