Computing Thoughts
Graceful Failure
by Bruce Eckel
August 20, 2005

Summary
While experimenting to find a good introductory exercise for the PriorityQueue class, I discovered several anomalous results which I think produce a higher-order exercise in library design.

In an early chapter in Thinking in Java Fourth Edition, I hadn't introduced Comparable. I hoped to begin motivating the need for Comparable using a reader exercise to show what happens when you create a class that doesn't implement Comparable, then place objects of that class in a PriorityQueue. So I came up with this:


import java.util.*;

class ThizBin1 { }

public class Version1 {
  public static void main(String[] args) {
    Queue<ThizBin1> qf = new PriorityQueue<ThizBin1>();
    qf.offer(new ThizBin1());
    qf.offer(new ThizBin1());
  }
}

Because of Java's emphasis on static type checking, without giving it much thought I expected the lack of Comparable to cause a compile-time error, but that didn't happen. Instead, I got this at runtime:


Exception in thread "main" java.lang.ClassCastException: ThizBin1
        at java.util.PriorityQueue.fixUp(Unknown Source)
        at java.util.PriorityQueue.offer(Unknown Source)
        at Version1.main(Version1.java:9)

The problem in the example is that the PriorityQueue doesn't know what to do with the 2nd element that's offered because it can't establish the relative priority. We may guess that the ClassCastException comes when the PriorityQueue tries to cast the object in question to a Comparable. But the above error message doesn't give you any clue to that. You must have the necessary knowledge to figure out this message because you aren't given any help at either compile time or runtime.

This is rather reminiscent of C++ templates. When you make a mistake with a template, you get an error, although at compile time rather than runtime; a dauntingly long and usually incomprehensible sequence of messages. The experienced C++ programmer has come to recognize this as meaning "something is screwed up involving template code, but don't try to figure it out from this message -- instead, go back and stare at the code." The messages are generally too cryptic to figure out, although g++ has been producing more useful error messages and Leor Zolman has created an STL error message decryptor for C++ called STLFilt. The primary complaints that people (especially those criticizing C++ without much direct experience with it) have had about templates actually comes down to bad error messages, and the fact that the C++ compiler writers didn't build the equivalent of STLFilt into their compilers themselves points to a rather significant disconnect between compiler writers and their consumers. On the other hand, the C++ committee is now adding a feature to templates that will allow even better template error messages in the next version of C++. (These are called template concepts and are briefly described here.)

My observation about the above Java example is that it doesn't represent a graceful failure. Despite all the arguments about how generics allow static type checking, this doesn't take advantage of that. I personally have no problem with discovering some problems at runtime (indeed, I suspect that it might even be mathematically provable that you can only discover a relatively small set of problems at compile time). But the above error message doesn't give you much help in that direction, and would likely send the less-experienced programmer down many blind alleys in attempting to discover the problem.

Moving on, I decided to see if I could add Comparable without using the generic syntax for Comparable, which is a little confusing to programmers at this point in the book. This produced version 2 of the example:


import java.util.*;

class ThizBin2 implements Comparable {
  static int counter = 0;
  int id = counter++;
  public int compareTo(Object o) { return 0; }
  public String toString() { return Integer.toString(id); }
}

public class Version2 {
  public static void main(String[] args) {
    Queue<ThizBin2> qf = new PriorityQueue<ThizBin2>();
    for(int i = 0; i < 11; i++)
      qf.offer(new ThizBin2());
    while(!qf.isEmpty())
      System.out.println(qf.poll());
  }
}

My expectation was that I would get a warning at compile time, because usually when a generic version is available and you don't use it, the Java compiler warns you about "unchecked or unsafe operations." But not in this case -- there's no guidance to suggest to the programmer that Comparable should use generic syntax instead.

In the above case, all ThizBin2 objects end up being comparably equivalent. It's certainly legal for two objects to compare as equivalent, but it's interesting to see what the PriorityQueue does with such objects:

Because they are comparably equivalent, it doesn't technically matter what order they appear, but it's still somewhat surprising that the fallback position isn't just to leave them in insertion order. This decision, if it was made consciously, was probably that it wasn't worth messing up the algorithm for such a special case.

For the final version of the exercise (which was ultimately a failure, since it ended up being too complicated for that point in the book), I embedded an Integer object in the ThizBin3 class, and effectively "passed" the Integer Comparable through as the Comparable for ThizBin3:


import java.util.*;

class ThizBin3 implements Comparable<ThizBin3> {
  static Random rand = new Random();
  Integer priority;
  ThizBin3() { priority = rand.nextInt(100); }
  public int compareTo(ThizBin3 t) {
    return priority.compareTo(t.priority);
  }
  public String toString() { return priority.toString(); }
}

public class Version3 {
  public static void main(String[] args) {
    Queue<ThizBin3> qf = new PriorityQueue<ThizBin3>();
    for(int i = 0; i < 10; i++)
      qf.offer(new ThizBin3());
    while(!qf.isEmpty())
      System.out.println(qf.poll());
  }
}

To test the PriorityQueue behavior, the random number generator produces a value for priority, and this value is used in the compareTo() method. We can see the effect of the PriorityQueue in the output from one run:

PriorityQueue was written by Josh Bloch, and from past experience I would guess that the reason that it works the way it does is not because he forgot to think about the issue. It's more likely that he gave it a great deal of thought and decided that this was the most reasonable way to solve the problem. What's unfortunate is that the tools -- in particular, the Java generics implementation -- didn't provide better support for producing a compile-time error message that would direct the programmer to the problem.

Talk Back!

Have an opinion? Readers have already posted 53 comments about this weblog entry. Why not add yours?

RSS Feed

If you'd like to be notified whenever Bruce Eckel adds a new entry to his weblog, subscribe to his RSS feed.

Digg |

del.icio.us |

About the Blogger

Bruce Eckel (www.BruceEckel.com) provides development assistance in Python with user interfaces in Flex. He is the author of Thinking in Java (Prentice-Hall, 1998, 2nd Edition, 2000, 3rd Edition, 2003, 4th Edition, 2005), the Hands-On Java Seminar CD ROM (available on the Web site), Thinking in C++ (PH 1995; 2nd edition 2000, Volume 2 with Chuck Allison, 2003), C++ Inside & Out (Osborne/McGraw-Hill 1993), among others. He's given hundreds of presentations throughout the world, published over 150 articles in numerous magazines, was a founding member of the ANSI/ISO C++ committee and speaks regularly at conferences.


	Web Artima.com