Double dispatch

Jeremy Miller recently had a post that mentioned ”double dispatch”, and I had to delve down into the dusty recesses of my at-best-mediocre brain to come up with a definition. Chances are everyone has come across double dispatch in one form or another, and understands it implicitly. However I find it harder to articulate the definition explicitly.

My (admittedly limited) understanding of double dispatch is that it chooses a method to evaluate based on the runtime types of two objects. Also, C# does not support double dispatch, but you can emulate it a number of ways by doing reflection tricks or by using a Visitor-pattern style approach. To illustrate the limitations in C#, I’ll borrow the example from Wikipedia and collide some asteroids with spaceships.

[TestFixture]
public class DispatchBehaviour {
  public class SpaceShip { }
  public class GiantSpaceShip : SpaceShip { }
  public class Asteroid {
    public virtual String CollideWith(SpaceShip ship) {
      return "Asteroid hit a SpaceShip";
    }
    public virtual String CollideWith(GiantSpaceShip ship) {
      return "Asteroid hit a GiantSpaceShip";
    }
  }
  public class ExplodingAsteroid : Asteroid {
    public override string CollideWith(SpaceShip ship) {
      return "ExplodingAsteroid hit a SpaceShip";
    }
    public override string CollideWith(GiantSpaceShip ship) {
      return "ExplodingAsteroid hit a GiantSpaceShip";
    }
  }
  [Test]
  public void TestFailsWhenTryingDoubleDispatch() {
    SpaceShip ship = new SpaceShip();
    SpaceShip giantShip = new GiantSpaceShip();
    Asteroid asteroid = new Asteroid();
    Asteroid explodingAsteroid = new ExplodingAsteroid();
    Assert.That(asteroid.CollideWith(ship), Is.EqualTo("Asteroid hit a SpaceShip"));
    Assert.That(explodingAsteroid.CollideWith(ship), Is.EqualTo("ExplodingAsteroid hit a SpaceShip"));
    //This assertion fails:
    Assert.That(explodingAsteroid.CollideWith(giantShip), Is.EqualTo("ExplodingAsteroid hit a GiantSpaceShip"));
 
  }
}

The explodingAsteroid reference looks up the correct virtual function in the ExplodingAsteroid class despite it being referenced via the Asteroid type, thanks to polymorphism and virtual functions. But because C# uses single dispatch, the above test fails because based on the compile-time lookup of the giantShip reference (which is a SpaceShip reference at compile-time). If it where doing that lookup at run-time we’d have a different story.

One way of dealing with this is to switch on the type within the CollideWith methods.

public class ExplodingAsteroid : Asteroid {
  public override string CollideWith(SpaceShip ship) {
    if (ship is GiantSpaceShip) {
      return "ExplodingAsteroid hit a GiantSpaceShip";
    } else {
      return "ExplodingAsteroid hit a SpaceShip";
    }
  }
}
//...similar implementation for Asteroid.CollideWith(...)

This works, but if you end up with lots of different SpaceShip types then you are in for a hard time. If your group of asteroids is fairly static, you can use a Visitor-approach to accommodate lots of different spaceships. First we’ll define an IAsteroid interface to represent the fairly stable group of asteroids, and an IAsteroidTarget as a Visitor, to represent anything that can collide with our stable group of asteroids:

//Element that accepts a visit, in Visitor pattern parlance
public interface IAsteroid {
  string CollideWith(IAsteroidTarget target);
}
//Visitor, in Visitor pattern parlance
public interface IAsteroidTarget {
  String CollideWith(Asteroid asteroid);
  String CollideWith(ExplodingAsteroid asteroid);
}

As our spaceships can “visit” the asteroid types, let’s implement those next:

public class SpaceShip : IAsteroidTarget {
  public string CollideWith(Asteroid asteroid) {
    return "Asteroid hit a SpaceShip";
  }
  public string CollideWith(ExplodingAsteroid asteroid) {
    return "ExplodingAsteroid hit a SpaceShip";
  }
}
public class GiantSpaceShip : IAsteroidTarget {
  public string CollideWith(Asteroid asteroid) {
    return "Asteroid hit a GiantSpaceShip";
  }
  public string CollideWith(ExplodingAsteroid asteroid) {
    return "ExplodingAsteroid hit a GiantSpaceShip";
  }
}

Now comes the double-dispatchy emulation part. Let’s make our asteroids accept visits from our IAsteroidTarget objects.

public class Asteroid : IAsteroid {
  public string CollideWith(IAsteroidTarget target) {
    return target.CollideWith(this); // <-- The double dispatchy part
  }
}
//Same implementation for ExplodingAsteroid : IAsteroid ...

The emphasised part of the code above delegates the way each target will be hit to the target itself. A slightly modified version of our original test will now pass:

[Test]
public void TestDoubleDispatchWorkAround2() {
  IAsteroidTarget ship = new SpaceShip();
  IAsteroidTarget giantShip = new GiantSpaceShip();
  IAsteroid asteroid = new Asteroid();
  IAsteroid explodingAsteroid = new ExplodingAsteroid();
  Assert.That(asteroid.CollideWith(ship), Is.EqualTo("Asteroid hit a SpaceShip"));
  Assert.That(explodingAsteroid.CollideWith(ship), Is.EqualTo("ExplodingAsteroid hit a SpaceShip"));
  Assert.That(explodingAsteroid.CollideWith(giantShip), Is.EqualTo("ExplodingAsteroid hit a GiantSpaceShip"));
}

Obviously there are disadvantages to this pattern. If you need to add more asteroid types things are going to be painful. (There are also much better ways of implementing this particular example of returning strings, but that is just due to its contrived nature. For a realistic example see Jeremy’s post.) On the other hand, the process of adding targets is now trivial, even non-spaceship ones:

public class Earth : IAsteroidTarget {
  public string CollideWith(Asteroid asteroid) {
    return "Asteroid hit Earth";
  }
  public string CollideWith(ExplodingAsteroid asteroid) {
    return "ExplodingAsteroid hit Earth, causing the extinction of the dinosaurs";
  }
}

As an aside, this single dispatching behaviour of C# explains the cause of the generic overloading behaviour I mentioned before.

Finally, Derrick Coetzee has a good explanation of technical aspects of dispatching in C# with regards to the Visitor pattern.

Comments