Skip to content
November 24, 2008 / Abe Pralle

Pondering double dispatch

This semester I gave my nooblet CS 110 students a tile-based game framework and had them add some additional actor classes and behaviors.  It worked out pretty well, but the big thing I noticed was that the majority of my students were trying to override methods in a way that was intuitively but not technically correct for Java.

For example, the bump( TileActor actor, int dir ) method is called whenever you bump into someone while moving in a certain direction.  To have Snake actors kill any other “Being” actors you’d give them this bump method:

    public void bump( TileActor actor, int dir )
    {
      if (actor instanceOf Being) actor.die();
    }

However, most of my students were defining this method instead:

    public void bump( Being actor, int dir )
    {
      actor.die();
    }

Of course in Java you have to override a method using the exact same parameter types as the original definition.  But their code would have worked in a language that uses double dispatch.

This was enough to push me over the edge on something I’d already been considering: I’m in all likelihood going to give gen2 Slag double dispatch (aka multi-dispatch) as standard behavior.  This is a big step for a statically-typed language, so let me describe multimethods (double dispatch methods), lay out my reasoning, and see if you can spot any deal-breakers in my plan.

Original C has static dispatch.  If you call a function “fn(x)”, you know exactly which function is going to be called.

All Java methods (as well as virtual C++ member functions) are dynamic dispatch.  If you call a method “obj.fn(x)”, then any of several methods will be called depending on the actual type of the context object.

You’ve probably run into the limitation of dynamic dispatch: the potential methods that may be called are limited by the type of the argument references; the actual argument object types aren’t considered.  The infamous example is equals(Object) in Java:

    class Book
    {
      public boolean equals( Object obj ) { ... }
      public boolean equals( Book book ) { ... }
    }
    ...
    Book b1 = new Book(...);
    Book b2 = new Book(...);
    Object obj = b2;
    b1.equals(b2);   // calls equals(Book)
    b1.equals(obj);  // calls equals(Object)

Double dispatch is a fix for just that problem.  If the methods in the example above were multimethods, then both of the calls at the bottom would call equals(Book).  Double dispatch means that the actual types of the parameters are taken into consideration.

Dynamic dispatch has a bit more overhead than static dispatch does.  Likewise, double dispatch has more overhead than dynamic dispatch.  Underneath the hood, a multimethod call can be converted into a dynamic call to a “middleman method” that handles the second part of the dispatch.  For example, b1.equals(obj) might automatically become:

    b1.dispatch_equals(obj);
    ...
    // class Book
    public boolean dispatch_equals( Object param1 )
    {
      if (param1 instanceof Book) return equals( (Book) param1 );
      else return equals( (Object) param1 );
    }

<edit>
Or, for an even simpler, faster pattern that works well with just one uncertain parameter, we can use the core mechanism from the Visitor pattern:

    obj.dispatch_equals( b1 );

    // class Object
    public boolean dispatch_equals( Book b ) { return b.equals(this); }

    // class Book
    public boolean dispatch_equals( Book b ) { return b.equals(this); }

</edit> 

Kind of a lot of overhead for a large-scale program, eh? Here’s the thing though: of course I already have the compiler change dynamic dispatch calls to static dispatch calls when there’s only one possible method that might be called.  And of course I would change double dispatch calls to dynamic dispatch calls when feasible.  With optimizations in place, I assert that all remaining calls require double dispatch handling either way whether it’s manual or automatic – so why not have it be automatic?

Advertisements

3 Comments

Leave a Comment
  1. ClintTorres / Nov 27 2008 12:12 am

    Dynamic dispatch usually offers flexibility in object design, so in the right hands it’ll be faster to prototype.

    Static dispatch, like static type checking, helps find errors at compile-time, which is probably more important for new and learning programmers.

    When you lean towards dynamic dispatch, I think you implicitly lean towards inheritance and away from composition as object design principles. This sets off an alarm for me because maintainability and long-term flexibility is usually greater for systems built by composition. Also, in more “bulletproof” production environments, composition and static checks are generally preferred.

    In the end, if students understand the difference between what happens for a static or a dynamic dispatch event, then you’re the big winner. Especially if they know which languages exhibit those behaviors by default.

  2. abepralle / Nov 27 2008 12:27 am

    So… what are your thoughts on *double* dispatch?

  3. abepralle / Nov 27 2008 10:41 am

    Addendum: after reading some related literature for a while, I realize that “multiple dispatch” is a more accurate term than “double dispatch”. Double dispatch is a technique of implementing multiple dispatch when there’s only one argument to consider, as seen in the Visitor pattern.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: