The Artima Developer Community
Sponsored Link

Weblogs Forum
Graceful Failure

53 replies on 4 pages. Most recent reply: Aug 30, 2005 5:50 PM by Gregg Wonderly

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 53 replies on 4 pages [ 1 2 3 4 | » ]
Bruce Eckel

Posts: 875
Nickname: beckel
Registered: Jun, 2003

Graceful Failure (View in Weblogs)
Posted: Aug 20, 2005 11:58 AM
Reply to this message Reply
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.
Advertisement
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:


0
10
9
8
7
6
5
4
3
2
1

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:

5
7
15
34
41
44
45
69
74
83
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.


Krzysztof Sobolewski

Posts: 7
Nickname: jezuch
Registered: Dec, 2003

Re: Graceful Failure Posted: Aug 20, 2005 1:40 PM
Reply to this message Reply
I was wondering why PriorityQueue wasn't declared as

public class PriorityQueue<E extends Comparable<? super E>> ...

but the very first paragraph of Javadocs has the answer. The order can be determined either by the elements themselves (*if* they're Comparable) or by Comparator. This choice is a great idea (it is also consistent with many other classes and methods) but this forces the type parameter to be unbounded. What a waste... I think even Josh Bloch must have felt frustration when he was designing this class :)

Bruce Eckel

Posts: 875
Nickname: beckel
Registered: Jun, 2003

Re: Graceful Failure Posted: Aug 20, 2005 4:14 PM
Reply to this message Reply
This is the downside of explicit, rather than implicit constraints (ala Duck Typing), and an example of where compile-time type checking can be taken too far; in this case to the point where it actually prevented the appropriate use of generics.

I suppose an alternative that would have still allowed compile-time checking would have been an "OR" constraint, so you could have said:

public class PriorityQueue<E extends Comparable<? super E> | ?>

To say that it is either Comparable or something else, in this case '?' to mean "anything," so that it could take the Comparator strategy object instead.

Keith Ray

Posts: 658
Nickname: keithray
Registered: May, 2003

Re: Graceful Failure Posted: Aug 20, 2005 5:10 PM
Reply to this message Reply
How hard would it be for "ClassCastException" to include the name of the desired class as well as the actual class?

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: Graceful Failure Posted: Aug 22, 2005 2:33 AM
Reply to this message Reply
The design of all the sorted collections is the same, you can either use a comparable object or provide a comparator with the constructor. If you do neither then you get a problem that shows up as a runtime exception. If you wish to dissallow the option of providing a comparator with the constructor then do:
class MyCollection< E extends Comparable< E > > extends PriorityQueue< E > { /* or some other sorted collection */
    MyCollection( final Collection< E > c ) { super( e ); }
    MyCollection() {}
}

David Gates

Posts: 4
Nickname: dagates
Registered: Jul, 2005

Re: Graceful Failure Posted: Aug 22, 2005 7:34 AM
Reply to this message Reply
They absolutely could have made PriorityQueue typesafe, but its style would be inconsistant with the rest of the Collections framework. The trick is to use static factory methods instead of constructors, since static factory methods let you specify additional type constraints:

public static <T extends Comparable<T>> PriorityQueue<T> newInstance() { ... }

public static <T> PriorityQueue<T> newInstance(Comparator<? super T> comparator) { ... }

This way, if the type has no natural ordering, the client has to provide a valid Comparator.

Todd Blanchard

Posts: 316
Nickname: tblanchard
Registered: May, 2003

Re: Graceful Failure Posted: Aug 22, 2005 4:02 PM
Reply to this message Reply
Great example of why I think these compile time type systems often have a net negative value. In this case you were lulled into a false sense of security.

In equivalent smalltalk code, you'd get the runtime error, but it would make sense, you'd fix it right away and move on.

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: Graceful Failure Posted: Aug 22, 2005 8:12 PM
Reply to this message Reply
I don't get this critism that seems to be underlying a lot of the "I don't like generics" type comments. The critisisms seems to be of the form:

I can think of a case were generics don't provide compile time type safety

Then the suggested solution is never use generics, instead use pre-generic code (and casts) or use a dynamically typed language (Python, Ruby, Smalltalk, etc.). To me this is a spurious argument, the worst that happens with generics is that you get a runtime error, just like you do in pre-generic code or if you use a dynamically typed language!

So why are these proposed solutions any good? If you use generics it will get 99% of your type errors and the remaining 1% will be runtime errors. It would seem to me that catching 99% of the errors is a good deal! (Before anyone takes umbridge about the 99% comment I have yet to have a case myself that generics have failed to catch, therefore for me the figure is 100%.)

Also with generics you can usually catch the outlying cases with a few extra lines, e.g. see suggestions in this forum from David Gates and myself.

What's the big deal? Why are generics such a failure? They seem to work well to me.

David Hall

Posts: 4
Nickname: dhall
Registered: Jul, 2005

Re: Graceful Failure Posted: Aug 22, 2005 9:43 PM
Reply to this message Reply
>> class MyCollection< E extends Comparable< E > > extends PriorityQueue< E > { /* or some other sorted collection */

I've run into the same issue with the design of some of the JGA library. In comparison functors, you must instantiate the functor with a type that implements Comparable -or- you must provide a Comparator. The proposal that I submitted was to allow for a local restriction on the generic types.

class Less<T>{
    public <T> Less(Comparator<T> comp) { ... }
    public <T extends Comparable<T>>Less() {
        this(new ComparableComparator<T>());
    }
}


The basic idea was to modify the method/constructor matching algorithms: when called with parms that implement comparable, the second of the two constructors is visible to the matching algorithms. When called with parms that do not implement comparable, then the second constructor is
ignored by the matching algorithms.

Less<Integer> = new Less<Integer>();

vs
Less<Foo> = new Less<Foo>(FooComparator comp);


I submitted it as Bug#6261190


>> The trick is to use static factory methods instead of constructors, since static factory methods let you specify additional type constraints


This seems to be the standard answer, (it was Sun's answer to my submission) and it is, unfortunately, wrong in some cases. I wrote this up in my blog(1): the crux of the matter is that it is OK in cases where there is enough information in the parameter lists to correctly infer the desired type. In other cases, it requires falling back to the much less readable

Less<String> lessStandard = Less.<String>newInstance();


syntax. Having to use this style in some but not all cases simply makes any API that much harder to learn, which works against the stated goals of all of the new features of Java 1.5.

The answer I finally came up with is to split into two classes: the base class requires a comparator, the derived class restricts the generic parms to those that implement Comparable, and provides a default constructor that passes the default Comparator. Two classes is hardly an ideal answer but it does successfully preserve type-safety.

=========

(1) http://www.jroller.com/page/dhall/?anchor=generics_can_force_uncomfortable_design

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: Graceful Failure Posted: Aug 23, 2005 2:15 AM
Reply to this message Reply
@DavidHall,

I don't think that the explicit syntax is that bad nor the use of two classes with different generic constraints. All would seem to be viable options. EG you could suggest that everyone uses the static factories and supplies the type in all cases, this way all declarations have the same syntax.

As an aside, I would code your example something like this:
package davidhallexamples;
 
import java.util.*;
 
public class Less< T > {
    private static final Comparator< Comparable< Object > > naturalComparator = new Comparator<  Comparable< Object >  >() {
        public int compare( final Comparable< Object > lhs, final Comparable< Object > rhs ) {
            return lhs.compareTo( rhs );
        }
    };
    
    private final Comparator< T > c;
    
    public Less( final Comparator< T > c ) {
        if ( c == null ) throw new NullPointerException( "Null comparator" );
        this.c = c;
    }
    
    @SuppressWarnings( "unchecked" )
    public Less( final Class< T > clazz ) {
        this( (Comparator< T >)naturalComparator ); // Unchecked cast - OK - ignore
        if ( !Comparable.class.isAssignableFrom( clazz ) ) throw new IllegalArgumentException( "Given class, " +  clazz.getName() + ", does not implement Comparable" );
    }
    
    public static < T > Less< T > instance( final Class< T > clazz ) {
        return new Less< T >( clazz );
    }
    
    public static < T > Less< T > instance( final Comparator< T > comp ) {
        return new Less< T >( comp );
    }
    
    public boolean f( final T lhs, final T rhs ) {
        return c.compare( lhs, rhs ) < 0;
    }
    
    public static void main( final String[] notUsedInExample ) {
        final Less< String > lessString = instance( String.class );
        System.out.println( lessString.f( "A", "B" ) );
        final Less< Date > lessDate = instance( Date.class );
        System.out.println( lessDate.f( new java.sql.Time( 1 ), new java.sql.Time( 2 ) ) );
        final Less< java.sql.Time > lessTime = instance( java.sql.Time.class );
        System.out.println( lessTime.f( new java.sql.Time( 1 ), new java.sql.Time( 2 ) ) );
        final Less< Object > lessError = instance( Object.class ); // runtime exception
    }
}


This generates a runtime exception as soon as you try and declare the illegal Object comparator. The output is:

true
true
true
Exception in thread "main" java.lang.IllegalArgumentException: Given class, java.lang.Object, does not implement Comparable
at davidhallexamples.Less.<init>(Less.java:22)
at davidhallexamples.Less.instance(Less.java:26)
at davidhallexamples.Less.main(Less.java:44)
Java Result: 1

Note the above works for the derived type java.sql.Time, has consistant syntax for all types, and uses the same comparator (same instance) for all the naturally ordered types. Sun didn't code their collection classes this way for reasons of backward compatability. If you don't have the constraint of compatability with the past or the need to be consistant with classes designed in the past, then you can do better than the techniques in the collections API.

Vesa Karvonen

Posts: 116
Nickname: vkarvone
Registered: Jun, 2004

Re: Graceful Failure Posted: Aug 23, 2005 10:35 AM
Reply to this message Reply
Well, the type systems of most, if not all, mainstream languages (including Java) are quite weak (broken, verbose, get in the way rather than help). Those ignorant of the better type systems seem to repeatedly make the mistake of generalizing the shortcomings of the mainstream languages to advocate dynamically checked languages.

Isaac Gouy

Posts: 527
Nickname: igouy
Registered: Jul, 2003

Re: Graceful Failure Posted: Aug 23, 2005 12:24 PM
Reply to this message Reply
Howard wrote: The critisisms seems to be of the form: I can think of a case were generics don't provide compile time type safety... Then the suggested solution is never use generics,instead use pre-generic code (and casts) or use a dynamically typed language (Python, Ruby, Smalltalk, etc.).
Before we get to that, there's some simple FUD: "In this case you were lulled into a false sense of security". If static type checks can lull us into a false sense of security then testing code must be really bad!


Howard wrote: To me this is a spurious argument, the worst that happens with generics is that you get a runtime error, just like you do in pre-generic code or if you use a dynamically typed language!
It may be spurious for other reasons, but I think you've missed part of the argument - it's a complaint that we paid for static type checks but didn't get them, with the 'dynamic language' we didn't pay for static type checks and didn't expect to get them.


-snip-
Also with generics you can usually catch the outlying cases with a few extra lines, e.g. see suggestions in this forum from David Gates and myself... What's the big deal? Why are generics such a failure? They seem to work well to me.
Cui bono? Is this a scientific report or a cross between marketing and infotainment :-)

Isaac Gouy

Posts: 527
Nickname: igouy
Registered: Jul, 2003

Re: Graceful Failure Posted: Aug 23, 2005 1:16 PM
Reply to this message Reply
Todd wrote: In equivalent smalltalk code, you'd get the runtime error, but it would make sense, you'd fix it right away and move on.
This pollyanaish happy-talk just won't do.

Errare humanum est.
The real struggle isn't between static type checking and dynamic type checking - the real struggle is against software bugs.

The more ways we have to prevent and identify software bugs the better - we know static type analysis will find software bugs we missed after years of testing and use.

See "Detecting Software Defects in Telecom Applications
Through Lightweight Static Analysis: A War Story"
http://user.it.uu.se/~kostis/Papers/bugs05.pdf
http://user.it.uu.se/~kostis/Papers/war_story.pdf

Bruce Eckel

Posts: 875
Nickname: beckel
Registered: Jun, 2003

Re: Graceful Failure Posted: Aug 23, 2005 1:33 PM
Reply to this message Reply
> Errare humanum est.
> The real struggle isn't between static type checking and
> dynamic type checking - the real struggle is against
> software bugs.

Exactly. And to that I would add that it's worth doing a cost-benefit analysis of the various techniques that we have to choose from. Rather than just saying "static/dynamic typing is good/bad," asking "what does this particular technique really cost and how much leverage does it really get you?" And then to go further and ask "is there some orthogonal approach, that we haven't yet considered or thought of, that might solve the bug-finding problem even better?" Bringing developer-testing to the forefront, for example (initially in the form of unit testing), has helped automate the discovery of bugs that were previously slipping through the cracks. I personally think there are a lot of possibilities to be mined in the area of automatically searching for particular coding patterns that may reveal buggy regions of code.

Todd Blanchard

Posts: 316
Nickname: tblanchard
Registered: May, 2003

Re: Graceful Failure Posted: Aug 23, 2005 2:20 PM
Reply to this message Reply
> The real struggle isn't between static type checking and
> dynamic type checking - the real struggle is against
> software bugs.
>
> The more ways we have to prevent and identify software
> bugs the better - we know static type analysis will find
> software bugs we missed after years of testing and use.

This particular language feature seems to be not only not finding the bugs, but obscurring them. I have to question its value in light of this.

Flat View: This topic has 53 replies on 4 pages [ 1  2  3  4 | » ]
Topic: The miseducation of C++ programmers Previous Topic   Next Topic Topic: My Pycon 2005 Presentation


Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2014 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use - Advertise with Us