Tuesday, January 12, 2010

Dual dispatch

Computer programming is about describing the behavior of entities in various scenarios. For instance, if you're writing a data entry form, you might need to describe how it behaves when you click a certain button, how it behaves when you type into a field, and so forth. In object-oriented programming, we try to organize the code that describes an object's behavior together with the data that describes its state.

This gets messy when objects interact. Suppose you've got three Animals (Dog, Cat, Monkey), and three kinds of Food (DogChow, CatChow, MonkeyChow). You want your program to ensure that Monkeys can only eat Monkey Chow, Cats can only eat Cat Chow, but Dogs can eat all three kinds. So, you add a method to each of the three Animal classes, something like "boolean canEat(Food chow)". The implementation for Cat looks like "return chow instanceof CatChow", Dog looks like "return true", and so forth.

What happens when you add an animal? No problem, you just have to implement its canEat() method. What about when you add a new type of food? Well, you have to go through all the existing animals and make sure their implementation is still right. For instance, since chocolate is poisonous to dogs, the Dog implementation of canEat() is wrong. No compiler error, but your dog might die.

Or, you could flip the problem around, and put methods on all the Foods, saying what animals can eat it. Now, when you add a food, it's just a matter of implementing its canBeEatenBy(Animal animal) method. But when you add a new animal, you have to check all the Food implementations.

This problem of how to describe the interactions between entities is called "dual dispatch." I know of no particularly good general solution.