Dispatch - Single, Multiple and Dynamic

Well, starting with a simple topic about dispatch. Though a simple one, if you search on the net about single dispatch or dynamic dispatch, it can confusing.
Lets start with understanding what is "dispatch". To put it simply, dispatch is about deciding which method to call.

1. Static Dispatch
If it can be decided at compile time which method is to be called, it is referred to as static dispath. The advantage of static dispatch is that the code gets generated at compile time, and the "wiring" of the function calls and value invocations are determined at compile time -- or even before the program is run.

2. Dynamic Dispatch
If the decision about which method to invoke can be made only at runtime it is called as dynamic dispatch. Dynamic dispatch is needed when multiple classes contain different implementations of the same method foo(). If the class of an object x is not known at compile-time, then when x.foo() is called, the program must decide at runtime which implementation of foo() to invoke, based on the runtime type of object x. Overriding in C# is example of dynamic dispatch.

2.1 Single Dispatch
C# or C++ are single dispatch languages since the decision about which method to call is made on the basis of only one parameter or argument of the function i.e. the implicit this parameter. So, which method gets called is decided by the type of the "object".


2.2 Multiple Dispatch
There are a few languages where functions can also be dynamically dispatched based on the type of arguments. This is known as multiple dispatch.

2.2.1 Why is multiple dispatch needed ?
Virtual functions allow polymorphism on a single argument but at times there is a need for multi-argument polymorphism. One of the solution is double dispatch but it does not lend easily extensible code. The other possible solutions can be found at http://www.eptacom.net/pubblicazioni/pub_eng/mdisp.html

2.2.1.1 Example 1

abstract class Shape{
  public abstract double Intersect (Shape s);
}

class Circle : Shape{
  public override double Intersect (Shape s){
  }
}

class Rectangle : Shape{
  public override double Intersect (Shape s){
  }
}

The problem here is that Intersect() method cannot be implemented for a generic shape object.
It maybe tempting to use an if/else sequence based on the dynamic type of the argument

class Circle : Shape{
  public override double Intersect (Shape s){
    if(s is Circle){
    }
    else if (s is Rectangle){
    }
  }
}

But this in unsatisfactory as you have to update the Intersect method of each class
derived from Shape every time a new class is derived. The need for multiple
polymorphism the need for multiple polymorphism arises naturally in several real-world problems. In general, the selection of the most efficient algorithm may depend on the type of more than one parameter.

abstract class Shape{
  public abstract double Intersect(Shape s);
  public abstract double Intersect(Circle s);
  public abstract double Intersect(Rectangle s);
}

class Circle : Shape{
  public override double Intersect(Shape s){
    return s.Intersect(this);
  }
  public override double Intersect(Circle s){
     return 1.0;
  }
  public override double Intersect(Rectangle s){
     return 1.0;
  }
}
class Rectangle : Shape{
  public override double Intersect(Shape s){
    return s.Intersect(this);
  }
  public override double Intersect(Circle s){
    return 1.0;
  }
  public override double Intersect(Rectangle s){
    return 1.0;
  }
}

Basically, double dispatch uses two calls to resolve on the type of both arguments.
but in C# it does not come without problems. The base class Shape must know about
all the derived classes, resulting in circular dependencies. If you derive a new class from Shape (say Triangle), you must update the interface of Shape and the interface/implementation of all the other derived classes.

2.2.1.2 Example 2

class SpaceShip{
}
class GiantSpaceShip : SpaceShip{
}
class Asteroid{
  public virtual void CollideWith(SpaceShip s){
    Console.WriteLine("Asteroid hit a SpaceShip");
  }
  public virtual void CollideWith(GiantSpaceShip s){
    Console.WriteLine("Asteroid hit a GiantSpaceShip");
  }
}

class ExplodingAsteroid : Asteroid{
   public override void CollideWith(SpaceShip s){
     Console.WriteLine("ExplodingAsteroid hit a SpaceShip");
   }
   public override void CollideWith(GiantSpaceShip s){
     Console.WriteLine("ExplodingAsteroid hit a GiantSpaceShip");
   }
}

Asteroid theAsteroid = new Asteroid();
SpaceShip theSpaceShip = new SpaceShip();
GiantSpaceShip theGiantSpaceShip = new GiantSpaceShip();
ExplodingAsteroid theExplodingAsteroid = new ExplodingAsteroid();
SpaceShip temp = theGiantSpaceShip;
theAsteroid.CollideWith(temp);

What gets printed ? ..."Asteroid hit a SpaceShip", which is incorrect.

Now, if both SpaceShip and GiantSpaceShip had a method CollideWith, the previous lines would still not work but the following would work.

temp.CollideWith(theAsteroid);
temp.CollideWith(theExplodingAsteroid);

class SpaceShip{
   public virtual void CollideWith(Asteroid asteroid){
      asteroid.CollideWith(this);
   }
}
class GiantSpaceShip : SpaceShip{
   public override void CollideWith(Asteroid asteroid){
      asteroid.CollideWith(this);
   }
}