COMP 212 Lab 07: Double-Dispatch Pattern

In class, you were introduced to the double-dispatch pattern. You may find it useful for the last milestone of the hangman project, although you are not required to use it. The last part of today's lab gives an overview of how double-dispatch would be relevant to the project, but the majority of the lab works with a simpler example.

Overview/Review

In most OO languages, including Java, when you call a method on an object that belongs to a union, the call is dispatched to the appropriate method based solely on the type of the receiver. In other words, we choose among the various definitions of that method based solely on the concrete class of the receiver of the method call. This is called single-dispatching. In constrast, Mmltiple-dispatching is the ability to dispatch the appropriate method call based on the type of more than one of the parameters.

While a few OO languages directly support multiple-dispatching, most do not. The double-dispatch pattern allows us to model this idea in languages that do not support this concept directly.

Motivation: Arithmetic example

Example

The need to extract the primitively-typed numbers from Number objects in order to perform any arithmetic can be annoying. Let's explore what the designers of Java could have done to allow addition directly on Numbers (including Integers, Floats, and Doubles).

To be robust, we expect to be able to add any two Numbers, e.g., an Integer and a Float. So, our first attempt would be to write something like

     public class Integer extends Number
     {
          ...

          /* all the possible definitions of add() */
          public Number add(Integer i) {...}
          public Number add(Float f)   {...}
          public Number add(Double d)  {...}

          ...
     }
In each Number subclass, we would overload add() for each Number subclass. This large amount of code is unavoidable, but there's a more fundamental problem.

Question: With the above definitions, which of the following tests work and which don't? Why do some fail? The answer.

     Integer i1, i2;
     Number  num1, num2, num3;
     ...
     num3 = i1.add(i2);
     num3 = num1.add(i2);
     num3 = i1.add(num2);
     num3 = num1.add(num2);

Instead, we can write classes like the following. This will pass the previous tests. Question: Why? The answer.

     public class Integer extends Number
     {
          ...

          public Number add(Number n)
          {
               return n.addFromInt(this);
          }

          public Number addFromInt(Integer i) {...}

	  /* Need to declare the following two methods also because     */
	  /* they are called from the similar Float and Double classes. */

          public Number addFromFloat(Float f)   {...}
          public Number addFromDouble(Double d)  {...}

          ...
     }

One last thing. Each Number class has addTo() methods with the same signatures. We should also make them part of the Number abstract class. (Using an interface for this purpose would also be reasonable.)

Note that the visitor pattern is really just one specific use of double-dispatching. There, we dispatch on both the host object and the algorithm.

Working with the example

Well, Java doesn't actually have such methods in its Number classes. (Why? All this dispatching is computationally expensive, whereas the same goals can be obtained on primitive types more easily. So, Java programmers are "encouraged" (forced) to use what can be implemented efficiently.) Moreover, Integer and such are all final classes, so you can't extend them with your own addition methods. For the purposes of some exercises, we can just create our own versions of these classes.

Exercise: Write and test your own version of these classes (Number, Integer, Float, and Double) in your own package. The concrete classes should have a field for the underlying primitively-typed number. You'll need a constructor in each concrete class. Implement each of the add() and addTo() methods. You'll need a selector (a.k.a. getter) method in each concrete class to get the underlying primitively-typed number, so that you can test your code. Don't bother implementing all the other features of the normal Number classes.

Mental Exercise: In that exercise, the methods all look very similar, since Java provides a single piece of syntax + for addition on their underlying data. But, consider adding other Number subclasses, such as complex and rational numbers. These aren't supported inherently by Java. So, for example, a complex number would be represented with two numbers, the real and imaginary parts. What would the corresponding AddTo() methods look like?


Application to Hangman

We'll outline this in lab, but you should should read this in detail on your own.

Null Object Pattern

Consider the code of the left button's action listener, from the previously provided Hangman milestone #2 sample:

     _rightBPList.insertEnd(_leftBPList.removeFront());
Here we remove a body part from the front of the left list and insert it into the end of the right list. When the left list becomes empty, what should we do?

In the implementation given in the lab, the empty list throws an exception on the removal operations (removeFront and removeEnd). As a result, using that code means using a try/catch statement to handle the exception. This is tantamount to allowing your code to die and then try resuscitate it. It is generally bad style to use exceptions for a normal occurrence, so this is a bad choice.

We could reprogram the empty list to return some special value on the removal operations. Let's somewhat arbitrarily pick null as this special value. Now each use must check for null. This is a very non-OO-style solution. As always, our goal is to let the OO mechanisms handle almost all of our control.

We've seen this basic problem many times before, although not exactly in this context. What we need to do is return a special (singleton) object that will know how to do the right thing. Let's call that object NullDrawable. This use of the singleton pattern is sometimes call the null object pattern.

Now, at some point in the program's run time, we might be executing something like this:

     _rightBPList.insertEnd(NullDrawable.Singleton);
As it currently stands, the NullDrawable object will be inserted into the right list. And if we keep clicking the left button, the right list will keep inserting more NullDrawable objects, one for each click. This will appear OK on the canvas since the NullDrawable object does not draw anything. However, a problem will surface when we start moving body parts from the end of the right list to the front of the left list by clicking on the right button. For a while nothing seems to happen because we are just moving the NullDrawable object and nothing is drawn. This is not OK because we only sees regular body parts and we expect t see them move one at a time on each click of a button.

Double-Dispatch Pattern

What we want is for the BPList not to insert the NullDrawable object at all. But what we don't want is to have to write code to check for the type of body parts before or inside of the insertion operations (insertFront and insertEnd). The problem here stems from the fact that the insertion operations depend not only on the receiver (BPList) but also on the input parameter, which, in this case, is the body part object. So the insertion operations depends on two types: the type of its receiver, and the type of its parameter. Thus, we now have an situation where we want to use the double-dispatch pattern.

For example, to implement the BPList insertFront method using double-dispatch, we need to do the following:

The code to remove a body part from the front of the left list and insert it into the end of the right list will now look like:

     _leftBPList.removeFront().enterEnd(_rightBPList);

Below is the UML diagram describing the null object pattern and the double-dispatch pattern applied to the hangman body parts and body parts list.

BParts.png (13062 bytes)

Conclusion

There are no ifs, no conds, no switches! Only objects requesting other objects to do their jobs. The program's control flow is directed by the underlining polymorphic machinery. The programmer is freed from writing control statements. The program as a whole is glued together by the architecture of the object model and not by contorted control code, and thus is more robust and easier to maintain.