Lab 3--Advanced: Eliminating Instanceof in Java

Lab 3–Advanced: Eliminating Instanceof in Java

1 Lab Objectives

Explore proposals for eliminating instanceof from Java programs

The remElt method on binary search trees decides how to combine the subtrees based on whether or not they are empty. Our BSTs classes contain one for empty trees and one for non-empty trees. When implementing remElt, it is both tempting and easy to use instanceOf (like dillo? or cons? from Racket) to distinguish between these classes. Yet we have also said that writing conditionals to check the type of an object (ie, using instanceOf) violates the spirit of OO programming. This leaves the question: how could you write remElt without using instanceOf?

This lab lets you play with various options for doing this, contrasting the strengths and limitations of each. It doesn’t assume that you have prior experience with instanceOf: it does assume that you get the idea, that instaceOf asks whether an object came from a certain class (as dillo? did in Racket).

Several of the problems ask you to write down a couple of sentences describing your understanding of a problem. Doing these will make sure you understand the issues – take them seriously!. If you can’t put your understanding into words, you don’t understand the concept well enough yet. Ask for help either in lab or in office hours. If you are more comfortable in a language other than English, answer these first in your preferred language then try to translate them.

Before you start, download the BST implementation with instanceof to your computer.

2 Write Additional Methods to Avoid InstanceOf

The starter file for remElt implements an algorithm with the following structure:

    public IBST remElt (int elt) {
      if (elt == this.data) {
        if <BOTH CHILDREN ARE MtBSTs> {
          return new MtBST();
        } else if <LEFT IS AN MtBST> {
          return this.right;
        } else if <RIGHT IS AN MtBST> {
          return this.left;
        } else { // both children are DataBSTs
          ...
        }
      else { ... }
    }
  }

This leads naturally to the instanceOf implementation in the starter file.

Rework this code to remove the uses of instanceOf; this means you will make Java call the right code based on the object instead. As a hint, remember that Java dispatches on the type of an object: if you call a method on the left or right subtree, Java will automatically call either the empty or non-empty BST version depending on the actual object in left/right. So the task here is to rework the if statements into a form that can be turned into methods on the left/right trees.

It’s worth beating your head on this for a few minutes. If you get stuck, here are notes that show one solution.

The next option builds off of the solution to this one.

3 Multiple Methods with Different Headers

Java allows you to define multiple methods with the same name but different argument types. When you call a method with actual arguments, Java uses the one with types that most precisely match those of the arguments. This is also part of dispatching.

When we created methods to eliminate instanceof in the notes linked above, we created methods on different types of individual children (in other words, we called a method on the left child passing the right child as argument or vice versa). This raises a question though: what if we instead defined four helper methods in the DataBST class with the headers:

  DataBST remParentNode(MtBST left, MtBST right){...}
  DataBST remParentNode(MtBST left, DataBST right){...}
  DataBST remParentNode(DataBST left, MtBST right){...}
  DataBST remParentNode(DataBST left, DataBST right){...}

and rewrote remElt to do

  public IBST remElt (int elt) {
    if (elt == this.data)
      return this.remParentNode(this.left, this.right);
    ...
  }

Modify the code that uses instanceof to implement this suggestion. If it works, would you recommend this solution over the one in class? Why or why not? If it doesn’t work, explain clearly what goes wrong (i.e., don’t restate the error messages – instead, explain what Java is doing and why this solution is problematic in light of that).

4 Use A Different Data Definition

Perhaps we needed instanceof because we had the wrong data definition in the first place. Our approach created two kinds of trees: empty trees (MtBST) and non-empty trees (DataBST). Arguably, our DataBST fails to distinguish different kinds of data: there are Leaf nodes (have values but no children), Partial-leaf nodes (have value and only one child), and Internal nodes (have two children, each of which may be any kind of node). This would suggest that we instead had the following classes:

  class Leaf implements INode {
    int data;
    // no other fields
  }

  class LeftOnly implements INode {
    int data;
    INode left;
    // no other fields
  }

  class RightOnly implements INode {
    int data;
    INode right;
    // no other fields
  }

  class Internal implements INode {
    int data;
    INode left;
    INode right;
    // no other fields
  }

With INode and an MtBST class extending/implementing the IBST interface.

Such a code organization would seem to solve our instanceof problems, because the data would explicit capture whether the children were empty.

Explore this approach, fleshing out these classes to implement the BST operations. How does this approach compare to what we did in class? Would you recommend it? Why or why not? Answer in prose with crisp, technical answers.

5 Pulling it all Together

Summarize in prose your current understanding of the concern with using instanceOf and viable options for writing Java programs without it. Your goal is to balance the tension between exploiting dispatch, writing maintainable code, and enabling future extensions to code. Discuss your thoughts on this problem with others in your lab who also worked on these problems.

1	Lab Objectives
2	Write Additional Methods to Avoid Instance Of
3	Multiple Methods with Different Headers
4	Use A Different Data Definition
5	Pulling it all Together